The NP-complete problems Colouring and k-Colouring (k ≥ 3) are well studied on H-free graphs, i.e., graphs that do not contain some fixed graph H as an induced subgraph. We research to what extent the known polynomial-time algorithms for H-free graphs can be generalized if we only know some of the edges of the input graph. We do this by considering the classical probe graph model introduced in the early nineties. For a graph H, a partitioned probe H-free graph (G,P,N) consists of a graph G = (V,E), together with a set P ⊆ V of probes and an independent set N = V ⧵ P of non-probes, such that G+F is H-free for some edge set F ⊆ binom(N,2). We show the following: - We fully classify Colouring on partitioned probe H-free graphs and show that the obtained complexity dichotomy differs from the known dichotomy of Colouring for H-free graphs. - We fully classify 3-Colouring on partitioned probe P_t-free graphs: we prove polynomial-time solvability for t ≤ 5 and NP-completeness for t ≥ 6. In contrast, 3-Colouring on P_t-free graphs is known to be polynomial-time solvable for t ≤ 7 and quasi-polynomial-time solvable for t ≥ 8. Our main result is our polynomial-time algorithm for 3-Colouring on partitioned P₅-free graphs. For this result, and also for all our other polynomial-time results, we do not need to know the edge set F; we only need to know its existence. Moreover, the class of probe P₅-free graphs includes not only paths of arbitrary length but even all bipartite graphs and is much richer than the class of P₅-free graphs. The latter is also evidenced by the fact that there exist graph problems, such as Matching Cut, that are known to be polynomial-time solvable for P₅-free graphs but NP-complete for partitioned probe P₅-free graphs. In particular, unlike the class of 3-colourable P₅-free graphs, the class of 3-colourable probe P₅-free graphs has unbounded mim-width. Hence, our polynomial-time result for 3-Colouring for probe P₅-free graphs suggests that there may be another, deeper overarching reason why 3-Colouring is polynomial-time solvable for P₅-free graphs.

We consider the Edge Multiway Cut problem on planar graphs. It is known that this can be solved in \(n^{{O}(\sqrt{t})}\) time (Klein and Marx) and not in \(n^{o(\sqrt{t})}\) time under the Exponential Time Hypothesis (Marx), where \( t \) is the number of terminals. A stronger parameter is the number \( k \) of faces of the planar graph that jointly cover all terminals. For the related Steiner Tree problem, an \(n^{{O}(\sqrt{k})}\) time algorithm was recently shown (Kisfaludi-Bak et al.). By a completely different approach, we prove in this article that Edge Multiway Cut can be solved in \(n^{{O}(\sqrt{k})}\) time as well. Our approach employs several major concepts on planar graphs, including homotopy and sphere-cut decomposition. We also mix a global treewidth dynamic program with a Dreyfus-Wagner style dynamic program to locally deal with large numbers of terminals.

Abstract For a set of graphs $${\mathcal {H}}$$ H , a graph G is $${\mathcal {H}}$$ H -subgraph-free if G does not contain any graph from $${{{\mathcal {H}}}}$$ H as a subgraph. We propose general and easy-to-state conditions on graph problems that explain a large set of results for $${\mathcal {H}}$$ H -subgraph-free graphs. Namely, a graph problem must be efficiently solvable on graphs of bounded treewidth, computationally hard on subcubic graphs, and computational hardness must be preserved under edge subdivision of subcubic graphs. Our meta-classification says that if a graph problem $$\Pi $$ Π satisfies all three conditions, then for every finite set $${{{\mathcal {H}}}}$$ H , it is “efficiently solvable” on $${{{\mathcal {H}}}}$$ H -subgraph-free graphs if $${\mathcal {H}}$$ H contains a disjoint union of one or more paths and subdivided claws, and $$\Pi $$ Π is “computationally hard” otherwise. We apply our meta-classification on many well-known partitioning, covering and packing problems, network design problems and width parameter problems to obtain a dichotomy between polynomial-time solvability and -completeness. For distance-metric problems, we obtain a dichotomy between almost-linear-time solvability and having no subquadratic-time algorithm (conditioned on some hardness hypotheses). Apart from capturing a large number of explicitly and implicitly known results in the literature, we also prove a number of new results. Moreover, we perform an extensive comparison between the subgraph framework and the existing frameworks for the minor and topological minor relations, and pose several new open problems and research directions.

We study Steiner Forest on H -subgraph-free graphs, that is, graphs that do not contain some fixed graph H as a (not necessarily induced) subgraph. In contrast to the related Steiner Tree problem, Steiner Forest falls outside a recent framework that completely characterizes the complexity of many problems on H -subgraph-free graphs. Hence, the complexity of Steiner Forest on H -subgraph-free graphs remained open. Our main results are four polynomial-time algorithms for different excluded graphs H that are central to further understand its complexity. We also study the complexity of Steiner Forest for graphs with a small c -deletion set, that is, a small set X of vertices such that each connected component of G − X has size at most c . For this parameter, we give two algorithms that we later employ as subroutines (including a faster algorithm when c = 1 , that is, the vertex cover number) and exhibit a dichotomy theorem.

Abstract. The intensively studied Diameter problem is to find the diameter of a given connected graph. We investigate, for the first time in a structured manner, the complexity of Diameter for [Formula: see text]-free graphs, that is, graphs that do not contain a fixed graph [Formula: see text] as an induced subgraph. We first show that if [Formula: see text] is not a linear forest with small components, then Diameter cannot be solved in subquadratic time for [Formula: see text]-free graphs under SETH. For some small linear forests, we do show linear-time algorithms for solving Diameter. For other linear forests [Formula: see text], we make progress towards linear-time algorithms by considering specific diameter values. If [Formula: see text] is a linear forest, the maximum value of the diameter of any graph in a connected [Formula: see text]-free graph class is some constant [Formula: see text] dependent only on [Formula: see text]. We give linear-time algorithms for deciding if a connected [Formula: see text]-free graph has diameter [Formula: see text] for several linear forests [Formula: see text]. In contrast, for one such linear forest [Formula: see text], Diameter cannot be solved in subquadratic time for [Formula: see text]-free graphs under SETH. Moreover, we even show that, for several other linear forests [Formula: see text], one cannot decide in subquadratic time if a connected [Formula: see text]-free graph has diameter [Formula: see text] under SETH.

We consider a natural generalization of Vertex Cover : the Subset Vertex Cover problem, which is to decide for a graph G = ( V , E ) , a subset T ⊆ V and integer k , if V has a subset S of size at most k , such that S contains at least one end-vertex of every edge incident to a vertex of T . A graph is H -free if it does not contain H as an induced subgraph. We solve two open problems from the literature by proving that Subset Vertex Cover is NP -complete on subcubic (claw, diamond)-free planar graphs and on 2-unipolar graphs, a subclass of 2 P 3 -free weakly chordal graphs. Our results show for the first time that Subset Vertex Cover is computationally harder than Vertex Cover (under P ≠ NP ). We also prove new polynomial time results, some of which follow from a reduction to Vertex Cover restricted to classes of probe graphs. We first give a dichotomy on graphs where G [ T ] is H -free. Namely, we show that Subset Vertex Cover is polynomial-time solvable on graphs G , for which G [ T ] is H -free, if H = s P 1 + t P 2 and NP -complete otherwise. Moreover, we prove that Subset Vertex Cover is polynomial-time solvable for ( s P 1 + P 2 + P 3 ) -free graphs and bounded mim-width graphs. By combining our new results with known results we obtain a partial complexity classification for Subset Vertex Cover on H -free graphs.

The hyperbolicity of a graph, informally, measures how close a graph is (metrically) to a tree. Hence, it is intuitively similar to treewidth, but the measures are formally incomparable. Motivated by the broad study of algorithms and separators on planar graphs and their relation to treewidth, we initiate the study of planar graphs of bounded hyperbolicity. Our main technical contribution is a novel balanced separator theorem for planar $δ$-hyperbolic graphs that is substantially stronger than the classic planar separator theorem. For any fixed $δ\geq 0$, we can find balanced separator that induces either a single geodesic (shortest) path or a single geodesic cycle in the graph. An important advantage of our separator is that the union of our separator (vertex set $Z$) with any subset of the connected components of $G - Z$ induces again a planar $δ$-hyperbolic graph, which would not be guaranteed with an arbitrary separator. Our construction runs in near-linear time and guarantees that size of separator is $\mathrm{poly}(δ) \cdot \log n$. As an application of our separator theorem and its strong properties, we obtain two novel approximation schemes on planar $δ$-hyperbolic graphs. We prove that Maximum Independent Set and the Traveling Salesperson problem have a near-linear time FPTAS for any constant $δ$, running in $n\, \mathrm{polylog}(n) \cdot 2^{\mathcal{O}(δ^2)} \cdot \varepsilon^{-\mathcal{O}(δ)}$ time. We also show that our approximation scheme for Maximum Independent Set has essentially the best possible running time under the Exponential Time Hypothesis (ETH). This immediately follows from our third contribution: we prove that Maximum Independent Set has no $n^{o(δ)}$-time algorithm on planar $δ$-hyperbolic graphs, unless ETH fails.

Abstract We initiate the investigation of the parameterized complexity of Diameter and Connectivity in the streaming paradigm. On the positive end, we show that knowing a vertex cover of size k allows for algorithms in the Adjacency List (AL) streaming model whose number of passes is constant and memory is $$\mathcal {O}(\log n)$$ O ( log n ) for any fixed k. Underlying these algorithms is a method to execute a breadth-first search in $$\mathcal {O}(k)$$ O ( k ) passes and $$\mathcal {O}(k \log n)$$ O ( k log n ) bits of memory. On the negative end, we show that many other parameters lead to lower bounds in the AL model, where $$\Omega (n/p)$$ Ω ( n / p ) bits of memory is needed for any p-pass algorithm even for constant parameter values. In particular, this holds for graphs with a known modulator (deletion set) of constant size to a graph that has no induced subgraph isomorphic to a fixed graph H, for most H. For some cases, we can also show one-pass, $$\Omega (n \log n)$$ Ω ( n log n ) bits of memory lower bounds. We also prove a much stronger $$\Omega (n^2/p)$$ Ω ( n 2 / p ) lower bound for Diameter on bipartite graphs. Finally, using the insights we developed into streaming parameterized graph exploration algorithms, we show a new streaming kernelization algorithm for computing a vertex cover of size k. This yields a kernel of 2k vertices (with $$\mathcal {O}(k^2)$$ O ( k 2 ) edges) produced as a stream in $$\text {poly}(k)$$ poly ( k ) passes and only $$\mathcal {O}(k \log n)$$ O ( k log n ) bits of memory.

Dynamic programming on various graph decompositions is one of the most fundamental techniques used in parameterized complexity. Unfortunately, even if we consider concepts as simple as path or tree decompositions, such dynamic programming uses space that is exponential in the decomposition's width, and there are good reasons to believe that this is necessary. However, it has been shown that in graphs of low treedepth it is possible to design algorithms which achieve polynomial space complexity without requiring worse time complexity than their counterparts working on tree decompositions of bounded width. Here, treedepth is a graph parameter that, intuitively speaking, takes into account both the depth and the width of a tree decomposition of the graph, rather than the width alone. Motivated by the above, we consider graphs that admit clique expressions with bounded depth and label count, or equivalently, graphs of low shrubdepth (sd). Here, sd is a bounded-depth analogue of cliquewidth, in the same way as td is a bounded-depth analogue of treewidth. We show that also in this setting, bounding the depth of the decomposition is a deciding factor for improving the space complexity. Precisely, we prove that on $n$-vertex graphs equipped with a tree-model (a decomposition notion underlying sd) of depth $d$ and using $k$ labels, we can solve - Independent Set in time $2^{O(dk)}\cdot n^{O(1)}$ using $O(dk^2\log n)$ space; - Max Cut in time $n^{O(dk)}$ using $O(dk\log n)$ space; and - Dominating Set in time $2^{O(dk)}\cdot n^{O(1)}$ using $n^{O(1)}$ space via a randomized algorithm. We also establish a lower bound, conditional on a certain assumption about the complexity of Longest Common Subsequence, which shows that at least in the case of IS the exponent of the parametric factor in the time complexity has to grow with $d$ if one wishes to keep the space complexity polynomial.

The Integer Multicommodity Flow problem has been studied extensively in the literature. However, from a parameterised perspective, mostly special cases, such as the Disjoint Path problem, have been considered. Therefore, we investigate the parameterised complexity of the general Integer Multicommodity Flow problem. We show that the decision version of this problem on directed graphs for a constant number of commodities, when the capacities are given in unary, is XNLP-complete with pathwidth as parameter and XALP-complete with treewidth as parameter. When the capacities are given in binary, the problem is NP-complete even for graphs of pathwidth at most 13. We give related results for undirected graphs. These results imply that the problem is unlikely to be fixed-parameter tractable by these parameters. In contrast, we show that the problem does become fixed-parameter tractable when weighted tree partition width (a variant of tree partition width for edge weighted graphs) is used as parameter.

For any finite set H = {H1, . . ., Hp} of graphs, a graph is H-subgraph-free if it does not contain any of H1, . . ., Hp as a subgraph. In recent work, meta-classifications have been studied: these show that if graph problems satisfy certain prescribed conditions, their complexity can be classified on classes of H-subgraph-free graphs. We continue this work and focus on problems that have polynomial-time solutions on classes that have bounded treewidth or maximum degree at most 3 and examine their complexity on H-subgraph-free graph classes where H is a connected graph. With this approach, we obtain comprehensive classifications for (Independent) Feedback Vertex Set, Connected Vertex Cover, Colouring and Matching Cut. This resolves a number of open problems. We highlight that, to establish that Independent Feedback Vertex Set belongs to this collection of problems, we first show that it can be solved in polynomial time on graphs of maximum degree 3. We demonstrate that, with the exception of the complete graph on four vertices, each graph in this class has a minimum size feedback vertex set that is also an independent set.

Abstract Paths $$P^1,\ldots ,P^k$$ P 1 , … , P k in a graph $$G=(V,E)$$ G = ( V , E ) are mutually induced if any two distinct $$P^i$$ P i and $$P^j$$ P j have neither common vertices nor adjacent vertices. The Induced Disjoint Paths problem is to decide if a graph G with k pairs of specified vertices $$(s_i,t_i)$$ ( s i , t i ) contains k mutually induced paths $$P^i$$ P i such that each $$P^i$$ P i starts from $$s_i$$ s i and ends at $$t_i$$ t i . This is a classical graph problem that is -complete even for $$k=2$$ k = 2 . We introduce a natural generalization, Induced Disjoint Connected Subgraphs: instead of connecting pairs of terminals, we must connect sets of terminals. We give almost-complete dichotomies of the computational complexity of both problems for H-free graphs, that is, graphs that do not contain some fixed graph H as an induced subgraph. Finally, we give a complete classification of the complexity of the second problem if the number k of terminal sets is fixed, that is, not part of the input.

Paths P1,…,Pk in a graph G=(V,E) are mutually induced if any two distinct Pi and Pj have neither common vertices nor adjacent vertices. For a fixed integer k, the k-Induced Disjoint Paths problem is to decide if a graph G with k pairs of specified vertices (si,ti) contains k mutually induced paths Pi such that each Pi starts from si and ends at ti. Whereas the non-induced version is well-known to be polynomial-time solvable for every fixed integer k, a classical result from the literature states that even 2-Induced Disjoint Paths is NP-complete. We prove new complexity results for k-Induced Disjoint Paths if the input is restricted to H-free graphs, that is, graphs without a fixed graph H as an induced subgraph. We compare our results with a complexity dichotomy for Induced Disjoint Paths, the variant where k is part of the input.

Streaming is a model where an input graph is provided one edge at a time, instead of being able to inspect it at will. In this work, we take a parameterized approach by assuming a vertex cover of the graph is given, building on work of Bishnu et al. [COCOON 2020]. We show the further potency of combining this parameter with the Adjacency List streaming model to obtain results for vertex deletion problems. This includes kernels, parameterized algorithms, and lower bounds for the problems of Π-free Deletion, H-free Deletion, and the more specific forms of Cluster Vertex Deletion and Odd Cycle Transversal. We focus on the complexity in terms of the number of passes over the input stream, and the memory used. This leads to a pass/memory trade-off, where a different algorithm might be favourable depending on the context and instance. We also discuss implications for parameterized complexity in the non-streaming setting.

We initiate the investigation of the parameterized complexity of Diameter and Connectivity in the streaming paradigm. On the positive end, we show that knowing a vertex cover of size $k$ allows for algorithms in the Adjacency List (AL) streaming model whose number of passes is constant and memory is $O(\log n)$ for any fixed $k$. Underlying these algorithms is a method to execute a breadth-first search in $O(k)$ passes and $O(k \log n)$ bits of memory. On the negative end, we show that many other parameters lead to lower bounds in the AL model, where $Ω(n/p)$ bits of memory is needed for any $p$-pass algorithm even for constant parameter values. In particular, this holds for graphs with a known modulator (deletion set) of constant size to a graph that has no induced subgraph isomorphic to a fixed graph $H$, for most $H$. For some cases, we can also show one-pass, $Ω(n \log n)$ bits of memory lower bounds. We also prove a much stronger $Ω(n^2/p)$ lower bound for Diameter on bipartite graphs. Finally, using the insights we developed into streaming parameterized graph exploration algorithms, we show a new streaming kernelization algorithm for computing a vertex cover of size $k$. This yields a kernel of $2k$ vertices (with $O(k^2)$ edges) produced as a stream in $\text{poly}(k)$ passes and only $O(k \log n)$ bits of memory.

We consider the Edge Multiway Cut problem on planar graphs. It is known that this can be solved in time [Klein, Marx, ICALP 2012] and not in time under the Exponential Time Hypothesis [Marx, ICALP 2012], where t is the number of terminals. A generalization of this parameter is the number k of faces of the planar graph that jointly cover all terminals. For the related Steiner Tree problem, an time algorithm was recently shown [Kisfaludi-Bak et al., SODA 2019]. By a completely different approach, we prove in this paper that Edge Multiway Cut can be solved in time as well. Our approach employs several major concepts on planar graphs, including homotopy and sphere-cut decomposition. We also mix a global treewidth dynamic program with a Dreyfus-Wagner style dynamic program to locally deal with large numbers of terminals.

Abstract Let $${\mathcal {C}}$$ C and $${\mathcal {D}}$$ D be hereditary graph classes. Consider the following problem: given a graph $$G\in {\mathcal {D}}$$ G ∈ D , find a largest, in terms of the number of vertices, induced subgraph of G that belongs to $${\mathcal {C}}$$ C . We prove that it can be solved in $$2^{o(n)}$$ 2 o ( n ) time, where n is the number of vertices of G , if the following conditions are satisfied: the graphs in $${\mathcal {C}}$$ C are sparse, i.e., they have linearly many edges in terms of the number of vertices; the graphs in $${\mathcal {D}}$$ D admit balanced separators of size governed by their density, e.g., $${\mathcal {O}}(\varDelta )$$ O ( Δ ) or $${\mathcal {O}}(\sqrt{m})$$ O ( m ) , where $$\varDelta$$ Δ and m denote the maximum degree and the number of edges, respectively; and the considered problem admits a single-exponential fixed-parameter algorithm when parameterized by the treewidth of the input graph. This leads, for example, to the following corollaries for specific classes $${\mathcal {C}}$$ C and $${\mathcal {D}}$$ D : a largest induced forest in a $$P_t$$ P t -free graph can be found in $$2^{\tilde{{\mathcal {O}}}(n^{2/3})}$$ 2 O ~ ( n

We show that Odd Cycle Transversal and Vertex Multiway Cut admit deterministic polynomial kernels when restricted to planar graphs and parameterized by the solution size. This answers a question of Saurabh. On the way to these results, we provide an efficient sparsification routine in the flavor of the sparsification routine used for the Steiner Tree problem in planar graphs [Pilipczuk et al., ACM Trans. Algorithms, 14 (2018), 53]. It differs from the previous work because it preserves the existence of low-cost subgraphs that are not necessarily Steiner trees in the original plane graph, but structures that turn into (supergraphs of) Steiner trees after adding all edges between pairs of vertices that lie on a common face. We also show connections between Vertex Multiway Cut and the Vertex Planarization problem, where the existence of a polynomial kernel remains an important open problem.

Given a vertex-colored graph, we say a path is a rainbow vertex path if all its internal vertices have distinct colors. The graph is rainbow vertex-connected if there is a rainbow vertex path between every pair of its vertices. In the Rainbow Vertex Coloring (RVC) problem we want to decide whether the vertices of a given graph can be colored with at most k colors so that the graph becomes rainbow vertex-connected. This problem is known to be NP-complete even in very restricted scenarios, and very few efficient algorithms are known for it. In this work, we give polynomial-time algorithms for RVC on permutation graphs, powers of trees and split strongly chordal graphs. The algorithm for the latter class also works for the strong variant of the problem, where the rainbow vertex paths between each vertex pair must be shortest paths. We complement the polynomial-time solvability results for split strongly chordal graphs by showing that, for any fixed p≥3 both variants of the problem become NP-complete when restricted to split (S3,…,Sp)-free graphs, where Sq denotes the q-sun graph.

A disconnected cut of a connected graph is a vertex cut that itself also induces a disconnected subgraph. The corresponding decision problem is called Disconnected Cut . This problem is known to be NP -hard on general graphs. We prove that it is polynomial-time solvable on claw-free graphs, answering a question of Ito et al. (TCS 2011). The basis for our result is a decomposition theorem for claw-free graphs of diameter 2, which we believe is of independent interest and builds on the research line initiated by Chudnovsky and Seymour (JCTB 2007–2012) and Hermelin et al. (ICALP 2011). On our way to exploit this decomposition theorem, we characterize how disconnected cuts interact with certain cobipartite subgraphs, and prove two further algorithmic results, namely that Disconnected Cut is polynomial-time solvable on circular-arc graphs and line graphs.

A fundamental graph problem is to recognize whether the vertex set of a graph $G$ can be bipartitioned into sets $A$ and $B$ such that $G[A]$ and $G[B]$ satisfy properties $\Pi_A$ and $\Pi_B$, respectively. This so-called $(\Pi_A,\Pi_B)$-Recognition problem generalizes, amongst others, the recognition of 3-colorable, bipartite, split, and monopolar graphs. In this paper, we study whether certain fixed-parameter tractable $(\Pi_A,\Pi_B)$-Recognition problems admit polynomial kernels. In our study, we focus on the first level above triviality, where $\Pi_A$ is the set of $P_3$-free graphs (disjoint unions of cliques, or cluster graphs), the parameter is the number of clusters in the cluster graph $G[A]$, and $\Pi_B$ is characterized by a set $\mathcal{H}$ of connected forbidden induced subgraphs. We prove that, under the assumption that ${NP} \not\subseteq {coNP}/{poly}$, $(\Pi_A,\Pi_B)$-Recognition admits a polynomial kernel if and only if $\mathcal{H}$ contains a graph with at most two vertices. In both the kernelization and the lower bound results, we exploit the properties of a pushing process, which is an algorithmic technique used recently by Heggerness et al. and by Kanj et al. to obtain fixed-parameter algorithms for many cases of $(\Pi_A,\Pi_B)$-Recognition, as well as several other problems.

The S TEINER T REE problem is one of the most fundamental NP-complete problems, as it models many network design problems. Recall that an instance of this problem consists of a graph with edge weights and a subset of vertices (often called terminals); the goal is to find a subtree of the graph of minimum total weight that connects all terminals. A seminal paper by Erickson et al. [Math. Oper. Res., 1987{ considers instances where the underlying graph is planar and all terminals can be covered by the boundary of k faces. Erickson et al. show that the problem can be solved by an algorithm using n O(k) time and n O(k) space, where n denotes the number of vertices of the input graph. In the past 30 years there has been no significant improvement of this algorithm, despite several efforts. In this work, we give an algorithm for P LANAR S TEINER T REE with running time 2 O(k) n O(√k) with the above parameterization, using only polynomial space. Furthermore, we show that the running time of our algorithm is almost tight: We prove that there is no f ( k ) n o(√k) algorithm for P LANAR S TEINER T REE for any computable function f , unless the Exponential Time Hypothesis fails.

We study SET COVER for orthants: Given a set of points in a d-dimensional Euclidean space and a set of orthants of the form (-infty,p_1] x ... x (-infty,p_d], select a minimum number of orthants so that every point is contained in at least one selected orthant. This problem draws its motivation from applications in multi-objective optimization problems. While for d=2 the problem can be solved in polynomial time, for d>2 no algorithm is known that avoids the enumeration of all size-k subsets of the input to test whether there is a set cover of size k. Our contribution is a precise understanding of the complexity of this problem in any dimension d >= 3, when k is considered a parameter: - For d=3, we give an algorithm with runtime n^O(sqrt{k}), thus avoiding exhaustive enumeration. - For d=3, we prove a tight lower bound of n^Omega(sqrt{k}) (assuming ETH). - For d >=slant 4, we prove a tight lower bound of n^Omega(k) (assuming ETH). Here n is the size of the set of points plus the size of the set of orthants. The first statement comes as a corollary of a more general result: an algorithm for SET COVER for half-spaces in dimension 3. In particular, we show that given a set of points U in R^3, a set of half-spaces D in R^3, and an integer k, one can decide whether U can be covered by the union of at most k half-spaces from D in time |D|^O(sqrt{k})* |U|^O(1). We also study approximation for SET COVER for orthants. While in dimension 3 a PTAS can be inferred from existing results, we show that in dimension 4 and larger, there is no 1.05-approximation algorithm with runtime f(k)* n^o(k) for any computable f, where k is the optimum.

The Steiner Tree problem is one of the most fundamental NP-complete problems as it models many network design problems. Recall that an instance of this problem consists of a graph with edge weights, and a subset of vertices (often called terminals); the goal is to find a subtree of the graph of minimum total weight that connects all terminals. A seminal paper by Erickson et al. [Math. Oper. Res., 1987] considers instances where the underlying graph is planar and all terminals can be covered by the boundary of k faces. Erickson et al. show that the problem can be solved by an algorithm using nO(k) time and nO(k) space, where n denotes the number of vertices of the input graph. In the past 30 years there has been no significant improvement of this algorithm, despite several efforts. In this work, we give an algorithm for Planar Steiner Tree with running time using only polynomial space. Furthermore, we show the running time of our algorithm is almost tight: we prove that there is no algorithm for Planar Steiner Tree for any computable function f, unless the Exponential Time Hypothesis fails.

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 algorithmize the structural characterization for claw-free graphs by Chudnovsky and Seymour. Building on this result, we show that D ominating S et on claw-free graphs is (i) fixed-parameter tractable and (ii) even possesses a polynomial kernel. To complement these results, we establish that D ominating S et is unlikely to be fixed-parameter tractable on the slightly larger class of graphs that exclude K 1,4 as an induced subgraph ( K 1,4 -free graphs). We show that our algorithmization can also be used to show that the related C onnected D ominating S et problem is fixed-parameter tractable on claw-free graphs. To complement that result, we show that C onnected D ominating S et is unlikely to have a polynomial kernel on claw-free graphs and is unlikely to be fixed-parameter tractable on K 1,4 -free graphs. Combined, our results provide a dichotomy for D ominating S et and C onnected D ominating S et on K 1,ℓ -free graphs and show that the problem is fixed-parameter tractable if and only if ℓ ≤ 3.

We consider two optimization problems in planar graphs. In {Maximum Weight Independent Set of Objects} we are given a graph G and a family D of {objects}, each being a connected subgraph of G with a prescribed weight, and the task is to find a maximum-weight subfamily of D consisting of pairwise disjoint objects. In {Minimum Weight Distance Set Cover} we are given an edge-weighted graph G, two sets D,C of vertices of G, where vertices of D have prescribed weights, and a nonnegative radius r. The task is to find a minimum-weight subset of D such that every vertex of C is at distance at most r from some selected vertex. Via simple reductions, these two problems generalize a number of geometric optimization tasks, notably {Maximum Weight Independent Set} for polygons in the plane and {Weighted Geometric Set Cover} for unit disks and unit squares. We present {quasi-polynomial time approximation schemes} (QPTASs) for both of the above problems in planar graphs: given an accuracy parameter epsilon>0 we can compute a solution whose weight is within multiplicative factor of (1+epsilon) from the optimum in time 2^{poly(1/epsilon,log |D|)}* n^{O(1)}, where n is the number of vertices of the input graph. Our main technical contribution is to transfer the techniques used for recursive approximation schemes for geometric problems due to Adamaszek, Har-Peled, and Wiese [Adamaszek and Wiese, 2013; Adamaszek and Wiese, 2014; Sariel Har-Peled, 2014] to the setting of planar graphs. In particular, this yields a purely combinatorial viewpoint on these methods.

Given a graph with colors on its vertices, a path is called a rainbow vertex path if all its internal vertices have distinct colors. We say that the graph is rainbow vertex-connected if there is a rainbow vertex path between every pair of its vertices. We study the problem of deciding whether the vertices of a given graph can be colored with at most k colors so that the graph becomes rainbow vertex-connected. Although edge-colorings have been studied extensively under similar constraints, there are significantly fewer results on the vertex variant that we consider. In particular, its complexity on structured graph classes was explicitly posed as an open question. We show that the problem remains NP-complete even on bipartite apex graphs and on split graphs. The former can be seen as a first step in the direction of studying the complexity of rainbow coloring on sparse graphs, an open problem which has attracted attention but limited progress. We also give hardness of approximation results for both bipartite and split graphs. To complement the negative results, we show that bipartite permutation graphs, interval graphs, and block graphs can be rainbow vertex-connected optimally in polynomial time.

In the M aximum W eight I ndependent S et problem, the input is a graph G , every vertex has a non-negative integer weight, and the task is to find a set S of pairwise nonadjacent vertices, maximizing the total weight of the vertices in S . We give an n O (log 2 n ) time algorithm for this problem on graphs excluding the path P 6 on 6 vertices as an induced subgraph. Currently, there is no constant k known for which M aximum W eight I ndependent S et on P k -free graphs becomes NP-hard, and our result implies that if such a k exists, then k > 6 unless all problems in NP can be decided in quasi-polynomial time. Using the combinatorial tools that we develop for this algorithm, we also give a polynomial-time algorithm for M aximum W eight E fficient D ominating S et on P 6 -free graphs. In this problem, the input is a graph G , every vertex has an integer weight, and the objective is to find a set S of maximum weight such that every vertex in G has exactly one vertex in S in its closed neighborhood or to determine that no such set exists. Prior to our work, the class of P 6 -free graphs was the only class of graphs defined by a single forbidden induced subgraph on which the computational complexity of M aximum W eight E fficient D ominating S et was unknown.

We propose polynomial-time algorithms that sparsify planar and bounded-genus graphs while preserving optimal or near-optimal solutions to Steiner problems. Our main contribution is a polynomial-time algorithm that, given an unweighted undirected graph G embedded on a surface of genus g and a designated face f bounded by a simple cycle of length k , uncovers a set F ⊆ E ( G ) of size polynomial in g and k that contains an optimal Steiner tree for any set of terminals that is a subset of the vertices of f . We apply this general theorem to prove that: — Given an unweighted graph G embedded on a surface of genus g and a terminal set S ⊆ V ( G ), one can in polynomial time find a set F ⊆ E ( G ) that contains an optimal Steiner tree T for S and that has size polynomial in g and | E ( T )|. — An analogous result holds for an optimal Steiner forest for a set S of terminal pairs. — Given an unweighted planar graph G and a terminal set S ⊆ V ( G ), one can in polynomial time find a set F ⊆ E ( G ) that contains an optimal (edge) multiway cut C separating S (i.e., a cutset that intersects any path with endpoints in different terminals from S ) and that has size polynomial in | C |. In the language of parameterized complexity, these results imply the first polynomial kernels for S teiner T ree and S teiner F orest on planar and bounded-genus graphs (parameterized by the size of the tree and forest, respectively) and for (E dge ) M ultiway C ut on planar graphs (parameterized by the size of the cutset). Additionally, we obtain a weighted variant of our main contribution: a polynomial-time algorithm that, given an undirected plane graph G with positive edge weights, a designated face f bounded by a simple cycle of weight w ( f ), and an accuracy parameter ε > 0, uncovers a set F ⊆ E ( G ) of total weight at most poly(ε -1 ) w ( f ) that, for any set of terminal pairs that lie on f , contains a Steiner forest within additive error ε w ( f ) from the optimal Steiner forest.

Consider the Maximum Weight Independent Set problem for rectangles: given a family of weighted axis-parallel rectangles in the plane, find a maximum-weight subset of non-overlapping rectangles. The problem is notoriously hard both in the approximation and in the parameterized setting. The best known polynomial-time approximation algorithms achieve super-constant approximation ratios [Chalermsook & Chuzhoy, Proc. SODA 2009; Chan & Har-Peled, Discrete & Comp. Geometry, 2012], even though there is a (1+epsilon)-approximation running in quasi-polynomial time [Adamaszek & Wiese, Proc. FOCS 2013; Chuzhoy & Ene, Proc. FOCS 2016]. When parameterized by the target size of the solution, the problem is W[1]-hard even in the unweighted setting [Marx, ESA 2005]. To achieve tractability, we study the following shrinking model: one is allowed to shrink each input rectangle by a multiplicative factor 1-delta for some fixed delta > 0, but the performance is still compared against the optimal solution for the original, non-shrunk instance. We prove that in this regime, the problem admits an EPTAS with running time f(epsilon,delta) n^{O(1)}, and an FPT algorithm with running time f(k,delta) n^{O(1)}, in the setting where a maximum-weight solution of size at most k is to be computed. This improves and significantly simplifies a PTAS given earlier for this problem [Adamaszek, Chalermsook & Wiese, Proc. APPROX/RANDOM 2015], and provides the first parameterized results for the shrinking model. Furthermore, we explore kernelization in the shrinking model, by giving efficient kernelization procedures for several variants of the problem when the input rectangles are squares.

A graph is called {claw,diamond}-free if it contains neither a claw (a K 1,3) nor a diamond (a K 4 with an edge removed) as an induced subgraph. Equivalently, {claw,diamond}-free graphs are characterized as line graphs of triangle-free graphs, or as linear dominoes (graphs in which every vertex is in at most two maximal cliques and every edge is in exactly one maximal clique). We consider the parameterized complexity of the {claw,diamond}-free Edge Deletion problem, where given a graph G and a parameter k, the question is whether one can remove at most k edges from G to obtain a {claw,diamond}-free graph. Our main result is that this problem admits a polynomial kernel. We complement this result by proving that, even on instances with maximum degree 6, the problem is NP-complete and cannot be solved in time $2^{o(k)}\cdot |V(G)|^{\mathcal {O}(1)}$ unless the Exponential Time Hypothesis fails.

In the Maximum Weight Independent Set problem, the input is a graph G, every vertex has a nonnegative integer weight, and the task is to find a set S of pairwise non-adjacent vertices, maximizing the total weight of the vertices in S. We give an time algorithm for this problem on graphs excluding the path P6 on 6 vertices as an induced subgraph. Currently, there is no constant k known for which Maximum Weight Independent Set on Pk-free graphs becomes NP-complete, and our result implies that if such a k exists, then k > 6 unless all problems in NP can be decided in (quasi)polynomial time. Using the combinatorial tools that we develop for the above algorithm, we also give a polynomial-time algorithm for Maximum Weight Efficient Dominating Set on P6-free graphs. In this problem, the input is a graph G, every vertex has an integer weight, and the objective is to find a set S of maximum weight such that every vertex in G has exactly one vertex in S in its closed neighborhood, or to determine that no such set exists. Prior to our work, the class of P6-free graphs was the only class of graphs defined by a single forbidden induced subgraph on which the computational complexity of Maximum Weight Efficient Dominating Set was unknown.

We consider the problem to find a set X of vertices (or arcs) with |X| <= k in a given digraph G such that D = G-X is an acyclic digraph. In its generality, this is DIRECTED FEEDBACK VERTEX SET or DIRECTED FEEDBACK ARC SET respectively. The existence of a polynomial kernel for these problems is a notorious open problem in the field of kernelization, and little progress has been made. In this paper, we consider both deletion problems with an additional restriction on D, namely that D must be an out-forest, an out-tree, or a (directed) pumpkin. Our main results show that for each of these three restrictions the vertex deletion problem remains NP-hard, but we can obtain a kernel with k^{O(1)} vertices on general digraphs G. We also show that, in contrast to the vertex deletion problem, the arc deletion problem with each of the above restrictions can be solved in polynomial time.

We consider the Steiner Multicut problem, which asks, given an undirected graph G, a collection T = \{T_{1},...,T_{t}}, T_i \subseteq V(G), of terminal sets of size at most p, and an integer k, whether there is a set S of at most k edges or nodes such that of each set T_{i} at least one pair of terminals is in different connected components of G \ S. This problem generalizes several well-studied graph cut problems, in particular the Multicut problem, which corresponds to the case p = 2. The Multicut problem was recently shown to be fixed-parameter tractable for parameter k [Marx and Razgon, Bousquet et al., STOC 2011]. The question whether this result generalizes to Steiner Multicut motivates the present work. We answer the question that motivated this work, and in fact provide a dichotomy of the parameterized complexity of Steiner Multicut on general graphs. That is, for any combination of k, t, p, and the treewidth tw(G) as constant, parameter, or unbounded, and for all versions of the problem (edge deletion and node deletion with and without deletable terminals), we prove either that the problem is fixed-parameter tractable or that the problem is hard (W[1]-hard or even (para-)NP-complete). Among the many results in the paper, we highlight that: - The edge deletion version of Steiner Multicut is fixed-parameter tractable for parameter k+t on general graphs (but has no polynomial kernel, even on trees). - In contrast, both node deletion versions of Steiner Multicut are W[1]-hard for the parameter k+t on general graphs. - All versions of Steiner Multicut are W[1]-hard for the parameter k, even when p=3 and the graph is a tree plus one node. Since we allow k, t, p, and tw(G) to be any constants, our characterization includes a dichotomy for Steiner Multicut on trees (for tw(G) = 1) as well as a polynomial time versus NP-hardness dichotomy (by restricting k,t,p,tw(G) to constant or unbounded).

Paths $P_1,\ldots,P_k$ in a graph $G=(V,E)$ are said to be mutually induced if for any $1\leq i

We propose polynomial-time algorithms that sparsify planar and bounded-genus graphs while preserving optimal or near-optimal solutions to Steiner problems. Our main contribution is a polynomial-time algorithm that, given an unweighted graph G embedded on a surface of genus g and a designated face f bounded by a simple cycle of length k, uncovers a set F in E(G) of size polynomial in g and k that contains an optimal Steiner tree for any set of terminals that is a subset of the vertices of f. We apply this general theorem to prove that: (2) given an unweighted graph G embedded on a surface of genus g and a terminal set S in V(G), one can in polynomial time find a set F in E(G) that contains an optimal Steiner tree T for S and that has size polynomial in g and |E(T)|; (2) an analogous result holds for an optimal Steiner forest for a set S of terminal pairs, (3) given an unweighted planar graph G and a terminal set S in V(G), one can in polynomial time find a set F in E(G) that contains an optimal (edge) multiway cut C separating S (i.e., a cutset that intersects any path with endpoints in different terminals from S) and has size polynomial in |C|. In the language of parameterized complexity, these results imply the first polynomial kernels for Steiner Tree and Steiner Forest on planar and bounded-genus graphs (parameterized by the size of the tree and forest, respectively) and for (Edge) Multiway Cut on planar graphs (parameterized by the size of the cutset). Steiner Tree and similar "subset" problems were identified in [Demaine, Hajiaghayi, Computer J., 2008] as important to the quest to widen the reach of the theory of bidimensionality ([Demaine et al., JACM 2005], [Fomin et al., SODA 2010]). Therefore, our results can be seen as a leap forward to achieve this broader goal. Additionally, we obtain a weighted variant of our main contribution: a polynomial-time algorithm that, given an edge-weighted planar graph G, a designated face f bounded by a simple cycle of weight w(f), and an accuracy parameter ε > 0, uncovers a set F in E(G) of total weight at most poly(1/ε) w(f) that, for any set of terminal pairs that lie on f, contains a Steiner forest within additive error ε w(f) from the optimal Steiner forest. This result deepens the understanding of the recent framework of approximation schemes for network design problems on planar graphs ([Klein, SICOMP 2008], [Borradaile, Klein, Mathieu, ACM TALG 2009], and later works) by explaining the structure of the solution space within a brick of the so-called mortar graph -- the central notion of this framework.

The well-known bidimensionality theory provides a method for designing fast, subexponential-time parameterized algorithms for a vast number of NP-hard problems on sparse graph classes such as planar graphs, bounded genus graphs, or, more generally, graphs with a fixed excluded minor. However, in order to apply the bidimensionality framework the considered problem needs to fulfill a special density property. Some well-known problems do not have this property, unfortunately, with probably the most prominent and important example being the Steiner Tree problem. Hence the question whether a subexponential-time parameterized algorithm for Steiner Tree on planar graphs exists has remained open. In this paper, we answer this question positively and develop an algorithm running in O(2^{O((k log k)^{2/3})}n) time and polynomial space, where k is the size of the Steiner tree and n is the number of vertices of the graph. Our algorithm does not rely on tools from bidimensionality theory or graph minors theory, apart from Baker's classical approach. Instead, we introduce new tools and concepts to the study of the parameterized complexity of problems on sparse graphs.

We determine tight bounds on the smallest-size integer grid needed to represent the $n$-node intersection graphs of a convex polygon $P$ with P given in rational coordinates. The intersection graphs use only polygons that are geometrically similar to $P$ (translates or homothets) and must be represented such that each corner of each polygon lies on a point of the grid. We show the following generic results: if $P$ is a parallelogram and only translates of $P$ are used, then an $\Omega(n^2) \times\Omega(n^2)$ grid is sufficient and is needed for some graphs; if $P$ is any other convex polygon and only translates of $P$ are used, then a $2^{\Omega(n)}\times 2^{\Omega(n)}$ grid is sufficient and is needed for some graphs; if $P$ is any convex polygon and arbitrary homothets of $P$ are allowed, then a $2^{\Omega(n)}\times 2^{\Omega(n)}$ grid is sufficient and is needed for some graphs. The results substantially improve earlier bounds and settle the complexity of representing convex polygon intersection graphs. The results also imply small polynomial certificates for the recognition problem for all graph classes considered.

We study the problem of determining the spanning tree congestion of a graph. We present some sharp contrasts in the parameterized complexity of this problem. First, we show that on apex-minor-free graphs, a general class of graphs containing planar graphs, graphs of bounded treewidth, and graphs of bounded genus, the problem to determine whether a given graph has spanning tree congestion at most k can be solved in linear time for every fixed k . We also show that for every fixed k and d the problem is solvable in linear time for graphs of degree at most d . In contrast, if we allow only one vertex of unbounded degree, the problem immediately becomes NP-complete for any fixed k ≥8. Moreover, the hardness result holds for graphs excluding the complete graph on 6 vertices as a minor. We also observe that for k ≤3 the problem becomes polynomially time solvable.

Approximation schemes are commonly classified as being either a polynomial-time approximation scheme (ptas) or a fully polynomial-time approximation scheme (fptas). To properly differentiate between approximation schemes for concrete problems, several subclasses have been identified: (optimum-)asymptotic schemes (ptas ∞ , fptas ∞ ), efficient schemes (eptas), and size-asymptotic schemes. We explore the structure of these subclasses, their mutual relationships, and their connection to the classic approximation classes. We prove that several of the classes are in fact equivalent. Furthermore, we prove the equivalence of eptas to so-called convergent polynomial-time approximation schemes. The results are used to refine the hierarchy of polynomial-time approximation schemes considerably and demonstrate the central position of eptas among approximation schemes. We also present two ways to bridge the hardness gap between asymptotic approximation schemes and classic approximation schemes. First, using notions from fixed-parameter complexity theory, we provide new characterizations of when problems have a ptas or fptas. Simultaneously, we prove that a large class of problems (including all MAX-SNP-complete problems) cannot have an optimum-asymptotic approximation scheme unless P=NP, thus strengthening results of Arora et al. (J. ACM 45(3):501–555, 1998 ). Secondly, we distinguish a new property exhibited by many optimization problems: pumpability. With this notion, we considerably generalize several problem-specific approaches to improve the effectiveness of approximation schemes with asymptotic behavior.

We give the first lower bounds on the grid size needed to represent the intersection graphs of~convex polygons. Here each corner of a polygon in the representation must lie on a corner of the grid. We provide a series of geometric constructions showing that for intersection graphs of: translated copies of any fixed parallelogram, grids of size Ω(n2) x Ω(n2) are needed; translated copies of any other fixed convex polygon, grids of size 2Ω(n) x 2Ω(n) are needed; homothetic copies of any fixed convex polygon, grids of size 2Ω(n) x 2Ω(n) are needed.