The fundamental caching problem in networks asks to find an allocation of contents to a network of caches with the aim of maximizing the cache hit rate. Despite the problem's importance to a variety of research areas - including not only content delivery, but also edge intelligence and inference - and the extensive body of work on empirical aspects of caching, very little is known about the exact boundaries of tractability for the problem beyond its general NP-hardness. We close this gap by performing a comprehensive complexity-theoretic analysis of the problem through the lens of the parameterized complexity paradigm, which is designed to provide more precise statements regarding algorithmic tractability than classical complexity. Our results include algorithmic lower and upper bounds which together establish the conditions under which the caching problem becomes tractable.

We study the classical and parameterized complexity of computing the positive non-clashing teaching dimension of a set of concepts, that is, the smallest number of examples per concept required to successfully teach an intelligent learner under the considered, previously established model. For any class of concepts, it is known that this problem can be effortlessly transferred to the setting of balls in a graph $G$. We establish (1) the NP-hardness of the problem even when restricted to instances with positive non-clashing teaching dimension $k=2$ and where all balls in the graph are present, (2) near-tight running time upper and lower bounds for the problem on general graphs, (3) fixed-parameter tractability when parameterized by the vertex integrity of $G$, and (4) a lower bound excluding fixed-parameter tractability when parameterized by the feedback vertex number and pathwidth of $G$, even when combined with $k$. Our results provide a nearly complete understanding of the complexity landscape of computing the positive non-clashing teaching dimension and answer open questions from the literature.

We perform a refined complexity-theoretic analysis of three classical problems in the context of Hierarchical Task Network Planning: the verification of a provided plan, whether an executable plan exists, and whether a given state can be reached. Our focus lies on identifying structural properties which yield tractability. We obtain new polynomial algorithms for all three problems on a natural class of primitive networks, along with corresponding lower bounds. We also obtain an algorithmic meta-theorem for lifting polynomial-time solvability from primitive to general task networks, and prove that its preconditions are tight. Finally, we analyze the parameterized complexity of the three problems.

The VC-dimension is a well-studied and fundamental complexity measure of a set system (or hypergraph) that is central to many areas of machine learning. We establish several new results on the complexity of computing the VC-dimension. In particular, given a hypergraph $\mathcal{H}=(\mathcal{V},\mathcal{E})$, we prove that the naive $2^{\mathcal{O}(|\mathcal{V}|)}$-time algorithm is asymptotically tight under the Exponential Time Hypothesis (ETH). We then prove that the problem admits a $1$-additive fixed-parameter approximation algorithm when parameterized by the maximum degree of $\mathcal{H}$ and a fixed-parameter algorithm when parameterized by its dimension, and that these are essentially the only such exploitable structural parameters. Lastly, we consider a generalization of the problem, formulated using graphs, which captures the VC-dimension of both set systems and graphs. We design a $2^{\mathcal{O}(\texttt{tw}\cdot \log \texttt{tw})}\cdot |V|$-time algorithm for any graph $G=(V,E)$ of treewidth $\texttt{tw}$ (which, for a set system, applies to the treewidth of its incidence graph). This is in contrast with closely related problems that require a double-exponential dependency on the treewidth (assuming the ETH).

For a graph G, a subset S ⊆ V(G) is called a resolving set of G if, for any two vertices u,v ∈ V(G), there exists a vertex w ∈ S such that d(w,u) ≠ d(w,v). The Metric Dimension problem takes as input a graph G on n vertices and a positive integer k, and asks whether there exists a resolving set of size at most k. In another metric-based graph problem, Geodetic Set, the input is a graph G and an integer k, and the objective is to determine whether there exists a subset S ⊆ V(G) of size at most k such that, for any vertex u ∈ V(G), there are two vertices s₁, s₂ ∈ S such that u lies on a shortest path from s₁ to s₂. These two classical problems are known to be intractable with respect to the natural parameter, i.e., the solution size, as well as most structural parameters, including the feedback vertex set number and pathwidth. We observe that both problems admit an FPT algorithm running in 2^𝒪(vc²) ⋅ n^𝒪(1) time, and a kernelization algorithm that outputs a kernel with 2^𝒪(vc) vertices, where vc is the vertex cover number. We prove that unless the Exponential Time Hypothesis (ETH) fails, Metric Dimension and Geodetic Set, even on graphs of bounded diameter, do not admit - an FPT algorithm running in 2^o(vc²) ⋅ n^𝒪(1) time, nor - a kernelization algorithm that does not increase the solution size and outputs a kernel with 2^o(vc) vertices. We only know of one other problem in the literature that admits such a tight algorithmic lower bound with respect to vc. Similarly, the list of known problems with exponential lower bounds on the number of vertices in kernelized instances is very short.

Atomic congestion games are a classic topic in network design, routing, and algorithmic game theory , and are capable of modeling congestion and flow optimization tasks in various application areas. While both the price of anarchy for such games as well as the computational complexity of computing their Nash equilibria are by now well-understood, the computational complexity of computing a system-optimal set of strategies—that is, a centrally planned routing that minimizes the average cost of agents—is severely understudied in the literature. We close this gap by identifying the exact boundaries of tractability for the problem through the lens of the parameterized complexity paradigm. After showing that the problem remains highly intractable even on extremely simple networks, we obtain a set of results which demonstrate that the structural parameters which control the computational (in)tractability of the problem are not vertex-separator based in nature (such as, e.g., treewidth), but rather based on edge separators. We conclude by extending our analysis towards the (even more challenging) min-max variant of the problem.

We investigate how efficiently a well-studied family of domination-type problems can be solved on bounded-treewidth graphs. For sets \(\sigma,\rho\) of non-negative integers, a \((\sigma,\rho)\) -set of a graph G is a set S of vertices such that \(|N(u)\cap S|\in\sigma\) for every \(u\in S\) , and \(|N(\!\textit{v})\cap S|\in\rho\) for every \(\textit{v}\not\in S\) . The problem of finding a \((\sigma,\rho)\) -set (of a certain size) unifies standard problems, such as Independent Set , Dominating Set , Independent Dominating Set , and many others. For all pairs of finite or cofinite sets \((\sigma,\rho)\) , we determine (under standard complexity assumptions) the best possible value \(c_{\sigma,\rho}\) such that there is an algorithm that counts \((\sigma,\rho)\) -sets in time \(c_{\sigma,\rho}^{\textsf{tw}}\cdot n^{O(1)}\) (if a tree decomposition of width \(\textsf{tw}\) is given in the input). Let \(s_{{\rm top}}\) denote the largest element of \(\sigma\) if \(\sigma\) is finite, or the largest missing integer \(+1\) if \(\sigma\) is cofinite; \(r_{{\rm top}}\) is defined analogously for \(\rho\) . Surprisingly, \(c_{\sigma,\rho}\) is often significantly smaller than the natural bound \(s_{{\rm top}}+r_{{\rm top}}+2\) achieved by existing algorithms. Toward defining \(c_{\sigma,\rho}\) , we say that \((\sigma,\rho)\) is \({\mathrm{m}}\) -structured if there is a pair \((\alpha,\beta)\) such that every integer in \(\sigma\) equals \(\alpha\) mod \({\mathrm{m}}\) , and every integer in \(\rho\) equals \(\beta\) mod \({\mathrm{m}}\) . Then, setting — \(c_{\sigma,\rho}=s_{{\rm top}}+r_{{\rm top}}+2\) if \((\sigma,\rho)\) is not \({\mathrm{m}}\) -structured for any \({\mathrm{m}}\geq 2\) , — \(c_{\sigma,\rho}=\max\{s_{{\rm top}},r_{{\rm top}}\}+2\) if \((\sigma,\rho)\) is 2-structured, but not \({\mathrm{m}}\) -structured for any \({\mathrm{m}}\geq 3\) , and

Atomic congestion games are a classic topic in network design, routing, and algorithmic game theory, and are capable of modeling congestion and flow optimization tasks in various application areas. While both the price of anarchy for such games as well as the computational complexity of computing their Nash equilibria are by now well-understood, the computational complexity of computing a system-optimal set of strategies - that is, a centrally planned routing that minimizes the average cost of agents - is severely understudied in the literature. We close this gap by identifying the exact boundaries of tractability for the problem through the lens of the parameterized complexity paradigm. After showing that the problem remains highly intractable even on extremely simple networks, we obtain a set of results which demonstrate that the structural parameters which control the computational (in)tractability of the problem are not vertex-separator based in nature (such as, e.g., treewidth), but rather based on edge separators. We conclude by extending our analysis towards the (even more challenging) min-max variant of the problem.

Recently, Kirkpatrick et al. [ALT 2019] and Fallat et al. [JMLR 2023] introduced non-clashing teaching and showed it to be the most efficient machine teaching model satisfying the benchmark for collusion-avoidance set by Goldman and Mathias. A teaching map $T$ for a concept class $\mathcal{C}$ assigns a (teaching) set $T(C)$ of examples to each concept $C \in \mathcal{C}$. A teaching map is non-clashing if no pair of concepts are consistent with the union of their teaching sets. The size of a non-clashing teaching map (NCTM) $T$ is the maximum size of a teaching set $T(C)$, $C \in \mathcal{C}$. The non-clashing teaching dimension $\text{NCTD}(\mathcal{C})$ of $\mathcal{C}$ is the minimum size of an NCTM for $\mathcal{C}$. $\text{NCTM}^+$ and $\text{NCTD}^+(\mathcal{C})$ are defined analogously, except the teacher may only use positive examples. We study NCTMs and $\text{NCTM}^+\text{s}$ for the concept class $\mathcal{B}(G)$ consisting of all balls of a graph $G$. We show that the associated decision problem $\text{B-NCTD}^+$ for $\text{NCTD}^+$ is NP-complete in split, co-bipartite, and bipartite graphs. Surprisingly, we even prove that, unless the ETH fails, $\text{B-NCTD}^+$ does not admit an algorithm running in time $2^{2^{o(\mathtt{vc})}}\cdot n^{\mathcal{O}(1)}$, nor a kernelization algorithm outputting a kernel with $2^{o(\mathtt{vc})}$ vertices, where $\mathtt{vc}$ is the vertex cover number of $G$. We complement these lower bounds with matching upper bounds. These are extremely rare results: it is only the second problem in NP to admit such a tight double-exponential lower bound parameterized by $\mathtt{vc}$, and only one of very few problems to admit such an ETH-based conditional lower bound on the number of vertices in a kernel. For trees, interval graphs, cycles, and trees of cycles, we derive $\text{NCTM}^+\text{s}$ or NCTMs for $\mathcal{B}(G)$ of size proportional to its VC-dimension. For Gromov-hyperbolic graphs, we design an approximate $\text{NCTM}^+$ for $\mathcal{B}(G)$ of size $2$, in which only pairs of balls with Hausdorff distance larger than some constant must satisfy the non-clashing condition.

Treewidth (tw) is an important parameter that, when bounded, yields tractability for many problems. For example, graph problems expressible in Monadic Second Order (MSO) logic and QUANTIFIED SAT or, more generally, QUANTIFIED CSP, are FPT parameterized by the tw of the input's (primal) graph plus the length of the MSO-formula [Courcelle, Information & Computation 1990] and the quantifier rank [Chen, ECAI 2004], resp. The algorithms from these (meta-)results have running times whose dependence on tw is a tower of exponents. A conditional lower bound by Fichte et al. [LICS 2020] shows that, for QUANTIFIED SAT, the height of this tower is equal to the number of quantifier alternations. Lower bounds showing that at least double-exponential factors in the running time are necessary are rare: there are very few (for tw and vertex cover vc parameterizations) and they are for problems that are complete for #NP, $Σ_2^p$, $Π_2^p$, or higher levels of the polynomial hierarchy. We show, for the first time, that it is not necessary to go higher up in the polynomial hierarchy to obtain such lower bounds. We design a novel, yet simple versatile technique based on Sperner families to obtain such lower bounds and apply it to 3 problems: METRIC DIMENSION, STRONG METRIC DIMENSION, and GEODETIC SET. We prove that they do not admit $2^{2^{o(tw)}} \cdot n^{O(1)}$-time algorithms, even on bounded diameter graphs, unless the ETH fails. For STRONG METRIC DIMENSION, the lower bound holds even for vc. We complement our lower bounds with matching upper bounds.

In this paper, we introduce and study a new scoring game on graphs called smash and grab. In this game, two players, called Left and Right, take turns removing a vertex of the graph as well as all of its neighbours that become isolated by this removal. For each player and each of their turns, they score the number of vertices that were removed on their turn. The game ends when there are no more vertices remaining, and the player with the highest final score wins. We denote by Ls(G) the difference between Left and Right's final scores in G when Left starts and both players play optimally (they both aim to maximise their scores). We mainly study this parameter for different graph classes. We notably prove that Ls(F)≥0 for any forest F (i.e., the first player cannot lose). We then use this result to compute the exact value of Ls(G) for particular forests such as unions of paths and subdivided stars. The result in paths then solves the case of a unique cycle. Finally, we prove that, for a generalisation of the game, computing the score is PSPACE-complete.

We investigate how efficiently a well-studied family of domination-type problems can be solved on bounded-treewidth graphs. For sets σ, ρ of non-negative integers, a (σ, ρ)-set of a graph G is a set S of vertices such that | N (u) ∩ S| ∈ σ for every u ∈ S, and | N (v) ∩ S| ∈ ρ for every v ∉ S. The problem of finding a (σ, ρ)-set (of a certain size) unifies standard problems such as INDEPENDENT SET, DOMINATING SET, INDEPENDENT DOMINATING SET, and many others. For all pairs of finite or cofinite sets (σ, ρ), we determine (under standard complexity assumptions) the best possible value cσ,ρ such that there is an algorithm that counts (σ, ρ)-sets in time ctwσ,ρ · nO(1) (if a tree decomposition of width tw is given in the input). Let stop denote the largest element of σ if σ is finite, or the largest missing integer +1 if σ is cofinite; rtop is defined analogously for ρ. Surprisingly, cσ,ρ is often significantly smaller than the natural bound stop + rtop + 2 achieved by existing algorithms [van Rooij, 2020]. Toward defining cσ,ρ, we say that (σ,ρ) is m-structured if there is a pair (α,β) such that every integer in σ equals α mod m, and every integer in ρ equals β mod m. Then, setting • cσ,ρ = stop + rtop +2 if (σ, ρ) is not m-structured for any m ≥ 2 • cσ,ρ = max{stop,rtop} + 2 if (σ,ρ) is 2-structured, but not m-structured for any m ≥ 3, and stop = rtop is even, and • cσ,ρ = max{stop, rtop} + 1, otherwise we provide algorithms counting (σ, ρ)-sets in time ctwσ,ρ · nO(1). For example, for the EXACT INDEPENDENT DOMINATING SET problem (also known as PERFECT CODE) corresponding to σ = {0} and ρ = {1}, this improves the 3tw · nO(1) algorithm of van Rooij to 2tw· nO(1). Despite the unusually delicate definition of cσ,ρ, we show that our algorithms are most likely optimal, i.e., for any pair (σ, ρ) of finite or cofinite sets where the problem is non-trivial, and any ε > 0, a (cσ,ρ — ε)tw · nO(1)- algorithm counting the number of (σ, ρ)-sets would violate the COUNTING STRONG EXPONENTIAL-TIME HYPOTHESIS (#SETH). For finite sets σ and ρ, our lower bounds also extend to the decision version, showing that our algorithms are optimal in this setting as well. In contrast, for many cofinite sets, we show that further significant improvements for the decision and optimization versions are possible using the technique of representative sets. * The full version of this work can be accessed at https://arxiv.org/abs/2211.04278. Research supported by the European Research Council (ERC) consolidator grant No. 725978 SYSTEMATICGRAPH.

Abstract We consider two variants of orthogonal colouring games on graphs. In these games, two players alternate colouring uncoloured vertices (from a choice of $$m\in {\mathbb {N}}$$ m ∈ N colours) of a pair of isomorphic graphs while respecting the properness and the orthogonality of the partial colourings. In the normal play variant, the first player unable to move loses. In the scoring variant, each player aims to maximise their score, which is the number of coloured vertices in their copy of the graph. We prove that, given an instance with partial colourings, both the normal play and the scoring variant of the game are PSPACE-complete. An involution $$\sigma $$ σ of a graph G is strictly matched if its fixed point set induces a clique and $$v\sigma (v)\in E(G)$$ v σ ( v ) ∈ E ( G ) for any non-fixed point $$v\in V(G)$$ v ∈ V ( G ) . Andres et al. (Theor Comput Sci 795:312–325, 2019) gave a solution of the normal play variant played on graphs that admit a strictly matched involution. We prove that recognising graphs that admit a strictly matched involution is NP-complete.

Abstract. One of the open problems in machine learning is whether any set-family of VC-dimension [Formula: see text] admits a sample compression scheme of size [Formula: see text]. In this paper, we study this problem for balls in graphs. For a ball [Formula: see text] of a graph [Formula: see text], a realizable sample for [Formula: see text] is a signed subset [Formula: see text] of [Formula: see text] such that [Formula: see text] contains [Formula: see text] and is disjoint from [Formula: see text]. A proper sample compression scheme of size [Formula: see text] consists of a compressor and a reconstructor. The compressor maps any realizable sample [Formula: see text] to a subsample [Formula: see text] of size at most [Formula: see text]. The reconstructor maps each such subsample [Formula: see text] to a ball [Formula: see text] of [Formula: see text] such that [Formula: see text] includes [Formula: see text] and is disjoint from [Formula: see text]. For balls of arbitrary radius [Formula: see text], we design proper labeled sample compression schemes of size 2 for trees, of size 3 for cycles, of size 4 for interval graphs, of size 6 for trees of cycles, and of size 22 for cube-free median graphs. For balls of a given radius, we design proper labeled sample compression schemes of size 2 for trees and of size 4 for interval graphs. We also design approximate sample compression schemes of size 2 for balls of [Formula: see text]-hyperbolic graphs.

Abstract. For a graph [Formula: see text], a subset [Formula: see text] is called a resolving set if for any two vertices [Formula: see text], there exists a vertex [Formula: see text] such that [Formula: see text]. The Metric Dimension problem takes as input a graph [Formula: see text] and a positive integer [Formula: see text], and asks whether there exists a resolving set of size at most [Formula: see text]. This problem was introduced in the 1970s and is known to be NP -hard [M. R. Garey and D. S. Johnson, Computers and Intractability—A Guide to NP-Completeness, Freeman, San Francisco, 1979]. In the realm of parameterized complexity, Hartung and Nichterlein [28 th Conference on Computational Complexity, IEEE, Piscataway, NJ, 2013, pp. 266–276] proved that the problem is W [2]-hard when parameterized by the natural parameter [Formula: see text]. They also observed that it is fixed parameter tractable ( FPT) when parameterized by the vertex cover number and asked about its complexity under smaller parameters, in particular, the feedback vertex set number. We answer this question by proving that Metric Dimension is W [1]-hard when parameterized by the combined parameter feedback vertex set number plus pathwidth. This also improves the result of Bonnet and Purohit [IPEC 2019] which states that the problem is W [1]-hard parameterized by the pathwidth. On the positive side, we show that Metric Dimension is FPT when parameterized by either the distance to cluster or the distance to cocluster, both of which are smaller parameters than the vertex cover number.

One of the open problems in machine learning is whether any set-family of VC-dimension d admits a sample compression scheme of size O(d). In this paper, we study this problem for balls in graphs. For balls of arbitrary radius r, we design proper sample compression schemes of size 4 for interval graphs, of size 6 for trees of cycles, and of size 22 for cube-free median graphs. We also design approximate sample compression schemes of size 2 for balls of δ-hyperbolic graphs.

For a graph G, a subset S ⊆ V(G) is called a resolving set if for any two vertices u,v ∈ V(G), there exists a vertex w ∈ S such that d(w,u) ≠ d(w,v). The Metric Dimension problem takes as input a graph G and a positive integer k, and asks whether there exists a resolving set of size at most k. This problem was introduced in the 1970s and is known to be NP-hard [GT 61 in Garey and Johnson’s book]. In the realm of parameterized complexity, Hartung and Nichterlein [CCC 2013] proved that the problem is W[2]-hard when parameterized by the natural parameter k. They also observed that it is FPT when parameterized by the vertex cover number and asked about its complexity under smaller parameters, in particular the feedback vertex set number. We answer this question by proving that Metric Dimension is W[1]-hard when parameterized by the feedback vertex set number. This also improves the result of Bonnet and Purohit [IPEC 2019] which states that the problem is W[1]-hard parameterized by the treewidth. Regarding the parameterization by the vertex cover number, we prove that Metric Dimension does not admit a polynomial kernel under this parameterization unless NP ⊆ coNP/poly. We observe that a similar result holds when the parameter is the distance to clique. On the positive side, we show that Metric Dimension is FPT when parameterized by either the distance to cluster or the distance to co-cluster, both of which are smaller parameters than the vertex cover number.

In the eternal domination game played on graphs, an attacker attacks a vertex at each turn and a team of guards must move a guard to the attacked vertex to defend it. The guards may only move to adjacent vertices on their turn. The goal is to determine the eternal domination number $$\gamma ^{\infty }_{all}$$ of a graph, which is the minimum number of guards required to defend against an infinite sequence of attacks. This paper first continues the study of the eternal domination game on strong grids $$P_n\boxtimes P_m$$ . Cartesian grids $$P_n \square P_m$$ have been vastly studied with tight bounds existing for small grids such as $$k\times n$$ grids for $$k\in \{2,3,4,5\}$$ . It was recently proven that $$\gamma ^{\infty }_{all}(P_n \square P_m)=\gamma (P_n \square P_m)+O(n+m)$$ where $$\gamma (P_n \square P_m)$$ is the domination number of $$P_n \square P_m$$ which lower bounds the eternal domination number [Lamprou et al. Eternally dominating large grids. Theoretical Computer Science, 794:27–46, 2019]. We prove that, for all $$n,m\in \mathbb {N^*}$$ such that $$m\ge n$$ , $$\lfloor \frac{n}{3} \rfloor \lfloor \frac{m}{3} \rfloor +\Omega (n+m)=\gamma _{all}^{\infty } (P_{n}\boxtimes P_{m})=\lceil \frac{n}{3} \rceil \lceil \frac{m}{3} \rceil + O(m\sqrt{n})$$ (note that $$\lceil \frac{n}{3} \rceil \lceil \frac{m}{3} \rceil$$ is the domination number of $$P_n\boxtimes P_m$$ ). We then generalise our technique to prove that $$\gamma _{all}^{\infty }(G)=\gamma (G)+o(\gamma (G))$$ for all graphs $$G\in {\mathcal {F}}$$ , where $${\mathcal {F}}$$ is a large family of D-dimensional grids which are supergraphs of the D-dimensional Cartesian grid and subgraphs of the D-dimensional strong grid. In particular, $${\mathcal {F}}$$ includes both the D-dimensional Cartesian grid and the D-dimensional strong grid.

In the Spy Game played on a graph G, a single spy travels the ertices of G at speed s, while multiple slow guards strive to have, at all times, one of them within distance d of that spy. In order to determine the smallest number of guards necessary for this task, we analyze the game through a Linear Programming formulation and the fractional strategies it yields for the guards. We then show the equivalence of fractional and integral strategies in trees. This allows us to design a polynomial-time algorithm for computing an optimal strategy in this class of graphs. Using duality in Linear Programming, we also provide non-trivial bounds on the fractional guardnumber of grids and torus. We believe that the approach using fractional relaxation and Linear Programming is promising to obtain new results in the field of combinatorial games.