Research map / Learning theory and algorithms / Sample complexity
Parameterized Complexity of Caching in Networks
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Gives a comprehensive parameterized complexity classification of the network caching (cache hit rate maximization) problem under three content-size encodings, identifying FPT, XP, W[1]-hard, and paraNP-hard regions across parameters like caches, users, capacity, and degree.
Problem
Proactive caching in networks: allocate contents to caches (bipartite user-cache network) to maximize cache hit rate. Its exact tractability boundaries under parameterized complexity are unknown beyond NP-hardness.
Approach
Systematically analyzes three variants (homogeneous, heterogeneous unary-sized, heterogeneous binary-sized content sizes) against six natural parameters (C, K, S, U, Delta, lambda) and structural parameters, giving FPT algorithms via branching/dynamic programming, XP algorithms, hardness reductions, and showing equivalences among open cases.
Key results
- HetNC-B is FPT parameterized by C+S and by U+S, and paraNP-hard for all remaining parameterizations including C=1 or lambda=1.
- HetNC-U is XP parameterized by C and U+K, FPT parameterized by C+K, and W[1]-hard parameterized by C even when U=1.
- HomNC is NP-hard even with S=lambda=2, K=1, Delta=3, and XP parameterized by U; five open HomNC cases (C, U, C+U, C+lambda, vertex cover) are shown to be equivalent.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| parameterize by C+S | HetNC-B · Network-Caching | parameterized complexity | Helped |
| parameterize by U+S | HetNC-B · Network-Caching | parameterized complexity | Helped |
| parameterize by C+K | HetNC-U · Network-Caching | parameterized complexity | Helped |
| parameterize by C alone | HetNC-U · Network-Caching | parameterized complexity | Helped |
| parameterize by U+K | HetNC-U · Network-Caching | parameterized complexity | Helped |
| parameterize by U alone | HomNC · Network-Caching | parameterized complexity | Helped |
| restrict to S=λ=2, K=1, and Δ=3 | HomNC · Network-Caching | computational complexity | Hurt |
| restrict to U=1 | HetNC-U · Network-Caching | computational complexity | Hurt |
| restrict to C=λ=1 | HetNC-B · Network-Caching | computational complexity | Hurt |
| restrict to a planar network with K=1, λ=3, and Δ=5 | HomNC · Network-Caching | computational complexity | Hurt |
| parameterize by C alone | HetNC-B · Network-Caching | parameterized complexity | Hurt |
Surprising findings
- Bounding the maximum degree Delta and the number of requested contents per user lambda does not yield tractability; hardness persists even with Delta=3 and lambda=2.
- HomNC is NP-hard even on planar networks with K=1, lambda=3, Delta=5.
Limitations
- Five parameterizations for HomNC remain open (conjectured W[1]-hard) and are not resolved.
- Purely theoretical; no empirical evaluation of algorithms.
Experimental setup
Builds on: Network-Caching problem formulation Monotone NAE-3-SAT-B3 hardness Unary Bin Packing W[1]-hardness 0-1 Knapsack
Closest papers by meaning
- Robustifying Learning-Augmented Caching Efficiently without Compromising 1-Consistency (NeurIPS 2025 · similarity 0.85)
- Algorithms for Caching and MTS with reduced number of predictions (ICLR 2024 · similarity 0.85)
- Online Weighted Paging with Unknown Weights (NeurIPS 2024 · similarity 0.83)
- Learning-Augmented Streaming Algorithms for Approximating Boolean Max-CSPs (NeurIPS 2026 · similarity 0.82)
- The Complexity of Optimizing Atomic Congestion (AAAI 2024 · similarity 0.81)
- Randomization Boosts KV Caching, Learning Balances Query Load: A Joint Perspective (ICLR 2026 · similarity 0.81)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.