For fixed sets $σ, ρ$ of non-negative integers, the $(σ, ρ)$-domination framework introduced by Telle [Nord. J. Comput. 1994] captures many classical graph problems. For a graph $G$, a $(σ,ρ)$-set is a set $S$ of vertices such that for every $v\in V(G)$, we have (1) if $v \in S$, then $|N(v) \cap S| \in σ$, and (2) if $v \notin S$, then $|N(v) \cap S| \in ρ$. We initiate the study of a natural partial variant $(σ,ρ)$-MinParDomSet of the problem, in which the constraints given by $σ, ρ$ need not be fulfilled for all vertices, but we want to find a set of size at most $k$ that maximizes the number of vertices that are satisfied in the sense that they satisfy (1) or (2) above. Our goal is to understand whether $(σ,ρ)$-MinParDomSet can be solved in the same running time as the nonpartial version, or whether it is strictly harder. Formally, we consider nonempty finite or simple cofinite sets $σ$ and $ρ$ (simple cofinite sets are of the form $\mathbb{Z}_{\geq c}$), and we try to determine the smallest constant $c_{σ,ρ}$ such that there is a $c_{σ,ρ}^{tw}\cdot n^{O(1)}$ time algorithm for the problem if a tree decomposition of width $tw$ is given. We obtain matching upper and lower bounds on $c_{σ,ρ}$ for every such fixed $σ$ and $ρ$ under the Primal Pathwidth Strong Exponential Time Hypothesis, and establish whether the partial problem is harder than the nonpartial variant. For some sets $σ$ and $ρ$, the more general $(σ,ρ)$-MinParDomSet has the same complexity as the nonpartial special case (e.g., for Dominating Set), while for other choices, the partial version is significantly harder (e.g., for Perfect Code).

Publisher Copyright: © 2026 Copyright held by the owner/author(s).

Abstract 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

Abstract. A well-studied continuous model of graphs, introduced by Dearing and Francis [Transportation Science, 1974], considers each edge as a continuous unit-length interval of points. In the problem [Formula: see text]-Tour defined within this model, the objective is to find a shortest tour that comes within a distance of [Formula: see text] of every point on every edge. This problem was introduced in the predecessor to this article and shown to be essentially equivalent to the Chinese Postman problem for [Formula: see text], to the graphic Travel Salesman Problem (TSP) for [Formula: see text], and close to first vertex cover and then dominating set for even larger [Formula: see text]. Moreover, approximation algorithms for multiple parameter ranges were provided. In this article, we provide complementing inapproximability bounds and examine the fixed-parameter tractability of the problem. On the one hand, we show the following: (1) For every fixed [Formula: see text], the problem [Formula: see text]-Tour is APX-hard, while for every fixed [Formula: see text], the problem has no polynomial-time [Formula: see text]-approximation unless [Formula: see text]. Our techniques also yield the new result that TSP remains APX-hard on cubic (and even cubic bipartite) graphs. (2) For every fixed [Formula: see text], the problem [Formula: see text]-Tour is fixed-parameter tractable (FPT) when parameterized by the length of a shortest tour, while it is W[2]-hard for every fixed [Formula: see text] and para-NP-hard for [Formula: see text] being part of the input. On the other hand, if [Formula: see text] is considered to be part of the input, then an interesting nontrivial phenomenon occurs when [Formula: see text] is a constant fraction of the number of vertices: (3) If [Formula: see text] is part of the input, then the problem can be solved in time [Formula: see text], where [Formula: see text]; however, assuming the exponential-time hypothesis (ETH), there is no algorithm that solves the problem and runs in time [Formula: see text].

H-Packing is the problem of finding a maximum number of vertex-disjoint copies of H in a given graph G. H-Partition is the special case of finding a set of vertex-disjoint copies that cover each vertex of G exactly once. Our goal is to study these problems and some generalizations on bounded-treewidth graphs. The case of H being a triangle is well understood: given a tree decomposition of G having treewidth tw, the K₃-Packing problem can be solved in time 2^tw⋅ n^O(1), while Lokshtanov et al. [ACM Transactions on Algorithms 2018] showed, under the Strong Exponential-Time Hypothesis (SETH), that there is no (2-ε)^tw⋅ n^O(1) algorithm for any ε > 0 even for K₃-Partition. Similar results can be obtained for any other clique K_d for d ≥ 3. We provide generalizations in two directions: - We consider a generalization of the problem where every vertex can be used at most c times for some c ≥ 1. When H is any clique K_d with d ≥ 3, then we give upper and lower bounds showing that the optimal running time increases to (c+1)^tw⋅ n^O(1). We consider two variants depending on whether a copy of H can be used multiple times in the packing. - If H is not a clique, then the dependence of the running time on treewidth may not be even single exponential. Specifically, we show that if H is any fixed graph where not every 2-connected component is a clique, then there is no 2^o(tw log tw)⋅ n^O(1) algorithm for H-Partition, assuming the Exponential-Time Hypothesis (ETH).

Given a graph $G$, a set $T$ of terminal vertices, and a demand graph $H$ on $T$, the \textsc{Multicut} problem asks for a set of edges of minimum weight that separates the pairs of terminals specified by the edges of $H$. The \textsc{Multicut} problem can be solved in polynomial time if the number of terminals and the genus of the graph is bounded (Colin de Verdière [Algorithmica, 2017]). Focke et al.~[SoCG 2024] characterized which special cases of Multicut are fixed-parameter tractable parameterized by the number of terminals on planar graphs. Moreover, they precisely determined how the parameter genus influences the complexity and presented partial results of this form for graphs that can be made planar by the deletion of $π$ edges. We complete the picture on how this parameter $π$ influences the complexity of different special cases and precisely determine the influence of the crossing number. Formally, let $\mathcal{H}$ be any class of graphs (satisfying a mild closure property) and let Multicut$(\mathcal{H})$ be the special case when the demand graph $H$ is in $\mathcal{H}$. Our first main result is showing that if $\mathcal{H}$ has the combinatorial property of having bounded distance to extended bicliques, then Multicut$(\mathcal{H})$ on unweighted graphs is FPT parameterized by the number $t$ of terminals and $π$. For the case when $\mathcal{H}$ does not have this combinatorial property, Focke et al.~[SoCG 2024] showed that $O(\sqrt{t})$ is essentially the best possible exponent of the running time; together with our result, this gives a complete understanding of how the parameter $π$ influences complexity on unweighted graphs. Our second main result is giving an algorithm whose existence shows that the parameter crossing number behaves analogously if we consider weighted graphs.

We prove a robust contraction decomposition theorem for $H$-minor-free graphs, which states that given an $H$-minor-free graph $G$ and an integer $p$, one can partition in polynomial time the vertices of $G$ into $p$ sets $Z_1,\dots,Z_p$ such that $\operatorname{tw}(G/(Z_i \setminus Z')) = O(p + |Z'|)$ for all $i \in [p]$ and $Z' \subseteq Z_i$. Here, $\operatorname{tw}(\cdot)$ denotes the treewidth of a graph and $G/(Z_i \setminus Z')$ denotes the graph obtained from $G$ by contracting all edges with both endpoints in $Z_i \setminus Z'$. Our result generalizes earlier results by Klein [SICOMP 2008] and Demaine et al. [STOC 2011] based on partitioning $E(G)$, and some recent theorems for planar graphs by Marx et al. [SODA 2022], for bounded-genus graphs (more generally, almost-embeddable graphs) by Bandyapadhyay et al. [SODA 2022], and for unit-disk graphs by Bandyapadhyay et al. [SoCG 2022]. The robust contraction decomposition theorem directly results in parameterized algorithms with running time $2^{\widetilde{O}(\sqrt{k})} \cdot n^{O(1)}$ or $n^{O(\sqrt{k})}$ for every vertex/edge deletion problems on $H$-minor-free graphs that can be formulated as Permutation CSP Deletion or 2-Conn Permutation CSP Deletion. Consequently, we obtain the first subexponential-time parameterized algorithms for Subset Feedback Vertex Set, Subset Odd Cycle Transversal, Subset Group Feedback Vertex Set, 2-Conn Component Order Connectivity on $H$-minor-free graphs. For other problems which already have subexponential-time parameterized algorithms on $H$-minor-free graphs (e.g., Odd Cycle Transversal, Vertex Multiway Cut, Vertex Multicut, etc.), our theorem gives much simpler algorithms of the same running time.

A graph property is a function Φ that maps every graph to {0,1} and is invariant under isomorphism. In the #IndSub(Φ) problem, given a graph G and an integer k, the task is to count the number of k-vertex induced subgraphs G’ with Φ(G’ ) = 1. For example, this problem family includes counting k-cliques or induced k vertex subgraphs that are connected, among others. There has been extensive work on determining the parameterized complexity of #IndSub(Φ) for various properties Φ. Very recently, Döring, Marx, and Wellnitz [STOC 2024] showed the general result that #IndSub(Φ) is #W[1]-hard for every nontrivial edge-monotone property Φ and, assuming ETH, cannot be solved in time f (k ) no (log k ).

Abstract 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 1 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

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

The Multicut problem asks for a minimum cut separating certain pairs of vertices: formally, given a graph G and demand graph H on a set T\subseteq 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. 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})}. Cohen-Addad et al. [JACM, 2021] proved a matching lower bound showing that the exponent of n is essentially best possible (for fixed values 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. 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})}, and furthermore this is the only property that allows such an improvement. Formally, for a class \mathcal{H} of graphs, Multicut(\mathcal{H}) is the special case where the demand graph H is in \mathcal{H}. For every fixed class \mathcal{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 Multicut(\mathcal{H}). In addition, we investigate a similar setting where, instead of parameterizing by the genus g of G, we parameterize by the minimum number k of edges of G that need to be deleted to obtain a planar graph. Interestingly, in this setting it makes a significant difference whether the graph G is weighted or unweighted: further nontrivial algorithmic techniques give substantial improvements in the unweighted case.

The goal of this paper is to investigate a family of optimization problems arising from list homomorphisms, and to understand what the best possible algorithms are if we restrict the problem to bounded-treewidth graphs. For a fixed $H$, the input of the optimization problem LHomVD($H$) is a graph $G$ with lists $L(v)$, and the task is to find a set $X$ of vertices having minimum size such that $(G-X,L)$ has a list homomorphism to $H$. We define analogously the edge-deletion variant LHomED($H$). This expressive family of problems includes members that are essentially equivalent to fundamental problems such as Vertex Cover, Max Cut, Odd Cycle Transversal, and Edge/Vertex Multiway Cut. For both variants, we first characterize those graphs $H$ that make the problem polynomial-time solvable and show that the problem is NP-hard for every other fixed $H$. Second, as our main result, we determine for every graph $H$ for which the problem is NP-hard, the smallest possible constant $c_H$ such that the problem can be solved in time $c^t_H\cdot n^{O(1)}$ if a tree decomposition of $G$ having width $t$ is given in the input.Let $i(H)$ be the maximum size of a set of vertices in $H$ that have pairwise incomparable neighborhoods. For the vertex-deletion variant LHomVD($H$), we show that the smallest possible constant is $i(H)+1$ for every $H$. The situation is more complex for the edge-deletion version. For every $H$, one can solve LHomED($H$) in time $i(H)^t\cdot n^{O(1)}$ if a tree decomposition of width $t$ is given. However, the existence of a specific type of decomposition of $H$ shows that there are graphs $H$ where LHomED($H$) can be solved significantly more efficiently and the best possible constant can be arbitrarily smaller than $i(H)$. Nevertheless, we determine this best possible constant and (assuming the SETH) prove tight bounds for every fixed $H$.

We study a general family of problems that form a common generalization of classic hitting (also referred to as covering or transversal) and packing problems. An instance of X-HitPack asks: Can removing k (deletable) vertices of a graph G prevent us from packing $\ell$ vertex-disjoint objects of type X? This problem captures a spectrum of problems with standard hitting and packing on opposite ends. Our main motivating question is whether the combination X-HitPack can be significantly harder than these two base problems. Already for a particular choice of X, this question can be posed for many different complexity notions, leading to a large, so-far unexplored domain in the intersection of the areas of hitting and packing problems. On a high-level, we present two case studies: (1) X being all cycles, and (2) X being all copies of a fixed graph H. In each, we explore the classical complexity, as well as the parameterized complexity with the natural parameters k+l and treewidth. We observe that the combined problem can be drastically harder than the base problems: for cycles or for H being a connected graph with at least 3 vertices, the problem is Σ_2^P-complete and requires double-exponential dependence on the treewidth of the graph (assuming the Exponential-Time Hypothesis). In contrast, the combined problem admits qualitatively similar running times as the base problems in some cases, although significant novel ideas are required. For example, for X being all cycles, we establish a 2^poly(k+l)n^O(1) algorithm using an involved branching method. Also, for X being all edges (i.e., H = K_2; this combines Vertex Cover and Maximum Matching) the problem can be solved in time 2^\poly(tw)n^O(1) on graphs of treewidth tw. The key step enabling this running time relies on a combinatorial bound obtained from an algebraic (linear delta-matroid) representation of possible matchings.

We consider the well-studied Robust (k,z)-Clustering problem, which generalizes the classic k-Median, k-Means, and k-Center problems and arises in the domains of robust optimization [Anthony, Goyal, Gupta, Nagarajan, Math. Oper. Res. 2010] and in algorithmic fairness [Abbasi, Bhaskara, Venkatasubramanian, 2021 & Ghadiri, Samadi, Vempala, 2022]. Given a constant z ≥ 1, the input to Robust (k,z)-Clustering is a set P of n points in a metric space (M,δ), a weight function w: P → ℝ_{≥ 0} and a positive integer k. Further, each point belongs to one (or more) of the m many different groups S_1,S_2,…,S_m ⊆ P. Our goal is to find a set X of k centers such that max_{i ∈ [m]} ∑_{p ∈ S_i} w(p) δ(p,X)^z is minimized. Complementing recent work on this problem, we give a comprehensive understanding of the parameterized approximability of the problem in geometric spaces where the parameter is the number k of centers. We prove the following results: [(i)] 1) For a universal constant η₀ > 0.0006, we devise a 3^z(1-η₀)-factor FPT approximation algorithm for Robust (k,z)-Clustering in discrete high-dimensional Euclidean spaces where the set of potential centers is finite. This shows that the lower bound of 3^z for general metrics [Goyal, Jaiswal, Inf. Proc. Letters, 2023] no longer holds when the metric has geometric structure. 2) We show that Robust (k,z)-Clustering in discrete Euclidean spaces is (√{3/2}- o(1))-hard to approximate for FPT algorithms, even if we consider the special case k-Center in logarithmic dimensions. This rules out a (1+ε)-approximation algorithm running in time f(k,ε)poly(m,n) (also called efficient parameterized approximation scheme or EPAS), giving a striking contrast with the recent EPAS for the continuous setting where centers can be placed anywhere in the space [Abbasi et al., FOCS'23]. 3) However, we obtain an EPAS for Robust (k,z)-Clustering in discrete Euclidean spaces when the dimension is sublogarithmic (for the discrete problem, earlier work [Abbasi et al., FOCS'23] provides an EPAS only in dimension o(log log n)). Our EPAS works also for metrics of sub-logarithmic doubling dimension.

In the Directed Steiner Network problem, the input is a directed graph G, a subset T of k vertices of G called the terminals, and a demand graph D on T. The task is to find a subgraph H of G with the minimum number of edges such that for every edge (s,t) in D, the solution H contains a directed s to t path. In this paper we investigate how the complexity of the problem depends on the demand pattern when G is planar. Formally, if \mathcal{D} is a class of directed graphs closed under identification of vertices, then the \mathcal{D}-Steiner Network (\mathcal{D}-SN) problem is the special case where the demand graph D is restricted to be from \mathcal{D}. For general graphs, Feldmann and Marx [ICALP 2016] characterized those families of demand graphs where the problem is fixed-parameter tractable (FPT) parameterized by the number k of terminals. They showed that if \mathcal{D} is a superset of one of the five hard families, then \mathcal{D}-SN is W[1]-hard parameterized by k, otherwise it can be solved in time f(k)n^{O(1)}. For planar graphs an interesting question is whether the W[1]-hard cases can be solved by subexponential parameterized algorithms. Chitnis et al. [SICOMP 2020] showed that, assuming the ETH, there is no f(k)n^{o(k)} time algorithm for the general \mathcal{D}-SN problem on planar graphs, but the special case called Strongly Connected Steiner Subgraph can be solved in time f(k) n^{O(\sqrt{k})} on planar graphs. We present a far-reaching generalization and unification of these two results: we give a complete characterization of the behavior of every $\mathcal{D}$-SN problem on planar graphs. We show that assuming ETH, either the problem is (1) solvable in time 2^{O(k)}n^{O(1)}, and not in time 2^{o(k)}n^{O(1)}, or (2) solvable in time f(k)n^{O(\sqrt{k})}, but not in time f(k)n^{o(\sqrt{k})}, or (3) solvable in time f(k)n^{O(k)}, but not in time f(k)n^{o({k})}.

A well-studied continuous model of graphs, introduced by Dearing and Francis [Transportation Science, 1974], considers each edge as a continuous unit-length interval of points. For $δ\geq 0$, we introduce the problem $δ$-Tour, where the objective is to find the shortest tour that comes within a distance of $δ$ of every point on every edge. It can be observed that 0-Tour is essentially equivalent to the Chinese Postman Problem, which is solvable in polynomial time. In contrast, 1/2-Tour is essentially equivalent to the Graphic Traveling Salesman Problem (TSP), which is NP-hard but admits a constant-factor approximation in polynomial time. We investigate $δ$-Tour for other values of $δ$, noting that the problem's behavior and the insights required to understand it differ significantly across various $δ$ regimes. We design polynomial-time approximation algorithms summarized as follows: (1) For every fixed $0 < δ< 3/2$, the problem $δ$-Tour admits a constant-factor approximation. (2) For every fixed $δ\geq 3/2$, the problem admits an $O(\log{n})$-approximation. (3) If $δ$ is considered to be part of the input, then the problem admits an $O(\log^3{n})$-approximation. This is the first of two articles on the $δ$-Tour problem. In the second one we complement the approximation algorithms presented here with inapproximability results and related to parameterized complexity.

The goal of this paper is to understand how exponential-time approximation algorithms can be obtained from existing polynomial-time approximation algorithms, existing parameterized exact algorithms, and existing parameterized approximation algorithms. More formally, we consider a monotone subset minimization problem over a universe of size n (e.g., VERTEX COVER or FEEDBACK VERTEX Set). We have access to an algorithm that finds an α-approximate solution in time ck · nO(1) if a solution of size k exists (and more generally, an extension algorithm that can approximate in a similar way if a set can be extended to a solution with k further elements). Our goal is to obtain a dn · nO(1) time β-approximation algorithm for the problem with d as small as possible. That is, for every fixed α,c,β ≥ 1, we would like to determine the smallest possible d that can be achieved in a model where our problem-specific knowledge is limited to checking the feasibility of a solution and invoking the α-approximate extension algorithm. Our results completely resolve this question:

We study the parameterized complexity of #IndSub(Φ), where given a graph G and an integer k, the task is to count the number of induced subgraphs on k vertices that satisfy the graph property Φ. Focke and Roth [STOC 2022] completely characterized the complexity for each Φ that is a hereditary property (that is, closed under vertex deletions): #IndSub(Φ) is #W[1]-hard except in the degenerate cases when every graph satisfies Φ or only finitely many graphs satisfy Φ. We complement this result with a classification for each Φ that is edge-monotone (that is, closed under edge deletions): #IndSub(Φ) is #W[1]-hard except in the degenerate case when there are only finitely many integers k such that Φ is nontrivial on k-vertex graphs. Our result generalizes earlier results for specific properties Φ that are related to the connectivity or density of the graph. Further, we extend the #W[1]-hardness result by a lower bound which shows that #IndSub(Φ) cannot be solved in time f(k) · |V(G)|o(√logk / loglogk) for any function f, unless the Exponential-Time Hypothesis (ETH) fails. For many natural properties, we obtain even a tight bound f(k) · |V(G)|o(k); for example, this is the case for every property Φ that is nontrivial on k-vertex graphs for each k greater than some k0.

Abstract In this paper, we consider a general notion of convolution. Let $$D$$ D be a finite domain and let $$D^n$$ D n be the set of n-length vectors (tuples) of $$D$$ D . Let $$f :D\times D\rightarrow D$$ f : D × D → D be a function and let $$\oplus _f$$ ⊕ f be a coordinate-wise application of f. The $$f$$ f -Convolution of two functions $$g,h :D^n \rightarrow \{-M,\ldots ,M\}$$ g , h : D n → { - M , … , M } is $$\begin{aligned} (g \mathbin {\circledast _{f}}h)(\textbf{v}) {:}{=}\sum _{\begin{array}{c} \textbf{v}_g,\textbf{v}_h \in D^n\\ \text {s.t. } \textbf{v}= \textbf{v}_g \oplus _f \textbf{v}_h \end{array}} g(\textbf{v}_g) \cdot h(\textbf{v}_h) \end{aligned}$$ ( g ⊛ f h ) ( v ) : = ∑ v g , v h ∈ D n s.t. v = v g ⊕ f v h g ( v g ) · h ( v h ) for every $$\textbf{v}\in D^n$$ v ∈ D n . This problem generalizes many fundamental convolutions such as Subset Convolution, XOR Product, Covering Product or Packing Product, etc. For arbitrary function f and domain $$D$$ D we can compute $$f$$ f -Convolution via brute-force enumeration in $$\widetilde{{\mathcal {O}}}(|D|^{2n} \cdot \textrm{polylog}(M))$$ O

Abstract The leafage of a chordal graph G is the minimum integer $$\ell $$ ℓ such that G can be realized as an intersection graph of subtrees of a tree with $$\ell $$ ℓ leaves. We consider structural parameterization by the leafage of classical domination and cut problems on chordal graphs. Fomin, Golovach, and Raymond [ESA 2018, Algorithmica 2020] proved, among other things, that Dominating Set on chordal graphs admits an algorithm running in time $$2^{\mathcal {O}(\ell ^2)} \cdot n^{\mathcal {O}(1)}$$ 2 O ( ℓ 2 ) · n O ( 1 ) . We present a conceptually much simpler algorithm that runs in time $$2^{\mathcal {O}(\ell )} \cdot n^{\mathcal {O}(1)}$$ 2 O ( ℓ ) · n O ( 1 ) . We extend our approach to obtain similar results for Connected Dominating Set and Steiner Tree. We then consider the two classical cut problems MultiCut with Undeletable Terminals and Multiway Cut with Undeletable Terminals. We prove that the former is [1]-hard when parameterized by the leafage and complement this result by presenting a simple $$n^{\mathcal {O}(\ell )}$$ n O ( ℓ ) -time algorithm. To our surprise, we find that Multiway Cut with Undeletable Terminals on chordal graphs can be solved, in contrast, in $$n^{{{\mathcal {O}}}(1)}$$ n O ( 1 ) -time.

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.

This paper considers the well-studied algorithmic regime of designing a $(1+\epsilon)$-approximation algorithm for a k-clustering problem that runs in time $f(k,\epsilon)poly(n)$ (sometimes called an efficient parameterized approximation scheme or EPAS for short1). Notable results of this kind include EPASes in the high-dimensional Euclidean setting for k-center [Badŏiu, Har-Peled, Indyk; STOC’02] as well as k-median, and k-means [Kumar, Sabharwal, Sen; J. ACM 2010]. Our main contribution is a clean and simple EPAS that settles more than ten clustering problems (across multiple well-studied objectives as well as metric spaces) and unifies well-known EPASes. More specifically, our algorithm gives EPASes in the following settings:•Clustering objectives: k-means, k-center, k-median, priority k-center, $\ell$-centrum, ordered k-median, socially fair k-median (aka robust k-median), or any other objective that can be formulated as minimizing a monotone (not necessarily symmetric!) norm of the distances of the points from the solution (generalizing the symmetric formulation introduced by Chakrabarty and Swamy [STOC’19]).•Metric spaces: Continuous high-dimensional Euclidean spaces, metrics of bounded doubling dimension, bounded treewidth metrics, and planar metrics. Prior to our results, EPASes were only known for vanilla clustering objectives (k-means, k-median, and k-center) and each such algorithm is tailored to work for the specific input metric and clustering objective (e.g., EPASes for k means and k-center in $\mathbb{R}^{d}$ are conceptually very different). In contrast, our algorithmic framework is applicable to a wide range of well-studied objective functions in a uniform way, and is (almost) entirely oblivious to any specific metric structures and yet is able to effectively exploit those unknown structures. In particular, our algorithm is not based on the (metric- and objective-specific) technique of coresets. Key to our analysis is a new concept that we call bounded $\epsilon$-scatter dimension—an intrinsic complexity measure of a metric space that is a relaxation of the standard notion of bounded doubling dimension(often used as a source of algorithmic tractability for geometric problems). Our main technical result shows that two conditions are essentially sufficient for our algorithm to yield an EPAS on the input metric M for any clustering objective:(i)The objective is described by a monotone norm, and(ii)the $\epsilon$-scatter dimension of M is upper bounded by a function of $\epsilon$.1Quick remarks: (i) An EPAS is not comparable to polynomial time approximation schemes (PTAS), (ii) before the term EPAS was invented some researchers call this type of approximation schemes a PTAS or simply an approximation scheme (in clustering, it is often assumed that k is small) [1], [2], and (iii) both EPAS and PTAS are implied by the existence of efficient polynomial time approximation schemes (EPTAS).

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 $α\cdot W$ (and of arbitrary cardinality) in time $c^k \cdot 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 $β$-approximation algorithm running in time $d^n \cdot n^{O(1)}$ can be obtained in this model. We show that the same dependencies also hold in a weighted setting in this model: for every fixed $\varepsilon>0$ we obtain a $β$-approximation algorithm running in time $O\left((d+\varepsilon)^{n}\right)$, for the same $d$ as in the unweighted setting. Similarly, we also extend a $β$-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 $β$-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.

A square coloring of a graph G is a coloring of the square G2 of G, that is, a coloring of the vertices of G such that any two vertices that are at distance at most 2 in G receive different colors. We investigate the complexity of finding a square coloring with a given number of q colors. We show that the problem is polynomial-time solvable on graphs of bounded treewidth by presenting an algorithm with running time for graphs of treewidth at most tw. The somewhat unusual exponent 2tw in the running time is essentially optimal: we show that for any ε > 0, there is no algorithm with running time f (tw)n(2-ε)tw unless the Exponential-Time Hypothesis (ETH) fails. We also show that the square coloring problem is NP-hard on planar graphs for any fixed number q ≥ 4 of colors. Our main algorithmic result is showing that the problem (when the number of colors q is part of the input) can be solved in subexponential time on planar graphs. The result follows from the combination of two algorithms. If the number q of colors is small (≤ n1/3), then we can exploit a treewidth bound on the square of the graph to solve the problem in time . If the number of colors is large (≥ n1/3), then an algorithm based on protrusion decompositions and building on our result for the bounded- treewidth case solves the problem in time . * The full version of the paper can be accessed at https://arxiv.org/abs/2211.04458. Research supported by the European Research Council (ERC) consolidator grant No. 725978 SYSTEMATICGRAPH.

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.

The Dynamic Time Warping (DTW) distance is a popular measure of similarity for a variety of sequence data. For comparing polygonal curves π, σ in ℝ^d, it provides a robust, outlier-insensitive alternative to the Fréchet distance. However, like the Fréchet distance, the DTW distance is not invariant under translations. Can we efficiently optimize the DTW distance of π and σ under arbitrary translations, to compare the curves' shape irrespective of their absolute location? There are surprisingly few works in this direction, which may be due to its computational intricacy: For the Euclidean norm, this problem contains as a special case the geometric median problem, which provably admits no exact algebraic algorithm (that is, no algorithm using only addition, multiplication, and k-th roots). We thus investigate exact algorithms for non-Euclidean norms as well as approximation algorithms for the Euclidean norm. For the L₁ norm in ℝ^d, we provide an 𝒪(n^{2(d+1)})-time algorithm, i.e., an exact polynomial-time algorithm for constant d. Here and below, n bounds the curves' complexities. For the Euclidean norm in ℝ², we show that a simple problem-specific insight leads to a (1+ε)-approximation in time 𝒪(n³/ε²). We then show how to obtain a subcubic 𝒪̃(n^{2.5}/ε²) time algorithm with significant new ideas; this time comes close to the well-known quadratic time barrier for computing DTW for fixed translations. Technically, the algorithm is obtained by speeding up repeated DTW distance estimations using a dynamic data structure for maintaining shortest paths in weighted planar digraphs. Crucially, we show how to traverse a candidate set of translations using space-filling curves in a way that incurs only few updates to the data structure. We hope that our results will facilitate the use of DTW under translation both in theory and practice, and inspire similar algorithmic approaches for related geometric optimization problems.

We generalize the monotone local search approach of Fomin, Gaspers, Lokshtanov and Saurabh [J.ACM 2019], by establishing a connection between parameterized approximation and exponential-time approximation algorithms for monotone subset minimization problems. In a monotone subset minimization problem the input implicitly describes a non-empty set family over a universe of size n which is closed under taking supersets. The task is to find a minimum cardinality set in this family. Broadly speaking, we use approximate monotone local search to show that a parameterized α-approximation algorithm that runs in c^k⋅n^𝒪(1) time, where k is the solution size, can be used to derive an α-approximation randomized algorithm that runs in dⁿ⋅n^𝒪(1) time, where d is the unique value in (1, 1+{c-1}/α) such that 𝒟(1/α‖{d-1}/{c-1}) = {ln c}/α and 𝒟(a‖b) is the Kullback-Leibler divergence. This running time matches that of Fomin et al. for α = 1, and is strictly better when α > 1, for any c > 1. Furthermore, we also show that this result can be derandomized at the expense of a sub-exponential multiplicative factor in the running time. We use an approximate variant of the exhaustive search as a benchmark for our algorithm. We show that the classic 2ⁿ⋅n^𝒪(1) exhaustive search can be adapted to an α-approximate exhaustive search that runs in time (1+exp(-α⋅ℋ(1/(α))))ⁿ⋅n^𝒪(1), where ℋ is the entropy function. Furthermore, we provide a lower bound stating that the running time of this α-approximate exhaustive search is the best achievable running time in an oracle model. When compared to approximate exhaustive search, and to other techniques, the running times obtained by approximate monotone local search are strictly better for any α ≥ 1, c > 1. We demonstrate the potential of approximate monotone local search by deriving new and faster exponential approximation algorithms for Vertex Cover, 3-Hitting Set, Directed Feedback Vertex Set, Directed Subset Feedback Vertex Set, Directed Odd Cycle Transversal and Undirected Multicut. For instance, we get a 1.1-approximation algorithm for Vertex Cover with running time 1.114ⁿ⋅n^𝒪(1), improving upon the previously best known 1.1-approximation running in time 1.127ⁿ⋅n^𝒪(1) by Bourgeois et al. [DAM 2011].

In this paper, we consider a general notion of convolution. Let $D$ be a finite domain and let $D^n$ be the set of $n$-length vectors (tuples) of $D$. Let $f : D \times D \to D$ be a function and let $\oplus_f$ be a coordinate-wise application of $f$. The $f$-Convolution of two functions $g,h : D^n \to \{-M,\ldots,M\}$ is $$(g \otimes_f h)(\textbf{v}) := \sum_{\substack{\textbf{v}_g,\textbf{v}_h \in D^n\\ \text{s.t. } \textbf{v}_g \oplus_f \textbf{v}_h}} g(\textbf{v}_g) \cdot h(\textbf{v}_h)$$ for every $\textbf{v} \in D^n$. This problem generalizes many fundamental convolutions such as Subset Convolution, XOR Product, Covering Product or Packing Product, etc. For arbitrary function $f$ and domain $D$ we can compute $f$-Convolution via brute-force enumeration in $\widetilde{O}(|D|^{2n}\mathrm{polylog}(M))$ time. Our main result is an improvement over this naive algorithm. We show that $f$-Convolution can be computed exactly in $\widetilde{O}((c \cdot |D|^2)^{n}\mathrm{polylog}(M))$ for constant $c := 3/4$ when $D$ has even cardinality. Our main observation is that a \emph{cyclic partition} of a function $f : D \times D \to D$ can be used to speed up the computation of $f$-Convolution, and we show that an appropriate cyclic partition exists for every $f$. Furthermore, we demonstrate that a single entry of the $f$-Convolution can be computed more efficiently. In this variant, we are given two functions $g,h : D^n \to \{-M,\ldots,M\}$ alongside with a vector $\textbf{v} \in D^n$ and the task of the $f$-Query problem is to compute integer $(g \otimes_f h)(\textbf{v})$. This is a generalization of the well-known Orthogonal Vectors problem. We show that $f$-Query can be computed in $\widetilde{O}(|D|^{\fracω{2} n}\mathrm{polylog}(M))$ time, where $ω\in [2,2.372)$ is the exponent of currently fastest matrix multiplication algorithm.

In the general AntiFactor problem, a graph G and, for every vertex v of G, a set X_v ⊆ ℕ 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. 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)^{tw}⋅n^{O(1)} if a tree decomposition of width tw is given. However, significantly faster algorithms are possible if the sets X_v are sparse: our main algorithmic result shows that if every vertex has at most x forbidden degrees (we call this special case AntiFactor_x), then the problem can be solved in time (x+1)^{O(tw)}⋅n^{O(1)}. That is, AntiFactor_x is fixed-parameter tractable parameterized by treewidth tw and the maximum number 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 #W[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, we denote by X-AntiFactor the special case where every vertex v has the same set X_v = X of forbidden degrees. We show the following lower bound for every fixed set X: if there is an ε > 0 such that #X-AntiFactor can be solved in time (max X+2-ε)^{tw}⋅n^{O(1)} given a tree decomposition of width 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 list homomorphism is a function 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 . 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 if a tree decomposition of G having width at most t is given in the input, and given that irr(H) ≥ 2, cannot be counted in time for any ∊ > 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.

Subexponential parameterized algorithms are known for a wide range of natural problems on planar graphs, but the techniques are usually highly problem specific. The goal of this paper is to introduce a framework for obtaining time algorithms for a family of graph modification problems that includes problems that can be seen as generalized cycle hitting problems. Our starting point is the Node Unique Label Cover problem (that is, given a CSP instance where each constraint is a permutation of values on two variables, the task is to delete k variables to make the instance satisfiable). We introduce a variant of the problem where k vertices have to be deleted such that every 2-connected component of the remaining instance is satisfiable. Then we extend the problem with cardinality constraints that restrict the number of times a certain value can be used (globally or within a 2-connected component of the solution). We show that there is an time algorithm on planar graphs for any problem that can be formulated this way, which includes a large number of well-studied problems, for example, Odd Cycle Transversal, Subset Feedback Vertex Set, Group Feedback Vertex Set, Subset Group Feedback Vertex Set, Vertex Multiway Cut, and Component Order Connectivity. For those problems that admit appropriate (quasi)polynomial kernels (that increase the parameter only linearly and preserve planarity), our results immediately imply time parameterized algorithms on planar graphs. In particular, we use or adapt known kernelization results to obtain time (randomized) algorithms for Vertex Multiway Cut, Group Feedback Vertex Set, and Subset Feedback Vertex Set. Our algorithms are designed with possible generalization to H-minor free graphs in mind. To obtain the same time algorithms on H-minor free graphs, the only missing piece is the vertex version of a contraction decomposition theorem that we currently have only for planar graphs.

Given a graph G and an integer k, the H-free Edge Editing problem is to find whether there exist at most k pairs of vertices in G such that changing the adjacency of the pairs in G results in a graph without any induced copy of H. Nontrivial polynomial kernels are known to exist for some graphs H with at most 4 vertices, but starting from 5 vertices, polynomial kernels are known only if H is either complete or empty. This suggests the conjecture that there is no other H with at least 5 vertices where H-free Edge Editing admits a polynomial kernel. Towards this goal, we obtain a set H of nine 5-vertex graphs such that if for every H∈H, H-free Edge Editing is incompressible and the complexity assumption NP⊈coNP/poly holds, then H-free Edge Editing is incompressible for every graph H with at least five vertices that is neither complete nor empty. We obtain similar results also for H-free Edge Deletion/Completion.

Abstract. We prove the following theorem. Given a planar graph [Formula: see text] and an integer [Formula: see text], it is possible in polynomial time to randomly sample a subset [Formula: see text] of vertices of [Formula: see text] with the following properties: [Formula: see text] induces a subgraph of [Formula: see text] of treewidth [Formula: see text], and for every connected subgraph [Formula: see text] of [Formula: see text] on at most [Formula: see text] vertices, the probability that [Formula: see text] covers the whole vertex set of [Formula: see text] is at least [Formula: see text], where [Formula: see text] is the number of vertices of [Formula: see text]. Together with standard dynamic programming techniques for graphs of bounded treewidth, this result gives a versatile technique for obtaining (randomized) subexponential-time parameterized algorithms for problems on planar graphs, usually with running time bound [Formula: see text]. The technique can be applied to problems expressible as searching for a small, connected pattern with a prescribed property in a large host graph; examples of such problems include Directed [Formula: see text]-Path, Weighted [Formula: see text]-Path, Vertex Cover Local Search, and Subgraph Isomorphism, among others. Up to this point, it was open whether these problems could be solved in subexponential parameterized time on planar graphs, because they are not amenable to the classic technique of bidimensionality. Furthermore, all our results hold in fact on any class of graphs that exclude a fixed apex graph as a minor, in particular on graphs embeddable in any fixed surface.

There are numerous examples of the so-called “square root phenomenon” in the field of parameterized algorithms: many of the most fundamental graph problems, parameterized by some natural parameter $k$, become significantly simpler when restricted to planar graphs and in particular the best possible running time is exponential in $\mathcal{O}(\sqrt{k})$ instead of $\mathcal{O}(k)$ (modulo standard complexity assumptions). We consider a classic optimization problem Subset Traveling Salesman, where we are asked to visit all the terminals $T$ by a minimum-weight closed walk. We investigate the parameterized complexity of this problem in planar graphs, where the number $k=|T|$ of terminals is regarded as the parameter. We show that Subset TSP can be solved in time $2^{\mathcal{O}(\sqrt{k}\log k)}\cdot n^{\mathcal{O}(1)}$ even on edge-weighted directed planar graphs. This improves upon the algorithm of Klein and Marx [ SODA 2014, SIAM, Philadelphia, 2014, pp. 1812--1830] with the same running time that worked only on undirected planar graphs with polynomially large integer weights.

We study a general family of facility location problems defined on planar graphs and on the two-dimensional plane. In these problems, a subset of k objects has to be selected, satisfying certain packing (disjointness) and covering constraints. Our main result is showing that, for each of these problems, the n O (√ k ) time brute force algorithm of selecting k objects can be improved to n O (√ k ) time. The algorithm is based on an idea that was introduced recently in the design of geometric QPTASs, but was not yet used for exact algorithms and for planar graphs. We focus on the Voronoi diagram of a hypothetical solution of k objects, guess a balanced separator cycle of this Voronoi diagram to obtain a set that separates the solution in a balanced way, and then recurse on the resulting subproblems. The following list is an exemplary selection of concrete consequences of our main result. We can solve each of the following problems in time n O (√ k ), where n is the total size of the input: d -Scattered Set : find k vertices in an edge-weighted planar graph that pairwise are at distance at least d from each other ( d is part of the input). d -Dominating Set (or ( k,d )-Center): find k vertices in an edge-weighted planar graph such that every vertex of the graph is at distance at most d from at least one selected vertex ( d is part of the input). Given a set D of connected vertex sets in a planar graph G , find k disjoint vertex sets in D . Given a set D of disks in the plane (of possibly different radii), find k disjoint disks in D . Given a set D of simple polygons in the plane, find k disjoint polygons in D . Given a set D of disks in the plane (of possibly different radii) and a set P of points, find k disks in D that together cover the maximum number of points in P . Given a set D of axis-parallel squares in the plane (of possibly different sizes) and a set P of points, find k squares in D that together cover the maximum number of points in P . It is known from previous work that, assuming the Exponential Time Hypothesis (ETH), there is no f ( k ) n o (√ k ) time algorithm for any computable function f for any of these problems. Furthermore, we give evidence that packing problems have n O (√ k ) time algorithms for a much more general class of objects than covering problems have. For example, we show that, assuming ETH, the problem where a set D of axis-parallel rectangles and a set P of points are given, and the task is to select k rectangles that together cover the entire point set, does not admit an f ( k ) n o ( k ) time algorithm for any computable function f .

For the General Factor problem we are given an undirected graph $G$ and for each vertex $v\in V(G)$ a finite set $B_v$ of non-negative integers. The task is to decide if there is a subset $S\subseteq E(G)$ such that $deg_S(v)\in B_v$ for all vertices $v$ of $G$. The maxgap of a finite integer set $B$ is the largest $d\ge 0$ such that there is an $a\ge 0$ with $[a,a+d+1]\cap B=\{a,a+d+1\}$. Cornuéjols (1988) showed that if the maxgap of all sets $B_v$ is at most 1, then the decision version of General Factor is poly-time solvable. Dudycz and Paluch (2018) extended this result for the minimization and maximization versions. Using convolution techniques from van Rooij (2020), we improve upon the previous algorithm by Arulselvan et al. (2018) and present an algorithm counting the number of solutions of a certain size in time $O^*((M+1)^k)$, given a tree decomposition of width $k$, where $M=\max_v \max B_v$. We prove that this algorithm is essentially optimal for all cases that are not polynomial time solvable for the decision, minimization or maximization versions. We prove that such improvements are not possible even for $B$-Factor, which is General Factor on graphs where all sets $B_v$ agree with the fixed set $B$. We show that for every fixed $B$ where the problem is NP-hard, our new algorithm cannot be significantly improved: assuming the Strong Exponential Time Hypothesis (SETH), no algorithm can solve $B$-Factor in time $O^*((\max B+1-ε)^k)$ for any $ε>0$. We extend this bound to the counting version of $B$-Factor for arbitrary, non-trivial sets $B$, assuming #SETH. We also investigate the parameterization of the problem by cutwidth. Unlike for treewidth, a larger set $B$ does not make the problem harder: Given a linear layout of width $k$ we give a $O^*(2^k)$ algorithm for any $B$ and provide a matching lower bound that this is optimal for the NP-hard cases.

Conditional lower bounds based on $P\neq NP$, the Exponential-Time Hypothesis (ETH), or similar complexity assumptions can provide very useful information about what type of algorithms are likely to be possible. Ideally, such lower bounds would be able to demonstrate that the best known algorithms are essentially optimal and cannot be improved further. In this tutorial, we overview different types of lower bounds, and see how they can be applied to problems in database theory and constraint satisfaction.

Abstract Permutation patterns and pattern avoidance have been intensively studied in combinatorics and computer science, going back at least to the seminal work of Knuth on stack-sorting (1968). Perhaps the most natural algorithmic question in this area is deciding whether a given permutation of lengthncontains a given pattern of lengthk. In this work we give two new algorithms for this well-studied problem, one whose running time is $$n^{k/4 + o(k)}$$ nk/4+o(k) , and a polynomial-space algorithm whose running time is the better of $$O(1.6181^n)$$ O(1.6181n) and $$O(n^{k/2 + 1})$$ O(nk/2+1) . These results improve the earlier best bounds of $$n^{0.47k + o(k)}$$ n0.47k+o(k) and $$O(1.79^n)$$ O(1.79n) due to Ahal and Rabinovich (2000) resp. Bruner and Lackner (2012) and are the fastest algorithms for the problem when $$k \in \varOmega (\log {n})$$ k∈Ω(logn) . We show that both our new algorithms and the previous exponential-time algorithms in the literature can be viewed through the unifying lens ofconstraint-satisfaction. Our algorithms can alsocount, within the same running time, the number of occurrences of a pattern. We show that this result is close to optimal: solving the counting problem in time $$f(k) \cdot n^{o(k/\log {k})}$$ f(k)·no(k/logk) would contradict theexponential-time hypothesis(ETH). For some special classes of patterns we obtain improved running times. We further prove that 3-increasing(4321-avoiding) and 3-decreasing(1234-avoiding) permutations can, in some sense,embedarbitrary permutations of almost linear length, which indicates that a sub-exponential running time is unlikely with the current techniques, even for patterns from these restricted classes.

The -Even Set problem is a parameterized variant of the Minimum Distance Problem of linear codes over , which can be stated as follows: given a generator matrix and an integer , determine whether the code generated by has distance at most , or, in other words, whether there is a nonzero vector such that has at most nonzero coordinates. The question of whether -Even Set is fixed parameter tractable (FPT) parameterized by the distance has been repeatedly raised in the literature; in fact, it is one of the few remaining open questions from the seminal book of Downey and Fellows [1999]. In this work, we show that -Even Set is W [1]-hard under randomized reductions. We also consider the parameterized -Shortest Vector Problem (SVP) , in which we are given a lattice whose basis vectors are integral and an integer , and the goal is to determine whether the norm of the shortest vector (in the norm for some fixed ) is at most . Similar to -Even Set, understanding the complexity of this problem is also a long-standing open question in the field of Parameterized Complexity. We show that, for any , -SVP is W [1]-hard to approximate (under randomized reductions) to some constant factor.

We prove essentially tight lower bounds, conditionally to the Exponential Time Hypothesis, for two fundamental but seemingly very different cutting problems on surface-embedded graphs: the Shortest Cut Graph problem and the Multiway Cut problem. A cut graph of a graph G embedded on a surface S is a subgraph of G whose removal from S leaves a disk. We consider the problem of deciding whether an unweighted graph embedded on a surface of genus G has a cut graph of length at most a given value. We prove a time lower bound for this problem of n Ω( g log g ) conditionally to the ETH. In other words, the first n O(g) -time algorithm by Erickson and Har-Peled [SoCG 2002, Discr. Comput. Geom. 2004] is essentially optimal. We also prove that the problem is W[1]-hard when parameterized by the genus, answering a 17-year-old question of these authors. A multiway cut of an undirected graph G with t distinguished vertices, called terminals , is a set of edges whose removal disconnects all pairs of terminals. We consider the problem of deciding whether an unweighted graph G has a multiway cut of weight at most a given value. We prove a time lower bound for this problem of n Ω( gt + g 2 + t log ( g + t )) , conditionally to the ETH, for any choice of the genus g ≥ 0 of the graph and the number of terminals t ≥ 4. In other words, the algorithm by the second author [Algorithmica 2017] (for the more general multicut problem) is essentially optimal; this extends the lower bound by the third author [ICALP 2012] (for the planar case). Reductions to planar problems usually involve a gridlike structure. The main novel idea for our results is to understand what structures instead of grids are needed if we want to exploit optimally a certain value G of the genus.

To study the question under which circumstances small solutions can be found faster than by exhaustive search (and by how much), we study the fine-grained complexity of Boolean constraint satisfaction with size constraint exactly $k$. More precisely, we aim to determine, for any finite constraint family, the optimal running time $f(k)n^{g(k)}$ required to find satisfying assignments that set precisely $k$ of the $n$ variables to $1$. Under central hardness assumptions on detecting cliques in graphs and 3-uniform hypergraphs, we give an almost tight characterization of $g(k)$ into four regimes: (1) Brute force is essentially best-possible, i.e., $g(k) = (1\pm o(1))k$, (2) the best algorithms are as fast as current $k$-clique algorithms, i.e., $g(k)=(ω/3\pm o(1))k$, (3) the exponent has sublinear dependence on $k$ with $g(k) \in [Ω(\sqrt[3]{k}), O(\sqrt{k})]$, or (4) the problem is fixed-parameter tractable, i.e., $g(k) = O(1)$. This yields a more fine-grained perspective than a previous FPT/W[1]-hardness dichotomy (Marx, Computational Complexity 2005). Our most interesting technical contribution is a $f(k)n^{4\sqrt{k}}$-time algorithm for SubsetSum with precedence constraints parameterized by the target $k$ -- particularly the approach, based on generalizing a bound on the Frobenius coin problem to a setting with precedence constraints, might be of independent interest.

In the Directed Long Cycle Hitting Set} problem we are given a directed graph $G$, and the task is to find a set $S$ of at most $k$ vertices/arcs such that $G-S$ has no cycle of length longer than $\ell$. We show that the problem can be solved in time $2^{\mathcal O(\ell k^3\log k + k^5\log k\log\ell)}\cdot n^{\mathcal O(1)}$, that is, it is fixed-parameter tractable (FPT) parameterized by $k$ and $\ell$. This algorithm can be seen as a far-reaching generalization of the fixed-parameter tractability of {\sc Mixed Graph Feedback Vertex Set} [Bonsma and Lokshtanov WADS 2011], which is already a common generalization of the fixed-parameter tractability of (undirected) {\sc Feedback Vertex Set} and the {\sc Directed Feedback Vertex Set} problems, two classic results in parameterized algorithms. The algorithm requires significant insights into the structure of graphs without directed cycles length longer than $\ell$ and can be seen as an exact version of the approximation algorithm following from the Erd{ő}s-P{ó}sa property for long cycles in directed graphs proved by Kreutzer and Kawarabayashi [STOC 2015].

In this paper we study the hardness of the $$k$$ -Center problem on inputs that model transportation networks. For the problem, a graph $$G=(V,E)$$ with edge lengths and an integer k are given and a center set $$C\subseteq V$$ needs to be chosen such that $$|C|\le k$$ . The aim is to minimize the maximum distance of any vertex in the graph to the closest center. This problem arises in many applications of logistics, and thus it is natural to consider inputs that model transportation networks. Such inputs are often assumed to be planar graphs, low doubling metrics, or bounded highway dimension graphs. For each of these models, parameterized approximation algorithms have been shown to exist. We complement these results by proving that the $$k$$ -Center problem is W[1]-hard on planar graphs of constant doubling dimension, where the parameter is the combination of the number of centers k, the highway dimension h, and the pathwidth p. Moreover, under the exponential time hypothesis there is no $$f(k,p,h)\cdot n^{o(p+\sqrt{k+h})}$$ time algorithm for any computable function f. Thus it is unlikely that the optimum solution to $$k$$ -Center can be found efficiently, even when assuming that the input graph abides to all of the above models for transportation networks at once! Additionally we give a simple parameterized $$(1+{\varepsilon })$$ -approximation algorithm for inputs of doubling dimension d with runtime $$(k^k/{\varepsilon }^{O(kd)})\cdot n^{O(1)}$$ . This generalizes a previous result, which considered inputs in D-dimensional $$L_q$$ metrics.

In this paper, we study multi-budgeted variants of the classic minimum cut problem and graph separation problems that turned out to be important in parameterized complexity: Skew Multicut and Directed Feedback Arc Set. In our generalization, we assign colors $$1,2,\ldots ,\ell $$ to some edges and give separate budgets $$k_{1},k_{2},\ldots ,k_{\ell }$$ for colors $$1,2,\ldots ,\ell $$ . For every color $$i\in \{1,\ldots ,\ell \}$$ , let $$E_{i}$$ be the set of edges of color i. The solution C for the multi-budgeted variant of a graph separation problem not only needs to satisfy the usual separation requirements (i.e., be a cut, a skew multicut, or a directed feedback arc set, respectively), but also needs to satisfy that $$|C\cap E_{i}|\le k_{i}$$ for every $$i\in \{1,\ldots ,\ell \}$$ . Contrary to the classic minimum cut problem, the multi-budgeted variant turns out to be NP-hard even for $$\ell = 2$$ . We propose FPT algorithms parameterized by $$k=k_{1}+\cdots +k_{\ell }$$ for all three problems. To this end, we develop a branching procedure for the multi-budgeted minimum cut problem that measures the progress of the algorithm not by reducing k as usual, by but elevating the capacity of some edges and thus increasing the size of maximum source-to-sink flow. Using the fact that a similar strategy is used to enumerate all important separators of a given size, we merge this process with the flow-guided branching and show an FPT bound on the number of (appropriately defined) important multi-budgeted separators. This allows us to extend our algorithm to the Skew Multicut and Directed Feedback Arc Set problems. Furthermore, we show connections of the multi-budgeted variants with weighted variants of the directed cut problems and the Chain $$\ell $$ -SAT problem, whose parameterized complexity remains an open problem. We show that these problems admit a bounded-in-parameter number of “maximally pushed” solutions (in a similar spirit as important separators are maximally pushed), giving somewhat weak evidence towards their tractability.

We give an algorithmic and lower bound framework that facilitates the construction of subexponential algorithms and matching conditional complexity bounds. It can be applied to intersection graphs of similarly-sized fat objects, yielding algorithms with running time $2^{O(n^{1-1/d})}$ for any fixed dimension $d\ge 2$ for many well-known graph problems, including Independent Set, $r$-Dominating Set for constant $r$, and Steiner Tree. For most problems, we get improved running times compared to prior work; in some cases, we give the first known subexponential algorithm in geometric intersection graphs. Additionally, most of the obtained algorithms are representation-agnostic, i.e., they work on the graph itself and do not require the geometric representation. Our algorithmic framework is based on a weighted separator theorem and various treewidth techniques. The lower bound framework is based on a constructive embedding of graphs into $d$-dimensional grids, and it allows us to derive matching $2^{\Omega(n^{1-1/d})}$ lower bounds under the exponential time hypothesis even in the much more restricted class of $d$-dimensional induced grid graphs.

Given a vertex-weighted directed graph $G=(V,E)$ and a set $T=\{t_1, t_2, \ldots, t_k\}$ of $k$ terminals, the objective of the Strongly Connected Steiner Subgraph (SCSS) problem is to find a vertex set $H\subseteq V$ of minimum weight such that $G[H]$ contains a $t_{i}\rightarrow t_j$ path for each $i\neq j$. The problem is NP-hard, but Feldman and Ruhl [ SIAM J. Comput., 36 (2006), pp. 543--561] gave a novel $n^{O(k)}$ algorithm for the SCSS problem, where $n$ is the number of vertices in the graph and $k$ is the number of terminals. We explore how much easier the problem becomes on planar directed graphs. Our main algorithmic result is a $2^{O(k)}\cdot n^{O(\sqrt{k})}$ algorithm for planar SCSS, which is an improvement of a factor of $O(\sqrt{k})$ in the exponent over the algorithm of Feldman and Ruhl. Our main hardness result is a matching lower bound for our algorithm: we show that planar SCSS does not have an $f(k)\cdot n^{o(\sqrt{k})}$ algorithm for any computable function $f$, unless the exponential time hypothesis (ETH) fails. To obtain our algorithm, we first show combinatorially that there is a minimal solution whose treewidth is $O(\sqrt{k})$, and then use the dynamic-programming based algorithm for finding bounded-treewidth solutions due to Feldmann and Marx [The Complexity Landscape of Fixed-Parameter Directed Steiner Network Problems, preprint, ŭlhttps://arxiv.org/abs/1707.06808]. To obtain the lower bound matching the algorithm, we need a delicate construction of gadgets arranged in a gridlike fashion to tightly control the number of terminals in the created instance. The following additional results put our upper and lower bounds in context: our $2^{O(k)}\cdot n^{O(\sqrt{k})}$ algorithm for planar directed graphs can be generalized to graphs excluding a fixed minor. Additionally, we can obtain this running time for the problem of finding an optimal planar solution even if the input graph is not planar. In general graphs, we cannot hope for such a dramatic improvement over the $n^{O(k)}$ algorithm of Feldman and Ruhl: assuming ETH, SCSS in general graphs does not have an $f(k)\cdot n^{o(k/\log k)}$ algorithm for any computable function $f$. Feldman and Ruhl generalized their $n^{O(k)}$ algorithm to the more general Directed Steiner Network (DSN) problem; here the task is to find a subgraph of minimum weight such that for every source $s_i$ there is a path to the corresponding terminal $t_i$. We show that, assuming ETH, there is no $f(k)\cdot n^{o(k)}$ time algorithm for DSN on acyclic planar graphs. All our lower bounds hold for the integer weighted edge version, while the algorithm works for the more general unweighted vertex version.

The Directed Feedback Vertex Set (DFVS) problem takes as input a directed graph G and seeks a smallest vertex set S that hits all cycles in G. This is one of Karp’s 21 $$\mathsf {NP}$$ -complete problems. Resolving the parameterized complexity status of DFVS was a long-standing open problem until Chen et al. in 2008 showed its fixed-parameter tractability via a $$4^kk! n^{\mathcal {O}(1)}$$ -time algorithm, where $$k = |S|$$ . Here we show fixed-parameter tractability of two generalizations of DFVS: We also solve the corresponding arc versions of these problems by fixed-parameter algorithms.

We prove essentially tight lower bounds, conditionally to the Exponential Time Hypothesis, for two fundamental but seemingly very different cutting problems on surface-embedded graphs: the Shortest Cut Graph problem and the Multiway Cut problem. A cut graph of a graph G embedded on a surface S is a subgraph of G whose removal from S leaves a disk. We consider the problem of deciding whether an unweighted graph embedded on a surface of genus g has a cut graph of length at most a given value. We prove a time lower bound for this problem of n^{Omega(g/log g)} conditionally to ETH. In other words, the first n^{O(g)}-time algorithm by Erickson and Har-Peled [SoCG 2002, Discr. Comput. Geom. 2004] is essentially optimal. We also prove that the problem is W[1]-hard when parameterized by the genus, answering a 17-year old question of these authors. A multiway cut of an undirected graph G with t distinguished vertices, called terminals, is a set of edges whose removal disconnects all pairs of terminals. We consider the problem of deciding whether an unweighted graph G has a multiway cut of weight at most a given value. We prove a time lower bound for this problem of n^{Omega(sqrt{gt + g^2}/log(gt))}, conditionally to ETH, for any choice of the genus g >=0 of the graph and the number of terminals t >=4. In other words, the algorithm by the second author [Algorithmica 2017] (for the more general multicut problem) is essentially optimal; this extends the lower bound by the third author [ICALP 2012] (for the planar case). Reductions to planar problems usually involve a grid-like structure. The main novel idea for our results is to understand what structures instead of grids are needed if we want to exploit optimally a certain value g of the genus.

In this work, we initiate the study of the Min-Ones d-SAT problem in the parameterized streaming model. An instance of the problem consists of a d-CNF formula F and an integer k, and the objective is to determine if F has a satisfying assignment which sets at most k variables to 1. In the parameterized streaming model, input is provided as a stream, just as in the usual streaming model. A key difference is that the bound on the read-write memory available to the algorithm is O(f(k) log n) (f: N -> N, a computable function) as opposed to the O(log n) bound of the usual streaming model. The other important difference is that the number of passes the algorithm makes over its input must be a (preferably small) function of k. We design a (k + 1)-pass parameterized streaming algorithm that solves Min-Ones d-SAT (d >= 2) using space O((kd^(ck) + k^d)log n) (c > 0, a constant) and a (d + 1)^k-pass algorithm that uses space O(k log n). We also design a streaming kernelization for Min-Ones 2-SAT that makes (k + 2) passes and uses space O(k^6 log n) to produce a kernel with O(k^6) clauses. To complement these positive results, we show that any k-pass algorithm for or Min-Ones d-SAT (d >= 2) requires space Omega(max{n^(1/k) / 2^k, log(n / k)}) on instances (F, k). This is achieved via a reduction from the streaming problem POT Pointer Chasing (Guha and McGregor [ICALP 2008]), which might be of independent interest. Given this, our (k + 1)-pass parameterized streaming algorithm is the best possible, inasmuch as the number of passes is concerned. In contrast to the results of Fafianie and Kratsch [MFCS 2014] and Chitnis et al. [SODA 2015], who independently showed that there are 1-pass parameterized streaming algorithms for Vertex Cover (a restriction of Min-Ones 2-SAT), we show using lower bounds from Communication Complexity that for any d >= 1, a 1-pass streaming algorithm for Min-Ones d-SAT requires space Omega(n). This excludes the possibility of a 1-pass parameterized streaming algorithm for the problem. Additionally, we show that any p-pass algorithm for the problem requires space Omega(n/p).

Packing is a classical problem where one is given a set of subsets of Euclidean space called objects, and the goal is to find a maximum size subset of objects that are pairwise non-intersecting. The problem is also known as the Independent Set problem on the intersection graph defined by the objects. Although the problem is NP-complete, there are several subexponential algorithms in the literature. One of the key assumptions of such algorithms has been that the objects are fat, with a few exceptions in two dimensions; for example, the packing problem of a set of polygons in the plane surprisingly admits a subexponential algorithm. In this paper we give tight running time bounds for packing similarly-sized non-fat objects in higher dimensions. We propose an alternative and very weak measure of fatness called the stabbing number, and show that the packing problem in Euclidean space of constant dimension $d \geq 3$ for a family of similarly sized objects with stabbing number $α$ can be solved in $2^{O(n^{1-1/d}α)}$ time. We prove that even in the case of axis-parallel boxes of fixed shape, there is no $2^{o(n^{1-1/d}α)}$ algorithm under ETH. This result smoothly bridges the whole range of having constant-fat objects on one extreme ($α=1$) and a subexponential algorithm of the usual running time, and having very "skinny" objects on the other extreme ($α=n^{1/d}$), where we cannot hope to improve upon the brute force running time of $2^{O(n)}$, and thereby characterizes the impact of fatness on the complexity of packing in case of similarly sized objects. We also study the same problem when parameterized by the solution size $k$, and give a $n^{O(k^{1-1/d}α)}$ algorithm, with an almost matching lower bound.

In algorithmic graph theory, a classic open question is to determine the complexity of the Maximum Independent Set problem on $$P_t$$ -free graphs, that is, on graphs not containing any induced path on t vertices. So far, polynomial-time algorithms are known only for $$t\le 5$$ (Lokshtanov et al., in: Proceedings of the twenty-fifth annual ACM-SIAM symposium on discrete algorithms, SODA 2014, Portland, OR, USA, January 5–7, 2014, pp 570–581, 2014), and an algorithm for $$t=6$$ announced recently (Grzesik et al. in Polynomial-time algorithm for maximum weight independent set on $${P}_6$$ -free graphs. CoRR, arXiv:1707.05491 , 2017). Here we study the existence of subexponential-time algorithms for the problem: we show that for any $$t\ge 1$$ , there is an algorithm for Maximum Independent Set on $$P_t$$ -free graphs whose running time is subexponential in the number of vertices. Even for the weighted version MWIS, the problem is solvable in $$2^{\mathcal {O}(\sqrt{tn \log n})}$$ time on $$P_t$$ -free graphs. For approximation of MIS in broom-free graphs, a similar time bound is proved. Scattered Set is the generalization of Maximum Independent Set where the vertices of the solution are required to be at distance at least d from each other. We give a complete characterization of those graphs H for which d-Scattered Set on H-free graphs can be solved in time subexponential in the size of the input (that is, in the number of vertices plus the number of edges):

We study the version of the k -disjoint paths problem where k demand pairs ( s 1 , t 1 ) , …, ( s k , t k ) are specified in the input and the paths in the solution are allowed to intersect, but such that no vertex is on more than c paths. We show that on directed acyclic graphs the problem is solvable in time n O ( d ) if we allow congestion k − d for k paths. Furthermore, we show that, under a suitable complexity theoretic assumption, the problem cannot be solved in time f ( k ) n o ( d / log ⁡ d ) for any computable function f .

No abstract available.

There are numerous examples of the so-called "square root phenomenon" in the field of parameterized algorithms: many of the most fundamental graph problems, parameterized by some natural parameter k, become significantly simpler when restricted to planar graphs and in particular the best possible running time is exponential in O(sqrt(k)) instead of O(k) (modulo standard complexity assumptions). We consider two classic optimization problems parameterized by the number of terminals. The Steiner Tree problem asks for a minimum-weight tree connecting a given set of terminals T in an edge-weighted graph. In the Subset Traveling Salesman problem we are asked to visit all the terminals T by a minimum-weight closed walk. We investigate the parameterized complexity of these problems in planar graphs, where the number k = |T| of terminals is regarded as the parameter. Our results are the following: • Subset TSP can be solved in time 2^O(sqrt(k) log k) . n^O(1) even on edge-weighted directed planar graphs. This improves upon the algorithm of Klein and Marx [SODA 2014] with the same running time that worked only on undirected planar graphs with polynomially large integer weights. • Assuming the Exponential-Time Hypothesis, Steiner Tree on undirected planar graphs cannot be solved in time 2^o(k) . n^O(1), even in the unit-weight setting. This lower bound makes Steiner Tree the first "genuinely planar" problem (i.e., where the input is only planar graph with a set of distinguished terminals) for which we can show that the square root phenomenon does not appear. • Steiner Tree can be solved in time n^O(sqrt(k)) * W on undirected planar graphs with maximum edge weight W. Note that this result is incomparable to the fact that the problem is known to be solvable in time 2^k . n^O(1) even in general graphs. A direct corollary of the combination of our results for Steiner Tree is that this problem does not admit a parameter-preserving polynomial kernel on planar graphs unless ETH fails.

In this paper, we study multi-budgeted variants of the classic minimum cut problem and graph separation problems that turned out to be important in parameterized complexity: Skew Multicut and Directed Feedback Arc Set. In our generalization, we assign colors 1,2,...,l to some edges and give separate budgets k_1,k_2,...,k_l for colors 1,2,...,l. For every color i in {1,...,l}, let E_i be the set of edges of color i. The solution C for the multi-budgeted variant of a graph separation problem not only needs to satisfy the usual separation requirements (i.e., be a cut, a skew multicut, or a directed feedback arc set, respectively), but also needs to satisfy that |C cap E_i| <= k_i for every i in {1,...,l}. Contrary to the classic minimum cut problem, the multi-budgeted variant turns out to be NP-hard even for l = 2. We propose FPT algorithms parameterized by k=k_1 +...+ k_l for all three problems. To this end, we develop a branching procedure for the multi-budgeted minimum cut problem that measures the progress of the algorithm not by reducing k as usual, by but elevating the capacity of some edges and thus increasing the size of maximum source-to-sink flow. Using the fact that a similar strategy is used to enumerate all important separators of a given size, we merge this process with the flow-guided branching and show an FPT bound on the number of (appropriately defined) important multi-budgeted separators. This allows us to extend our algorithm to the Skew Multicut and Directed Feedback Arc Set problems. Furthermore, we show connections of the multi-budgeted variants with weighted variants of the directed cut problems and the Chain l-SAT problem, whose parameterized complexity remains an open problem. We show that these problems admit a bounded-in-parameter number of "maximally pushed" solutions (in a similar spirit as important separators are maximally pushed), giving somewhat weak evidence towards their tractability.

We consider the multiple traveling salesman problem on a weighted tree. In this problem there are m salesmen located at the root initially. Each of them will visit a subset of vertices and return to the root. The goal is to assign a tour to every salesman such that every vertex is visited and the longest tour among all salesmen is minimized. The problem is equivalent to the subtree cover problem, in which we cover a tree with rooted subtrees such that the weight of the maximum weighted subtree is minimized. The classical machine scheduling problem can be viewed as a special case of our problem when the given tree is a star. We provide approximation and parameterized algorithms for this problem. We first present a PTAS (Polynomial Time Approximation Scheme). We then observe that, the problem remains NP-hard even if tree height and edge weight are constant, and present an FPT algorithm for this problem parameterized by the largest tour length. To achieve the FPT algorithm, we first formulate the problem as an integer linear program having a certain “tree-fold” structure. Then we show that an ILP with such a structure is FPT, which is a generalization of an earlier FPT result for n-fold integer programming by Hemmecke, Onn and Romanchuk [5]. This extension of n-fold ILP may be of independent interest.

In the list homomorphism problem, the input consists of two graphs G and H, together with a list L(v) \subseteq V(H) for every vertex v \in V(G). The task is to find a homomorphism phi:V(G) -> V(H) respecting the lists, that is, we have that phi(v) \in L(v) for every v \in V(H) and if u and v are adjacent in G, then phi(u) and phi(v) are adjacent in H. If H is a fixed graph, then the problem is denoted LHom(H). We consider the reflexive version of the problem, where we assume that every vertex in H has a self-loop. If is known that reflexive LHom(H) is polynomial-time solvable if H is an interval graph and it is NP-complete otherwise [Feder and Hell, JCTB 1998]. We explore the complexity of the problem parameterized by the treewidth tw(G) of the input graph G. If a tree decomposition of G of width tw(G) is given in the input, then the problem can be solved in time |V(H)|^{tw(G)} n^{O(1)} by naive dynamic programming. Our main result completely reveals when and by exactly how much this naive algorithm can be improved. We introduce a simple combinatorial invariant i^*(H), which is based on the existence of decompositions and incomparable sets, and show that this number should appear as the base of the exponent in the best possible running time. Specifically, we prove for every fixed non-interval graph H that * If a tree decomposition of width tw(G) is given in the input, then the problem can be solved in time i^*(H)^{tw(G)} n^{O(1)}. * Assuming the Strong Exponential-Time Hypothesis (SETH), the probem cannot be solved in time (i^*(H)-epsilon)^{tw(G)} n^{O(1)} for any epsilon>0. Thus by matching upper and lower bounds, our result exactly characterizes for every fixed H the complexity of reflexive LHom(H) parameterized by treewidth.

We give an algorithmic and lower-bound framework that facilitates the construction of subexponential algorithms and matching conditional complexity bounds. It can be applied to a wide range of geometric intersection graphs (intersections of similarly sized fat objects), yielding algorithms with running time 2O(n1−1/d) for any fixed dimension d≥ 2 for many well known graph problems, including Independent Set, r-Dominating Set for constant r, and Steiner Tree. For most problems, we get improved running times compared to prior work; in some cases, we give the first known subexponential algorithm in geometric intersection graphs. Additionally, most of the obtained algorithms work on the graph itself, i.e., do not require any geometric information. Our algorithmic framework is based on a weighted separator theorem and various treewidth techniques.

A central problem in parameterized algorithms is to obtain algorithms with running time $f(k)\cdot n^{O(1)}$ such that $f$ is as slow growing a function of the parameter $k$ as possible. In particular, a large number of basic parameterized problems admit parameterized algorithms where $f(k)$ is single-exponential, that is, $c^k$ for some constant $c$, which makes aiming for such a running time a natural goal for other problems as well. However, there are still plenty of problems where the $f(k)$ appearing in the best-known running time is worse than single-exponential and it remained “slightly superexponential” even after serious attempts to bring it down. A natural question to ask is whether the $f(k)$ appearing in the running time of the best-known algorithms is optimal for any of these problems. In this paper, we examine parameterized problems where $f(k)$ is $k^{O(k)}=2^{O(k\log k)}$ in the best-known running time, and for a number of such problems we show that the dependence on $k$ in the running time cannot be improved to single-exponential. More precisely we prove the following tight lower bounds, for four natural problems, arising from three different domains: (1) In the Closest String problem, given strings $s_1$, $\dots$, $s_t$ over an alphabet $\Sigma$ of length $L$ each, and an integer $d$, the question is whether there exists a string $s$ over $\Sigma$ of length $L$, such that its hamming distance from each of the strings $s_i$, $1\leq i \leq t$, is at most $d$. The pattern matching problem Closest String is known to be solvable in times $2^{O(d\log d)}\cdot n^{O(1)}$ and $2^{O(d\log |\Sigma|)}\cdot n^{O(1)}$. We show that there are no $2^{o(d\log d)}\cdot n^{O(1)}$ or $2^{o(d\log |\Sigma|)}\cdot n^{O(1)}$ time algorithms, unless the Exponential Time Hypothesis (ETH) fails. (2) The graph embedding problem Distortion, that is, deciding whether a graph $G$ has a metric embedding into the integers with distortion at most $d$ can be solved in time $2^{O(d\log d)}\cdot n^{O(1)}$. We show that there is no $2^{o(d\log d)}\cdot n^{O(1)}$ time algorithm, unless the ETH fails. (3) The Disjoint Paths problem can be solved in time $2^{O(w\log w)}\cdot n^{O(1)}$ on graphs of treewidth at most $w$. We show that there is no $2^{o(w\log w)}\cdot n^{O(1)}$ time algorithm, unless the ETH fails. (4) The Chromatic Number problem can be solved in time $2^{O(w\log w)}\cdot n^{O(1)}$ on graphs of treewidth at most $w$. We show that there is no $2^{o(w\log w)}\cdot n^{O(1)}$ time algorithm, unless the ETH fails. To obtain our results, we first prove the lower bound for variants of basic problems: finding cliques, independent sets, and hitting sets. These artificially constrained variants form a good starting point for proving lower bounds on natural problems without any technical restrictions and could be of independent interest. Several follow-up works have already obtained tight lower bounds by using our framework, and we believe it will prove useful in obtaining even more lower bounds in the future.

We obtain a number of lower bounds on the running time of algorithms solving problems on graphs of bounded treewidth. We prove the results under the Strong Exponential Time Hypothesis of Impagliazzo and Paturi. In particular, assuming that n -variable m -clause SAT cannot be solved in time (2-ϵ) n m O (1) , we show that for any ϵ > 0: • I ndependent S et cannot be solved in time (2-ϵ) tw( G ) | V ( G )| O (1) , • D ominating S et cannot be solved in time (3-ϵ) tw( G ) | V ( G )| O (1) , • M ax C ut cannot be solved in time (2-ϵ) tw( G ) | V ( G )| O (1) , • O dd C ycle T ransversal cannot be solved in time (3-ϵ) tw( G ) | V ( G )| O (1) , • For any fixed q ≥ 3, q -C oloring cannot be solved in time ( q -ϵ) tw ( G ) | V ( G )| O (1) , • P artition I nto T riangles cannot be solved in time (2-ϵ) tw ( G ) | V ( G )| O (1) . Our lower bounds match the running times for the best known algorithms for the problems, up to the ϵ in the base.

We show that for a number of parameterized problems for which only 2^{O(k)} n^{O(1)} time algorithms are known on general graphs, subexponential parameterized algorithms with running time 2^{O(k^{1-1/(1+d)} log^2 k)} n^{O(1)} are possible for graphs of polynomial growth with growth rate (degree) d, that is, if we assume that every ball of radius r contains only O(r^d) vertices. The algorithms use the technique of low-treewidth pattern covering, introduced by Fomin et al. [FOCS 2016] for planar graphs; here we show how this strategy can be made to work for graphs of polynomial growth. Formally, we prove that, given a graph G of polynomial growth with growth rate d and an integer k, one can in randomized polynomial time find a subset A of V(G) such that on one hand the treewidth of G[A] is O(k^{1-1/(1+d)} log k), and on the other hand for every set X of vertices of size at most k, the probability that X is a subset of A is 2^{-O(k^{1-1/(1+d)} log^2 k)}. Together with standard dynamic programming techniques on graphs of bounded treewidth, this statement gives subexponential parameterized algorithms for a number of subgraph search problems, such as Long Path or Steiner Tree, in graphs of polynomial growth. We complement the algorithm with an almost tight lower bound for Long Path: unless the Exponential Time Hypothesis fails, no parameterized algorithm with running time 2^{k^{1-1/d-epsilon}}n^{O(1)} is possible for any positive epsilon and any integer d >= 3.

The complexity of evaluating conjunctive queries can depend significantly on the structure of the query. For example, it is well known that various notions of acyclicity can make the evaluation problem tractable. More generally, it seems that the complexity is connected to the "treelikeness" of the graph or hypergraph describing the query structure. In the lecture, we will review some of the notions of treelikeness that were proposed in the literature and how they are relevant for the complexity of evaluating conjunctive queries and related problems.

For a fixed graph H, we are interested in the parameterized complexity of the following problem, called {H}-M-Deletion, parameterized by the treewidth tw of the input graph: given an n-vertex graph G and an integer k, decide whether there exists S subseteq V(G) with |S| <= k such that G setminus S does not contain H as a minor. In previous work [IPEC, 2017] we proved that if H is planar and connected, then the problem cannot be solved in time 2^{o(tw)} * n^{O(1)} under the ETH, and can be solved in time 2^{O(tw * log tw)} * n^{O(1)}. In this article we manage to classify the optimal asymptotic complexity of {H}-M-Deletion when H is a connected planar graph on at most 5 vertices. Out of the 29 possibilities (discarding the trivial case H = K_1), we prove that 9 of them are solvable in time 2^{Theta (tw)} * n^{O(1)}, and that the other 20 ones are solvable in time 2^{Theta (tw * log tw)} * n^{O(1)}. Namely, we prove that K_4 and the diamond are the only graphs on at most 4 vertices for which the problem is solvable in time 2^{Theta (tw * log tw)} * n^{O(1)}, and that the chair and the banner are the only graphs on 5 vertices for which the problem is solvable in time 2^{Theta (tw)} * n^{O(1)}. For the version of the problem where H is forbidden as a topological minor, the case H = K_{1,4} can be solved in time 2^{Theta (tw)} * n^{O(1)}. This exhibits, to the best of our knowledge, the first difference between the computational complexity of both problems.

We study approximation and parameterized algorithms for R||C_max, focusing on the problem when the rank of the matrix formed by job processing times is small. Bhaskara et al. initiated the study of approximation algorithms with respect to the rank, showing that R||C_max admits a QPTAS (Quasi-polynomial time approximation scheme) when the rank is 2, and becomes APX-hard when the rank is 4. We continue this line of research. We prove that R||C_max is APX-hard even if the rank is 3, resolving an open problem. We then show that R||C_max is FPT parameterized by the rank and the largest job processing time p_max. This generalizes the parameterized results on P||C_max and R||C_max with few different types of machines. We also provide nearly tight lower bounds under Exponential Time Hypothesis which suggests that the running time of the FPT algorithm is unlikely to be improved significantly.

We introduce graph motif parameters, a class of graph parameters that depend only on the frequencies of constant-size induced subgraphs. Classical works by Lovász show that many interesting quantities have this form, including, for fixed graphs H, the number of H-copies (induced or not) in an input graph G, and the number of homomorphisms from H to G.

We study the complexity of a generic hitting problem H - Subgraph Hitting , where given a fixed pattern graph H and an input graph G , the task is to find a set X ⊆ V ( G ) of minimum size that hits all subgraphs of G isomorphic to H . In the colorful variant of the problem, each vertex of G is precolored with some color from V ( H ) and we require to hit only H -subgraphs with matching colors. Standard techniques shows that for every fixed H , the problem is fixed-parameter tractable parameterized by the treewidth of G ; however, it is not clear how exactly the running time should depend on treewidth. For the colorful variant, we demonstrate matching upper and lower bounds showing that the dependence of the running time on treewidth of G is tightly governed by μ ( H ) , the maximum size of a minimal vertex separator in H . That is, we show for every fixed H that, on a graph of treewidth t , the colorful problem can be solved in time 2 O ( t μ ( H ) ) ⋅ | V ( G ) | , but cannot be solved in time 2 o ( t μ ( H ) ) ⋅ | V ( G ) | O ( 1 ) , assuming the Exponential Time Hypothesis (ETH). Furthermore, we give some preliminary results showing that, in the absence of colors, the parameterized complexity landscape of H - Subgraph Hitting is much richer.

In the Asymmetric Traveling Salesperson Problem (ATSP) the goal is to find a closed walk of minimum cost in a directed graph visiting every vertex. We consider the approximability of ATSP on topologically restricted graphs. It has been shown by [Oveis Gharan and Saberi 2011] that there exists polynomial-time constant-factor approximations on planar graphs and more generally graphs of constant orientable genus. This result was extended to non-orientable genus by [Erickson and Sidiropoulos 2014]. We show that for any class of \emph{nearly-embeddable} graphs, ATSP admits a polynomial-time constant-factor approximation. More precisely, we show that for any fixed $k\geq 0$, there exist $α, β>0$, such that ATSP on $n$-vertex $k$-nearly-embeddable graphs admits a $α$-approximation in time $O(n^β)$. The class of $k$-nearly-embeddable graphs contains graphs with at most $k$ apices, $k$ vortices of width at most $k$, and an underlying surface of either orientable or non-orientable genus at most $k$. Prior to our work, even the case of graphs with a single apex was open. Our algorithm combines tools from rounding the Held-Karp LP via thin trees with dynamic programming. We complement our upper bounds by showing that solving ATSP exactly on graphs of pathwidth $k$ (and hence on $k$-nearly embeddable graphs) requires time $n^{Ω(k)}$, assuming the Exponential-Time Hypothesis (ETH). This is surprising in light of the fact that both TSP on undirected graphs and Minimum Cost Hamiltonian Cycle on directed graphs are FPT parameterized by treewidth.

Given a set of n points S in the plane, a triangulation T of S is a maximal set of non-crossing segments with endpoints in S. We present an algorithm that computes the number of triangulations on a given set of n points in time n^{ (11+ o(1)) sqrt{n} }, significantly improving the previous best running time of O(2^n n^2) by Alvarez and Seidel [SoCG 2013]. Our main tool is identifying separators of size O(sqrt{n}) of a triangulation in a canonical way. The definition of the separators are based on the decomposition of the triangulation into nested layers ("cactus graphs"). Based on the above algorithm, we develop a simple and formal framework to count other non-crossing straight-line graphs in n^{O(sqrt{n})} time. We demonstrate the usefulness of the framework by applying it to counting non-crossing Hamilton cycles, spanning trees, perfect matchings, 3-colorable triangulations, connected graphs, cycle decompositions, quadrangulations, 3-regular graphs, and more.

The minimum unsatisfiability version of a constraint satisfaction problem (CSP) asks for an assignment where the number of unsatisfied constraints is minimum possible, or equivalently, asks for a minimum-size set of constraints whose deletion makes the instance satisfiable. For a finite set Gamma of constraints, we denote by CSP(Gamma) the restriction of the problem where each constraint is from Gamma. The polynomial-time solvability and the polynomial-time approximability of CSP(Gamma) were fully characterized by [Khanna et al. SICOMP 2000]. Here we study the fixed-parameter (FP-) approximability of the problem: given an instance and an integer k, one has to find a solution of size at most g(k) in time f(k)n^{O(1)} if a solution of size at most k exists. We especially focus on the case of constant-factor FP-approximability. Our main result classifies each finite constraint language Gamma into one of three classes: (1) CSP(Gamma) has a constant-factor FP-approximation; (2) CSP(Gamma) has a (constant-factor) FP-approximation if and only if Nearest Codeword has a (constant-factor) FP-approximation; (3) CSP(Gamma) has no FP-approximation, unless FPT=W[P]. We show that problems in the second class do not have constant-factor FP-approximations if both the Exponential-Time Hypothesis (ETH) and the Linear PCP Conjecture (LPC) hold. We also show that such an approximation would imply the existence of an FP-approximation for the k-Densest Subgraph problem with ratio 1-epsilon for any epsilon>0.

We prove the following theorem. Given a planar graph G and an integer k, it is possible in polynomial time to randomly sample a subset A of vertices of G with the following properties: 1) A induces a subgraph of G of treewidth O(√(k log k)), and 2) for every connected subgraph H of G on at most k vertices, the probability that A covers the whole vertex set of H is at least (2O(√k log2 k)· nO(1))-1, where n is the number of vertices of G. Together with standard dynamic programming techniques for graphs of bounded treewidth, this result gives a versatile technique for obtaining (randomized) subexponential parameterized algorithms for problems on planar graphs, usually with running time bound 2O(√(k log2k))nO(1). The technique can be applied to problems expressible as searching for a small, connected pattern with a prescribed property in a large host graph, examples of such problems include DIRECTED k-Path, WEIGHTED k-Path, VERTEX COVER LOCAL SEARCH, and SUBGRAPH ISOMORPHISM, among others. Up to this point, it was open whether these problems can be solved in subexponential parameterized time on planar graphs, because they are not amenable to the classic technique of bidimensionality. Furthermore, all our results hold in fact on any class of graphs that exclude a fixed apex graph as a minor, in particular on graphs embeddable in any fixed surface.

Given a directed graph $G$ and a list $(s_1,t_1),\dots,(s_d,t_d)$ of terminal pairs, the Directed Steiner Network problem asks for a minimum-cost subgraph of $G$ that contains a directed $s_i\to t_i$ path for every $1\le i \le k$. The special case Directed Steiner Tree (when we ask for paths from a root $r$ to terminals $t_1,\dots,t_d$) is known to be fixed-parameter tractable parameterized by the number of terminals, while the special case Strongly Connected Steiner Subgraph (when we ask for a path from every $t_i$ to every other $t_j$) is known to be W[1]-hard. We systematically explore the complexity landscape of directed Steiner problems to fully understand which other special cases are FPT or W[1]-hard. Formally, if $\mathcal{H}$ is a class of directed graphs, then we look at the special case of Directed Steiner Network where the list $(s_1,t_1),\dots,(s_d,t_d)$ of requests form a directed graph that is a member of $\mathcal{H}$. Our main result is a complete characterization of the classes $\mathcal{H}$ resulting in fixed-parameter tractable special cases: we show that if every pattern in $\mathcal{H}$ has the combinatorial property of being "transitively equivalent to a bounded-length caterpillar with a bounded number of extra edges," then the problem is FPT, and it is W[1]-hard for every recursively enumerable $\mathcal{H}$ not having this property. This complete dichotomy unifies and generalizes the known results showing that Directed Steiner Tree is FPT [Dreyfus and Wagner, Networks 1971], $q$-Root Steiner Tree is FPT for constant $q$ [Such\'y, WG 2016], Strongly Connected Steiner Subgraph is W[1]-hard [Guo et al., SIAM J. Discrete Math. 2011], and Directed Steiner Network is solvable in polynomial-time for constant number of terminals [Feldman and Ruhl, SIAM J. Comput. 2006], and moreover reveals a large continent of tractable cases that were not known before.

Choosability, introduced by Erdös, Rubin, and Taylor [Congr. Number. 1979], is a well-studied concept in graph theory: we say that a graph is c-choosable if for any assignment of a list of c colors to each vertex, there is a proper coloring where each vertex uses a color from its list. We study the complexity of deciding choosability on graphs of bounded treewidth. It follows from earlier work that 3-choosability can be decided in time 2^(2^(O(w)))*n^(O(1)) on graphs of treewidth w. We complement this result by a matching lower bound giving evidence that double-exponential dependence on treewidth may be necessary for the problem: we show that an algorithm with running time 2^(2^(o(w)))*n^(O(1)) would violate the Exponential-Time Hypothesis (ETH). We consider also the optimization problem where the task is to delete the minimum number of vertices to make the graph 4-choosable, and demonstrate that dependence on treewidth becomes tripleexponential for this problem: it can be solved in time 2^(2^(2^(O(w))))*n^(O(1)) on graphs of treewidth w, but an algorithm with running time 2^(2^(2^(o(w))))*n^(O(1)) would violate ETH.

It is an outstanding open question in algorithmic graph theory to determine the complexity of the MAXIMUM INDEPENDENT SET problem on P_t-free graphs, that is, on graphs not containing any induced path on t vertices. So far, polynomial-time algorithms are known only for t at most 5 [Lokshtanov et al., SODA 2014, 570-581, 2014]. Here we study the existence of subexponential-time algorithms for the problem: by generalizing an earlier result of Randerath and Schiermeyer for t=5 [Discrete App. Math., 158 (2010), 1041-1044], we show that for any t at least 5, there is an algorithm for MAXIMUM INDEPENDENT SET on P_t-free graphs whose running time is subexponential in the number of vertices. SCATTERED SET is the generalization of MAXIMUM INDEPENDENT SET where the vertices of the solution are required to be at distance at least $d$ from each other. We give a complete characterization of those graphs H for which SCATTERED SET on H-free graphs can be solved in time subexponential in the size of the input (that is, in the number of vertices plus the number of edges): * If every component of H is a path, then d-SCATTERED SET on H-free graphs with n vertices and m edges can be solved in time 2^{(n+m)^{1-O(1/|V(H)|)}}, even if d is part of the input. * Otherwise, assuming ETH, there is no 2^{o(n+m)} time algorithm for d-SCATTERED SET for any fixed d at least 3 on H-free graphs with n vertices and m edges.

By now, we have a good understanding of how NP-hard problems become easier on graphs of bounded treewidth and bounded cliquewidth: for various problems, matching upper bounds and conditional lower bounds describe exactly how the running time has to depend on treewidth or cliquewidth. In particular, Fomin et al. (2009, 2010) have shown a significant difference between these two parameters: assuming the Exponential-Time Hypothesis (ETH), the optimal algorithms for problems such as Max Cut and Edge Dominating Set have running time 2O(t) nO(1) when parameterized by treewidth, but nO(t) when parameterized by cliquewidth. In this paper, we show that a similar phenomenon occurs also for counting problems. Specifically, we prove that, assuming the counting version of the Strong Exponential-Time Hypothesis (#SETH), the problem of counting perfect matchings has no (2 – ∊)knO(1) time algorithm for any ∊ > 0 on graphs of treewidth k (but it is known to be solvable in time 2knO(1) if a tree decomposition of width k is given), and has no O(n(1–∊)k) time algorithm for any ∊ > 0 on graphs of cliquewidth k (but it can be solved in time O(nk+1) if a k-expression is given). A celebrated result of Fisher, Kasteleyn, and Temperley from the 1960s shows that counting perfect matchings in planar graphs is polynomial-time solvable. This was later extended by Gallucio and Loebl (1999), Tesler (2000) and Regge and Zechina (2000) who gave 4k · nO(1) time algorithms for graphs of genus k. We show that the dependence on the genus k has to be exponential: assuming #ETH, the counting version of ETH, there is no 2o(k) · nO(1) time algorithm for the problem on graphs of genus k.

We present the first polynomial-time approximation scheme (PTAS), i.e., (1+ε)-approximation algorithm for any constant ε> 0, for the planar group Steiner tree problem (in which each group lies on a boundary of a face). This result improves on the best previous approximation factor of O(logn (loglogn)O(1)). We achieve this result via a novel and powerful technique called spanner bootstrapping, which allows one to bootstrap from a superconstant approximation factor (even superpolynomial in the input size) all the way down to a PTAS. This is in contrast with the popular existing approach for planar PTASs of constructing light-weight spanners in one iteration, which notably requires a constant-factor approximate solution to start from. Spanner bootstrapping removes one of the main barriers for designing PTASs for problems which have no known constant-factor approximation (even on planar graphs), and thus can be used to obtain PTASs for several difficult-to-approximate problems.

The field of exact exponential time algorithms for non-deterministic polynomial-time hard problems has thrived since the mid-2000s. While exhaustive search remains asymptotically the fastest known algorithm for some basic problems, non-trivial exponential time algorithms have been found for a myriad of problems, including G raph C oloring , H amiltonian P ath , D ominating S et , and 3-CNF-S at . In some instances, improving these algorithms further seems to be out of reach. The CNF-S at problem is the canonical example of a problem for which the trivial exhaustive search algorithm runs in time O (2 n ), where n is the number of variables in the input formula. While there exist non-trivial algorithms for CNF-S at that run in time o (2 n ), no algorithm was able to improve the growth rate 2 to a smaller constant, and hence it is natural to conjecture that 2 is the optimal growth rate. The strong exponential time hypothesis (SETH) by Impagliazzo and Paturi [JCSS 2001] goes a little bit further and asserts that, for every ϵ < 1, there is a (large) integer k such that k -CNF-S at cannot be computed in time 2 ϵ n . In this article, we show that, for every ϵ < 1, the problems H itting S et , S et S plitting , and NAE-S at cannot be computed in time O (2 ϵ n ) unless SETH fails. Here n is the number of elements or variables in the input. For these problems, we actually get an equivalence to SETH in a certain sense. We conjecture that SETH implies a similar statement for S et C over and prove that, under this assumption, the fastest known algorithms for S teiner T ree , C onnected V ertex C over , S et P artitioning , and the pseudo-polynomial time algorithm for S ubset S um cannot be significantly improved. Finally, we justify our assumption about the hardness of S et C over by showing that the parity of the number of solutions to S et C over cannot be computed in time O (2 ϵ n ) for any ϵ < 1 unless SETH fails.

We study a general family of facility location problems defined on planar graphs and on the 2-dimensional plane. In these problems, a subset of k objects has to be selected, satisfying certain packing (disjointness) and covering constraints. Our main result is showing that, for each of these problems, the $n^{{\mathcal{O}}(k)}$ time brute force algorithm of selecting k objects can be improved to $n^{{\mathcal{O}}(\sqrt{k})}$ time. The algorithm is based on focusing on the Voronoi diagram of a hypothetical solution of k objects; this idea was introduced recently in the design of geometric QPTASs, but was not yet used for exact algorithms and for planar graphs. As concrete consequences of our main result, we obtain $n^{{\mathcal{O}}(\sqrt{k})}$ time algorithms for the following problems: d -Scattered Set in planar graphs (find k vertices at pairwise distance d); d -Dominating Set/(k,d)-Center in planar graphs (find k vertices such that every vertex is at distance at most d from these vertices); select k pairwise disjoint connected vertex sets from a given collection; select k pairwise disjoint disks in the plane (of possibly different radii) from a given collection; cover a set of points in the plane by selecting k disks/axis-parallel squares from a given collection. We complement these positive results with lower bounds suggesting that some similar, but slightly more general problems (such as covering points with axis-parallel rectangles) do not admit $n^{{\mathcal{O}}(\sqrt{k})}$ time algorithms.

We study two fundamental problems related to finding subgraphs: (1) given graphs G and H, Subgraph Test asks if H is isomorphic to a subgraph of G, (2) given graphs G, H, and an integer t, PACKING asks if G contains t vertex-disjoint subgraphs isomorphic to H. For every graph class ℱ, let ℱ-Subgraph Test and ℱ-Packing be the special cases of the two problems where H is restricted to be in F. Our goal is to study which classes ℱ make the two problems tractable in one of the following senses: (randomized) polynomial-time solvable, admits a polynomial (many-one) kernel (that is, has a polynomial-time preprocessing procedure that creates an equivalent instance whose size is polynomially bounded by the size of the solution), or admits a polynomial Turing kernel (that is, has an adaptive polynomial-time procedure that reduces the problem to a polynomial number of instances, each of which has size bounded polynomially by the size of the solution). To obtain a more robust setting, we restrict our attention to hereditary classes F. It is known that if every component of every graph in ℱ has at most two vertices, then ℱ-Packing is polynomial-time solvable, and NP-hard otherwise. We identify a simple combinatorial property (every component of every graph in ℱ either has bounded size or is a bipartite graph with one of the sides having bounded size) such that if a hereditary class ℱ has this property, then ℱ-Packing admits a polynomial kernel, and has no polynomial (many-one) kernel otherwise, unless the polynomial hierarchy collapses. Furthermore, if ℱ does not have this property, then ℱ-Packing is either WK[1]-hard, W[1]-hard, or Long Path-hard, giving evidence that it does not admit polynomial Turing kernels either. For ℱ-Subgraph Test, we show that if every graph of a hereditary class ℱ satisfies the property that it is possible to delete a bounded number of vertices such that every remaining component has size at most two, then F-Subgraph Test is solvable in randomized polynomial time and it is NP-hard otherwise. We introduce a combinatorial property called (a, b, c, d)-splittability and show that if every graph in a hereditary class ℱ has this property, then F-Subgraph Test admits a polynomial Turing kernel and it is WK[1]-hard, W[1]-hard, or Long Path-hard otherwise. We do not give a complete characterization of the cases when F-Subgraph Test admits polynomial many-one kernels, but show examples that this question is much more fragile than the characterization for Turing kernels.

We study the following general disjoint paths problem: given a supply graph G, a set T ⊆ V(G) of terminals, a demand graph H on the vertices T, and an integer k, the task is to find a set of k pairwise vertex-disjoint valid paths, where we say that a path of the supply graph G is valid if its endpoints are in T and adjacent in the demand graph H. For a class H of graphs, we denote by Maximum Disjoint ℋ-Paths the restriction of this problem when the demand graph H is assumed to be a member of ℋ. We study the fixed-parameter tractability of this family of problems, parameterized by k. Our main result is a complete characterization of the fixed-parameter tractable cases of Maximum Disjoint ℋ-Paths for every hereditary class ℋ of graphs: it turns out that complexity depends on the existence of large induced matchings and large induced skew bicliques in the demand graph H (a skew biclique is a bipartite graph on vertices a1, …, an, b1, …, bn with ai and bj being adjacent if and only if i ≤ j). Specifically, we prove the following classification for every hereditary class ℋ. If ℋ does not contain every matching and does not contain every skew biclique, then MAXIMUM Disjoint ℋ-Paths is FPT. If ℋ does not contain every matching, but contains every skew biclique, then MAXIMUM DISJOINT ℋ-Paths is W[1]-hard, admits an FPT approximation, and the valid paths satisfy an analog of the Erdös-Pósa property. If ℋ contains every matching, then MAXIMUM DISJOINT ℋ-Paths is W[1]-hard and the valid paths do not satisfy the analog of the Erdös-Pósa property.

We generalize the structure theorem of Robertson and Seymour for graphs excluding a fixed graph $H$ as a minor to graphs excluding $H$ as a topological subgraph. We prove that for a fixed $H$, every graph excluding $H$ as a topological subgraph has a tree decomposition where each part is either “almost embeddable” to a fixed surface or has bounded degree with the exception of a bounded number of vertices. Furthermore, we prove that such a decomposition is computable by an algorithm that is fixed-parameter tractable with parameter $|H|$. We present two algorithmic applications of our structure theorem. To illustrate the mechanics of a “typical” application of the structure theorem, we show that on graphs excluding $H$ as a topological subgraph, Partial Dominating Set (find $k$ vertices whose closed neighborhood has maximum size) can be solved in time $f(H,k)\cdot n^{O(1)}$. More significantly, we show that on graphs excluding $H$ as a topological subgraph, Graph Isomorphism can be solved in time $n^{f(H)}$. This result unifies and generalizes two previously known important polynomial time solvable cases of Graph Isomorphism: bounded-degree graphs [E. M. Luks, J. Comput. System Sci., 25 (1982), pp. 42--65] and $H$-minor free graphs [I. N. Ponomarenko, Zap. Nauchn. Sem. Leningrad. Otdel. Mat. Inst. Steklov. (LOMI), 174 (1988), pp. 147--177, 182]. The proof of this result needs a generalization of our structure theorem to the context of invariant treelike decomposition.

We study the minimum interval deletion problem, which asks for the removal of a set of at most k vertices to make a graph of n vertices into an interval graph. We present a parameterized algorithm of runtime 10 k ⋅ n O (1) for this problem—that is, we show that the problem is fixed-parameter tractable.

Given a graphGand an integerk, theFeedback Vertex Set(FVS) problem asks if there is a vertex setTof size at mostkthat hits all cycles in the graph. The first fixed-parameter algorithm for FVS in undirected graphs appeared in a monograph of Mehlhorn in 1984. The fixed-parameter tractability (FPT) status of FVS in directed graphs was a long-standing open problem until Chen et al. (STOC ’08, JACM ’08) showed that it is fixed-parameter tractable by giving a 4kk! ·nO(1)time algorithm. There are two subset versions of this problems: We are given an additional subsetSof vertices (resp., edges), and we want to hit all cycles passing through a vertex ofS(resp., an edge ofS); the two variants are known to be equivalent in the parameterized sense. Recently, theSubsetFVS problem in undirected graphs was shown to be FPT by Cygan et al. (ICALP’11, SIDMA’13) and independently by Kakimura et al. (SODA ’12). We generalize the result of Chen et al. (STOC ’08, JACM ’08) by showing that aSubsetFVS in directed graphs can be solved in time 2O(k3)ċnO(1)(i.e., FPT parameterized by sizekof the solution). By our result, we complete the picture for FVS problems and their subset versions in undirected and directed graphs. The technique of random sampling of important separators was used by Marx and Razgon (STOC ’11, SICOMP ’14) to show thatUndirected Multicutis FPT, and it was generalized by Chitnis et al. (SODA ’12, SICOMP ’13) to directed graphs to show thatDirected Multiway Cutis FPT. In addition to proving the FPT of aDirected SubsetFVS, we reformulate the random sampling of important separators technique in an abstract way that can be used with a general family of transversal problems. We believe this general approach will be useful for showing the FPT of other problems in directed graphs. Moreover, we modify the probability distribution used in the technique to achieve better running time; in particular, this gives an improvement from 22O(k)to 2O(k2)in the parameter dependence of theDirected Multiway Cutalgorithm of Chitnis et al. (SODA ’12, SICOMP ’13).

We consider connectivity-augmentation problems in a setting where each potential new edge has a non-negative cost associated with it, and the task is to achieve a certain connectivity target with at most p new edges of minimum total cost. The main result is that the minimum cost augmentation of edge-connectivity from k − 1 to k with at most p new edges is fixed-parameter tractable parameterized by p and admits a polynomial kernel. We also prove the fixed-parameter tractability of increasing edge connectivity from 0 to 2 and increasing node connectivity from 1 to 2.

We are studying d-dimensional geometric problems that have algorithms with 1−1/d appearing in the exponent of the running time, for example, in the form of 2n1−1/d or nk1−1/d. This means that these algorithms perform somewhat better in low dimensions, but the running time is almost the same for all large values d of the dimension. Our main result is showing that for some of these problems the dependence on 1−1/d is best possible under a standard complexity assumption. We show that, assuming the Exponential Time Hypothesis,

For a class C of graphs, #Sub(C) is the counting problem that, given a graph H from C and an arbitrary graph G, asks for the number of subgraphs of G isomorphic to H. It is known that if C has bounded vertex-cover number (equivalently, the size of the maximum matching in C is bounded), then #Sub(C) is polynomial-time solvable. We complement this result with a corresponding lower bound: if C is any recursively enumerable class of graphs with unbounded vertexcover number, then #Sub(C) is #W[1]-hard parameterized by the size of H and hence not polynomial-time solvable and not even fixed-parameter tractable, unless FPT is equal to #W[1]. As a first step of the proof, we show that counting kmatchings in bipartite graphs is #W[1]-hard. Recently, Curticapean [ICALP 2013] proved the #W[1]-hardness of counting k-matchings in general graphs; our result strengthens this statement to bipartite graphs with a considerably simpler proof and even shows that, assuming the Exponential Time Hypothesis (ETH), there is no f(k)*n^o(k/log(k)) time algorithm for counting k-matchings in bipartite graphs for any computable function f. As a consequence, we obtain an independent and somewhat simpler proof of the classical result of Flum and Grohe [SICOMP 2004] stating that counting paths of length k is #W[1]-hard, as well as a similar almost-tight ETH-based lower bound on the exponent.

We study the minimum interval deletion problem, which asks for the removal of a set of at most k vertices to make a graph on n vertices into an interval graph. We present a parameterized algorithm of runtime 10k · nO(1) for this problem, thereby showing its fixed-parameter tractability.

Given a vertex-weighted directed graph G = (V, E) and a set T = {t1, t2, … tk} of k terminals, the objective of the Strongly Connected Steiner Subgraph (SCSS) problem is to find a vertex set H ⊆ V of minimum weight such that G[H] contains a ti → tj path for each i = j. The problem is NP-hard, but Feldman and Ruhl (FOCS '99; SICOMP '06) gave a novel nO(k) algorithm for the SCSS problem, where n is the number of vertices in the graph and k is the number of terminals. We explore how much easier the problem becomes on planar directed graphs. Our main algorithmic result is a algorithm for planar SCSS, which is an improvement of a factor of in the exponent over the algorithm of Feldman and Ruhl. Our main hardness result is a matching lower bound for our algorithm: we show that planar SCSS does not have an algorithm for any computable function f, unless the Exponential Time Hypothesis (ETH) fails. The algorithm eventually relies on the excluded grid theorem for planar graphs, but we stress that it is not simply a straightforward application of treewidth-based techniques: we need several layers of abstraction to arrive to a problem formulation where the speedup due to planarity can be exploited. To obtain the lower bound matching the algorithm, we need a delicate construction of gadgets arranged in a grid-like fashion to tightly control the number of terminals in the created instance. The following additional results put our upper and lower bounds in context: Our algorithm for planar directed graphs can be generalized to graphs excluding a fixed minor. In general graphs, we cannot hope for such a dramatic improvement over the nO(k) algorithm of Feldman and Ruhl: assuming ETH, SCSS in general graphs does not have an f(k) · no(k/logk) algorithm for any computable function f. Feldman and Ruhl generalized their nO(k) algorithm to the more general Directed Steiner Forest (DSF) problem; here the task is to find a subgraph of minimum weight such that for every source si there is a path to the corresponding terminal ti. We show that that, assuming ETH, there is no f(k) · no(k) time algorithm for DSF on acyclic planar graphs.

Given two permutations σ and π, the Permutation Pattern problem asks if σ is a subpattern of π. We show that the problem can be solved in time 2O(ℓ2 log ℓ). n, where ℓ = |σ| and n = |π|. In other words, the problem is fixed-parameter tractable parameterized by the size of the subpattern to be found.

Given a graph G and a subset S of vertices, the Subset TSP problem asks for a shortest closed walk in G visiting all vertices of S. The problem can be solved in time 2k · nO(1) using the classical dynamic programming algorithms of Bellman and of Held and Karp, where k = |S| and n = |V (G)|. Our main result is showing that the problem can be solved in time if G is a planar graph with weights that are integers no greater than W. While similar speedups have been observed for various paramterized problems on planar graphs, our result cannot be simply obtained as a consequence of bounding the treewidth of G or invoking bidimensionality theory. Our algorithm consists of two steps: (1) find a locally optimal solution, and (2) use it to guide a dynamic program. The proof of correctness of the algorithm depends on a treewidth bound on a graph obtained by combining an optimal solution with a locally optimal solution.

Graph modification problems are typically asked as follows: is there a set of k operations that transforms a given graph to have a certain property. The most commonly considered operations include vertex deletion, edge deletion, and edge addition; for the same property, one can define significantly different versions by allowing different operations. We study a very general graph modification problem which allows all three types of operations: given a graph G and integers k_1, k_2, and k_3, the CHORDAL EDITING problem asks if G can be transformed into a chordal graph by at most k_1 vertex deletions, k_2 edge deletions, and k_3 edge additions. Clearly, this problem generalizes both CHORDAL VERTEX/EDGE DELETION and CHORDAL COMPLETION (also known as MINIMUM FILL-IN). Our main result is an algorithm for CHORDAL EDITING in time 2^O(k.log(k))·n^O(1), where k:=k_1+k_2+k_3; therefore, the problem is fixed-parameter tractable parameterized by the total number of allowed operations. Our algorithm is both more efficient and conceptually simpler than the previously known algorithm for the special case CHORDAL DELETION.

Given two graphs H and G, the Subgraph Isomorphism problem asks if H is isomorphic to a subgraph of G. While NP-hard in general, algorithms exist for various parameterized versions of the problem. However, the literature contains very little guidance on which combinations of parameters can or cannot be exploited algorithmically. Our goal is to systematically investigate the possible parameterized algorithms that can exist for Subgraph Isomorphism. We develop a framework involving 10 relevant parameters for each of H and G (such as treewidth, pathwidth, genus, maximum degree, number of vertices, number of components, etc.), and ask if an algorithm with running time f1_(p_1,p_2,...,p_l).n^f_2(p_(l+1),...,p_k) exists, where each of p_1,...,p_k is one of the 10 parameters depending only on H or G. We show that all the questions arising in this framework are answered by a set of 11 maximal positive results (algorithms) and a set of 17 maximal negative results (hardness proofs); some of these results already appear in the literature, while others are new in this paper. On the algorithmic side, our study reveals for example that an unexpected combination of bounded degree, genus, and feedback vertex set number of G gives rise to a highly nontrivial algorithm for Subgraph Isomorphism. On the hardness side, we present W[1]-hardness proofs under extremely restricted conditions, such as when H is a bounded-degree tree of constant pathwidth and G is a planar graph of bounded pathwidth.

We study a family of problems where the goal is to make a graph Eulerian, i.e., connected and with all the vertices having even degrees, by a minimum number of deletions. We completely classify the parameterized complexity of various versions: undirected or directed graphs, vertex or edge deletions, with or without the requirement of connectivity, etc. The collection of results shows an interesting contrast: while the node-deletion variants remain intractable, i.e., W[1]-hard for all the studied cases, edge-deletion problems are either fixed-parameter tractable or polynomial-time solvable. Of particular interest is a randomized FPT algorithm for making an undirected graph Eulerian by deleting the minimum number of edges, based on a novel application of the color coding technique. For versions that remain NP-complete but fixed-parameter tractable we consider also possibilities of polynomial kernelization; unfortunately, we prove that this is not possible unless NP⊆coNP/poly.

In the constraint satisfaction problem (CSP) corresponding to a constraint language (i.e., a set of relations) $\Gamma$, the goal is to find an assignment of values to variables so that a given set of constraints specified by relations from $\Gamma$ is satisfied. The complexity of this problem has received a substantial amount of attention in the past decade. In this paper, we study the fixed-parameter tractability of CSPs parameterized by the size of the solution in the following sense: one of the possible values, say 0, is “free,” and the number of variables allowed to take other, “expensive,” values is restricted. A size constraint requires that exactly $k$ variables take nonzero values. We also study a more refined version of this restriction: a global cardinality constraint prescribes how many variables have to be assigned each particular value. We study the parameterized complexity of these types of CSPs where the parameter is the required number $k$ of nonzero variables. As special cases, we can obtain natural and well-studied parameterized problems such as Independent set, Vertex Cover, $d$-Hitting Set, Biclique, etc. In the case of constraint languages closed under substitution of constants, we give a complete characterization of the fixed-parameter tractable cases of CSPs with size constraints, and we show that all the remaining problems are W[1]-hard. For CSPs with cardinality constraints, we obtain a similar classification, but for some of the problems we are only able to show that they are Biclique-hard. The exact parameterized complexity of the Biclique problem is a notorious open problem, although it is believed to be W[1]-hard.

Given an undirected graph $G$, a collection $\{(s_1,t_1), \dots, (s_{k},t_{k})\}$ of pairs of vertices, and an integer ${{p}}$, the Edge Multicut problem asks if there is a set $S$ of at most ${{p}}$ edges such that the removal of $S$ disconnects every $s_i$ from the corresponding $t_i$. Vertex Multicut is the analogous problem where $S$ is a set of at most ${{p}}$ vertices. Our main result is that both problems can be solved in time $2^{O({{p}}^3)}\cdot n^{O(1)}$, i.e., fixed-parameter tractable parameterized by the size ${{p}}$ of the cutset in the solution. By contrast, it is unlikely that an algorithm with running time of the form $f({{p}})\cdot n^{O(1)}$ exists for the directed version of the problem, as we show it to be W[1]-hard parameterized by the size of the cutset.

We consider the problem of how much edge connectivity is necessary to force a graph $G$ to contain a fixed graph $H$ as an immersion. We show that if the maximum degree in $H$ is $\Delta$, then all the examples of $\Delta$-edge connected graphs which do not contain $H$ as a weak immersion must have a treelike decomposition called a tree-cut decomposition of bounded width. If we consider strong immersions, then it is easy to see that there are arbitrarily highly edge connected graphs which do not contain a fixed clique $K_t$ as a strong immersion. We give a structure theorem which roughly characterizes those highly edge connected graphs which do not contain $K_t$ as a strong immersion.

We show conditional lower bounds for well-studied #P-hard problems: The number of satisfying assignments of a 2-CNF formula with n variables cannot be computed in time exp( o ( n )), and the same is true for computing the number of all independent sets in an n -vertex graph. The permanent of an n × n matrix with entries 0 and 1 cannot be computed in time exp( o ( n )). The Tutte polynomial of an n -vertex multigraph cannot be computed in time exp( o ( n )) at most evaluation points ( x , y ) in the case of multigraphs, and it cannot be computed in time exp( o ( n /poly log n )) in the case of simple graphs. Our lower bounds are relative to (variants of) the Exponential Time Hypothesis (ETH), which says that the satisfiability of n -variable 3-CNF formulas cannot be decided in time exp( o ( n )). We relax this hypothesis by introducing its counting version #ETH; namely, that the satisfying assignments cannot be counted in time exp( o ( n )). In order to use #ETH for our lower bounds, we transfer the sparsification lemma for d -CNF formulas to the counting setting.

We study an extensive class of movement minimization problems that arise from many practical scenarios but so far have little theoretical study. In general, these problems involve planning the coordinated motion of a collection of agents (representing robots, people, map labels, network messages, etc.) to achieve a global property in the network while minimizing the maximum or average movement (expended energy). The only previous theoretical results about this class of problems are about approximation and are mainly negative: many movement problems of interest have polynomial inapproximability. Given that the number of mobile agents is typically much smaller than the complexity of the environment, we turn to fixed-parameter tractability. We characterize the boundary between tractable and intractable movement problems in a very general setup: it turns out the complexity of the problem fundamentally depends on the treewidth of the minimal configurations. Thus, the complexity of a particular problem can be determined by answering a purely combinatorial question. Using our general tools, we determine the complexity of several concrete problems and fortunately show that many movement problems of interest can be solved efficiently.

Many important combinatorial problems can be modeled as constraint satisfaction problems. Hence, identifying polynomial-time solvable classes of constraint satisfaction problems has received a lot of attention. In this article, we are interested in structural properties that can make the problem tractable. So far, the largest structural class that is known to be polynomial-time solvable is the class of bounded hypertree width instances introduced by Gottlob et al. [2002]. Here we identify a new class of polynomial-time solvable instances: those having bounded fractional edge cover number. Combining hypertree width and fractional edge cover number, we then introduce the notion of fractional hypertree width. We prove that constraint satisfaction problems with bounded fractional hypertree width can be solved in polynomial time (provided that the tree decomposition is given in the input). Together with a recent approximation algorithm for finding such decompositions [Marx 2010], it follows that bounded fractional hypertree width is now the most generally known structural property that guarantees polynomial-time solvability.

Given a graph G and k pairs of vertices (s1, t1), ..., (sk, tk), the k-Vertex-Disjoint Paths problem asks for pair wise vertex-disjoint paths P1, ..., Pk such that Pi goes from si to ti. Schrijver [SICOMP'94] proved that the k-Vertex-Disjoint Paths problem on planar directed graphs can be solved in timenO(k). We give an algorithm with running time 22O(k2)* nO(1)for the problem, that is, we show the fixed-parameter tractability of the problem.

The Graph Minors project of Robertson and Seymour uncovered a very deep structural theory of graphs. This theory had several important consequences, among others, the proof of Wagner's Conjecture. While the whole theory, presented in a series of 23 very dense papers, is notoriously difficult to understand, it has to be emphasized that these papers introduced several elementary concepts and tools that had strong impact on algorithms, complexity, and combinatorics. Moreover, even some of the very deep results can be stated in a compact and useful way, and it is possible to build upon these results without a complete understanding of the underlying machinery. In the first part of the lecture, I will introduce the concept of treewidth, which can be thought of as an elementary entry point to graph minors theory. I will overview its graph-theoretic and algorithmic properties that make it especially important in the design of parameterized algorithms and approximation schemes on planar graphs. Furthermore, I will briefly explain some of the connections of treewidth to complexity and automata theory. In the next part of the lecture, we will turn our attention to the more advanced topic of graphs excluding a fixed minor: the structure of such graphs, finding minors, and the well-quasi-ordering of the minor relation. The primary goal here is to provide clear and useful statements of these results and to show how they generalize the concepts of treewidth and planar graphs. Finally, I will briefly overview some more recent results involving different kinds of excluded structures, such as graphs excluding odd minors and topological minors.

An important question in the study of constraint satisfaction problems (CSP) is understanding how the graph or hypergraph describing the incidence structure of the constraints influences the complexity of the problem. For binary CSP instances (that is, where each constraint involves only two variables), the situation is well understood: the complexity of the problem essentially depends on the treewidth of the graph of the constraints [Grohe 2007; Marx 2010b]. However, this is not the correct answer if constraints with unbounded number of variables are allowed, and in particular, for CSP instances arising from query evaluation problems in database theory. Formally, if H is a class of hypergraphs, then let CSP( H ) be CSP restricted to instances whose hypergraph is in H . Our goal is to characterize those classes of hypergraphs for which CSP( H ) is polynomial-time solvable or fixed-parameter tractable, parameterized by the number of variables. Note that in the applications related to database query evaluation, we usually assume that the number of variables is much smaller than the size of the instance, thus parameterization by the number of variables is a meaningful question. The most general known property of H that makes CSP( H ) polynomial-time solvable is bounded fractional hypertree width. Here we introduce a new hypergraph measure called submodular width , and show that bounded submodular width of H (which is a strictly more general property than bounded fractional hypertree width) implies that CSP( H ) is fixed-parameter tractable. In a matching hardness result, we show that if H has unbounded submodular width, then CSP( H ) is not fixed-parameter tractable (and hence not polynomial-time solvable), unless the Exponential Time Hypothesis (ETH) fails. The algorithmic result uses tree decompositions in a novel way: instead of using a single decomposition depending on the hypergraph, the instance is split into a set of instances (all on the same set of variables as the original instance), and then the new instances are solved by choosing a different tree decomposition for each of them. The reason why this strategy works is that the splitting can be done in such a way that the new instances are “uniform” with respect to the number extensions of partial solutions, and therefore the number of partial solutions can be described by a submodular function. For the hardness result, we prove via a series of combinatorial results that if a hypergraph H has large submodular width, then a 3SAT instance can be efficiently simulated by a CSP instance whose hypergraph is H . To prove these combinatorial results, we need to develop a theory of (multicommodity) flows on hypergraphs and vertex separators in the case when the function b ( S ) defining the cost of separator S is submodular, which can be of independent interest.

Relational joins are at the core of relational algebra, which in turn is the core of the standard database query language SQL. As their evaluation is expensive and very often dominated by the output size, it is an important task for database query optimizers to compute estimates on the size of joins and to find good execution plans for sequences of joins. We study these problems from a theoretical perspective, both in the worst-case model and in an average-case model where the database is chosen according to a known probability distribution. In the former case, our first key observation is that the worst-case size of a query is characterized by the fractional edge cover number of its underlying hypergraph, a combinatorial parameter previously known to provide an upper bound. We complete the picture by proving a matching lower bound and by showing that there exist queries for which the join-project plan suggested by the fractional edge cover approach may be substantially better than any join plan that does not use intermediate projections. On the other hand, we show that in the average-case model, every join-project plan can be turned into a plan containing no projections in such a way that the expected time to evaluate the plan increases only by a constant factor independent of the size of the database. Not surprisingly, the key combinatorial parameter in this context is the maximum density of the underlying hypergraph. We show how to make effective use of this parameter to eliminate the projections.

Given a directed graph $G$, a set of $k$ terminals, and an integer $p$, the Directed Vertex Multiway Cut problem asks whether there is a set $S$ of at most $p$ (nonterminal) vertices whose removal disconnects each terminal from all other terminals. Directed Edge Multiway Cut is the analogous problem where $S$ is a set of at most $p$ edges. These two problems are indeed known to be equivalent. A natural generalization of the multiway cut is the Multicut problem, in which we want to disconnect only a set of $k$ given pairs instead of all pairs. Marx [Theoret. Comput. Sci., 351 (2006), pp. 394--406] showed that in undirected graphs Vertex/Edge Multiway cut is fixed-parameter tractable (FPT) parameterized by $p$. Marx and Razgon [Proceedings of the 43rd ACM Symposium on Theory of Computing, 2011, pp. 469--478] showed that undirected Multicut is FPT and Directed Multicut is W[1]-hard parameterized by $p$. We complete the picture here by our main result, which is that both Directed Vertex Multiway Cut and Directed Edge Multiway Cut can be solved in time $2^{2^{O(p)}}n^{O(1)}$, i.e., FPT parameterized by size $p$ of the cutset of the solution. This answers an open question raised by the aforementioned papers. It follows from our result that Directed Edge/Vertex Multicut is FPT for the case of $k=2$ terminal pairs, which answers another open problem raised by Marx and Razgon.

We present a method for reducing the treewidth of a graph while preserving all of its minimal s - t separators up to a certain fixed size k . This technique allows us to solve s - t Cut and Multicut problems with various additional restrictions (e.g., the vertices being removed from the graph form an independent set or induce a connected graph) in linear time for every fixed number k of removed vertices. Our results have applications for problems that are not directly defined by separators, but the known solution methods depend on some variant of separation. For example, we can solve similarly restricted generalizations of Bipartization (delete at most k vertices from G to make it bipartite) in almost linear time for every fixed number k of removed vertices. These results answer a number of open questions in the area of parameterized complexity. Furthermore, our technique turns out to be relevant for ( H , C , K )- and ( H , C ,≤K)-coloring problems as well, which are cardinality constrained variants of the classical H -coloring problem. We make progress in the classification of the parameterized complexity of these problems by identifying new cases that can be solved in almost linear time for every fixed cardinality bound.

The field of exact exponential time algorithms for NP-hard problems has thrived over the last decade. While exhaustive search remains asymptotically the fastest known algorithm for some basic problems, difficult and non-trivial exponential time algorithms have been found for a myriad of problems, including GRAPH COLORING, HAMILTONIAN PATH, DOMINATING SET and 3-CNF-SAT. In some instances, improving these algorithms further seems to be out of reach. The CNF-SAT problem is the canonical example of a problem for which the trivial exhaustive search algorithm runs in time O(2n), where n is the number of variables in the input formula. While there exist non-trivial algorithms for CNF-SAT that run in time o(2n), no algorithm was able to improve the growth rate 2 to a smaller constant, and hence it is natural to conjecture that 2 is the optimal growth rate. The strong exponential time hypothesis (SETH) by Impagliazzo and Paturi [JCSS 2001] goes a little bit further and asserts that, for every ϵϵn. In this paper, we show that, for every ϵϵn) unless SETH fails. Here n is the number of elements or variables in the input. For these problems, we actually get an equivalence to SETH in a certain sense. We conjecture that SETH implies a similar statement for SET COVER, and prove that, under this assumption, the fastest known algorithms for STEINTER TREE, CONNECTED VERTEX COVER, SET PARTITIONING, and the pseudo-polynomial time algorithm for SUBSET SUM cannot be significantly improved. Finally, we justify our assumption about the hardness of SET COVER by showing that the parity of the number of set covers.

Given a directed graph G, a set of k terminals and an integer p, the Directed Vertex Multiway Cut problem asks if there is a set S of at most p (nonterminal) vertices whose removal disconnects each terminal from all other terminals. Directed Edge Multiway Cut is the analogous problem where S is a set of at most p edges. These two problems indeed are known to be equivalent. A natural generalization of the multiway cut is the multicut problem, in which we want to disconnect only a set of k given pairs instead of all pairs. Marx (Theor. Comp. Sci. 2006) showed that in undirected graphs multiway cut is fixed-parameter tractable (FPT) parameterized by p. Marx and Razgon (STOC 2011) showed that undirected multicut is FPT and directed multicut is W[1]-hard parameterized by p. We complete the picture here by our main result which is that both Directed Vertex Multiway Cut and Directed Edge Multiway Cut can be solved in time 22O(p) nO(1), i.e., FPT parameterized by size p of the cutset of the solution. This answers an open question raised by Marx (Theor. Comp. Sci. 2006) and Marx and Razgon (STOC 2011). It follows from our result that Directed Multicut is FPT for the case of k = 2 terminal pairs, which answers another open problem raised in Marx and Razgon (STOC 2011).

Kernelization algorithms are polynomial-time reductions from a problem to itself that guarantee their output to have a size not exceeding some bound. For example, d-Set Matching for integers d ≥ 3 is the problem of finding a matching of size at least k in a given d-uniform hypergraph and has kernels with O(kd) edges. Recently, Bodlaender et al. [ICALP 2008], Fortnow and Santhanam [STOC 2008], Dell and Van Melkebeek [STOC 2010] developed a framework for proving lower bounds on the kernel size for certain problems, under the complexity-theoretic hypothesis that coNP is not contained in NP/poly. Under the same hypothesis, we show lower bounds for the kernelization of d-Set Matching and other packing problems. Our bounds are tight for d-Set Matching: It does not have kernels with O(kd−∊) edges for any ∊ > 0 unless the hypothesis fails. By reduction, this transfers to a bound of O(kd − 1 − ∊) for the problem of finding k vertex-disjoint cliques of size d in standard graphs. It is natural to ask for tight bounds on the kernel sizes of such graph packing problems. We make first progress in that direction by showing non-trivial kernels with O(k2.5) edges for the problem of finding k vertex-disjoint paths of three edges each. This does not quite match the best lower bound of O(k2−∊) that we can prove. Most of our lower bound proofs follow a general scheme that we discover: To exclude kernels of size O(kd−∊) for a problem in d-uniform hypergraphs, one should reduce from a carefully chosen d-partite problem that is still NP-hard. As an illustration, we apply this scheme to the vertex cover problem, which allows us to replace the number-theoretical construction by Dell and Van Melkebeek [STOC 2010] with shorter elementary arguments.

We generalize the structure theorem of Robertson and Seymour for graphs excluding a fixed graph H as a minor to graphs excluding H as a topological subgraph. We prove that for a fixed H, every graph excluding H as a topological subgraph has a tree decomposition where each part is either "almost embeddable" to a fixed surface or has bounded degree with the exception of a bounded number of vertices. Furthermore, such a decomposition is computable by an algorithm that is fixed-parameter tractable with parameter |H|.

The constraint satisfaction problem (CSP) is a general problem central to computer science and artificial intelligence. Although the CSP is NP-hard in general, considerable effort has been spent on identifying tractable subclasses. The main two approaches consider structural properties (restrictions on the hypergraph of constraint scopes) and relational properties (restrictions on the language of constraint relations). Recently, some authors have considered hybrid properties that restrict the constraint hypergraph and the relations simultaneously. Our key contribution is the novel concept of a CSP pattern and classes of problems defined by forbidden patterns (which can be viewed as forbidding generic sub-problems). We describe the theoretical framework which can be used to reason about classes of problems defined by forbidden patterns. We show that this framework generalises certain known hybrid tractable classes. Although we are not close to obtaining a complete characterisation concerning the tractability of general forbidden patterns, we prove a dichotomy in a special case: classes of problems that arise when we can only forbid binary negative patterns (generic sub-problems in which only disallowed tuples are specified). In this case we show that all (finite sets of) forbidden patterns define either polynomial-time solvable or NP-complete classes of instances.

The homomorphism problem for relational structures is an abstract way of formulating constraint satisfaction problems (CSP) and various problems in database theory. The decision version of the homomorphism problem received a lot of attention in literature; in particular, the way the graph-theoretical structure of the variables and constraints influences the complexity of the problem is intensively studied. Here we study the problem of enumerating all the solutions with polynomial delay from a similar point of view. It turns out that the enumeration problem behaves very differently from the decision version. We give evidence that it is unlikely that a characterization result similar to the decision version can be obtained. Nevertheless, we show nontrivial cases where enumeration can be done with polynomial delay.

We study the complexity of local search for the Boolean constraint satisfaction problem (CSP), in the following form: given a CSP instance, that is, a collection of constraints, and a solution to it, the question is whether there is a better (lighter, i.e., having strictly less Hamming weight) solution within a given distance from the initial solution. We classify the complexity, both classical and parameterized, of such problems by a Schaefer-style dichotomy result, that is, with a restricted set of allowed types of constraints. Our results show that there is a considerable amount of such problems that are NP-hard, but fixed-parameter tractable when parameterized by the distance.

In this paper, we reduce Prize-Collecting Steiner TSP (PCTSP), Prize-Collecting Stroll (PCS), Prize-Collecting Steiner Tree (PCST), Prize-Collecting Steiner Forest (PCSF), and more generally Submodular Prize-Collecting Steiner Forest (SPCSF), on planar graphs (and also on bounded-genus graphs) to the corresponding problem on graphs of bounded treewidth. More precisely, for each of the mentioned problems, an α-approximation algorithm for the problem on graphs of bounded treewidth implies an (α + ε)-approximation algorithm for the problem on planar graphs (and also bounded-genus graphs), for any constant ε > 0. PCS, PCTSP, and PCST can be solved exactly on graphs of bounded treewidth and hence we obtain a PTAS for these problems on planar graphs and bounded-genus graphs. In contrast, we show that PCSF is APX-hard to approximate on series-parallel graphs, which are planar graphs of treewidth at most 2. Apart from ruling out a PTAS for PCSF on planar graphs and bounded treewidth graphs, this result is also interesting since it gives the first provable hardness separation between the approximability of a problem and its prize-collecting version. We also show that PCSF is APX-hard on Euclidean instances.

A central problem in parameterized algorithms is to obtain algorithms with running time f(k) · nO(1) such that f is as slow growing function of the parameter k as possible. In particular, the first natural goal is to make f(k) single-exponential, that is, ck for some constant c. This has led to the development of parameterized algorithms for various problems where f(k) appearing in their running time is of form 2O(k). However there are still plenty of problems where the “slightly superexponential” f(k) appearing in the best known running time has remained non single-exponential even after a lot of attempts to bring it down. A natural question to ask is whether the f(k) appearing in the running time of the best-known algorithms is optimal for any of these problems. In this paper, we examine parameterized problems where f(k) is kO(k) = 2O(k log k) in the best known running time and for a number of such problems, we show that the dependence on k in the running time cannot be improved to single exponential. More precisely we prove following tight lower bounds, for three natural problems, arising from three different domains: The pattern matching problem Closest String is known to be solvable in time 2O(d log d) · nO(1) and 2O(d log |σ|) · nO(1). We show that there is no 2o(d log d).· nO(1) and 2o(d log |σ|) · nO(1) time algorithm, unless Exponential Time Hypothesis (ETH) fails. The graph embedding problem Distortion, that is, deciding whether a graph G has a metric embedding into the integers with distortion at most d can be done in time 2O(d log d) · nO(1). We show that there is no 2o(d log d) · nO(1) time algorithm, unless ETH fails. The Disjoint Paths problem can be solved in time in time 2O(w log w) · nO(1) on graphs of treewidth at most w. We show that there is no 2o(w log w) · nO(1) time algorithm, unless ETH fails. To obtain our result we first prove the lower bound for variants of basic problems: finding cliques, independent sets, and hitting sets. These artificially constrained variants form a good starting point for proving lower bounds on natural problems without any technical restrictions and could be of independent interest. We believe that many further results of this form can be obtained by using the framework of the current paper.

We obtain a number of lower bounds on the running time of algorithms solving problems on graphs of bounded treewidth. We prove the results under the Strong Exponential Time Hypothesis of Impagliazzo and Paturi. In particular, assuming that SAT cannot be solved in (2 − ε) nmO(1) time, we show that for any ε > 0; Independent Set cannot be solved in time (2 − ε)tw(G)|V(G)|O(1), Dominating Set cannot be solved in time (3 − ε)tw(G)|V(G)|O(1), Max Cut cannot be solved in time (2 − ε)tw(G)|V(G)|O(1), Odd Cycle Tranversal cannot be solved in time (3 − ε)tw(G) |V(G)|O(1), For any q ≥ 3, q-Coloring cannot be solved in time (q − ε)tw(G)|V(G)|O(1), Partition Into Triangles cannot be solved in time (2 − ε)tw(G)|V(G)|O(1). Our lower bounds match the running times for the best known algorithms for the problems, up to the ε in the base.

We prove that for every fixed undirected graph H, there is an O(|V(G)|3) time algorithm that, given a graph G, tests if G contains H as a topological subgraph (that is, a subdivision of H is subgraph of G). This shows that topological subgraph testing is fixed-parameter tractable, resolving a longstanding open question of Downey and Fellows from 1992. As a corollary, for every H we obtain an O(|V(G)|3) time algorithm that tests if there is an immersion of H into a given graph G. This answers another open question raised by Downey and Fellows in 1992.

Given an undirected graph $G$, a collection {(s1,t1), ..., (sl,tl)} of pairs of vertices, and an integer p, the Edge Multicut problem ask if there is a set S of at most p edges such that the removal of S disconnects every si from the corresponding ti. Vertex Multicut is the analogous problem where S is a set of at most p vertices. Our main result is that both problems can be solved in time 2O(p3) ⋅ nO(1), i.e., fixed-parameter tractable parameterized by the size p of the cutset in the solution. By contrast, it is unlikely that an algorithm with running time of the form f(p) ⋅ nO(1) exists for the directed version of the problem, as we show it to be W[1]-hard parameterized by the size of the cutset.

We give the first polynomial-time approximation scheme (PTAS) for the Steiner forest problem on planar graphs and, more generally, on graphs of bounded genus. As a first step, we show how to build a Steiner forest spanner for such graphs. The crux of the process is a clustering procedure called prize-collecting clustering that breaks down the input instance into separate subinstances which are easier to handle; moreover, the terminals in different subinstances are far from each other. Each subinstance has a relatively inexpensive Steiner tree connecting all its terminals, and the subinstances can be solved (almost) separately. Another building block is a PTAS for Steiner forest on graphs of bounded treewidth. Surprisingly, Steiner forest is NP-hard even on graphs of treewidth 3. Therefore, our PTAS for bounded-treewidth graphs needs a nontrivial combination of approximation arguments and dynamic programming on the tree decomposition. We further show that Steiner forest can be solved in polynomial time for series-parallel graphs (graphs of treewidth at most two) by a novel combination of dynamic programming and minimum cut computations, completing our thorough complexity study of Steiner forest in the range of bounded-treewidth graphs, planar graphs, and bounded-genus graphs.

In many combinatorial problems one may need to model the diversity or similarity of assignments in a solution. For example, one may wish to maximise or minimise the number of distinct values in a solution. To formulate problems of this type, we can use soft variants of the well known AllDifferent and AllEqual constraints. We present a taxonomy of six soft global constraints, generated by combining the two latter ones and the two standard cost functions, which are either maximised or minimised. We characterise the complexity of achieving arc and bounds consistency on these constraints, resolving those cases for which NP-hardness was neither proven nor disproven. In particular, we explore in depth the constraint ensuring that at least k pairs of variables have a common value. We show that achieving arc consistency is NP-hard, however achieving bounds consistency can be done in polynomial time through dynamic programming. Moreover, we show that the maximum number of pairs of equal variables can be approximated by a factor 1/2 with a linear time greedy algorithm. Finally, we provide a fixed parameter tractable algorithm with respect to the number of values appearing in more than two distinct domains. Interestingly, this taxonomy shows that enforcing equality is harder than enforcing difference.

We consider the problem of partitioning the vertices of an [Formula: see text]-vertex graph with maximum degree [Formula: see text] into [Formula: see text] classes [Formula: see text] of size at most [Formula: see text] in a way that minimizes the number of pairs [Formula: see text] for which there is an edge between [Formula: see text] and [Formula: see text]. We show that there is always such a partition with [Formula: see text] adjacent pairs, and this bound is tight. This problem is related to questions about the depth of certain graph embeddings, which have been used in the study of the complexity of subgraph and constraint satisfaction problems. (A corrected version of this paper has been appended to the originally posted pdf.)

We study the parameterized complexity of the k -center problem on a given n -point set P in ℝ d , with the dimension d as the parameter. We show that the rectilinear 3-center problem is fixed-parameter tractable, by giving an algorithm that runs in O ( n log n ) time for any fixed dimension d . On the other hand, we show that this is unlikely to be the case with both the Euclidean and rectilinear k -center problems for any k ≥ 2 and k ≥ 4 respectively. In particular, we prove that deciding whether P can be covered by the union of 2 balls of given radius or by the union of 4 cubes of given side length is W[1]-hard with respect to d , and thus not fixed-parameter tractable unless FPT=W[1]. For the Euclidean case, we also show that even an n o ( d ) -time algorithm does not exist, unless there is a 2 o ( n ) -time algorithm for n -variable 3SAT, that is, the Exponential Time Hypothesis fails.

We prove that weighted monotone/antimonotone circuit satisfiability has no fixed-parameter tractable approximation algorithm with any approximation ratio function ρ, unless FPT ≠ W[1]. In particular, not having such an fpt-approximation algorithm implies that these problems have no polynomial-time approximation algorithms with ratio ρ(OPT) for any nontrivial function ρ.

We present a method for reducing the treewidth of a graph while preserving all the minimal $s-t$ separators. This technique turns out to be very useful for establishing the fixed-parameter tractability of constrained separation and bipartization problems. To demonstrate the power of this technique, we prove the fixed-parameter tractability of a number of well-known separation and bipartization problems with various additional restrictions (e.g., the vertices being removed from the graph form an independent set). These results answer a number of open questions in the area of parameterized complexity.

We give the first polynomial-time approximation scheme (PTAS) for the Steiner forest problem on planar graphs and, more generally, on graphs of bounded genus. As a first step, we show how to build a Steiner forest spanner for such graphs. The crux of the process is a clustering procedure called prize-collecting clustering that breaks down the input instance into separate subinstances which are easier to handle; moreover, the terminals in different subinstances are far from each other. Each subinstance has a relatively inexpensive Steiner tree connecting all its terminals, and the subinstances can be solved (almost) separately. Another building block is a PTAS for Steiner forest on graphs of bounded treewidth. Surprisingly, Steiner forest is NP-hard even on graphs of treewidth 3. Therefore, our PTAS for bounded treewidth graphs needs a nontrivial combination of approximation arguments and dynamic programming on the tree decomposition. We further show that Steiner forest can be solved in polynomial time for series-parallel graphs (graphs of treewidth at most two) by a novel combination of dynamic programming and minimum cut computations, completing our thorough complexity study of Steiner forest in the range of bounded treewidth graphs, planar graphs, and bounded genus graphs.

An important question in the study of constraint satisfaction problems (CSP) is understanding how the graph or hypergraph describing the incidence structure of the constraints influences the complexity of the problem. For binary CSP instances (i.e., where each constraint involves only two variables), the situation is well understood: the complexity of the problem essentially depends on the treewidth of the graph of the constraints. However, this is not the correct answer if constraints with unbounded number of variables are allowed, and in particular, for CSP instances arising from query evaluation problems in database theory. Formally, if H is a class of hypergraphs, then let CSP(H) be CSP restricted to instances whose hypergraph is in H. Our goal is to characterize those classes of hypergraphs for which CSP(H) is polynomial-time solvable or fixed-parameter tractable, parameterized by the number of variables. In the applications related to database query evaluation, we usually assume that the number of variables is much smaller than the size of the instance, thus parameterization by the number of variables is a meaningful question. The most general known property of H that makes CSP(H) polynomial-time solvable is bounded fractional hypertree width. Here we introduce a new hypergraph measure called submodular width, and show that bounded submodular width of H (which is a strictly more general property than bounded fractional hypertree width) implies that CSP(H) is fixed-parameter tractable. In a matching hardness result, we show that if H has unbounded submodular width, then CSP(H) is not fixed-parameter tractable (and hence not polynomial-time solvable), unless the Exponential Time Hypothesis (ETH) fails. The algorithmic result uses tree decompositions in a novel way: instead of using a single decomposition depending on the hypergraph, the instance is split into a set of instances (all on the same set of variables as the original instance), and then the new instances are solved by choosing a different tree decomposition for each of them. The reason why this strategy works is that the splitting can be done in such a way that the new instances are "uniform" with respect to the number extensions of partial solutions, and therefore the number of partial solutions can be described by a submodular function. For the hardness result, we prove via a series of combinatorial results that if a hypergraph H has large submodular width, then a 3SAT instance can be efficiently simulated by a CSP instance whose hypergraph is H. To prove these combinatorial results, we need to develop a theory of (multicommodity) flows on hypergraphs and vertex separators in the case when the function b(S) defining the cost of separator S is submodular.

Fractional hypertree width is a hypergraph measure similar to tree width and hypertree width. Its algorithmic importance comes from the fact that, as shown in previous work, Constraint Satisfaction Problems (CSP) and various problems in database theory are polynomial-time solvable if the input contains a bounded-width fractional hypertree decomposition of the hypergraph of the constraints. In this article, we show that for every fixed w ≥ 1, there is a polynomial-time algorithm that, given a hypergraph H with fractional hypertree width at most w , computes a fractional hypertree decomposition of width O ( w 3 ) for H . This means that polynomial-time algorithms relying on bounded-width fractional hypertree decompositions no longer need to be given a decomposition explicitly in the input, since an appropriate decomposition can be computed in polynomial time. Therefore, if H is a class of hypergraphs with bounded fractional hypertree width, then a CSP restricted to instances whose structure is in H is polynomial-time solvable. This makes bounded fractional hypertree width the most general known hypergraph property that makes CSP, Boolean conjunctive queries, and conjunctive query containment polynomial-time solvable.

In a constraint satisfaction problem (CSP) the goal is to find an assignment of a given set of variables subject to specified constraints. A global cardinality constraint is an additional requirement that prescribes how many variables must be assigned a certain value. We study the complexity of the problem CCSP(Gamma), the constraint satisfaction problem with global cardinality constraints that allows only relations from the set Gamma. The main result of this paper characterizes sets Gamma that give rise to problems solvable in polynomial time, and states that the remaining such problems are NP-complete.

Fractional hypertree width is a hypergraph measure similar to tree width and hypertree width. Its algorithmic importance comes from the fact that, as shown in previous work [14], constraint satisfaction problems (CSP) and various problems in database theory are polynomial-time solvable if the input contains a bounded-width fractional hypertree decomposition of the hypergraph of the constraints. In this paper, we show that for every w ≥ 1, there is a polynomial-time algorithm that, given a hypergraph H with fractional hypertree width at most w, computes a fractional hypertree decomposition of width O(w3) for H. This means that polynomial-time algorithms relying on bounded-width fractional hypertree decompositions no longer need to be given a decomposition explicitly in the input, since an appropriate decomposition can be computed in polynomial time. Therefore, if ℋ is a class of hypergraphs with bounded fractional hypertree width, then CSP restricted to instances whose structure is in ℋ is polynomial-time solvable. This makes bounded fractional hypertree width the most general known hypergraph property that makes CSP, Boolean Conjuctive Queries, and Conjunctive Query Containment polynomial-time solvable.

The way the graph structure of the constraints influences the complexity of constraint satisfaction problems (CSP) is well understood for bounded-arity constraints. The situation is less clear if there is no bound on the arities. In this case the answer depends also on how the constraints are represented in the input. We study this question for the truth table representation of constraints. We introduce a new hypergraph measure {\em adaptive width} and show that CSP with truth tables is polynomial-time solvable if restricted to a class of hypergraphs with bounded adaptive width. Conversely, assuming a conjecture on the complexity of binary CSP, there is no other polynomial-time solvable case.

Relational joins are at the core of relational algebra, which in turn is the core of the standard database query language SQL. As their evaluation is expensive and very often dominated by the output size, it is an important task for database query optimisers to compute estimates on the size of joins and to find good execution plans for sequences of joins. We study these problems from a theoretical perspective, both in the worst-case model, and in an average-case model where the database is chosen according to a known probability distribution. In the former case, our first key observation is that the worst-case size of a query is characterised by the fractional edge cover number of its underlying hypergraph, a combinatorial parameter previously known to provide an upper bound. We complete the picture by proving a matching lower bound, and by showing that there exist queries for which the join-project plan suggested by the fractional edge cover approach may be substantially better than any join plan that does not use intermediate projections.

Approximation algorithms and parameterized complexity are usually considered to be two separate ways of dealing with hard algorithmic problems. In this paper, our aim is to investigate how these two fields can be combined to achieve better algorithms than what any of the two theories could offer. We discuss the different ways parameterized complexity can be extended to approximation algorithms, survey results of this type and propose directions for future research. 1.

We study two pattern matching problems that are motivated by applications in computational biology. In the Closest Substring problem k strings $s_1,\dots, s_k$ are given, and the task is to find a string s of length L such that each string $s_i$ has a consecutive substring of length L whose distance is at most d from s. We present two algorithms that aim to be efficient for small fixed values of d and k: for some functions f and g, the algorithms have running time $f(d)\cdot n^{O(\log d)}$ and $g(d,k)\cdot n^{O(\log\log k)}$, respectively. The second algorithm is based on connections with the extremal combinatorics of hypergraphs. The Closest Substring problem is also investigated from the parameterized complexity point of view. Answering an open question from [P. A. Evans, A. D. Smith, and H. T. Wareham, Theoret. Comput. Sci., 306 (2003), pp. 407–430, M. R. Fellows, J. Gramm, and R. Niedermeier, Combinatorica, 26 (2006), pp. 141–167, J. Gramm, J. Guo, and R. Niedermeier, Lecture Notes in Comput. Sci. 2751, Springer, Berlin, 2003, pp. 195–209, J. Gramm, R. Niedermeier, and P. Rossmanith, Algorithmica, 37 (2003), pp. 25–42], we show that the problem is W[1]-hard even if both d and k are parameters. It follows as a consequence of this hardness result that our algorithms are optimal in the sense that the exponent of n in the running time cannot be improved to $o(\log d)$ or to $o(\log \log k)$ (modulo some complexity-theoretic assumptions). Consensus Patterns is the variant of the problem where, instead of the requirement that each $s_i$ has a substring that is of distance at most d from s, we have to select the substrings in such a way that the average of these k distances is at most $\delta$. By giving an $f(\delta)\cdot n^9$ time algorithm, we show that the problem is fixed-parameter tractable. This answers an open question from [M. R. Fellows, J. Gramm, and R. Niedermeier, Combinatorica, 26 (2006), pp. 141–167].

It is well-known that constraint satisfaction problems (CSP) can be solved in time nO(k)if the treewidth of the primal graph of the instance is at most k and n is the size of the input. We show that no algorithm can be significantly better than this treewidth-based algorithm, even if we restrict the problem to some special class of primal graphs. Formally, let g be an arbitrary class of graphs and assume that there is an algorithm A solving binary CSP for instances whose primal graph is in g. We prove that if the running lime of A is f(G)nO(k/logk), where k is the treewidth of the primal graph G and f is an arbitrary function, then the Exponential Time Hypothesis fails. We prove the result also in the more general framework of the homomorphism problem for bounded-arity relational structures. For this problem, the treewidth of the core of the left-hand side structure plays the same role as the. treewidth of the primal graph above.

We show for several planar and geometric problems that the best known approximation schemes are essentially optimal with respect to the dependence on epsi. For example, we show that the 2O(1/epsi)ldrn time approximation schemes for planar maximum independent set and for TSP on a metric defined bv a planar graph are essentially optimal: if there is a delta>0 such that any of these problems admits a 2O((1/epsi)1-delta)nO(1)time PTAS, then the exponential tune hypothesis (ETH) fails. It is known that maximum independent set on unit disk graphs and the planar logic problems MPSAT. TMIN, TMAX admit nO(1/epsi)time approximation schemes. We show that they are optimal in the sense that if there is a delta>0 such that any of these problems admits a 2(1/epsi)O(1)nO((1/epsi)1-delta)time PTAS, then ETH fails.

In the closest substring problem k strings s/sub 1/, ..., s/sub k/ are given, and the task is to find a string s of length L such that each string s/sub i/, has a consecutive substring of length L whose distance is at most d from s. The problem is motivated by applications in computational biology. We present two algorithms that can be efficient for small fixed values of d and k: for some functions f and g, the algorithms have running time f(d) /spl middot/ n(O(log d)) and g(d,k) /spl middot/ n(O(log log k)), respectively. The second algorithm is based on connections with the extremal combinatorics of hypergraphs. The closest substring problem is also investigated from the parameterized complexity point of view. Answering an open question from (Evans et al., 2003; Fellows et al.; Gramm et al., 2003), we show that the problem is W[1] hard even if both d and k are parameters. It follows as a consequence of this hardness result that our algorithms are optimal in the sense that the exponent of n in the running time cannot be improved to o(log d) or to o(log log k) (modulo some complexity-theoretic assumptions). Another consequence is that the running time n/sup O(1//spl epsiv/4)/ of the approximation scheme for closest substring presented in (Li et al., 2002) cannot be improved to f(/spl epsiv/) /spl middot/ n/sup c/, i.e. the /spl epsiv/ has to appear in the exponent of n.

We prove a parameterized analog of Schaefer’s Dichotomy Theorem: we show that for every finite boolean constraint family ℱ, deciding whether a formula containing constraints from ℱ has a satisfying assignment of weight exactly k is either fixed-parameter tractable (FPT) or W[1]-complete. We give a simple characterization of those constraints that make the problem fixed-parameter tractable. The special cases when the formula is restricted to be bounded occurrence, bounded treewidth, or planar are also considered: it turns out that in these cases the problem is in FPT for every constraint family ℱ.

We prove a parameterized analog of Schaefer's Dichotomy Theorem: we show that for every finite Boolean constraint family F, deciding whether a formula containing constraints from F has a satisfying assignment of weight exactly k is either fixed-parameter tractable (TPT,) or W[l]-complete. We give a simple characterization of those constraints that make the problem fixed-parameter tractable. The special cases when the formula is restricted to be bounded occurrence, bounded treewidth or planar are also considered, it turns out that in these cases the problem is in FPT for every constraint family, F.

An efficient and general graph-theoretic model (the wavelength-graph (WG)) has been proposed which enables solution of the static routing and wavelength assignment (RWA) problems in multihop wavelength routing (WR) wavelength division multiplexing (WDM) networks simultaneously, and-as a unique feature-it optimises the optical layer jointly with the electrical one. Based on the proposed WG model the problem has been formulated as an integer linear program (ILP), solved by stochastic algorithms improved by simple heuristics. The topology of the physical layer, the type of each node (e.g., OADM, OXC or EXC), the number of available wavelengths per link and the capacity of each wavelength-channel are assumed given with the aggregated traffic demand of each node-pair. The output of the optimisation is the system of wavelength paths, light paths and semi-light paths. The objective of the optimisation is to reduce resource usage at upper (electrical) layers, subject to the constrained amount of capacity of each wavelength and a limited number of wavelengths. Although the problem to be solved is NP-hard, all methods proposed give a result in a very short time.