Homogeneous Network Caching is Fixed-Parameter Tractable Parameterized by the Number of Caches
For theoretical computer scientists studying parameterized complexity, this resolves an open conjecture and establishes tractability for a family of parameterizations previously thought to be hard.
The paper resolves a conjecture about the parameterized complexity of homogeneous network caching (HomNC), proving it is fixed-parameter tractable when parameterized by the number of caches C, and thus for all six related parameterizations. The algorithm uses n-fold integer programming to achieve running time f(C)|I|^{O(1)}.
Network caching asks how to place contents in distributed caches so that future requests are served close to their users. Ganian, Mc Inerney and Tsigkari recently initiated the parameterized-complexity study of the problem and, for the homogeneous unit-size variant (HomNC), isolated an unresolved family of six parameterizations: by the number of caches $C$, the number of users $U$, $U+K$, $C+U$, $C+λ$, and the vertex-cover number $\text{vc}(G)$, where $K$ is the maximum cache capacity and $λ$ is the maximum number of contents requested with nonzero probability by any user. Their interreducibility theorem showed that these six cases stand or fall together under parameterized reductions, and they conjectured the family to be W[1]-hard. We resolve this conjecture in the opposite direction. We prove that HomNC is fixed-parameter tractable parameterized by $C$ alone, and therefore fixed-parameter tractable for all six parameterizations. Our algorithm is based on an exact $n$-fold integer programming formulation that reveals a nontrivial block structure in homogeneous network caching, with the repeated part depending only on $C$. Standard algorithms for $n$-fold integer programming then yield a running time of the form $f(C)\lvert I\rvert^{O(1)}$.