Fix a parameter k ∈ ℕ. We give dynamic data structures that for a fully dynamic undirected graph G, updated over time by edge insertions and edge deletions, can answer the following queries: - Long (u,v)-path: Given u,v ∈ V(G), is there a path from u to v of length at least k? - Long (u,v)-detour: Given u,v ∈ V(G), is there a path from u to v of length at least dist_G(u,v)+k? - Even/odd (u,v)-path: Given u,v ∈ V(G), is there a path from u to v of even/odd length? The amortized time of executing an update or answering a query is 2^𝒪(k³) log n + 𝒪(log² n log² log n) in the first two cases, and 𝒪(log² n log² log n) in the last, where n is the number of vertices of G. The first result is in sharp contrast with known conditional lower bounds for reporting paths of length at most k. Specifically, there is no data structure supporting queries about (u,v)-paths of length at most two in time n^o(1) unless the Triangle Conjecture fails. Our main technical contribution is a mechanism of "delayed edge insertion" that works locally on the level of biconnected components.

We introduce a new logic for describing properties of graphs, which we call low rank MSO. This is the fragment of monadic second-order logic in which set quantification is restricted to vertex sets of bounded cutrank. We prove the following statements about the expressive power of low rank MSO. - Over any class of graphs that is weakly sparse, low rank MSO has the same expressive power as separator logic. This equivalence does not hold over all graphs. - Over any class of graphs that has bounded VC dimension, low rank MSO has the same expressive power as flip-connectivity logic. This equivalence does not hold over all graphs. - Over all graphs, low rank MSO has the same expressive power as flip-reachability logic. Here, separator logic is an extension of first-order logic by basic predicates for checking connectivity, which was proposed by Bojańczyk [ArXiv 2107.13953] and by Schirrmacher, Siebertz, and Vigny [ACM ToCL 2023]. Flip-connectivity logic and flip-reachability logic are analogues of separator logic suited for non-sparse graphs, which we propose in this work. In particular, the last statement above implies that every property of undirected graphs expressible in low rank MSO can be decided in polynomial time.

In the Disjoint Shortest Paths problem one is given a graph \(G\) and a set \(\mathcal{T} = \{(s_1,t_1),\ldots,(s_k,t_k)\}\) of \(k\) vertex pairs. The question is whether there exist vertex-disjoint paths \(P_1,\ldots,P_k\) in \(G\) so that each \(P_i\) is a shortest path between \(s_i\) and \(t_i\). While the problem is known to be \(\textsf{W}\)[1]-hard in general, we show that it is fixed-parameter tractable on planar graphs with positive edge weights. Specifically, we propose an algorithm for Planar Disjoint Shortest Paths with running time \(2^{\mathcal{O}(k \log k)} \cdot n^{\mathcal{O}(1)}\). Notably, our parameter dependency is better than state-of-the-art \(2^{\mathcal{O}(k^2)}\) for the Planar Disjoint Paths problem, where the sought paths are not required to be shortest paths.

(First-order) transductions are a basic notion capturing graph modifications that can be described in first-order logic. In this work, we propose an efficient algorithmic method to approximately reverse the application of a transduction, assuming the source graph is sparse. Precisely, for any graph class C that has structurally bounded expansion (i.e., can be transduced from a class of bounded expansion), we give an O(n4)-time algorithm that given a graph G∈ C, computes a vertex-colored graph H such that G can be recovered from H using a first-order interpretation and H belongs to a graph class D of bounded expansion. This answers an open problem raised by Gajarský et al. [ACM TOCL, ’20]. In fact, for our procedure to work we only need to assume that C is monadically stable (i.e., does not transduce the class of all half-graphs) and has inherently linear neighborhood complexity (i.e., the neighborhood complexity is linear in all graph classes transducible from C). This renders the conclusion that the graph classes satisfying these two properties coincide with classes of structurally bounded expansion.

We prove that a number of computational problems that ask for the largest sparse induced subgraph satisfying some property definable in \(\mathsf{CMSO}_{2}\) logic, most notably Feedback Vertex Set , are polynomial-time solvable in the class of \(P_{6}\) -free graphs. This generalizes the work of Grzesik, Klimošová, Pilipczuk, and Pilipczuk on the Maximum Weight Independent Set problem in \(P_{6}\) -free graphs [SODA 2019, TALG 2022], and of Abrishami, Chudnovsky, Pilipczuk, Rzążewski, and Seymour on problems in \(P_{5}\) -free graphs [SODA 2021]. The key step is a new generalization of the framework of potential maximal cliques . We show that instead of listing a large family of potential maximal cliques, it is sufficient to only list their carvers : vertex sets that contain the same vertices from the sought solution and have similar separation properties.

We show that for any fixed integer k ⩾ 0, there exists an algorithm that computes the diameter and the eccentricies of all vertices of an input unweighted, undirected n-vertex graph of Euler genus at most k in time 𝒪_k(n^{2-1/25}). Furthermore, for the more general class of graphs that can be constructed by clique-sums from graphs that are of Euler genus at most k after deletion of at most k vertices, we show an algorithm for the same task that achieves the running time bound 𝒪_k(n^{2-1/356} log^{6k} n). Up to today, the only known subquadratic algorithms for computing the diameter in those graph classes are that of [Ducoffe, Habib, Viennot; SICOMP 2022], [Le, Wulff-Nilsen; SODA 2024], and [Duraj, Konieczny, Potępa; ESA 2024]. These algorithms work in the more general setting of K_h-minor-free graphs, but the running time bound is 𝒪_h(n^{2-c_h}) for some constant c_h > 0 depending on h. That is, our savings in the exponent of the polynomial function of n, as compared to the naive quadratic algorithm, are independent of the parameter k. The main technical ingredient of our work is an improved bound on the number of distance profiles, as defined in [Le, Wulff-Nilsen; SODA 2024], in graphs of bounded Euler genus.

We investigate the parameterised complexity of the classic coverability problem for vector addition systems (VAS): V ⊆ ℤ^d, an initial configuration s ∈ ℕ^d, and a target configuration t ∈ ℕ^d, decide whether starting from s, one can iteratively add vectors from V to ultimately arrive at a configuration that is larger than or equal to t on every coordinate, while not observing any negative value on any coordinate along the way. We consider two natural parameters for the problem: the dimension d and the size of V, defined as the total bitsize of its encoding. We present several results charting the complexity of those two parameterisations, among which the highlight is that coverability for VAS parameterised by the dimension and with all the numbers in the input encoded in unary is complete for the class XNL under PL-reductions. We also discuss open problems in the topic, most notably the question about fixed-parameter tractability for the parameterisation by the size of V.

We prove that the class of 3D-grids cannot be transduced from planar graphs, and more generally, from any class of graphs of bounded genus. To prove our result, we introduce a new structural tool called slice decompositions and study its properties. We show that every graph class transducible from a class of graphs of bounded genus is a perturbation of a graph class that admits slice decompositions. Moreover, we show that edge-stable graph classes that admit slice decomposition are transducible from weakly sparse graph classes that admits slice decompositions.

Cohen-Addad, Le, Pilipczuk, and Pilipczuk [CLPP23] recently constructed a stochastic embedding with expected 1 + ε distortion of n-vertex planar graphs (with polynomial aspect ratio) into graphs of treewidth O (ε-1 log13n ). Their embedding is the first to achieve polylogarithmic treewidth. However, there remains a large gap between the treewidth of their embedding and the treewidth lower bound of Ω(log n ) shown by Carroll and Goel [CG04]. In this work, we substantially narrow the gap by constructing a stochastic embedding with treewidth O (ε-1 log3 n ).

Abstract. In the disjoint paths problem, the input is an undirected graph [Formula: see text] on [Formula: see text] vertices and a set of [Formula: see text] vertex pairs, [Formula: see text], and the task is to find [Formula: see text] pairwise vertex-disjoint paths such that the [Formula: see text]’th path connects [Formula: see text] to [Formula: see text]. In this paper, we give a parameterized algorithm with running time [Formula: see text] for planar disjoint paths, the variant of the problem where the input graph is required to be planar. Our algorithm is based on the unique linkage/treewidth reduction theorem for planar graphs by Adler et al. [ J. Combin. Theory Ser. B, 122 (2017), pp. 815–843], the algebraic cohomology based technique of Schrijver [ SIAM J. Comput., 23 (1994), pp. 780–788], and one of the key combinatorial insights developed by Cygan et al. [ Proceedings of the 2013 IEEE 54 th Annual Symposium on Foundations of Computer Science, 2013, pp. 197–206] in their algorithm for disjoint paths on directed planar graphs. To the best of our knowledge, our algorithm is the first parameterized algorithm to exploit the fact that the treewidth of the input graph is small, and it does so in a way that is completely different from the use of dynamic programming.

In the Maximum Weight Independent Set of Rectangles problem (MWISR) we are given a weighted set of n axis-parallel rectangles in the plane. The task is to find a subset of pairwise non-overlapping rectangles with the maximum possible total weight. This problem is NP-hard and the best-known polynomial-time approximation algorithm, due to Chalermsook and Walczak [SODA 2021], achieves approximation factor 𝒪(log log n). While in the unweighted setting, constant factor approximation algorithms are known, due to Mitchell [FOCS 2021] and to Gálvez et al. [SODA 2022], it remains open to extend these techniques to the weighted setting. In this paper, we consider MWISR through the lens of parameterized approximation. Grandoni, Kratsch and Wiese [ESA 2019] gave a (1-ε)-approximation algorithm running in k^{𝒪(k/ε⁸)} n^{𝒪(1/ε⁸)} time, where k is the number of rectangles in an optimum solution. Unfortunately, their algorithm works only in the unweighted setting and they left it as an open problem to give a parameterized approximation scheme in the weighted setting. We give a parameterized approximation algorithm for MWISR that given a parameter k ∈ ℕ, finds a set of non-overlapping rectangles of weight at least (1-ε) opt_k in 2^{𝒪(k log(k/ε))} n^{𝒪(1/ε)} time, where opt_k is the maximum weight of a solution of cardinality at most k. We also propose a parameterized approximation scheme with running time 2^{𝒪(k² log(k/ε))} n^{𝒪(1)} that finds a solution with cardinality at most k and total weight at least (1-ε)opt_k for the special case of axis-parallel segments.

We design a randomized data structure that, for a fully dynamic graph $G$ updated by edge insertions and deletions and integers $k, d$ fixed upon initialization, maintains the answer to the Split Completion problem: whether one can add $k$ edges to $G$ to obtain a split graph. The data structure can be initialized on an edgeless $n$-vertex graph in time $n \cdot (k d \cdot \log n)^{\mathcal{O}(1)}$, and the amortized time complexity of an update is $5^k \cdot (k d \cdot \log n)^{\mathcal{O}(1)}$. The answer provided by the data structure is correct with probability $1-\mathcal{O}(n^{-d})$.

A graph class$\mathscr{C}$is called monadically stable if one cannot interpret, in first-order logic, arbitrary large linear orders in colored graphs from$\mathscr{C}$. We prove that the model checking problem for first-order logic is fixed-parameter tractable on every monadically stable graph class. This extends the results of [Grohe, Kreutzer, Siebertz; J. ACM '17] for nowhere dense classes and of [Dreier, Mählmann, Siebertz; STOC '23] for structurally nowhere dense classes to all monadically stable classes. This result is complemented by a hardness result showing that monadic stability is precisely the dividing line between tractability and intractability of first-order model checking on hereditary classes that are edge-stable: exclude some half-graph as a semi-induced subgraph. Precisely, we prove that for every hereditary graph class$\mathscr{C}$that is edge-stable but not monadically stable, first-order model checking is$\text{AW}[*]$-hard on$\mathscr{C}$, and W[1]-hard when restricted to existential sentences. This confirms, in the special case of edge-stable classes, an open conjecture that the notion of monadic dependence delimits the tractability of first-order model checking on hereditary classes of graphs. For our tractability result, we first prove that monadically stable graph classes have almost linear neighborhood complexity, by combining tools from stability theory and from sparsity theory. We then use this result to construct sparse neighborhood covers for monadically stable graph classes, which provides the missing ingredient for the algorithm of [Dreier, Mählmann, Siebertz; STOC '23]. The key component of this construction is the usage of orders with low crossing number [Welzl; SoCG '88], a tool from the area of range queries. For our hardness result, we first prove a new characterization of monadically stable graph classes in terms of forbidden induced subgraphs. We then use this characterization to show that in hereditary classes that are edge-stable but not monadically stable, one can efficiently interpret the class of all graphs using only existential formulas; this implies W[1]-hardness of model checking already for existential formulas.

We give an algorithm that, given graphs$G$and$H$, tests whether$H$is a minor of$G$in time$\mathcal{O}_{H}(\overline{n}^{1+o(1)})$; here,$n$is the number of vertices of$G$and the$\mathrm{O}_{H}(.)$-notation hides factors that depend on$H$and are computable. By the Graph Minor Theorem, this implies the existence of an$n^{1+o(1)}$-time membership test for every minor-closed class of graphs. More generally, we give an$\mathcal{O}_{H,\vert X\vert} (m^{1+o(1)})$-time algorithm for the rooted version of the problem, in which$G$comes with a set of roots$X\subseteq V(G)$and some of the branch sets of the sought minor model of$H$are required to contain prescribed subsets of$X$; here,$m$is the total number of vertices and edges of$G$. This captures the Disjoint Pathsproblem, for which we obtain an$\mathcal{O}_{k}(m^{1+o(1)\backslash }$-time algorithm, where$k$is the number of terminal pairs. For all the mentioned problems, the fastest algorithms known before are due to Kawarabayashi, Kobayashi, and Reed [JCTB 2012], and have a time complexity that is quadratic in the number of vertices of$G$. Our algorithm has two main ingredients: First, we show that by using the dynamic treewidth data structure of Korhonen, Majewski, Nadara, Pilipczuk, and Sokolowski [FOCS 2023], the irrelevant vertex technique of Robertson and Seymour can be implemented in almost-linear time on apex-minor-free graphs. Then, we apply the recent advances in almost-linear time flow/cut algorithms to give an almost-linear time implementation of the recursive understanding technique, which effectively reduces the problem to apex-minor-free graphs.

It is known that for subgraph-closed graph classes the first-order model checking problem is fixed-parameter tractable if and only if the class is nowhere dense [Grohe, Kreutzer, Siebertz, STOC 2014]. However, the dependency on the formula size is non-elementary, and in fact, this is unavoidable even for the class of all trees [Frick and Grohe, LICS 2002]. On the other hand, it is known that the dependency is elementary for classes of bounded degree [Frick and Grohe, LICS 2002] as well as for classes of bounded pathwidth [Lampis, ICALP 2023]. In this paper we generalise these results and almost completely characterise subgraph-closed graph classes for which the model checking problem is fixed-parameter tractable with an elementary dependency on the formula size. Those are the graph classes for which there exists a number d such that for every r, some tree of depth d and size bounded by an elementary function of r is avoided as an (≤r)-subdivision in all graphs in the class. In particular, this implies that if the class in question excludes a fixed tree as a topological minor, then first-order model checking for graphs in the class is fixed-parameter tractable with an elementary dependency on the formula size.

We prove that a number of computational problems that ask for the largest sparse induced subgraph satisfying some property definable in CMSO2 logic, most notably Feedback Vertex Set, are polynomial-time solvable in the class of P6-free graphs. This generalizes the work of Grzesik, Klimošová, Pilipczuk, and Pilipczuk on the Maximum Weight Independent Set problem in P6-free graphs [SODA 2019, TALG 2022], and of Abrishami, Chudnovsky, Pilipczuk, Rzążewski, and Seymour on problems in P5-free graphs [SODA 2021].

We study two classic variants of block-structured integer programming. Two-stage stochastic programs are integer programs of the form {Aix + Diyi = bi for all i = 1,…, n}, where Ai and Di are bounded-size matrices. Intuitively, this form corresponds to the setting when after setting a small set of global variables x, the program can be decomposed into a possibly large number of bounded-size subprograms. On the other hand, n-fold programs are integer programs of the form and Diyi = bi for all i = 1,…,n}, where again Ci and Di are bounded-size matrices. This form is natural for knapsack-like problems, where we have a large number of variables partitioned into small-size groups, each group needs to obey some set of local constraints, and there are only a few global constraints that link together all the variables.

In the Maximum Independent Set of Objects problem, we are given an n-vertex planar graph G and a family D of N objects, where each object is a connected subgraph of G. The task is to find a subfamily F ⊆ D of maximum cardinality that consists of pairwise disjoint objects. This problem is NP-hard and is equivalent to the problem of finding the maximum number of pairwise disjoint polygons in a given family of polygons in the plane.

We prove that every poset with bounded cliquewidth and with sufficiently large dimension contains the standard example of dimension k as a subposet. This applies in particular to posets whose cover graphs have bounded treewidth, as the cliquewidth of a poset is bounded in terms of the treewidth of the cover graph. For the latter posets, we prove a stronger statement: every such poset with sufficiently large dimension contains the Kelly example of dimension k as a subposet. Using this result, we obtain a full characterization of the minor-closed graph classes C such that posets with cover graphs in C have bounded dimension: they are exactly the classes excluding the cover graph of some Kelly example. Finally, we consider a variant of poset dimension called Boolean dimension, and we prove that posets with bounded cliquewidth have bounded Boolean dimension.

The classic technique of Baker [J. ACM ‘94] is the most fundamental approach for designing approximation schemes on planar, or more generally topologically-constrained graphs, and it has been applied in a myriad of different variants and settings throughout the last 30 years. In this work we propose a dynamic variant of Baker's technique, where instead of finding an approximate solution in a given static graph, the task is to design a data structure for maintaining an approximate solution in a fully dynamic graph, that is, a graph that is changing over time by edge deletions and edge insertions. Specifically, we address the two most basic problems — Maximum Weight Independent Set and Minimum Weight Dominating Set — and we prove the following: for a fully dynamic n-vertex planar graph G, one can

The well-known k-disjoint paths problem involves finding pairwise vertex-disjoint paths between k specified pairs of vertices within a given graph if they exist. In the shortest k-disjoint paths problem one looks for such paths of minimum total length. Despite nearly 50 years of active research on the k-disjoint paths problem, many open problems and complexity gaps still persist. A particularly well-defined scenario, inspired by VLSI design, focuses on infinite rectangular grids where the terminals are placed at arbitrary grid points. While the decision problem in this context remains NP-hard, no prior research has provided any positive results for the optimization version. The main result of this paper is a fixed-parameter tractable (FPT) algorithm for this scenario. It is important to stress that this is the first result achieving the FPT complexity of the shortest disjoint paths problem in any, even very restricted classes of graphs where we do not put any restriction on the placements of the terminals.

We study parameterized and approximation algorithms for a variant of Set Cover, where the universe of elements to be covered consists of points in the plane and the sets with which the points should be covered are segments. We call this problem Segment Set Cover. We also consider a relaxation of the problem called $δ$-extension, where we need to cover the points by segments that are extended by a tiny fraction, but we compare the solution's quality to the optimum without extension. For the unparameterized variant, we prove that Segment Set Cover does not admit a PTAS unless $\mathsf{P}=\mathsf{NP}$, even if we restrict segments to be axis-parallel and allow $\frac{1}{2}$-extension. On the other hand, we show that parameterization helps for the tractability of Segment Set Cover: we give an FPT algorithm for unweighted Segment Set Cover parameterized by the solution size $k$, a parameterized approximation scheme for Weighted Segment Set Cover with $k$ being the parameter, and an FPT algorithm for Weighted Segment Set Cover with $δ$-extension parameterized by $k$ and $δ$. In the last two results, relaxing the problem is probably necessary: we prove that Weighted Segment Set Cover without any relaxation is $\mathsf{W}[1]$-hard and, assuming ETH, there does not exist an algorithm running in time $f(k)\cdot n^{o(k / \log k)}$. This holds even if one restricts attention to axis-parallel segments.

We show that the Maximum Weight Independent Set problem (MWIS) can be solved in quasi-polynomial time on H-free graphs (graphs excluding a fixed graph H as an induced subgraph) for every H whose every connected component is a path or a subdivided claw (i.e., a tree with at most three leaves). This completes the dichotomy of the complexity of MWIS in F-free graphs for any finite set F of graphs into NP-hard cases and cases solvable in quasi-polynomial time, and corroborates the conjecture that the cases not known to be NP-hard are actually polynomial-time solvable. The key graph-theoretic ingredient in our result is as follows. Fix an integer t ≥ 1. Let St,t,t be the graph created from three paths on t edges by identifying one endpoint of each path into a single vertex. We show that, given a graph G, one can in polynomial time find either an induced St,t,t in G, or a balanced separator consisting of O(log|V(G)|) vertex neighborhoods in G, or an extended strip decomposition of G (a decomposition almost as useful for recursion for MWIS as a partition into connected components) with each particle of weight multiplicatively smaller than the weight of G. This is a strengthening of a result of Majewski, Masařík, Novotná, Okrasa, Pilipczuk, Rzążewski, and Sokołowski [Transactions on Computation Theory ‍2024] which provided such an extended strip decomposition only after the deletion of O(log|V(G)|) vertex neighborhoods. To reach the final result, we employ an involved branching strategy that relies on the structural lemma presented above.

Abstract We study the expressive power of polynomial recursive sequences, a nonlinear extension of the well-known class of linear recursive sequences. These sequences arise naturally in the study of nonlinear extensions of weighted automata, where (non)expressiveness results translate to class separations. A typical example of a polynomial recursive sequence is bn = n!. Our main result is that the sequence un = nn is not polynomial recursive.

Abstract. In the Maximum Independent Set problem we are asked to find a set of pairwise nonadjacent vertices in a given graph with the maximum possible cardinality. In general graphs, this classical problem is known to be NP-hard and hard to approximate within a factor of [Formula: see text] for any [Formula: see text]. Due to this, investigating the complexity of Maximum Independent Set in various graph classes in hope of finding better tractability results is an active research direction. In [Formula: see text]-free graphs, that is, graphs not containing a fixed graph [Formula: see text] as an induced subgraph, the problem is known to remain NP-hard and APX-hard whenever [Formula: see text] contains a cycle, a vertex of degree at least four, or two vertices of degree at least three in one connected component. For the remaining cases, where every component of [Formula: see text] is a path or a subdivided claw, the complexity of Maximum Independent Set remains widely open, with only a handful of polynomial-time solvability results for small graphs [Formula: see text] such as [Formula: see text], [Formula: see text], the claw, or the fork. We prove that for every such “possibly tractable” graph [Formula: see text] there exists an algorithm that, given an [Formula: see text]-free graph [Formula: see text] and an accuracy parameter [Formula: see text], finds an independent set in [Formula: see text] of cardinality within a factor of [Formula: see text] of the optimum in time exponential in a polynomial of [Formula: see text] and [Formula: see text]. Furthermore, an independent set of maximum size can be found in subexponential time [Formula: see text]. That is, we show that for every graph [Formula: see text] for which Maximum Independent Set is not known to be APX-hard and SUBEXP-hard in [Formula: see text]-free graphs, the problem admits a quasi-polynomial time approximation scheme and a subexponential-time exact algorithm in this graph class. Our algorithms also work in the more general weighted setting, where the input graph is supplied with a weight function on vertices and we are maximizing the total weight of an independent set.

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.

We prove that there is a randomized polynomialtime algorithm that given an edge-weighted graph G excluding a fixed-minor Q on n vertices and an accuracy parameter $\varepsilon\gt$ 0, constructs an edge-weighted graph H and an embedding $\eta: V(G) \rightarrow V(H)$ with the following properties:•For any constant size Q, the treewidth of H is polynomial in $\varepsilon^{-1}, \log n$, and the logarithm of the stretch of the distance metric in G.•The expected multiplicative distortion is $(1+\varepsilon)$: for every pair of vertices $u, v$ of G, we have $\operatorname{dist}_{H}(\eta(u), \eta(v)) \geqslant \operatorname{dist}_{G}(u, v)$ always and $\mathbb{E}\left[\operatorname{dist}_{H}(\eta(u), \eta(v))\right] \leqslant(1+\varepsilon) \operatorname{dist}_{G}(u, v)$. Our embedding is the first to achieve polylogarithmic treewidth of the host graph and comes close to the lower bound by Carroll and Goel, who showed that any embedding of a planar graph with $\mathcal{O}(1)$ expected distortion requires the host graph to have treewidth $\Omega(\log n)$. It also provides a unified framework for obtaining randomized quasi-polynomial-time approximation schemes for a variety of problems including network design, clustering or routing problems, in minor-free metrics where the optimization goal is the sum of selected distances. Applications include the capacitated vehicle routing problem, and capacitated clustering problems.

We present a data structure that for a dynamic graph G that is updated by edge insertions and deletions, maintains a tree decomposition of G of width at most $6 k+5$ under the promise that the treewidth of G never grows above k. The amortized update time is $\mathcal{O}_{k}\left(2^{\sqrt{\log n} \log \log n}\right)$, where n is the vertex count of G and the $\mathcal{O}_{k}(\cdot)$ notation hides factors depending on k. In addition, we also obtain the dynamic variant of Courcelle’s Theorem: for any fixed property $\varphi$ expressible in the CMSO2logic, the data structure can maintain whether G satisfies $\varphi$ within the same time complexity bounds. To a large extent, this answers a question posed by Bodlaender [WG 1993].

We investigate the parameterized complexity of Binary CSP parameterized by the vertex cover number and the treedepth of the constraint graph, as well as by a selection of related modulator-based parameters. The main findings are as follows: i) Binary CSP parameterized by the vertex cover number is $\mathrm{W}[3]$-complete. More generally, for every positive integer $d$, Binary CSP parameterized by the size of a modulator to a treedepth-d graph is $\mathrm{W}[2d+1]$-complete. This provides a new family of natural problems that are complete for odd levels of the W-hierarchy. ii) We introduce a new complexity class XSLP, defined so that Binary CSP parameterized by treedepth is complete for this class. We provide two equivalent characterizations of XSLP: the first one relates XSLP to a model of an alternating Turing machine with certain restrictions on conondeterminism and space complexity, while the second one links XSLP to the problem of model-checking first-order logic with suitably restricted universal quantification. Interestingly, the proof of the machine characterization of XSLP uses the concept of universal trees, which are prominently featured in the recent work on parity games iii) We describe a new complexity hierarchy sandwiched between the W-hierarchy and the A-hierarchy: For every odd $t$, we introduce a parameterized complexity class $\mathrm{S}[t]$ with $\mathrm{W}[t]\subseteq \mathrm{S}[t]\subseteq \mathrm{A}[t]$, defined using a parameter that interpolates between the vertex cover number and the treedepth. We expect that many of the studied classes will be useful in the future for pinpointing the complexity of various structural parameterizations of graph problems.

A class of graphs $\mathscr{C}$ is monadically stable if for any unary expansion $\widehat{\mathscr{C}}$ of $\mathscr{C}$, one cannot interpret, in first-order logic, arbitrarily long linear orders in graphs from $\widehat{\mathscr{C}}$. It is known that nowhere dense graph classes are monadically stable; these encompass most of the studied concepts of sparsity in graphs, including graph classes that exclude a fixed topological minor. On the other hand, monadic stability is a property expressed in purely model-theoretic terms and hence it is also suited for capturing structure in dense graphs. For several years, it has been suspected that one can create a structure theory for monadically stable graph classes that mirrors the theory of nowhere dense graph classes in the dense setting. In this work we provide a step in this direction by giving a characterization of monadic stability through the Flipper game: a game on a graph played by Flipper, who in each round can complement the edge relation between any pair of vertex subsets, and Connector, who in each round localizes the game to a ball of bounded radius. This is an analog of the Splitter game, which characterizes nowhere dense classes of graphs (Grohe, Kreutzer, and Siebertz, J.ACM'17). We give two different proofs of our main result. The first proof uses tools from model theory, and it exposes an additional property of monadically stable graph classes that is close in spirit to definability of types. Also, as a byproduct, we give an alternative proof of the recent result of Braunfeld and Laskowski (arXiv 2209.05120) that monadic stability for graph classes coincides with existential monadic stability. The second proof relies on the recently introduced notion of flip-wideness (Dreier, Mählmann, Siebertz, and Toruńczyk, ICALP 2023) and provides an efficient algorithm to compute Flipper's moves in a winning strategy.

We use model-theoretic tools originating from stability theory to derive a result we call the Finitary Substitute Lemma, which intuitively says the following. Suppose we work in a stable graph class C, and using a first-order formula ϕ with parameters we are able to define, in every graph G in C, a relation R that satisfies some hereditary first-order assertion ψ. Then we are able to find a first-order formula ϕ' that has the same property, but additionally is finitary: there is finite bound k such that in every graph G in C, different choices of parameters give only at most k different relations R that can be defined using ϕ'. We use the Finitary Substitute Lemma to derive two corollaries about the existence of certain canonical decompositions in classes of well-structured graphs. - We prove that in the Splitter game, which characterizes nowhere dense graph classes, and in the Flipper game, which characterizes monadically stable graph classes, there is a winning strategy for Splitter, respectively Flipper, that can be defined in first-order logic from the game history. Thus, the strategy is canonical. - We show that for any fixed graph class C of bounded shrubdepth, there is an O(n^2)-time algorithm that given an n-vertex graph G in C, computes in an isomorphism-invariant way a structure H of bounded treedepth in which G can be interpreted. A corollary of this result is an O(n^2)-time isomorphism test and canonization algorithm for any fixed class of bounded shrubdepth.

final_published

Let 𝜑 be a sentence of CMSO₂ (monadic second-order logic with quantification over edge subsets and counting modular predicates) over the signature of graphs. We present a dynamic data structure that for a given graph G that is updated by edge insertions and edge deletions, maintains whether 𝜑 is satisfied in G. The data structure is required to correctly report the outcome only when the feedback vertex number of G does not exceed a fixed constant k, otherwise it reports that the feedback vertex number is too large. With this assumption, we guarantee amortized update time O_{𝜑,k}(log n). By combining this result with a classic theorem of Erdős and Pósa, we give a fully dynamic data structure that maintains whether a graph contains a packing of k vertex-disjoint cycles with amortized update time O_k(log n). Our data structure also works in a larger generality of relational structures over binary signatures.

We revisit classic string problems considered in the area of parameterized complexity, and study them through the lens of dynamic data structures. That is, instead of asking for a static algorithm that solves the given instance efficiently, our goal is to design a data structure that efficiently maintains a solution, or reports a lack thereof, upon updates in the instance. We first consider the Closest String problem, for which we design randomized dynamic data structures with amortized update times $d^{\mathcal{O}(d)}$ and $|Σ|^{\mathcal{O}(d)}$, respectively, where $Σ$ is the alphabet and $d$ is the assumed bound on the maximum distance. These are obtained by combining known static approaches to Closest String with color-coding. Next, we note that from a result of Frandsen et al.~[J. ACM'97] one can easily infer a meta-theorem that provides dynamic data structures for parameterized string problems with worst-case update time of the form $\mathcal{O}(\log \log n)$, where $k$ is the parameter in question and $n$ is the length of the string. We showcase the utility of this meta-theorem by giving such data structures for problems Disjoint Factors and Edit Distance. We also give explicit data structures for these problems, with worst-case update times $\mathcal{O}(k2^{k}\log \log n)$ and $\mathcal{O}(k^2\log \log n)$, respectively. Finally, we discuss how a lower bound methodology introduced by Amarilli et al.~[ICALP'21] can be used to show that obtaining update time $\mathcal{O}(f(k))$ for Disjoint Factors and Edit Distance is unlikely already for a constant value of the parameter $k$.

Abstract. For many algorithmic problems on graphs of treewidth [Formula: see text], a standard dynamic programming approach gives algorithms with time and space complexity [Formula: see text]. It turns out that when one considers the more restrictive parameter treedepth, it is often the case that a variation of this technique can be used to reduce the space complexity to polynomial, while retaining time complexity of the form [Formula: see text], where [Formula: see text] is the treedepth. This transfer of methodology is, however, far from automatic. For instance, for problems with connectivity constraints, standard dynamic programming techniques give algorithms with time and space complexity [Formula: see text] on graphs of treewidth [Formula: see text], but it is not clear how to convert them into time-efficient polynomial space algorithms for graphs of low treedepth. Cygan et al. [ ACM Trans. Algorithms, 18 (2022), 17] introduced the Cut&Count technique and showed that a certain class of problems with connectivity constraints can be solved in time and space complexity [Formula: see text]. Recently, Hegerfeld and Kratsch (STACS’20) showed that, for some of those problems, the Cut&Count technique can be also applied in the setting of treedepth, and it gives algorithms with running time [Formula: see text] and polynomial space usage. However, several important problems eluded such a treatment, with the most prominent examples being Hamiltonian Cycle and Longest Path. In this paper, we clarify the situation by showing that Hamiltonian cycle, Hamiltonian Path, Long Cycle, Long Path, and Min Cycle Cover all admit [Formula: see text]-time and polynomial space algorithms on graphs of treedepth [Formula: see text]. The algorithms are randomized Monte Carlo with only false negatives.

The treedepth of a graph G is the least possible depth of an elimination forest of G: a rooted forest on the same vertex set where every pair of vertices adjacent in G is bound by the ancestor/descendant relation. We propose an algorithm that given a graph G and an integer d, either finds an elimination forest of G of depth at most d or concludes that no such forest exists; thus the algorithm decides whether the treedepth of G is at most d. The running time is 2^𝒪(d²)⋅n^𝒪(1) and the space usage is polynomial in n. Further, by allowing randomization, the time and space complexities can be improved to 2^𝒪(d²)⋅n and d^𝒪(1)⋅n, respectively. This improves upon the algorithm of Reidl et al. [ICALP 2014], which also has time complexity 2^𝒪(d²)⋅n, but uses exponential space.

We study problems connected to first-order logic in graphs of bounded twin-width. Inspired by the approach of Bonnet et al. [FOCS 2020], we introduce a robust methodology of local types and describe their behavior in contraction sequences - the decomposition notion underlying twin-width. We showcase the applicability of the methodology by proving the following two algorithmic results. In both statements, we fix a first-order formula φ(x_1,…,x_k) and a constant d, and we assume that on input we are given a graph G together with a contraction sequence of width at most d. - One can in time 𝒪(n) construct a data structure that can answer the following queries in time 𝒪(log log n): given w_1,…,w_k, decide whether φ(w_1,…,w_k) holds in G. - After 𝒪(n)-time preprocessing, one can enumerate all tuples w₁,…,w_k that satisfy φ(x_1,…,x_k) in G with 𝒪(1) delay. In the first case, the query time can be reduced to 𝒪(1/ε) at the expense of increasing the construction time to 𝒪(n^{1+ε}), for any fixed ε > 0. Finally, we also apply our tools to prove the following statement, which shows optimal bounds on the VC density of set systems that are first-order definable in graphs of bounded twin-width. - Let G be a graph of twin-width d, A be a subset of vertices of G, and φ(x_1,…,x_k,y_1,…,y_l) be a first-order formula. Then the number of different subsets of A^k definable by φ using l-tuples of vertices from G as parameters, is bounded by O(|A|^l).

We introduce a new data structure for answering connectivity queries in undirected graphs subject to batched vertex failures. Precisely, given any graph G and integer parameter k, we can in fixed-parameter time construct a data structure that can later be used to answer queries of the form: "are vertices s and t connected via a path that avoids vertices u₁,…, u_k?" in time 2^𝒪(k). In the terminology of the literature on data structures, this gives the first deterministic data structure for connectivity under vertex failures where for every fixed number of failures, all operations can be performed in constant time. With the aim to understand the power and the limitations of our new techniques, we prove an algorithmic meta theorem for the recently introduced separator logic, which extends first-order logic with atoms for connectivity under vertex failures. We prove that the model-checking problem for separator logic is fixed-parameter tractable on every class of graphs that exclude a fixed topological minor. We also show a weak converse. This implies that from the point of view of parameterized complexity, under standard complexity theoretical assumptions, the frontier of tractability of separator logic is almost exactly delimited by classes excluding a fixed topological minor. The backbone of our proof relies on a decomposition theorem of Cygan, Lokshtanov, Pilipczuk, Pilipczuk, and Saurabh [SICOMP '19], which provides a tree decomposition of a given graph into bags that are unbreakable. Crucially, unbreakability allows to reduce separator logic to plain first-order logic within each bag individually. Guided by this observation, we design our model-checking algorithm using dynamic programming over the tree decomposition, where the transition at each bag amounts to running a suitable model-checking subprocedure for plain first-order logic. This approach is robust enough to provide also an extension to efficient enumeration of answers to a query expressed in separator logic.

In this paper, we introduce a new class of parameterized problems, which we call XALP: the class of all parameterized problems that can be solved in $f(k)n^{O(1)}$ time and $f(k)\log n$ space on a non-deterministic Turing Machine with access to an auxiliary stack (with only top element lookup allowed). Various natural problems on `tree-structured graphs' are complete for this class: we show that List Colouring and All-or-Nothing Flow parameterized by treewidth are XALP-complete. Moreover, Independent Set and Dominating Set parameterized by treewidth divided by $\log n$, and Max Cut parameterized by cliquewidth are also XALP-complete. Besides finding a `natural home' for these problems, we also pave the road for future reductions. We give a number of equivalent characterisations of the class XALP, e.g., XALP is the class of problems solvable by an Alternating Turing Machine whose runs have tree size at most $f(k)n^{O(1)}$ and use $f(k)\log n$ space. Moreover, we introduce `tree-shaped' variants of Weighted CNF-Satisfiability and Multicolour Clique that are XALP-complete.

We give new decomposition theorems for classes of graphs that can be transduced in first-order logic from classes of sparse graphs — more precisely, from classes of bounded expansion and nowhere dense classes. In both cases, the decomposition takes the form of a single colored rooted tree of bounded depth where, in addition, there can be links between nodes that are not related in the tree. The constraint is that the structure formed by the tree and the links has to be sparse. Using the decomposition theorem for transductions of nowhere dense classes, we show that they admit low-shrubdepth covers of size , where n is the vertex count and ε > 0 is any fixed real. This solves an open problem posed by Gajarský et al. (ACM TOCL ’20) and also by Briański et al. (SIDMA ’21).

We prove that every class of graphs that is monadically stable and has bounded twin-width can be transduced from some class with bounded sparse twin-width. This generalizes analogous results for classes of bounded linear cliquewidth [Nešetřil et al. 2021b] and of bounded cliquewidth [Nešetřil et al. 2021a]. It also implies that monadically stable classes of bounded twin-width are linearly χ-bounded.

The Isolation Lemma of Mulmuley, Vazirani and Vazirani [Combinatorica'87] provides a self-reduction scheme that allows one to assume that a given instance of a problem has a unique solution, provided a solution exists at all. Since its introduction, much effort has been dedicated towards derandomization of the Isolation Lemma for specific classes of problems. So far, the focus was mainly on problems solvable in polynomial time. In this paper, we study a setting that is more typical for $\mathsf{NP}$-complete problems, and obtain partial derandomizations in the form of significantly decreasing the number of required random bits. In particular, motivated by the advances in parameterized algorithms, we focus on problems on decomposable graphs. For example, for the problem of detecting a Hamiltonian cycle, we build upon the rank-based approach from [Bodlaender et al., Inf. Comput.'15] and design isolation schemes that use - $O(t\log n + \log^2{n})$ random bits on graphs of treewidth at most $t$; - $O(\sqrt{n})$ random bits on planar or $H$-minor free graphs; and - $O(n)$-random bits on general graphs. In all these schemes, the weights are bounded exponentially in the number of random bits used. As a corollary, for every fixed $H$ we obtain an algorithm for detecting a Hamiltonian cycle in an $H$-minor-free graph that runs in deterministic time $2^{O(\sqrt{n})}$ and uses polynomial space; this is the first algorithm to achieve such complexity guarantees. For problems of more local nature, such as finding an independent set of maximum size, we obtain isolation schemes on graphs of treedepth at most $d$ that use $O(d)$ random bits and assign polynomially-bounded weights. We also complement our findings with several unconditional and conditional lower bounds, which show that many of the results cannot be significantly improved.

For every fixed $d \in \mathbb{N}$, we design a data structure that represents a binary $n \times n$ matrix that is $d$-twin-ordered. The data structure occupies $O_d(n)$ bits, which is the least one could hope for, and can be queried for entries of the matrix in time $O_d(\log \log n)$ per query.

We prove that Graph Isomorphism and Canonization in graphs excluding a fixed graph H as a minor can be solved by an algorithm working in time f(H)· nO(1), where f is some function. In other words, we show that these problems are fixed-parameter tractable when parameterized by the size of the excluded minor, with the caveat that the bound on the running time is not necessarily computable. The underlying approach is based on decomposing the graph in a canonical way into unbreakable (intuitively, well-connected) parts, which essentially provides a reduction to the case where the given H-minor-free graph is unbreakable itself. This is complemented by an analysis of unbreakable H-minor-free graphs, which reveals that every such graph can be canonically decomposed into a part that admits few automorphisms and a part that has bounded treewidth.

Abstract We study a variant of the classical membership problem in automata theory, which consists of deciding whether a given input word is accepted by a given automaton. We do so through the lenses of parameterized dynamic data structures: we assume that the automaton is fixed and its size is the parameter, while the input word is revealed as in a stream, one symbol at a time following the natural order on positions. The goal is to design a dynamic data structure that can be efficiently updated upon revealing the next symbol, while maintaining the answer to the query on whether the word consisting of symbols revealed so far is accepted by the automaton. We provide complexity bounds for this dynamic acceptance problem for timed automata that process symbols interleaved with time spans. The main contribution is a dynamic data structure that maintains acceptance of a fixed one-clock timed automaton $${\mathcal {A}}$$ A with amortized update time $$2^{{\mathcal {O}}(|{\mathcal {A}}|)}$$ 2 O ( | A | ) per input symbol.

The classic algorithm of Bodlaender and Kloks [J. Algorithms, 1996] solves the following problem in linear fixed-parameter time: given a tree decomposition of a graph of (possibly suboptimal) width k, compute an optimum-width tree decomposition of the graph. In this work, we prove that this problem can also be solved in mso in the following sense: for every positive integer k, there is an mso transduction from tree decompositions of width k to tree decompositions of optimum width. Together with our recent results [LICS 2016], this implies that for every k there exists an mso transduction which inputs a graph of treewidth k, and nondeterministically outputs its tree decomposition of optimum width. We also show that mso transductions can be implemented in linear fixed-parameter time, which enables us to derive the algorithmic result of Bodlaender and Kloks as a corollary of our main result.

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.

For the vast majority of local problems on graphs of small treewidth (where, by local we mean that a solution can be verified by checking separately the neighbourhood of each vertex), standard dynamic programming techniques give c tw | V | O(1) time algorithms, where tw is the treewidth of the input graph G = ( V,E ) and c is a constant. On the other hand, for problems with a global requirement (usually connectivity) the best–known algorithms were naive dynamic programming schemes running in at least tw tw time. We bridge this gap by introducing a technique we named Cut&Count that allows to produce c tw | V | O(1) time Monte-Carlo algorithms for most connectivity-type problems, including Hamiltonian Path , Steiner Tree , Feedback Vertex Set and Connected Dominating Set . These results have numerous consequences in various fields, like parameterized complexity, exact and approximate algorithms on planar and H -minor-free graphs and exact algorithms on graphs of bounded degree. The constant c in our algorithms is in all cases small, and in several cases we are able to show that improving those constants would cause the Strong Exponential Time Hypothesis to fail. In all these fields we are able to improve the best-known results for some problems. Also, looking from a more theoretical perspective, our results are surprising since the equivalence relation that partitions all partial solutions with respect to extendability to global solutions seems to consist of at least tw tw equivalence classes for all these problems. Our results answer an open problem raised by Lokshtanov, Marx and Saurabh [SODA’11]. In contrast to the problems aimed at minimizing the number of connected components that we solve using Cut&Count as mentioned above, we show that, assuming the Exponential Time Hypothesis, the aforementioned gap cannot be bridged for some problems that aim to maximize the number of connected components like Cycle Packing .

In the classic Maximum Weight Independent Set problem, we are given a graph G with a nonnegative weight function on its vertices, and the goal is to find an independent set in G of maximum possible weight. While the problem is NP-hard in general, we give a polynomial-time algorithm working on any P 6 -free graph, that is, a graph that has no path on 6 vertices as an induced subgraph. This improves the polynomial-time algorithm on P 5 -free graphs of Lokshtanov et al. [ 15 ] and the quasipolynomial-time algorithm on P 6 -free graphs of Lokshtanov et al. [ 14 ]. The main technical contribution leading to our main result is enumeration of a polynomial-size family ℱ of vertex subsets with the following property: For every maximal independent set I in the graph, ℱ contains all maximal cliques of some minimal chordal completion of G that does not add any edge incident to a vertex of I .

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 .

We consider the problem of solving integer programs of the form $\min \{\,c^\intercal x\ \colon\ Ax=b, x\geq 0\}$, where $A$ is a multistage stochastic matrix in the following sense: the primal treedepth of $A$ is bounded by a parameter $d$, which means that the columns of $A$ can be organized into a rooted forest of depth at most $d$ so that columns not bound by the ancestor/descendant relation in the forest do not have non-zero entries in the same row. We give an algorithm that solves this problem in fixed-parameter time $f(d,\|A\|_{\infty})\cdot n\log^{O(2^d)} n$, where $f$ is a computable function and $n$ is the number of rows of $A$. The algorithm works in the strong model, where the running time only measures unit arithmetic operations on the input numbers and does not depend on their bitlength. This is the first fpt algorithm for multistage stochastic integer programming to achieve almost linear running time in the strong sense. For the case of two-stage stochastic integer programs, our algorithm works in time $2^{(2\|A\|_\infty)^{O(r(r+s))}}\cdot n\log^{O(rs)} n$. The algorithm can be also parallelized: we give an implementation in the PRAM model that achieves running time $f(d,\|A\|_{\infty})\cdot \log^{O(2^d)} n$ using $n$ processors. The main conceptual ingredient in our algorithms is a new proximity result for multistage stochastic integer programs. We prove that if we consider an integer program $P$, say with a constraint matrix $A$, then for every optimum solution to the linear relaxation of $P$ there exists an optimum (integral) solution to $P$ that lies, in the $\ell_{\infty}$-norm, within distance bounded by a function of $\|A\|_{\infty}$ and the primal treedepth of $A$. On the way to achieve this result, we prove a generalization and considerable improvement of a structural result of Klein for multistage stochastic integer programs.

Ensuring the correctness of distributed cyber-physical systems can be done at runtime by monitoring properties over their behaviour. In a decentralised setting, such behaviour consists of multiple local traces, each offering an incomplete view of the system events to the local monitors, as opposed to the standard centralised setting with a unique global trace. We introduce the first monitoring framework for timed properties described by timed regular expressions over a distributed network of monitors. First, we define functions to rewrite expressions according to partial knowledge for both the centralised and decentralised cases. Then, we define decentralised algorithms for monitors to evaluate properties using these functions, as well as proofs of soundness and eventual completeness of said algorithms. Finally, we implement and evaluate our framework on synthetic timed regular expressions, giving insights on the cost of the centralised and decentralised settings and when to best use each of them.

We present a data structure that in a dynamic graph of treedepth at most d, which is modified over time by edge insertions and deletions, maintains an optimum-height elimination forest. The data structure achieves worst-case update time , which matches the best known parameter dependency in the running time of a static fpt algorithm for computing the treedepth of a graph. This improves a result of Dvořák et al. [ESA 2014], who for the same problem achieved update time f(d) for some non-elementary (i.e. tower-exponential) function f. As a by-product, we improve known upper bounds on the sizes of minimal obstructions for having treedepth d from doubly-exponential in d to dO(d). As applications, we design new fully dynamic parameterized data structures for detecting long paths and cycles in general graphs. More precisely, for a fixed parameter k and a dynamic graph G, modified over time by edge insertions and deletions, our data structures maintain answers to the following queries: Does G contain a simple path on k vertices? Does G contain a simple cycle on at least k vertices? In the first case, the data structure achieves amortized update time . In the second case, the amortized update time is . In both cases we assume access to a dictionary on the edges of G.

We study two notions of being well-structured for classes of graphs that are inspired by classic model theory. A class of graphs is monadically stable if it is impossible to define arbitrarily long linear orders in vertex-colored graphs from using a fixed first-order formula. Similarly, monadic dependence corresponds to the impossibility of defining all graphs in this way. Examples of monadically stable graph classes are nowhere dense classes, which provide a robust theory of sparsity. Examples of monadically dependent classes are classes of bounded rankwidth (or equivalently, bounded cliquewidth), which can be seen as a dense analog of classes of bounded treewidth. Thus, monadic stability and monadic dependence extend classical structural notions for graphs by viewing them in a wider, model-theoretical context. We explore this emerging theory by proving the following: 1) A class of graphs is a first-order transduction of a class with bounded treewidth if and only if has bounded rankwidth and a stable edge relation (i.e. graphs from exclude some half-graph as a semi-induced subgraph). 2) If a class of graphs is monadically dependent and not monadically stable, then has in fact an unstable edge relation. As a consequence, we show that classes with bounded rankwidth excluding some half-graph as a semi-induced subgraph are linearly χ-bounded. Our proofs are effective and lead to polynomial time algorithms.

For an integer t, a graph G is called C>t-free if G does not contain any induced cycle on more than t vertices. We prove the following statement: for every pair of integers d and t and a statement φ, there exists an algorithm that, given an n-vertex C>t-free graph G with weights on vertices, finds in time n(log3 n) a maximum-weight vertex subset S such that G[S] has degeneracy at most d and satisfies φ. The running time can be improved to n(log2 n) assuming G is Pt-free, that is, G does not contain an induced path on t vertices. This expands the recent results of the authors [FOCS 2020 and SOSA 2021] on the Maximum Weight Independent Set problem on Pt-free graphs in two directions: by encompassing the more general setting of C>t-free graphs, and by being applicable to a much wider variety of problems, such as Maximum Weight Induced Forest or Maximum Weight Induced Planar Graph.

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 prove that for every nowhere dense class of graphs $\mathcal{C}$, positive integer $d$, and $\varepsilon>0$, the following holds: in every $n$-vertex graph $G$ from $\mathcal{C}$ one can find two disjoint vertex subsets $A,B\subseteq V(G)$ such that $|A|\geq (1/2-\varepsilon)\cdot n$ and $|B|=\Omega(n^{1-\varepsilon})$; and either ${dist}(a,b)\leq d$ for all $a\in A$ and $b\in B$, or ${dist}(a,b)>d$ for all $a\in A$ and $b\in B$. We also show some stronger variants of this statement, including a generalization to the setting of first-order interpretations of nowhere dense graph classes.

We study the Max Partial $H$-Coloring problem: given a graph $G$, find the largest induced subgraph of $G$ that admits a homomorphism into $H$, where $H$ is a fixed pattern graph without loops. Note that when $H$ is a complete graph on $k$ vertices, the problem reduces to finding the largest induced $k$-colorable subgraph, which for $k=2$ is equivalent (by complementation) to Odd Cycle Transversal. We prove that for every fixed pattern graph $H$ without loops, Max Partial $H$-Coloring can be solved in $\{P_5,F\}$-free graphs in polynomial time, whenever $F$ is a threshold graph; in $\{P_5,{bull}\}$-free graphs in polynomial time; in $P_5$-free graphs in time $n^{\mathcal{O}(\omega(G))}$; and in $\{P_6,{1-subdivided claw}\}$-free graphs in time $n^{\mathcal{O}(\omega(G)^3)}$. Here, $n$ is the number of vertices of the input graph $G$ and $\omega(G)$ is the maximum size of a clique in $G$. Furthermore, by combining the mentioned algorithms for $P_5$-free and for $\{P_6,{1-subdivided claw}\}$-free graphs with a simple branching procedure, we obtain subexponential-time algorithms for Max Partial $H$-Coloring in these classes of graphs. Finally, we show that even a restricted variant of Max Partial $H$-Coloring is $\mathsf{NP}$-hard in the considered subclasses of $P_5$-free graphs if we allow loops on $H$.

Suppose ${\mathcal{F}}$ is a finite family of graphs. We consider the following meta-problem, called $\mathcal{F}$-Immersion Deletion: given a graph $G$ and integer $k$, decide whether the deletion of at most $k$ edges of $G$ can result in a graph that does not contain any graph from $\mathcal{F}$ as an immersion. This problem is a close relative of the $\mathcal{F}$-Minor Deletion problem studied by Fomin et al. [ Proceedings of FOCS, IEEE, 2012, pp. 470--479], where one deletes vertices in order to remove all minor models of graphs from $\mathcal{F}$. We prove that whenever all graphs from $\mathcal{F}$ are connected and at least one graph of $\mathcal{F}$ is planar and subcubic, then the $\mathcal{F}$-Immersion Deletion problem admits a constant-factor approximation algorithm running in time $\mathcal{O}(m^3 \cdot n^3 \cdot \log m)$, a linear kernel that can be computed in time $\mathcal{O}(m^4 \cdot n^3 \cdot \log m)$, and a $\mathcal{O}(2^{\mathcal{O}(k)} + m^4 \cdot n^3 \cdot \log m)$-time fixed-parameter algorithm, where $n,m$ count the vertices and edges of the input graph. These results mirror the findings of Fomin et al., who obtained a similar set of algorithmic results for $\mathcal{F}$-Minor Deletion, under the assumption that at least one graph from $\mathcal{F}$ is planar. An important difference is that we are able to obtain a linear kernel for $\mathcal{F}$-Immersion Deletion, while the exponent of the kernel of Fomin et al. for $\mathcal{F}$-Minor Deletion depends heavily on the family $\mathcal{F}$. In fact, this dependence is unavoidable under plausible complexity assumptions, as proven by Giannopoulou et al. [ ACM Trans. Algorithms, 13 (2017), p. 35]. This reveals that the kernelization complexity of $\mathcal{F}$-Immersion Deletion is quite different from that of $\mathcal{F}$-Minor Deletion.

We show an algorithm that, given an n -vertex graph G and a parameter k , in time 2 O ( k log k ) n O (1) finds a tree decomposition of G with the following properties: — every adhesion of the tree decomposition is of size at most k , and — every bag of the tree decomposition is ( i , i )-unbreakable in G for every 1 ⩽ i ⩽ k . Here, a set X ⊆ V ( G ) is ( a , b )-unbreakable in G if for every separation ( A , B ) of order at most b in G , we have | A \cap X | ⩽ a or | B ∩ X | ⩽ a . The resulting tree decomposition has arguably best possible adhesion size bounds and unbreakability guarantees. Furthermore, the parametric factor in the running time bound is significantly smaller than in previous similar constructions. These improvements allow us to present parameterized algorithms for M INIMUM B ISECTION , S TEINER C UT , and S TEINER M ULTICUT with improved parameteric factor in the running time bound. The main technical insight is to adapt the notion of lean decompositions of Thomas and the subsequent construction algorithm of Bellenbaum and Diestel to the parameterized setting.

The use of random samples to approximate properties of geometric configurations has been an influential idea for both combinatorial and algorithmic purposes. This chapter considers two related notions---$ε$-approximations and $ε$-nets---that capture the most important quantitative properties that one would expect from a random sample with respect to an underlying geometric configuration.

An adjacency labeling scheme for a given class of graphs is an algorithm that, for every graph $G$ from the class, assigns bit strings (labels) to vertices of $G$ so that for any two vertices $u,v$, whether $u$ and $v$ are adjacent can be determined by a fixed procedure that examines only their labels. It is known that planar graphs with $n$ vertices admit a labeling scheme with labels of bit length $(2+o(1))\log{n}$. In this work we improve this bound by designing a labeling scheme with labels of bit length $(\frac{4}{3}+o(1))\log{n}$. All the labels of the input graph can be computed in polynomial time, while adjacency can be decided from the labels in constant time. In graph-theoretical terms, this implies an explicit construction of a graph on $n^{4/3+o(1)}$ vertices that contains all planar graphs on $n$ vertices as induced subgraphs, improving the previous best upper bound of $n^{2+o(1)}$. Our labeling scheme can be generalized to larger classes of topologically constrained graphs, for instance, to graphs embeddable in any fixed surface or to $k$-planar graphs for any fixed $k$, at the cost of larger second-order terms.

In the Maximum Independent Set problem we are asked to find a set of pairwise nonadjacent vertices in a given graph with the maximum possible cardinality. In general graphs, this classical problem is known to be NP-hard and hard to approximate within a factor of n1−ε for any ε > 0. Due to this, investigating the complexity of Maximum Independent Set in various graph classes in hope of finding better tractability results is an active research direction. In H-free graphs, that is, graphs not containing a fixed graph H as an induced subgraph, the problem is known to remain NP-hard and APX-hard whenever H contains a cycle, a vertex of degree at least four, or two vertices of degree at least three in one connected component. For the remaining cases, where every component of H is a path or a subdivided claw, the complexity of Maximum Independent Set remains widely open, with only a handful of polynomial-time solvability results for small graphs H such as P5, P6, the claw, or the fork. We prove that for every such “possibly tractable” graph H there exists an algorithm that, given an H-free graph G and an accuracy parameter ε > 0, finds an independent set in G of cardinality within a factor of (1 – ε) of the optimum in time exponential in a polynomial of log | V(G) | and ε−1. That is, we show that for every graph H for which Maximum Independent Set is not known to be APX-hard in H-free graphs, the problem admits a quasi-polynomial time approximation scheme in this graph class. Our algorithm works also in the more general weighted setting, where the input graph is supplied with a weight function on vertices and we are maximizing the total weight of an independent set.

In the Disjoint Paths problem, the input is an undirected graph G on n vertices and a set of k vertex pairs, {s i ,t i } i=1 k , and the task is to find k pairwise vertex-disjoint paths such that the i’th path connects s i to t i . In this paper, we give a parameterized algorithm with running time 2 O(k 2) n O(1) for Planar Disjoint Paths, the variant of the problem where the input graph is required to be planar. Our algorithm is based on the unique linkage/treewidth reduction theorem for planar graphs by Adler et al. [JCTB 2017], the algebraic co-homology based technique developed by Schrijver [SICOMP 1994] for Disjoint Paths on directed planar graphs, and one of the key combinatorial insights developed by Cygan et al. [FOCS 2013] in their algorithm for Disjoint Paths on directed planar graphs. To the best of our knowledge our algorithm is the first parameterized algorithm to exploit that the treewidth of the input graph is small in a way completely different from the use of dynamic programming.

A hole in a graph is an induced cycle of length at least 4, and an antihole is the complement of an induced cycle of length at least 4. A hole or antihole is long if its length is at least 5. For an integer $k$, the $k$-prism is the graph consisting of two cliques of size $k$ joined by a matching. The complexity of Maximum (Weight) Independent Set (MWIS) in long-hole-free graphs remains an important open problem. In this paper we give a polynomial-time algorithm to solve MWIS in long-hole-free graphs with no $k$-prism (for any fixed integer $k$) and a subexponential algorithm for MWIS in long-hole-free graphs in general. As a special case this gives a polynomial-time algorithm to find a maximum weight clique in perfect graphs with no long antihole and no hole of length 6. The algorithms use the framework of minimal chordal completions and potential maximal cliques.

In this work, we focus on several completion problems for subclasses of chordal graphs: M INIMUM F ILL -I N , I NTERVAL C OMPLETION , P ROPER I NTERVAL C OMPLETION , T RIVIALLY P ERFECT C OMPLETION , and T HRESHOLD C OMPLETION . In these problems, the task is to add at most k edges to a given graph to obtain a chordal, interval, proper interval, threshold, or trivially perfect graph, respectively. We prove the following lower bounds for all these problems, as well as for the related C HAIN C OMPLETION problem: • Assuming the Exponential Time Hypothesis, none of these problems can be solved in time 2 O ( n 1/2 /log c n ) or 2 O ( k 1/4 /log c k )· n O (1) , for some integer c . • Assuming the non-existence of a subexponential-time approximation scheme for M IN B ISECTION on d -regular graphs, for some constant d , none of these problems can be solved in time 2 o ( n ) or 2 o √k) }· n O (1) . For all the aforementioned completion problems, apart from P ROPER I NTERVAL C OMPLETION , FPT algorithms with running time of the form 2 O (√ k log k ) · n O (1) are known. Thus, the second result proves that a significant improvement of any of these algorithms would lead to a surprising breakthrough in the design of approximation algorithms for M IN B ISECTION . To prove our results, we use a reduction methodology based on combining the classic approach of starting with a sparse instance of 3-S AT , prepared using the Sparsification Lemma, with the existence of almost linear-size Probabilistically Checkable Proofs. Apart from our main results, we also obtain lower bounds excluding the existence of subexponential algorithms for the O PTIMUM L INEAR A RRANGEMENT problem, as well as improved, yet still not tight, lower bounds for F EEDBACK A RC S ET IN T OURNAMENTS .

It is a long-standing open problem whether the minimal dominating sets of a graph can be enumerated in output-polynomial time. In this article we investigate this problem in graph classes defined by forbidding an induced subgraph. In particular, we provide output-polynomial time algorithms for K t -free graphs and for several related graph classes. This answers a question of Kanté et al. about enumeration in bipartite graphs.

We study the model-checking problem for first- and monadic second-order logic on finite relational structures. The problem of verifying whether a formula of these logics is true on a given structure is considered intractable in general, but it does become tractable on interesting classes of structures, such as on classes whose Gaifman graphs have bounded treewidth. In this article, we continue this line of research and study model-checking for first- and monadic second-order logic in the presence of an ordering on the input structure. We do so in two settings: the general ordered case, where the input structures are equipped with a fixed order or successor relation, and the order-invariant case, where the formulas may resort to an ordering, but their truth must be independent of the particular choice of order. In the first setting we show very strong intractability results for most interesting classes of structures. In contrast, in the order-invariant case we obtain tractability results for order-invariant monadic second-order formulas on the same classes of graphs as in the unordered case. For first-order logic, we obtain tractability of successor-invariant formulas on classes whose Gaifman graphs have bounded expansion. Furthermore, we show that model-checking for order-invariant first-order formulas is tractable on coloured posets of bounded width.

The notion of bounded expansion captures uniform sparsity of graph classes and renders various algorithmic problems that are hard in general tractable. In particular, the model-checking problem for first-order logic is fixed-parameter tractable over such graph classes. With the aim of generalizing such results to dense graphs, we introduce classes of graphs with structurally bounded expansion , defined as first-order transductions of classes of bounded expansion. As a first step towards their algorithmic treatment, we provide their characterization analogous to the characterization of classes of bounded expansion via low treedepth covers (or colorings), replacing treedepth by its dense analogue called shrubdepth.

In this paper we consider the reachability problem for bounded branching VASS. Bounded VASS are a variant of the classic VASS model where all values in all configurations are upper bounded by a fixed natural number, encoded in binary in the input. This model gained a lot of attention in 2012 when Haase et al. showed its connections with timed automata. Later in 2013 Fearnley and Jurdziński proved that the reachability problem in this model is PSPACE-complete even in dimension 1. Here, we investigate the complexity of the reachability problem when the model is extended with branching transitions, and we prove that the problem is EXPTIME-complete when the dimension is 2 or larger.

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.

We consider the k-Median problem on planar graphs: given an edge-weighted planar graph G, a set of clients C subseteq V(G), a set of facilities F subseteq V(G), and an integer parameter k, the task is to find a set of at most k facilities whose opening minimizes the total connection cost of clients, where each client contributes to the cost with the distance to the closest open facility. We give two new approximation schemes for this problem: - FPT Approximation Scheme: for any epsilon>0, in time 2^{O(k epsilon^{-3} log (k epsilon^{-1}))}* n^O(1) we can compute a solution that has connection cost at most (1+epsilon) times the optimum, with high probability. - Efficient Bicriteria Approximation Scheme: for any epsilon>0, in time 2^{O(epsilon^{-5} log (epsilon^{-1}))}* n^O(1) we can compute a set of at most (1+epsilon)k facilities whose opening yields connection cost at most (1+epsilon) times the optimum connection cost for opening at most k facilities, with high probability. As a direct corollary of the second result we obtain an EPTAS for Uniform Facility Location on planar graphs, with same running time. Our main technical tool is a new construction of a "coreset for facilities" for k-Median in planar graphs: we show that in polynomial time one can compute a subset of facilities F_0 subseteq F of size k * (log n/epsilon)^O(epsilon^{-3}) with a guarantee that there is a (1+epsilon)-approximate solution contained in F_0.

We consider the classic Facility Location problem on planar graphs (non-uniform, uncapacitated). Given an edge-weighted planar graph G, a set of clients C ⊆ V(G), a set of facilities F ⊆ V(G), and opening costs open: F → R≥0, the goal is to find a subset D of F that minimizes ΣcϵCminfϵDdist(c,f) + ΣfϵDopen(f). The Facility Location problem remains one of the most classic and fundamental optimization problem for which it is not known whether it admits a polynomial-time approximation scheme (PTAS) on planar graphs despite significant effort for obtaining one. We solve this open problem by giving an algorithm that for any ε>0, computes a solution of cost at most (1+ε) times the optimum in time n (2O(ε(-2) log(1/ε))) .

In the classic Maximum Weight Independent Set problem we are given a graph G with a nonnegative weight function on vertices, and the goal is to find an independent set in G of maximum possible weight. While the problem is NP-hard in general, we give a polynomial-time algorithm working on any P6-free graph, that is, a graph that has no path on 6 vertices as an induced subgraph. This improves the polynomial-time algorithm on P5-free graphs of Lokshtanov et al. [11], and the quasipolynomial-time algorithm on P6-free graphs of Lokshtanov et al. [12]. The main technical contribution leading to our main result is enumeration of a polynomial-size family ℱ of vertex subsets with the following property: for every maximal independent set I in the graph, ℱ contains all maximal cliques of some minimal chordal completion of G that does not add any edge incident to a vertex of I.

For p ∊ ℕ, a coloring λ of the vertices of a graph G is p-centered if for every connected subgraph H of G, either H receives more than p colors under λ or there is a color that appears exactly once in H. Centered colorings play an important role in the theory of sparse graphs introduced by Nešetřil and Ossona de Mendez [27], as they structurally characterize classes of bounded expansion, one of the key notions in this theory. More precisely, a class of graphs ℒ has bounded expansion if and only if there is a function f : ℕ → ℕ such that every graph G ∊ ℒ for every p ∊ ℕ admits a p-centered coloring with at most f(p) colors. Unfortunately, known proofs of the existence of such colorings yield large upper bounds on the function f governing the number of colors needed, even for as simple classes as planar graphs. We prove that every Kt-minor-free graph admits a p-centered coloring with O(pg(t)) colors for some function g. In the special case that the graph is embeddable in a fixed surface Σ we show that it admits a p-centered coloring with O(p19) colors, with the degree of the polynomial independent of the genus of Σ. This provides the first polynomial upper bounds on the number of colors needed in p-centered colorings of graphs drawn from proper minor-closed classes, which answers an open problem posed by Dvořák [1]. As an algorithmic application, we use our main result to prove that if ℒ is a fixed proper minor-closed class of graphs, then given graphs H and G, on p and n vertices, respectively, where G ∊ ℒ, it can be decided whether H is a subgraph of G in time 2O(p log p). nO(1) and space nO(1).

We consider a generic algorithmic paradigm that we call progressive exploration, which can be used to develop simple and efficient parameterized graph algorithms. We identify two model-theoretic properties that lead to efficient progressive algorithms, namely variants of the Helly property and stability. We demonstrate our approach by giving linear-time fixed-parameter algorithms for the Distance-r Dominating Set problem (parameterized by the solution size) in a wide variety of restricted graph classes, such as powers of nowhere dense classes, map graphs, and (for r=1) biclique-free graphs. Similarly, for the Distance-r Independent Set problem the technique can be used to give a linear-time fixed-parameter algorithm on any nowhere dense class. Despite the simplicity of the method, in several cases our results extend known boundaries of tractability for the considered problems and improve the best known running times.

Cutwidth is one of the classic layout parameters for graphs. It measures how well one can order the vertices of a graph in a linear manner, so that the maximum number of edges between any prefix and its complement suffix is minimized. As graphs of cutwidth at most k are closed under taking immersions, the results of Robertson and Seymour imply that there is a finite list of minimal immersion obstructions for admitting a cut layout of width at most k. We prove that every minimal immersion obstruction for cutwidth at most k has size at most $$2^{{O}(k^3\log k)}$$ . As an interesting algorithmic byproduct, we design a new fixed-parameter algorithm for computing the cutwidth of a graph that runs in time $$2^{{O}(k^2\log k)}\cdot n$$ , where k is the optimum width and n is the number of vertices. While being slower by a $$\log k$$ -factor in the exponent than the fastest known algorithm, given by Thilikos et al. (J Algorithms 56(1):1–24, 2005; J Algorithms 56(1):25–49, 2005), our algorithm has the advantage of being simpler and self-contained; arguably, it explains better the combinatorics of optimum-width layouts.

In the Edge Bipartization problem one is given an undirected graph G and an integer k, and the question is whether k edges can be deleted from G so that it becomes bipartite. Guo et al. (J Comput Syst Sci 72(8):1386–1396, 2006) proposed an algorithm solving this problem in time $$\mathcal {O}(2^k\cdot {m}^2)$$ ; today, this algorithm is a textbook example of an application of the iterative compression technique. Despite extensive progress in the understanding of the parameterized complexity of graph separation problems in the recent years, no significant improvement upon this result has been yet reported. We present an algorithm for Edge Bipartization that works in time $$\mathcal {O}(1.977^k\cdot {nm})$$ , which is the first algorithm with the running time dependence on the parameter better than $$2^k$$ . To this end, we combine the general iterative compression strategy of Guo et al. (2006), the technique proposed by Wahlström (in: Proceedings of SODA’14, SIAM, 2014) of using a polynomial-time solvable relaxation in the form of a Valued Constraint Satisfaction Problem to guide a bounded-depth branching algorithm, and an involved Measure&Conquer analysis of the recursion tree.

We show that any one-counter automaton with $n$ states, if its language is non-empty, accepts some word of length at most $O(n^2)$. This closes the gap between the previously known upper bound of $O(n^3)$ and lower bound of $\Omega(n^2)$. More generally, we prove a tight upper bound on the length of shortest paths between arbitrary configurations in one-counter transition systems (weaker bounds have previously appeared in the literature). Comment: 28 pages, 2 figures

In the classic Minimum Bisection problem we are given as input an undirected graph $G$ and an integer $k$. The task is to determine whether there is a partition of $V(G)$ into two parts $A$ and $B$ such that $||A|-|B|| \leq 1$ and there are at most $k$ edges with one endpoint in $A$ and the other in $B$. In this paper we give an algorithm for Minimum Bisection with running time $2^{\mathcal{O}(k^3)}n^3 \log^3 n$. This is the first fixed parameter tractable algorithm for Minimum Bisection parameterized by $k$. At the core of our algorithm lies a new decomposition theorem that states that every graph $G$ can be decomposed by small separators into parts where each part is “highly connected” in the following sense: any separator of bounded size can separate only a limited number of vertices from each part of the decomposition. Our techniques generalize to the weighted setting, where we seek a bisection of minimum weight among solutions that contain at most $k$ edges.

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.

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.

We prove that for every positive integer k, there exists an MSO1-transduction that given a graph of linear cliquewidth at most k outputs, nondeterministically, some clique decomposition of the graph of width bounded by a function of k. A direct corollary of this result is the equivalence of the notions of CMSO1-definability and recognizability on graphs of bounded linear cliquewidth.

We prove that for every class ℒ of graphs with effectively bounded expansion, given a first-order sentence φ and an n-element structure A whose Gaifman graph belongs to ℒ, the question whether φ holds in A can be decided by a family of AC-circuits of size f(φ) · nc and depth f(φ) + c log n, where f is a computable function and c is a universal constant. This places the model-checking problem for classes of bounded expansion in the parameterized circuit complexity class para-AC1. On the route to our result we prove that the basic decomposition toolbox for classes of bounded expansion, including orderings with bounded weak coloring numbers and low treedepth decompositions, can be computed in para-AC1.

We prove that for every class of graphs ℒ which is nowhere dense, as defined by Nešetřil and Ossona de Mendez [28, 29], and for every first order formula φ(x, y), whenever one draws a graph G ∈ ℒ and a subset of its nodes A, the number of subsets of A|y| which are of the form {u ∈ A|y|: G |= φ(ū, v)} for some valuation ū of x in G is bounded by O(|A||x|ε), for every ε > 0. This provides optimal bounds on the VC-density of first-order definable set systems in nowhere dense graph classes. We also give two new proofs of upper bounds on quantities in nowhere dense classes which are relevant for their logical treatment. Firstly, we provide a new proof of the fact that nowhere dense classes are uniformly quasi-wide, implying explicit, polynomial upper bounds on the functions relating the two notions. Secondly, we give a new combinatorial proof of the result of Adler and Adler [1] stating that every nowhere dense class of graphs is stable. In contrast to the previous proofs of the above results, our proofs are completely finitistic and constructive, and yield explicit and computable upper bounds on quantities related to uniform quasi-wideness (margins) and stability (ladder indices).

We give a kernel with $$O(k^7)$$ vertices for Trivially Perfect Editing, the problem of adding or removing at most k edges in order to make a given graph trivially perfect. This answers in affirmative an open question posed by Nastos and Gao (Soc Netw 35(3):439–450, 2013), and by Liu et al. (Tsinghua Sci Technol 19(4):346–357, 2014). Our general technique implies also the existence of kernels of the same size for related Trivially Perfect Completion and Trivially Perfect Deletion problems. Whereas for the former an $$O(k^3)$$ kernel was given by Guo (in: ISAAC 2007, LNCS, vol 4835, Springer, pp 915–926, 2007), for the latter no polynomial kernel was known. We complement our study of Trivially Perfect Editing by proving that, contrary to Trivially Perfect Completion, it cannot be solved in time $$2^{o(k)}\cdot n^{O(1)}$$ unless the exponential time hypothesis fails. In this manner we complete the picture of the parameterized and kernelization complexity of the classic edge modification problems for the class of trivially perfect graphs.

A vertex subset $S$ in a graph $G$ is a dominating set if every vertex not contained in $S$ has a neighbor in $S$. A dominating set $S$ is a connected dominating set if the subgraph $G[S]$ induced by $S$ is connected. A connected dominating set $S$ is a minimal connected dominating set if no proper subset of $S$ is also a connected dominating set. We prove that there exists a constant $\epsilon > 10^{-50}$ such that every graph $G$ on $n$ vertices has at most $\mathcal{O}(2^{(1-\epsilon)n})$ minimal connected dominating sets. For the same $\epsilon$ we also give an algorithm with running time $2^{(1-\epsilon)n}\cdot n^{\mathcal{O}(1)}$ to enumerate all minimal connected dominating sets in an input graph $G$.

A simple digraph is semicomplete if for any two of its vertices u and v , at least one of the arcs ( u , v ) and ( v , u ) is present. We study the complexity of computing two layout parameters of semicomplete digraphs: cutwidth and optimal linear arrangement (O la ). We prove the following: • Both parameters are NP-hard to compute and the known exact and parameterized algorithms for them have essentially optimal running times, assuming the Exponential Time Hypothesis. • The cutwidth parameter admits a quadratic Turing kernel, whereas it does not admit any polynomial kernel unless NP ⊆ coNP/poly. By contrast, O la admits a linear kernel. These results essentially complete the complexity analysis of computing cutwidth and O la on semicomplete digraphs (with respect to standard parameters). Our techniques also can be used to analyze the sizes of minimal obstructions for having a small cutwidth under the induced subdigraph relation.

In the I nterval C ompletion problem we are given an n -vertex graph G and an integer k , and the task is to transform G by making use of at most k edge additions into an interval graph. This is a fundamental graph modification problem with applications in sparse matrix multiplication and molecular biology. The question about fixed-parameter tractability of I nterval C ompletion was asked by Kaplan et al. [FOCS 1994; SIAM J. Comput. 1999] and was answered affirmatively more than a decade later by Villanger et al. [STOC 2007; SIAM J. Comput. 2009], who presented an algorithm with running time O ( k 2 k n 3 m ). We give the first subexponential parameterized algorithm solving I nterval C ompletion in time k O (√ k ) n O (1) . This adds I nterval C ompletion to a very small list of parameterized graph modification problems solvable in subexponential time.

We investigate the complexity of several fundamental polynomial-time solvable problems on graphs and on matrices, when the given instance has low treewidth; in the case of matrices, we consider the treewidth of the graph formed by non-zero entries. In each of the considered cases, the best known algorithms working on general graphs run in polynomial time; however, the exponent of the polynomial is large. Therefore, our main goal is to construct algorithms with running time of the form poly( k )⋅ n or poly( k )⋅ n log n , where k is the width of the tree decomposition given on the input. Such procedures would outperform the best known algorithms for the considered problems already for moderate values of the treewidth, like O ( n 1/ c ) for a constant c . Our results include the following: — an algorithm for computing the determinant and the rank of an n × n matrix using O ( k 3 ⋅ n ) time and arithmetic operations; —an algorithm for solving a system of linear equations using O ( k 3 ⋅ n ) time and arithmetic operations; —an O ( k 3 ⋅ n log n )-time randomized algorithm for finding the cardinality of a maximum matching in a graph; —an O ( k 4 ⋅ n log 2 n )-time randomized algorithm for constructing a maximum matching in a graph; —an O ( k 2 ⋅ n log n )-time algorithm for finding a maximum vertex flow in a directed graph. Moreover, we give an approximation algorithm for treewidth with time complexity suited to the running times as above. Namely, the algorithm, when given a graph G and integer k , runs in time O ( k 7 ⋅ n log n ) and either correctly reports that the treewidth of G is larger than k , or constructs a tree decomposition of G of width O ( k 2 ). The above results stand in contrast with the recent work of Abboud et al. (SODA 2016), which shows that the existence of algorithms with similar running times is unlikely for the problems of finding the diameter and the radius of a graph of low treewidth.

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.

We prove that whenever G is a graph from a nowhere dense graph class C, and A is a subset of vertices of G, then the number of subsets of A that are realized as intersections of A with r-neighborhoods of vertices of G is at most f(r,eps)|A|^(1+eps), where r is any positive integer, eps is any positive real, and f is a function that depends only on the class C. This yields a characterization of nowhere dense classes of graphs in terms of neighborhood complexity, which answers a question posed by [Reidl et al., CoRR, 2016]. As an algorithmic application of the above result, we show that for every fixed integer r, the parameterized Distance-r Dominating Set problem admits an almost linear kernel on any nowhere dense graph class. This proves a conjecture posed by [Drange et al., STACS 2016], and shows that the limit of parameterized tractability of Distance-r Dominating Set on subgraph-closed graph classes lies exactly on the boundary between nowhere denseness and somewhere denseness.

A successor-invariant first-order formula is a formula that has access to an auxiliary successor relation on a structure's universe, but the model relation is independent of the particular interpretation of this relation. It is well known that successor-invariant formulas are more expressive on finite structures than plain first-order formulas without a successor relation. This naturally raises the question whether this increase in expressive power comes at an extra cost to solve the model-checking problem, that is, the problem to decide whether a given structure together with some (and hence every) successor relation is a model of a given formula. It was shown earlier that adding successor-invariance to first-order logic essentially comes at no extra cost for the model-checking problem on classes of finite structures whose underlying Gaifman graph is planar [1], excludes a fixed minor [2] or a fixed topological minor [3], [4]. In this work we show that the model-checking problem for successor-invariant formulas is fixed-parameter tractable on any class of finite structures whose underlying Gaifman graphs form a class of bounded expansion. Our result generalises all earlier results and comes close to the best tractability results on nowhere dense classes of graphs currently known for plain first-order logic.

This is an overview of the invited talk delivered at the 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017).

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.

We investigate the complexity of several fundamental polynomial-time solvable problems on graphs and on matrices, when the given instance has low treewidth; in the case of matrices, we consider the treewidth of the graph formed by non-zero entries. In each of the considered cases, the best known algorithms working on general graphs run in polynomial, but far from linear, time. Thus, our goal is to construct algorithms with running time of the form poly(k) · n or poly(k) · n log n, where k is the width of the tree decomposition given on the input. Such procedures would outperform the best known algorithms for the considered problems already for moderate values of the treewidth, like O(n1/c) for some small constant c. Our results include: an algorithm for computing the determinant and the rank of an n × n matrix using O(k3 · n) time and arithmetic operations;an algorithm for solving a system of linear equations using O(k3 · n) time and arithmetic operations;an O(k3 · n log n)-time randomized algorithm for finding the cardinality of a maximum matching in a graph;an O(k4 · nlog2 n)-time randomized algorithm for constructing a maximum matching in a graph;an O(k2 · n log n)-time algorithm for finding a maximum vertex flow in a directed graph. Moreover, we provide an approximation algorithm for treewidth with time complexity suited to the running times as above. Namely, the algorithm, when given a graph G and integer k, runs in time O(k2 · n log n) and either correctly reports that the treewidth of G is larger than k, or constructs a tree decomposition of G of width O(k2). The above results stand in contrast with the recent work of Abboud et al. [SODA 2016], which shows that the existence of algorithms with similar running times is unlikely for the problems of finding the diameter and the radius of a graph of low treewidth.

In the $$k$$ -Leaf Out-Branching and $$k$$ -Internal Out-Branching problems we are given a directed graph D with a designated root r and a nonnegative integer k. The question is whether there exists an outbranching rooted at r that has at least k leaves, or at least k internal vertices, respectively. Both these problems have been studied from the points of view of parameterized complexity and kernelization, and in particular for both of them kernels with $$O(k^2)$$ vertices are known on general graphs. In this work we show that $$k$$ -Leaf Out-Branching admits a kernel with O(k) vertices on $${{\mathcal {H}}}$$ -minor-free graphs, for any fixed family of graphs $${{\mathcal {H}}}$$ , whereas $$k$$ -Internal Out-Branching admits a kernel with O(k) vertices on any graph class of bounded expansion.

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.

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.

We give a fixed-parameter tractable algorithm that, given a parameter $k$ and two graphs $G_1,G_2$, either concludes that one of these graphs has treewidth at least $k$ or determines whether $G_1$ and $G_2$ are isomorphic. The running time of the algorithm on an $n$-vertex graph is $2^{\mathcal{O}(k^5\log k)}\cdot n^5$, and this is the first fixed-parameter algorithm for Graph Isomorphism parameterized by treewidth. Our algorithm in fact solves the more general canonization problem. We namely design a procedure working in $2^{\mathcal{O}(k^5\log k)}\cdot n^5$ time that, for a given graph $G$ on $n$ vertices, either concludes that the treewidth of $G$ is at least $k$ or (i) finds in an isomorphic-invariant way a graph $\mathfrak{c}(G)$ that is isomorphic to $G$; (ii) finds an isomorphism-invariant construction term---an algebraic expression that encodes $G$ together with a tree decomposition of $G$ of width less than $k$. Hence, the isomorphism test reduces to verifying whether the computed isomorphic copies or the construction terms for $G_1$ and $G_2$ are equal.

The H-free Edge Deletion problem asks, for a given graph G and integer k, whether it is possible to delete at most k edges from G to make it H-free, that is, not containing H as an induced subgraph. The H-free Edge Completion problem is defined similarly, but we add edges instead of deleting them. The study of these two problem families has recently been the subject of intensive studies from the point of view of parameterized complexity and kernelization. In particular, it was shown that the problems do not admit polynomial kernels (under plausible complexity assumptions) for almost all graphs H, with several important exceptions occurring when the class of H-free graphs exhibits some structural properties. In this work we complement the parameterized study of edge modification problems to H-free graphs by considering their approximability. We prove that whenever H is 3-connected and has at least two non-edges, then both H-free Edge Deletion and H-free Edge Completion are very hard to approximate: they do not admit poly(OPT)-approximation in polynomial time, unless P=NP, or even in time subexponential in OPT, unless the Exponential Time Hypothesis fails. The assumption of the existence of two non-edges appears to be important: we show that whenever H is a complete graph without one edge, then H-free Edge Deletion is tightly connected to the \minhorn problem, whose approximability is still open. Finally, in an attempt to extend our hardness results beyond 3-connected graphs, we consider the cases of H being a path or a cycle, and we achieve an almost complete dichotomy there.

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.

In the EDGE BIPARTIZATION problem one is given an undirected graph G and an integer k, and the question is whether k edges can be deleted from G so that it becomes bipartite. In 2006, Guo et al. [J. Comput. Syst. Sci., 72(8):1386-1396, 2006] proposed an algorithm solving this problem in time O(2^k m^2); today, this algorithm is a textbook example of an application of the iterative compression technique. Despite extensive progress in the understanding of the parameterized complexity of graph separation problems in the recent years, no significant improvement upon this result has been yet reported. We present an algorithm for Edge Bipartization that works in time O(1.977^k nm), which is the first algorithm with the running time dependence on the parameter better than 2^k. To this end, we combine the general iterative compression strategy of Guo et al. [J. Comput. Syst. Sci., 72(8):1386-1396, 2006], the technique proposed by Wahlström [SODA'14] of using a polynomial-time solvable relaxation in the form of a Valued Constraint Satisfaction Problem to guide a bounded-depth branching algorithm, and an involved Measure&Conquer analysis of the recursion tree.

We prove a conjecture of Courcelle, which states that a graph property is definable in MSO with modular counting predicates on graphs of constant treewidth if, and only if it is recognizable in the following sense: constant-width tree decompositions of graphs satisfying the property can be recognized by tree automata. While the forward implication is a classic fact known as Courcelle's theorem, the converse direction remained open.

The generalised colouring numbers $\mathrm{adm}_r(G)$, $\mathrm{col}_r(G)$, and $\mathrm{wcol}_r(G)$ were introduced by Kierstead and Yang as generalisations of the usual colouring number, also known as the degeneracy of a graph, and have since then found important applications in the theory of bounded expansion and nowhere dense classes of graphs, introduced by Nešetřil and Ossona de Mendez. In this paper, we study the relation of the colouring numbers with two other measures that characterise nowhere dense classes of graphs, namely with uniform quasi-wideness, studied first by Dawar et al. in the context of preservation theorems for first-order logic, and with the splitter game, introduced by Grohe et al. We show that every graph excluding a fixed topological minor admits a universal order, that is, one order witnessing that the colouring numbers are small for every value of $r$. Finally, we use our construction of such orders to give a new proof of a result of Eickmeyer and Kawarabayashi, showing that the model-checking problem for successor-invariant first-order formulas is fixed-parameter tractable on classes of graphs with excluded topological minors.

XML schema validation can be performed in constant memory in the streaming model if and only if the schema admits only trees of bounded depth - an acceptable assumption from the practical view-point. In this paper we refine this analysis by taking into account that data can be streamed block-by-block, rather then letter-by-letter, which provides opportunities to speed up the computation by parallelizing the processing of each block. For this purpose we introduce the model of streaming circuits, which process words of arbitrary length in blocks of fixed size, passing constant amount of information between blocks. This model allows us to transfer fundamental results about the circuit complexity of regular languages to the setting of streaming schema validation, which leads to effective constructions of streaming circuits of depth logarithmic in the block size, or even constant under certain assumptions on the input schema. For nested-relational DTDs, a practically motivated class of bounded-depth XML schemas, we provide an efficient construction yielding constant-depth streaming circuits with particularly good parameters.

In this work, we focus on several completion problems for subclasses of chordal graphs: Minimum Fill-In, Interval Completion, Proper Interval Completion, Threshold Completion, and Trivially Perfect Completion. In these problems, the task is to add at most k edges to a given graph in order to obtain a chordal, interval, proper interval, threshold, or trivially perfect graph, respectively. We prove the following lower bounds for all these problems, as well as for the related Chain Completion problem: Assuming the Exponential Time Hypothesis, none of these problems can be solved in time 2O(n1/2/logcn) or 2O(k1/4/logck). nO(1) for some integer c. Assuming the non-existence of a subexponential-time approximation scheme for Min Bisection on d-regular graphs, for some constant d, none of these problems can be solved in time 2o(n) or .

In the Interval Completion problem we are given an n-vertex graph G and an integer k, and the task is to transform G by making use of at most k edge additions into an interval graph. This is a fundamental graph modification problem with applications in sparse matrix multiplication and molecular biology. The question about fixed-parameter tractability of Interval Completion was asked by Kaplan, Shamir and Tarjan [FOCS 1994; SIAM J. Comput. 1999] and was answered affirmatively more than a decade later by Villanger at el. [STOC 2007; SIAM J. Comput. 2009], who presented an algorithm with running time O(k2kn3m). We give the first subexponential parameterized algorithm solving Interval Completion in time . This adds Interval Completion to a very small list of parameterized graph modification problems solvable in subexponential time.

We prove that in a graph with n vertices, induced chordal and interval subgraphs with the maximum number of vertices can be found in time $$\mathcal {O}(2^{\lambda n})$$ for some $$\lambda <1$$ . These are the first algorithms breaking the trivial $$2^n n^{\mathcal {O}(1)}$$ bound of the brute-force search for these problems.

We give an algorithm that for an input $n$-vertex graph $G$ and integer $k>0$, in time $2^{O(k)} n$, either outputs that the treewidth of $G$ is larger than $k$, or gives a tree decomposition of $G$ of width at most $5k+4$. This is the first algorithm providing a constant factor approximation for treewidth which runs in time single exponential in $k$ and linear in $n$. Treewidth-based computations are subroutines of numerous algorithms. Our algorithm can be used to speed up many such algorithms to work in time which is single exponential in the treewidth and linear in the input size.

We introduce a new technique for designing fixed-parameter algorithms for cut problems, called randomized contractions. We apply our framework to obtain the first fixed-parameter algorithms (FPT algorithms) with exponential speed up for the Steiner Cut and Node Multiway Cut-Uncut problems. We prove that the parameterized version of the Unique Label Cover problem, which is the base of the Unique Games Conjecture, can be solved in $2^{O(k^2\log |\Sigma|)}n^4\log n$ deterministic time (even in the stronger, vertex-deletion variant), where $k$ is the number of unsatisfied edges and $|\Sigma|$ is the size of the alphabet. As a consequence, we show that one can in polynomial time solve instances of Unique Games where the number of edges allowed not to be satisfied is upper bounded by $O(\sqrt{\log n})$ to optimality, which improves over the trivial $O(1)$ upper bound. We prove that the Steiner Cut problem can be solved in $2^{O(k^2\log k)}n^4\log n$ deterministic time and $\tilde{O}(2^{O(k^2\log k)}n^2)$ randomized time, where $k$ is the size of the cutset. This result improves the double exponential running time of the recent work of Kawarabayashi and Thorup presented at FOCS'11. We show how to combine considering “cut” and “uncut” constraints at the same time. More precisely, we define a robust problem, Node Multiway Cut-Uncut, that can serve as an abstraction of introducing uncut constraints and show that it admits an algorithm running in $2^{O(k^2\log k)}n^4\log n$ deterministic time, where $k$ is the size of the cutset. To the best of our knowledge, the only known way of tackling uncut constraints was via the approach of Marx, O'Sullivan, and Razgon [ACM Trans. Algorithms, 9 (2013), 30], which yields algorithms with double exponential running time. An interesting aspect of our algorithms is that they can handle positive real weights.

In the Edge Clique Cover (ECC) problem, given an undirected graph $G$ and an integer $k$, we ask whether one can choose $k$ cliques in $G$ such that each edge of $G$ is contained in at least one of the chosen cliques. Gramm et al. [ACM J. Exp. Algorithmics, 13 (2008)] have shown a set of simple rules that reduce the number of vertices of $G$ to $2^k$ while preserving the answer to the instance at hand, that is, they have shown a kernel for the problem with at most $2^k$ vertices. No algorithm is known with significantly better running time bound than a brute-force search on this kernel. In this paper, we show that the approach of Gramm et al. is essentially optimal: we present a polynomial-time algorithm that reduces an arbitrary instance of $3$-CNF-SAT with $n$ variables and $m$ clauses to an equivalent ECC instance $(G,k)$ with $k = \mathcal{O}(\log n)$ and $|V(G)| = \mathcal{O}(n + m)$. Consequently, there is no $2^{2^{o(k)}}{\rm poly}(n)$ time algorithm for the ECC problem, unless the Exponential Time Hypothesis fails. Moreover, our reduction also implies that, unless P $ = $ NP, the ECC problem does not admit a subexponential kernel, i.e., a kernel of size $2^{o(k)}$.

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.

Signed graphs, i.e., undirected graphs with edges labelled with a plus or minus sign, are commonly used to model relationships in social networks. Recently, Kermarrec and Thraves (2011) initiated the study of the problem of appropriately visualising the network: They asked whether any signed graph can be embedded into the metric space ${{\mathbb {R}}}^{l}$ in such a manner that every vertex is closer to all its friends (neighbours via positive edges) than to all its enemies (neighbours via negative edges). Interestingly, embeddability into ${{\mathbb {R}}}^{1}$ can be expressed as a purely combinatorial problem. In this paper we pursue a deeper study of this case, answering several questions posed by Kermarrec and Thraves. First, we refine the approach of Kermarrec and Thraves for the case of complete signed graphs by showing that the problem is closely related to the recognition of proper interval graphs. Second, we prove that the general case, whose polynomial-time tractability remained open, is in fact NP-complete. Finally, we provide lower and upper bounds for the time complexity of the general case: we prove that the existence of a subexponential time (in the number of vertices and edges of the input signed graph) algorithm would violate the Exponential Time Hypothesis, whereas a simple dynamic programming approach gives a running time single-exponential in the number of vertices.

In the Proper Interval Completion problem we are given a graph $G$ and an integer $k$, and the task is to turn $G$ using at most $k$ edge additions into a proper interval graph, i.e., a graph admitting an intersection model of equal-length intervals on a line. The study of Proper Interval Completion from the viewpoint of parameterized complexity has been initiated by Kaplan, Shamir, and Tarjan [SIAM J. Comput., 28 (1999), pp. 1906--1922], who showed an algorithm for the problem working in $\mathcal{O}(16^k\cdot (n+m))$ time. In this paper we present an algorithm with running time $k^{\mathcal{O}(k^{2/3})} + \mathcal{O}(nm(kn+m))$, which is the first subexponential parameterized algorithm for Proper Interval Completion.

The Multicut problem, given a graph G, a set of terminal pairs $\mathcal{T}=\{(s_i,t_i)\ |\ 1\leq i\leq r\}$, and an integer $p$, asks whether one can find a cutset consisting of at most $p$ nonterminal vertices that separates all the terminal pairs, i.e., after removing the cutset, $t_i$ is not reachable from $s_i$ for each $1\leq i\leq r$. The fixed-parameter tractability of Multicut in undirected graphs, parameterized by the size of the cutset only, has been recently proved by Marx and Razgon [SIAM J. Comput., 43 (2014), pp. 355--388] and, independently, by Bousquet, Daligault, and Thomassé [Proceedings of STOC, ACM, 2011, pp. 459--468], after resisting attacks as a long-standing open problem. In this paper we prove that Multicut is fixed-parameter tractable on directed acyclic graphs when parameterized both by the size of the cutset and the number of terminal pairs. We complement this result by showing that this is implausible for parameterization by the size of the cutset only, as this version of the problem remains $W[1]$-hard.

We give a fixed-parameter tractable algorithm that, given a parameter k and two graphs G1, G2, either concludes that one of these graphs has treewidth at least k, or determines whether G1and G2are isomorphic. The running time of the algorithm on an n-vertex graph is 2O(k5 log k)· n5, and this is the first fixed-parameter algorithm for Graph Isomorphism parameterized by treewidth. Our algorithm in fact solves the more general canonization problem. We namely design a procedure working in 2OO(k5 log k)· n5time that, for a given graph G on n vertices, either concludes that the treewidth of G is at least k, or finds an isomorphism-invariant construction term - an algebraic expression that encodes G together with a tree decomposition of G of width O(k4). Hence, a canonical graph isomorphic to G can be constructed by simply evaluating the obtained construction term, while the isomorphism test reduces to verifying whether the computed construction terms for G1and G2are equal.

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.

International audience

Let F be a family of graphs. In the F-Completion problem, we are given an n-vertex graph G and an integer k as input, and asked whether at most k edges can be added to G so that the resulting graph does not contain a graph from F as an induced subgraph. It appeared recently that special cases of F-Completion, the problem of completing into a chordal graph known as "Minimum Fill-in", corresponding to the case of F={C_4,C_5,C_6,...}, and the problem of completing into a split graph, i.e., the case of F={C_4,2K_2,C_5}, are solvable in parameterized subexponential time. The exploration of this phenomenon is the main motivation for our research on F-Completion. In this paper we prove that completions into several well studied classes of graphs without long induced cycles also admit parameterized subexponential time algorithms by showing that: - The problem Trivially Perfect Completion is solvable in parameterized subexponential time, that is F-Completion for F={C_4,P_4}, a cycle and a path on four vertices. - The problems known in the literature as Pseudosplit Completion, the case where F={2K_2,C_4}, and Threshold Completion, where F={2K_2,P_4,C_4}, are also solvable in subexponential time. We complement our algorithms for $F$-Completion with the following lower bounds: - For F={2K_2}, F={C_4}, F={P_4}, and F={2K_2,P_4}, F-Completion cannot be solved in time 2^o(k).n^O(1) unless the Exponential Time Hypothesis (ETH) fails. Our upper and lower bounds provide a complete picture of the subexponential parameterized complexity of F-Completion problems for F contained inside {2K_2,C_4,P_4}.

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.

In the classic Minimum Bisection problem we are given as input a graph G and an integer k. The task is to determine whether there is a partition of V (G) into two parts A and B such that ||A| -- |B|| ≤ 1 and there are at most k edges with one endpoint in A and the other in B. In this paper we give an algorithm for Minimum Bisection with running time O(2O(k3) n3 log3 n). This is the first fixed parameter tractable algorithm for Minimum Bisection. At the core of our algorithm lies a new decomposition theorem that states that every graph G can be decomposed by small separators into parts where each part is "highly connected" in the following sense: any cut of bounded size can separate only a limited number of vertices from each part of the decomposition.

We study the Cutwidth problem, where the input is a graph G, and the objective is find a linear layout of the vertices that minimizes the maximum number of edges intersected by any vertical line inserted between two consecutive vertices. We give an algorithm for Cutwidth with running time O(2 k n O(1)). Here k is the size of a minimum vertex cover of the input graph G, and n is the number of vertices in G. Our algorithm gives an O(2 n/2 n O(1)) time algorithm for Cutwidth on bipartite graphs as a corollary. This is the first non-trivial exact exponential time algorithm for Cutwidth on a graph class where the problem remains NP-complete. Additionally, we show that Cutwidth parameterized by the size of the minimum vertex cover of the input graph does not admit a polynomial kernel unless NP⊆coNP/poly. Our kernelization lower bound contrasts with the recent results of Bodlaender et al. (ICALP, Springer, Berlin, 2011; SWAT, Springer, Berlin, 2012) that both Treewidth and Pathwidth parameterized by vertex cover do admit polynomial kernels.

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 a scheduling problem, denoted by 1|prec|∑C i in the Graham notation, we are given a set of n jobs, together with their processing times and precedence constraints. The task is to order the jobs so that their total completion time is minimized. 1|prec|∑C i is a special case of the Traveling Repairman Problem with precedences. A natural dynamic programming algorithm solves both these problems in 2 n n O(1) time, and whether there exists an algorithms solving 1|prec|∑C i in O(c n ) time for some constant c<2 was an open problem posted in 2004 by Woeginger. In this paper we answer this question positively.

The 2-Disjoint Connected Subgraphs problem, given a graph along with two disjoint sets of terminals Z 1,Z 2, asks whether it is possible to find disjoint sets A 1,A 2, such that Z 1⊆A 1, Z 2⊆A 2 and A 1,A 2 induce connected subgraphs. While the naive algorithm runs in O(2 n n O(1)) time, solutions with complexity of form O((2−ε) n ) have been found only for special graph classes (van ’t Hof et al. in Theor. Comput. Sci. 410(47–49):4834–4843, 2009; Paulusma and van Rooij in Theor. Comput. Sci. 412(48):6761–6769, 2011). In this paper we present an O(1.933 n ) algorithm for 2-Disjoint Connected Subgraphs in general case, thus breaking the 2 n barrier. As a counterpoise of this result we show that if we parameterize the problem by the number of non-terminal vertices, it is hard both to speed up the brute-force approach and to find a polynomial kernel.

We give an algorithm that for an input n-vertex graph G and integer k > 0, in time O(ckn) either outputs that the tree width of G is larger than k, or gives a tree decomposition of G of width at most 5k + 4. This is the first algorithm providing a constant factor approximation for tree width which runs in time single-exponential in k and linear in n. Tree width based computations are subroutines of numerous algorithms. Our algorithm can be used to speed up many such algorithms to work in time which is single-exponential in the tree width and linear in the input size.

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.

In the Edge Clique Cover (ECC) problem, given a graph G and an integer k, we ask whether the edges of G can be covered with k complete subgraphs of G or, equivalently, whether G admits an intersection model on k-element universe. Gramm et al. [JEA 2008] have shown a set of simple rules that reduce the number of vertices of G to 2k, and no algorithm is known with significantly better running time bound than a brute-force search on this reduced instance. In this paper we show that the approach of Gramm et al. is essentially optimal: we present a polynomial time algorithm that reduces an arbitrary 3-CNF-SAT formula with n variables and m clauses to an equivalent ECC instance (G, k) with k = O(log n) and |V (G)| = O(n + m). Consequently, there is no time algorithm for the ECC problem, unless the Exponential Time Hypothesis fails. To the best of our knowledge, these are the first results for a natural, fixed-parameter tractable problem, and proving that a doubly-exponential dependency on the parameter is essentially necessary.

We give a fixed-parameter tractable (FPT) approximation algorithm computing the pathwidth of a tournament, and more generally, of a semi-complete digraph. Based on this result, we prove the following. The Topological Containment problem is FPT on semi-complete digraphs. More precisely, given a semi-complete n-vertex digraph T and a digraph H, one can check in time f(|H|)n3 log n, where f is some elementary function, whether T contains a subdivision of H as a subgraph. The previous known algorithm for this problem was due to Fradkin and Seymour and was of running time nm(|H|), where m is a quadruple-exponential function. The Rooted Immersion problem is FPT on semi-complete digraphs. The complexity of this problem was left open by Fradkin and Seymour. Our algorithm solves it in time g(|H|)n4 log n, for some elementary function g. Vertex deletion distance to every immersion-closed class of semi-complete digraphs is fixed-parameter tractable. More precisely, for every immersion-closed class П of semi-complete digraphs, there exists an algorithm with running time h(k)n3 log n that checks, whether one can remove at most k vertices from a semi-complete n-vertex digraph to obtain a digraph from class Π. Here, h is some function depending on the class Π.

In the Correlation Clustering problem, also known as Cluster Editing, we are given an undirected graph G and a positive integer k; the task is to decide whether G can be transformed into a cluster graph, i.e., a disjoint union of cliques, by changing at most k adjacencies, that is, by adding or deleting at most k edges. The motivation of the problem stems from various tasks in computational biology (Ben-Dor et al., Journal of Computational Biology 1999) and machine learning (Bansal et al., Machine Learning 2004). Although in general Correlation Clustering is APX-hard (Charikar et al., FOCS 2003), the version of the problem where the number of cliques may not exceed a prescribed constant p admits a PTAS (Giotis and Guruswami, SODA 2006). We study the parameterized complexity of Correlation Clustering with this restriction on the number of cliques to be created. We give an algorithm that - in time O(2^{O(sqrt{pk})} + n+m) decides whether a graph G on n vertices and m edges can be transformed into a cluster graph with exactly p cliques by changing at most k adjacencies. We complement these algorithmic findings by the following, surprisingly tight lower bound on the asymptotic behavior of our algorithm. We show that unless the Exponential Time Hypothesis (ETH) fails - for any constant 0 <= sigma <= 1, there is p = Theta(k^sigma) such that there is no algorithm deciding in time 2^{o(sqrt{pk})} n^{O(1)} whether an n-vertex graph G can be transformed into a cluster graph with at most p cliques by changing at most k adjacencies. Thus, our upper and lower bounds provide an asymptotically tight analysis of the multivariate parameterized complexity of the problem for the whole range of values of p from constant to a linear function of k.

The notions of cutwidth and pathwidth of digraphs play a central role in the containment theory for tournaments, or more generally semi-complete digraphs, developed in a recent series of papers by Chudnovsky, Fradkin, Kim, Scott, and Seymour (Maria Chudnovsky, Alexandra Fradkin, and Paul Seymour, 2012; Maria Chudnovsky, Alex Scott, and Paul Seymour, 2011; Maria Chudnovsky and Paul D. Seymour, 2011; Alexandra Fradkin and Paul Seymour, 2010; Alexandra Fradkin and Paul Seymour, 2011; Ilhee Kim and Paul Seymour, 2012). In this work we introduce a new approach to computing these width measures on semi-complete digraphs, via degree orderings. Using the new technique we are able to reprove the main results of (Maria Chudnovsky, Alexandra Fradkin, and Paul Seymour, 2012; Alexandra Fradkin and Paul Seymour, 2011) in a unified and significantly simplified way, as well as obtain new results. First, we present polynomial-time approximation algorithms for both cutwidth and pathwidth, faster and simpler than the previously known ones; the most significant improvement is in case of pathwidth, where instead of previously known O(OPT)-approximation in fixed-parameter tractable time (Fedor V. Fomin and Michal Pilipczuk, 2013) we obtain a constant-factor approximation in polynomial time. Secondly, by exploiting the new set of obstacles for cutwidth and pathwidth, we show that topological containment and immersion in semi-complete digraphs can be tested in single-exponential fixed-parameter tractable time. Finally, we present how the new approach can be used to obtain exact fixed-parameter tractable algorithms for cutwidth and pathwidth, with single-exponential running time dependency on the optimal width.

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.

The classical Feedback Vertex Set problem asks, for a given undirected graph $G$ and an integer $k$, to find a set of at most $k$ vertices that hits all the cycles in the graph $G$. Feedback Vertex Set has attracted a large amount of research in the parameterized setting, and subsequent fixed-parameter and kernelization algorithms have been a rich source of ideas in the field. In this paper we consider a more general and difficult version of the problem, named Subset Feedback Vertex Set (Subset-FVS), where an instance comes additionally with a set $S \subseteq V$ of vertices, and we ask for a set of at most $k$ vertices that hits all simple cycles passing through $S$. Because of its applications in circuit testing and genetic linkage analysis, Subset-FVS was studied from the approximation algorithm perspective by Even et al. [SIAM J. Discrete Math., 13 (2000), pp. 225--267; SIAM J. Comput., 30 (2000), pp. 1231--1252]. The question of whether the Subset-FVS problem is fixed-parameter tractable was posed independently by Kawarabayashi and Saurabh in 2009. We answer this question affirmatively. We begin by showing that this problem is fixed-parameter tractable when parameterized by $|S|$. Next we present an algorithm which reduces the given instance to $2^k n^{O(1)}$ instances with the size of $S$ bounded by $O(k^3)$, using kernelization techniques such as the $2$-expansion lemma, Menger's theorem, and Gallai's theorem. These two facts allow us to give a $2^{O(k\log k)} n^{O(1)}$ time algorithm solving the Subset-FVS problem, proving that it is indeed fixed-parameter tractable.

We introduce a new technique for designing fixed-parameter algorithms for cut problems, namely randomized contractions. With our framework: (1) We obtain the first FPT algorithm for the parameterized version of the UNIQUE LABEL COVER problem, with single exponential dependency on the size of the cutset and the size of the alphabet. As a consequence, we extend the set of the polynomial time solvable instances of UNIQUE GAMES to those with at most O(√{log n}) violated constraints. (2) We obtain a new FPT algorithm for the STEINER CUT problem with exponential speed-up over the recent work of Kawarabayashi and Thorup (FOCS'11). (3) We show how to combine considering 'cut' and 'uncut' constraints at the same time. We define a robust problem NODE MULTIWAY CUT-UNCUT that can serve as an abstraction of introducing uncut constraints, and show that it admits an FPT algorithm with single exponential dependency on the size of the cutset. To the best of our knowledge, the only known way of tackling uncut constraints was via the approach of Marx, O'Sullivan and Razgon (STACS'10), which yields algorithms with double exponential running time. An interesting aspect of our algorithms is that they can handle real weights, to the best of our knowledge, the technique of important separators does not work in the weighted version.

The Pathwidth One Vertex Deletion (POVD) problem asks whether, given an undirected graph G and an integer k, one can delete at most k vertices from G so that the remaining graph has pathwidth at most 1. The question can be considered as a natural variation of the extensively studied Feedback Vertex Set (FVS) problem, where the deletion of at most k vertices has to result in the remaining graph having treewidth at most 1 (i.e., being a forest). Recently Philip et al. (WG, Lecture Notes in Computer Science, vol. 6410, pp. 196–207, 2010) initiated the study of the parameterized complexity of POVD, showing a quartic kernel and an algorithm which runs in time 7 k n O(1). In this article we improve these results by showing a quadratic kernel and an algorithm with time complexity 4.65 k n O(1), thus obtaining almost tight kernelization bounds when compared to the general result of Dell and van Melkebeek (STOC, pp. 251–260, ACM, New York, 2010). Techniques used in the kernelization are based on the quadratic kernel for FVS, due to Thomassé (ACM Trans. Algorithms 6(2), 2010).

One of the driving problems in the CSP area is the dichotomy conjecture, formulated in 1993 by Feder and Vardi [Monotone monadic SNP and constraint satisfaction, in Proceedings of the 25th Annual Symposium on Theory of Computing, ACM, New York, 1993, pp. 612--622], stating that for any fixed relational structure $\Gamma$ the constraint satisfaction problem CSP($\Gamma$) is either NP-complete or polynomial time solvable. A large amount of research has gone into checking various specific cases of this conjecture. One such variant which attracted a lot of attention in recent years is the List Matrix Partition problem. In 2004 Cameron et al. [SIAM J. Discrete Math., 21 (2007), pp. 900--929] classified almost all List Matrix Partition variants for matrices of size at most four. The only case which resisted the classification became known as the Stubborn problem. In this paper we show a result which enables us to finish the classification---thus solving a problem which resisted attacks for a few years. Our approach is based on a combinatorial problem known to be at least as hard as the Stubborn problem---the 3-Compatible Coloring problem. In this problem we are given a complete graph with each edge assigned one of three possible colors and we want to assign one of those three colors to each vertex in such a way that no edge has the same color as both of its endpoints. The tractability of the 3-Compatible Coloring problem has been open for several years and the best known algorithm prior to this paper is due to Feder et al. [Two algorithms for general list matrix partitions, in Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms, ACM, New York, SIAM, Philadelphia, 2005, pp. 870--876]---a quasipolynomial algorithm with a $n^{O(\log n / \log \log n)}$ time complexity. In this paper we present a polynomial-time algorithm for the 3-Compatible Coloring problem and consequently we prove a dichotomy for the k-Compatible Coloring problem.

For the vast majority of local problems on graphs of small tree width (where by local we mean that a solution can be verified by checking separately the neighbourhood of each vertex), standard dynamic programming techniques give c^tw |V|^O(1) time algorithms, where tw is the tree width of the input graph G = (V, E) and c is a constant. On the other hand, for problems with a global requirement (usually connectivity) the best -- known algorithms were naive dynamic programming schemes running in at least tw^tw time. We breach this gap by introducing a technique we named Cut&Count that allows to produce c^tw |V|^O(1) time Monte Carlo algorithms for most connectivity-type problems, including Hamiltonian Path, Steiner Tree, Feedback Vertex Set and Connected Dominating Set. These results have numerous consequences in various fields, like parameterized complexity, exact and approximate algorithms on planar and H-minor-free graphs and exact algorithms on graphs of bounded degree. The constant c in our algorithms is in all cases small, and in several cases we are able to show that improving those constants would cause the Strong Exponential Time Hypothesis to fail. In contrast to the problems aiming to minimize the number of connected components that we solve using Cut&Count as mentioned above, we show that, assuming the Exponential Time Hypothesis, the aforementioned gap cannot be breached for some problems that aim to maximize the number of connected components like Cycle Packing.

We present a polynomial time algorithm for the 3-Compatible colouring problem, where we are given a complete graph with each edge assigned one of 3 possible colours and we want to assign one of those 3 colours to each vertex in such a way that no edge has the same colour as both of its endpoints. Consequently we complete the proof of a dichotomy for the k-Compatible Colouring problem. The tractability of the 3-Compatible colouring problem has been open for several years and the best known algorithm prior to this paper is due to Feder et al. [SODA'05] — a quasipolynomial algorithm with a nO(log n/log log n) time complexity. Furthermore our result implies a polynomial algorithm for the Stubborn problem which enables us to finish the classification of all List Matrix Partition variants for matrices of size at most four over subsets of {0, 1} started by Cameron et al. [SODA'04].