Dániel Marx

In a recent work, Esmer et al. describe a simple method – approximate monotone local search – to obtain exponential approximation algorithms from existing parameterized exact algorithms, polynomial-time approximation algorithms and, more generally, parameterized approximation algorithms. In this work, we generalize those results to the weighted setting. More formally, we consider monotone subset minimization problems over a weighted universe of size n (e.g., Vertex Cover , d -Hitting Set and Feedback Vertex Set ). We consider a model where the algorithm is only given access to a subroutine that finds a solution of weight at most $$\alpha \cdot W$$ α · W (and of arbitrary cardinality) in time $$c^k \cdot n^{\mathcal {O}(1)}$$ c k · n O ( 1 ) where W is the minimum weight of a solution of cardinality at most k . In the unweighted setting, Esmer et al. determine the smallest value d for which a $$\beta $$ β -approximation algorithm running in time $$d^{n + o(n)}$$ d n + o ( n ) can be obtained in this model. We show that the same dependencies also hold in a weighted setting in this model: we obtain a $$\beta $$ β -approximation algorithm running in time $$d^{n + o(n)}$$ d n + o ( n ) , for the same d as in the unweighted setting. Similarly, we also extend a $$\beta $$ β -approximate brute-force search (in a model which only provides access to a membership oracle) to the weighted setting. Using existing approximation algorithms and exact parameterized algorithms for weighted problems, we obtain the first exponential-time $$\beta $$ β -approximation algorithms that are better than brute force for a variety of problems including Weighted Vertex Cover , Weighted d -Hitting Set , Weighted Feedback Vertex Set and Weighted Multicut .

We study the Steiner Tree problem on the intersection graph of most natural families of geometric objects, e.g., disks, squares, polygons, etc. Given a set of $n$ objects in the plane and a subset $T$ of $t$ terminal objects, the task is to find a subset $S$ of $k$ objects such that the intersection graph of $S\cup T$ is connected. Given how typical parameterized problems behave on planar graphs and geometric intersection graphs, we would expect that exact algorithms with some form of subexponential dependence on the solution size or the number of terminals exist. Contrary to this expectation, we show that, assuming the Exponential-Time Hypothesis (ETH), there is no $2^{o(k+t)}\cdot n^{O(1)}$ time algorithm even for unit disks or unit squares, that is, there is no FPT algorithm subexponential in the size of the Steiner tree. However, subexponential dependence can appear in a different form: we show that Steiner Tree can be solved in time $n^{O(\sqrt{t})}$ for many natural classes of objects, including: Disks of arbitrary size. Axis-parallel squares of arbitrary size. Similarly-sized fat polygons. This in particular significantly improves and generalizes two recent results: (1) Steiner Tree on unit disks can be solved in time $n^{\Oh(\sqrt{k + t})}$ (Bhore, Carmi, Kolay, and Zehavi, Algorithmica 2023) and (2) Steiner Tree on planar graphs can be solved in time $n^{O(\sqrt{t})}$ (Marx, Pilipczuk, and Pilipczuk, FOCS 2018). We complement our algorithms with lower bounds that demonstrate that the class of objects cannot be significantly extended, even if we allow the running time to be $n^{o(k+t)/\log(k+t)}$.

The Multicut problem asks for a minimum cut separating certain pairs of vertices: formally, given a graph G and a demand graph H on a set $$T\subseteq V(G)$$ T ⊆ V ( G ) of terminals, the task is to find a minimum-weight set C of edges of G such that whenever two vertices of T are adjacent in H , they are in different components of $$G\setminus C$$ G \ C . Colin de Verdière [ Algorithmica, 2017] showed that Multicut with t terminals on a graph G of genus g can be solved in time $$f(t,g)n^{O(\sqrt{g^2+gt+t})}$$ f ( t , g ) n O ( g 2 + g t + t ) . Cohen-Addad et al. [ JACM , 2021] proved a matching lower bound showing that the exponent of n is essentially best possible (for every fixed value of t and g ), even in the special case of Multiway Cut , where the demand graph H is a complete graph. However, this lower bound tells us nothing about other special cases of Multicut such as Group 3-Terminal Cut (where three groups of terminals need to be separated from each other). We show that if the demand pattern is, in some sense, close to being a complete bipartite graph, then Multicut can be solved faster than $$f(t,g)n^{O(\sqrt{g^2+gt+t})}$$ f ( t , g ) n O ( g 2 + g t + t ) , and furthermore this is the only property that allows such an improvement. Formally, for a class $$\mathcal {H}$$ H of graphs, $$\textsc {Multicut}(\mathcal {H})$$ M U L T I C U T ( H ) is the special case where the demand graph H is in $$\mathcal {H}$$ H . For every fixed class $$\mathcal {H}$$ H (satisfying some mild closure property), fixed g , and fixed t , our main result gives tight upper and lower bounds on the exponent of n in algorithms solving $$\textsc {Multicut}(\mathcal {H})$$ M U L T I C U T ( H ) .

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 \(s_{{\rm top}}=r_{{\rm top}}\) is even, and we count the number of edges between — \(c_{\sigma,\rho}=\max\{s_{{\rm top}},r_{{\rm top}}\}+1\) , otherwise, we provide algorithms counting \((\sigma,\rho)\) -sets in time \(c_{\sigma,\rho}^{\textsf{tw}}\cdot n^{O(1)}\) . For example, for the Exact Independent Dominating Set problem (also known as Perfect Code ) corresponding to \(\sigma=\{0\}\) and \(\rho=\{1\}\) , this improves the \(3^{\textsf{tw}}\cdot n^{O(1)}\) algorithm of van Rooij to \(2^{\textsf{tw}}\cdot n^{O(1)}\) . Despite the unusually delicate definition of \(c_{\sigma,\rho}\) , an accompanying paper shows that our algorithms are most likely optimal, that is, for any pair \((\sigma,\rho)\) of finite or cofinite sets where the problem is non-trivial, and any \(\varepsilon > 0\) , a \((c_{\sigma,\rho}-\varepsilon)^{\textsf{tw}}\cdot n^{O(1)}\) -algorithm counting the number of \((\sigma,\rho)\) -sets would violate the Counting Strong Exponential-Time Hypothesis (#SETH). For finite sets \(\sigma\) and \(\rho\) , these lower bounds also extend to the decision version, and hence, 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.

For a well-studied family of domination-type problems, in bounded-treewidth graphs, we investigate whether it is possible to find faster algorithms. For sets ς, ρ of non-negative integers, a (σ, ρ)-set of a graph G is a set S of vertices such that \(|N(u)\cap S|\in \sigma\) for every u ∈ S , and \(|N(v)\cap S|\in \rho\) for every \(v\not\in S\) . The problem of finding a (σ, ρ)-set (of a certain size) unifies common problems like Independent Set , Dominating Set , Independent Dominating Set , and many others. In an accompanying article, it is proven that, for all pairs of finite or cofinite sets (σ, ρ), there is an algorithm that counts (σ, ρ)-sets in time \((c_{\sigma ,\rho })^{\sf tw}\cdot n^{O(1)}\) (if a tree decomposition of width tw is given in the input). Here, ς, ρ is a constant with an intricate dependency on ς and ρ. Despite this intricacy, we show that the algorithms in the accompanying article 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_{\sigma ,\rho }-\varepsilon)^{\sf tw}\cdot n^{O(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 those algorithms are optimal in this setting as well.

In the general AntiFactor problem, a graph G and, for every vertex v of G, a set $$X_v\subseteq {\mathbb {N}}$$ X v ⊆ N of forbidden degrees is given. The task is to find a set S of edges such that the degree of v in S is not in the set $$X_v$$ X v . Standard techniques (dynamic programming plus fast convolution) can be used to show that if M is the largest forbidden degree, then the problem can be solved in time $$(M+2)^{{\operatorname {tw}}}\cdot n^{{\mathcal {O}}(1)}$$ ( M + 2 ) tw · n O ( 1 ) if a tree decomposition of width $${\operatorname {tw}}$$ tw is given. However, significantly faster algorithms are possible if the sets $$X_v$$ X v are sparse: our main algorithmic result shows that if every vertex has at most $$x$$ x forbidden degrees (we call this special case AntiFactor _x), then the problem can be solved in time $$(x+1)^{{\mathcal {O}}({\operatorname {tw}})}\cdot n^{{\mathcal {O}}(1)}$$ ( x + 1 ) O ( tw ) · n O ( 1 ) . That is, AntiFactor _x is fixed-parameter tractable parameterized by treewidth $${\operatorname {tw}}$$ tw and the maximum number $$x$$ x of excluded degrees. Our algorithm uses the technique of representative sets, which can be generalized to the optimization version, but (as expected) not to the counting version of the problem. In fact, we show that #AntiFactor ₁ is already # $$[1]$$ [ 1 ] -hard parameterized by the width of the given decomposition. Moreover, we show that, unlike for the decision version, the standard dynamic programming algorithm is essentially optimal for the counting version. Formally, for a fixed nonempty set $$X$$ X , we denote by $$X$$ X -AntiFactor the special case where every vertex v has the same set $$X_v=X$$ X v = X of forbidden degrees. We show the following lower bound for every fixed set $$X$$ X : if there is an $$\epsilon >0$$ ϵ > 0 such that # $$X$$ X -AntiFactor can be solved in time $$(\max X+2-\epsilon )^{{\operatorname {tw}}}\cdot n^{{\mathcal {O}}(1)}$$ ( max X + 2 - ϵ ) tw · n O ( 1 ) given a tree decomposition of width $${\operatorname {tw}}$$ tw , then the counting strong exponential-time hypothesis (#SETH) fails.

The goal of this work is to give precise bounds on the counting complexity of a family of generalized coloring problems (list homomorphisms) on bounded-treewidth graphs. Given graphs G , H , and lists L (v) ⊆ V(H) for every v ∈ V(G) , a f:V(G) → V(H) that preserves the edges (i.e., uv ∈ E(G) implies f(u)f(v) ∈ E(H) ) and respects the lists (i.e., f(v) ∈ L(v) ). Standard techniques show that if G is given with a tree decomposition of width t , then the number of list homomorphisms can be counted in time |V(H)| ^t ⋅ n ^????(1) . Our main result is determining, for every fixed graph H , how much the base |V(H)| in the running time can be improved. For a connected graph H , we define irr( H ) in the following way: if H has a loop or is nonbipartite, then irr( H ) is the maximum size of a set S⊆ V(H) where any two vertices have different neighborhoods; if H is bipartite, then irr( H ) is the maximum size of such a set that is fully in one of the bipartition classes. For disconnected H , we define irr( H ) as the maximum of irr( C ) over every connected component C of H . It follows from earlier results that if irr( H )=1, then the problem of counting list homomorphisms to H is polynomial-time solvable, and otherwise it is #P-hard. We show that, for every fixed graph H , the number of list homomorphisms from (G,L) to H — can be counted in time \(\operatorname{irr}(H)^t\cdot n^{\mathcal {O}(1)}\) if a tree decomposition of G having width at most t is given in the input, and, — given that \(\operatorname{irr}(H)\ge 2\) , cannot be counted in time \((\operatorname{irr}(H)-\varepsilon)^t\cdot n^{\mathcal {O}(1)}\) for any \(\varepsilon \gt 0\) , even if a tree decomposition of G having width at most t is given in the input, unless the Counting Strong Exponential-Time Hypothesis (#SETH) fails. Thereby, we give a precise and complete complexity classification featuring matching upper and lower bounds for all target graphs with or without loops.