Search

The Graph Minors Structure Theorem of Robertson and Seymour asserts that, for every graph H, every H-minor-free graph can be obtained by clique-sums of "almost embeddable" graphs. Here a graph is "almost embeddable" if it can be obtained from a graph of bounded Euler-genus by pasting graphs of bounded pathwidth in an "orderly fashion" into a bounded number of faces, called the vortices, and then adding a bounded number of additional vertices, called apices, with arbitrary neighborhoods. Our main result is a full classification of all graphs H for which the use of vortices in the theorem above can be avoided. To this end, we identify a (parametric) graph \(\mathscr{S}_{t}\) and prove that all \(\mathscr{S}_{t}\) -minor-free graphs can be obtained by clique-sums of graphs embeddable in a surface of bounded Euler-genus after deleting a bounded number of vertices. We show that this result is tight in the sense that the appearance of vortices cannot be avoided for H-minor-free graphs, whenever H is not a minor of \(\mathscr{S}_{t}\) for some \(t\in \mathbb {N}\). Using our new structure theorem, we design an algorithm that, given an \(\mathscr{S}_{t}\) -minor-free graph G, computes the generating function of all perfect matchings of G in polynomial time. Our results, combined with known complexity results, imply a complete characterization of minor-closed graph classes where the number of perfect matchings is polynomially computable: They are exactly those graph classes that do not contain every \(\mathscr{S}_{t}\) as a minor. This provides a sharp complexity dichotomy for the problem of counting perfect matchings in minor-closed classes. [ABSTRACT FROM AUTHOR]

For a fixed finite collection of graphs F, the F-M-DELETION problem is as follows: given an n-vertex input graph G, find the minimum number of vertices that intersect all minor models in G of the graphs in F. by Courcelle's Theorem, this problem can be solved in time fF(tw) - n°(1), where tw is the treewidth of G for some function ƒ depending on F. In a recent series of articles, we have initiated the program of optimizing asymptotically the function ff. Here we provide an algorithm showing that fF(tw) = 2° (tw.log tw) for every collection F. Prior to this work, the best known function ƒ was double- exponential in tw. In particular, our algorithm vastly extends the results of Jansen, Lokshtanov, and Saurabh [Proc. of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, 2014, pp. 1802-1811] for the particular case F = {K5, K3,3} and of Kociumaka and Pilipczuk [Algorithmica, 81 (2019), pp. 3655-3691] for graphs of bounded genus, and answers an open problem posed by Cygan et al. [Inform. Comput., 256 (2017), pp. 62-82]. We combine several ingredients such as the machinery of boundaried graphs in dynamic programming via representatives, the Flat Wall Theorem, bidimensionality, the irrelevant vertex technique, treewidth modulators, and protrusion replacement. Together with our previous results providing single-exponential algorithms for particular collections F [J. Baste, I. Sau, and D. M. Thilikos, Theoret. Comput. Sci., 814 (2020), pp. 135-152] and general lower bounds [J. Baste, I. Sau, and D. M. Thilikos, J. Comput. Syst. Sci., 109 (2020), pp. 56-77], our algorithm yields the following complexity dichotomy when F = {H} contains a single connected graph H, assuming the Exponential Time Hypothesis: ƒH(tw) = 2Θ(tw) if H is a contraction of the chair or the banner, and fH(tw) = 2Θ(tw-log tw) otherwise. [ABSTRACT FROM AUTHOR]

Let G be a minor-closed graph class. We say that a graph G is a k-apex of G if G contains a set S of at most k vertices such that G\S belongs to G. We denote by Ak (G) the set of all graphs that are k-apices of G. In the first paper of this series, we obtained upper bounds on the size of the graphs in the minor-obstruction set of Ak (G), i.e., the minor-minimal set of graphs not belonging to Ak (G). In this article, we provide an algorithm that, given a graph G on n vertices, runs in time 2poly(k) · n3 and either returns a set S certifying that G ∈ Ak (G), or reports that G ∉ Ak (G). Here poly is a polynomial function whose degree depends on the maximum size of a minor-obstruction of G. In the special case where G excludes some apex graph as a minor, we give an alternative algorithm running in 2poly(k) · n²-time. [ABSTRACT FROM AUTHOR]

For a finite collection of graphs F, the F-M-DELETION problem consists in, given a graph G and an integer k, deciding whether there exists S ⊆ V (G) with |S| ≤ k such that G\S does not contain any of the graphs in F as a minor. We are interested in the parameterized complexity of F-M-Deletion when the parameter is the treewidth of G, denoted by tw. Our objective is to determine, for a fixed F, the smallest function fF such that F-M-DELETION can be solved in time fF(tw) . nO(1) on n-vertex graphs. We prove that fF(tw) = 2²O(tw.logtw) for every collection F, that fF(tw) = 2O(tw.log tw) if F contains a planar graph, and that fF(tw) = 2O(tw) if in addition the input graph G is planar or embedded in a surface. We also consider the version of the problem where the graphs in F are forbidden as topological minors, called F-TM-Deletion. We prove similar results for this problem, except that in the last two algorithms, instead of requiring F to contain a planar graph, we need it to contain a subcubic planar graph. This is the first of a series of articles on this topic. [ABSTRACT FROM AUTHOR]

Given a finite set of graphs H and a non-negative integer k , we define A k (H) as the set containing every graph G that has k vertices whose removal provides a graph without any of the graphs in H as a minor. It is known that if H contains at least one planar graph then each obstruction in A k (H) has at most k c H vertices, for some c H depending only on the choice of H. In this paper, we investigate the size of the graphs in A k (H) that belong to certain classes of sparse graphs. In particular, we prove that for every graph F , if H contains at least one planar graph and only connected graphs, all graphs in A k (H) that are F -topological minor-free have at most c F , H ⋅ k vertices, where c F , H depends exclusively on the choice of H and F. Our result is a consequence of two more general conditions on graph parameters, namely the Finite Integer Index Property and Protrusion Decomposability, that can serve as a general framework for proving linear bounds for obstructions. [ABSTRACT FROM AUTHOR]

Several min–max relations in graph theory can be expressed in the framework of the Erdős–Pósa property. Typically, this property reveals a connection between packing and covering problems on graphs. We describe some recent techniques for proving this property that are related to tree-like decompositions. We also provide an unified presentation of the current state of the art on this topic. [ABSTRACT FROM AUTHOR]

Several algorithmic meta-theorems on kernelization have appeared in the last years, starting with the result of Bodlaender et al. [(Meta) kernelization, in Proceedings of the 50th IEEE Symposium on Foundations of Computer Science (FOCS), IEEE Computer Society, 2009, pp. 629– 638] on graphs of bounded genus, then generalized by Fomin et al. [Bidimensionality and kernels, in Proceedings of the 21st ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, Philadephia, 2010, pp. 503–510] to graphs excluding a fixed minor, and by Kim et al. [Linear kernels and single-exponential algorithms via protrusion decompositions, in Proceedings of the 40th International Colloquium on Automata, Languages and Programming (ICALP), Lecture Notes in Comput. Sci., 7965 (2013), pp. 613–624] to graphs excluding a fixed topological minor. Typically, these results guarantee the existence of linear or polynomial kernels on sparse graph classes for problems satisfying some generic conditions, but, mainly due to their generality, it is not clear how to derive from them constructive kernels with explicit constants. In this paper, we make a step toward a fully constructive meta-kernelization theory on sparse graphs. Our approach is based on a more explicit protrusion replacement machinery that, instead of expressibility in counting monadic second order logic, uses dynamic programming, which allows us to find an explicit upper bound on the size of the derived kernels. We demonstrate the usefulness of our techniques by providing the first explicit linear kernels for r-Dominating Set and r-Scattered Set on apex-minor-free graphs, and for PLANAR-F-DELETION on graphs excluding a fixed (topological) minor in the case where all the graphs in F are connected. [ABSTRACT FROM AUTHOR]

Abstract: Let be a graph class. The square root of contains all graphs whose squares belong in . We prove that if is non-trivial and minor closed, then all graphs in its square root have carving-width bounded by some constant depending only on . As a consequence, every square root of such a graph class has a linear time recognition algorithm. [Copyright &y& Elsevier]

One of the major results of [N. Robertson and P. D. Seymour, Graph minors. XIII. The disjoint paths problem, J. Combin. Theory Ser. B, 63 (1995), pp. 65-110], also known as the weak structure theorem, reveals the local structure of graphs excluding some graph as a minor: each such graph G either has small treewidth or contains the subdivision of a planar graph (a wall) that can be arranged in a flat manner inside G, given that some small set of vertices is removed. We prove an optimized version of that theorem where (i) the relation between the treewidth of the graph and the height of the wall is linear (thus best possible) and (ii) the number of vertices to be removed is minimized. [ABSTRACT FROM AUTHOR]

Let G be a minor-closed graph class. We say that a graph G is a k-apex of G if G contains a set S of at most k vertices such that G ∖ S belongs to G. We denote by A k (G) the set of all graphs that are k -apices of G. We prove that every graph in the obstruction set of A k (G) , i.e., the minor-minimal set of graphs not belonging to A k (G) , has order at most 2 2 2 2 poly (k) , where poly is a polynomial function whose degree depends on the order of the minor-obstructions of G. This bound drops to 2 2 poly (k) when G excludes some apex graph as a minor. [ABSTRACT FROM AUTHOR]

Abstract: Let be a graph class. The square root of contains all graphs whose square belong in . We prove that if is non-trivial and minor closed, then all graphs in its square root have carving-width bounded by some constant depending only on . As a consequence, every square root of such a graph class has a linear time recognition algorithm. [Copyright &y& Elsevier]

Abstract: We present subexponential parameterized algorithms on planar graphs for a family of problems of the following shape: given a graph, find a connected (induced) subgraph with bounded maximum degree and with maximum number of edges (or vertices). These problems are natural generalisations of the Longest Path problem. Our approach uses bidimensionality theory combined with novel dynamic programming techniques over branch decompositions of the input graph. These techniques can be applied to a more general family of problems that deal with finding connected subgraphs under certain degree constraints. [Copyright &y& Elsevier]

Abstract: For every , we define as the class of graphs with tree-depth at most k, i.e. the class containing every graph G admitting a valid colouring such that every -path between two vertices where contains a vertex z where . In this paper we study the class of minor-minimal elements not belonging in for every . We give a precise characterization of and prove a structural lemma for creating graphs , . As a consequence, we obtain a precise characterization of all acyclic graphs in and we prove that they are exactly . [Copyright &y& Elsevier]

Abstract: For , let be the class containing every graph that contains k vertices meeting all its cycles. The minor-obstruction set for is the set containing all minor-minimal graph that does not belong to . We denote by the set of all outerplanar graphs in . In this paper, we provide a precise characterization of the class . Then, using the symbolic method, we prove that where and . [Copyright &y& Elsevier]

Abstract: We present subexponential parameterized algorithms on planar graphs for a family of problems that consist in, given a graph G, finding a connected (induced) subgraph H with bounded maximum degree, while maximising the number of edges (or vertices) of H. These problems are natural generalisations of Longest Path. Our approach uses bidimensionality theory combined with novel dynamic programming techniques over branch decompositions of the input graph. These techniques can be applied to a more general family of problems that deal with finding connected subgraphs under certain degree constraints. [Copyright &y& Elsevier]

Bidimensionality provides a tool for developing subexponential fixed-parameter algorithms for combinatorial optimization problems on graph families that exclude a minor. This paper extends the theory of bidimensionality for graphs of bounded genus (which is a minor-excluding family). Specifically we show that, for any problem whose solution value does not increase under contractions and whose solution value is large on a grid graph augmented by a bounded number of handles, the treewidth of any bounded-genus graph is at most a constant factor larger than the square root of the problem's solution value on that graph. Such bidimensional problems include vertex cover, feedback vertex set, minimum maximal matching, dominating set, edge dominating set, r-dominating set, connected dominating set, planar set cover, and diameter. On the algorithmic side, by showing that an augmented grid is the prototype bounded-genus graph, we generalize and simplify many existing algorithms for such problems in graph classes excluding a minor. On the combinatorial side, our result is a step toward a theory of graph contractions analogous to the seminal theory of graph minors by Robertson and Seymour. [ABSTRACT FROM AUTHOR]

For several graph-theoretic parameters such as vertex cover and dominating set, it is known that if their sizes are bounded by k, then the treewidth of the graph is bounded by some function of k. This fact is used as the main tool for the design of several fixed-parameter algorithms on minor-closed graph classes such as planar graphs, single-crossing-minor-free graphs, and graphs of bounded genus. In this paper we examine whether similar bounds can be obtained for larger minor-closed graph classes and for general families of graph parameters, including all those for which such behavior has been reported so far. Given a graph parameter P, we say that a graph family F has the parameter-treewidth property for P if there is an increasing function t such that every graph G ∈ F has treewidth at most t(P(C)). We prove as our main result that, for a large family of graph parameters called contraction-bidimensional, a minor-closed graph family F has the parameter-treewidth property if F has bounded local treewidth. We also show "if and only if" for some graph parameters, and thus, this result is in some sense tight. In addition we show that, for a slightly smaller family of graph parameters called minor-bidimensional, all minor-closed graph families F, excluding some fixed graphs, have the parameter-treewidth property. The contraction-bidimensional parameters include many domination and covering graph parameters such as vertex cover, feedback vertex set, dominating set, edge-dominating set, and q-dominating set (for fixed q). We use our theorems to develop new fixed-parameter algorithms in these contexts. [ABSTRACT FROM AUTHOR]

For a finite fixed collection of graphs F , the F -M-Deletion problem consists in, given a graph G and an integer k , decide whether there exists S ⊆ V (G) with | S | ≤ k such that G ∖ S does not contain any of the graphs in F as a minor. We provide lower bounds under the ETH on the smallest function f F such that F -M-Deletion can be solved in time f F (tw) ⋅ n O (1) on n -vertex graphs, where tw denotes the treewidth of G. We first prove that for any F containing connected graphs of size at least two, f F (tw) = 2 Ω (tw) , even if G is planar. Our main result is that if F contains a single connected graph H that is either P 5 or is not a minor of the b a n n e r , then f F (tw) = 2 Ω (tw ⋅ log ⁡ tw). [ABSTRACT FROM AUTHOR]

For a finite collection of graphs F , the F -M-Deletion (resp. F -TM-Deletion) problem consists in, given a graph G and an integer k , decide whether there exists S ⊆ V (G) with | S | ≤ k such that G ∖ S does not contain any of the graphs in F as a minor (resp. topological minor). We are interested in the parameterized complexity of both problems when the parameter is the treewidth of G , denoted by tw , and specifically in the cases where F contains a single connected planar graph H. We present algorithms running in time 2 O (tw) ⋅ n O (1) , called single-exponential , when H is either P 3 , P 4 , C 4 , the paw , the chair , and the banner for both { H } -M-Deletion and { H } -TM-Deletion , and when H = K 1 , i , with i ≥ 1 , for { H } -TM-Deletion. Some of these algorithms use the rank-based approach introduced by Bodlaender et al. (2015) [7]. This is the second of a series of articles on this topic, and the results given here together with other ones allow us, in particular, to provide a tight dichotomy on the complexity of { H } -M-Deletion in terms of H. [ABSTRACT FROM AUTHOR]

Abstract: Our goal in this paper is the development of fast algorithms for recognizing general classes of graphs. We seek algorithms whose complexity can be expressed as a linear function of the graph size plus an exponential function of k, a natural parameter describing the class. In particular, we consider the class , where for each graph G in , the removal of a set of at most k vertices from G results in a graph in the base graph class . (If is the class of edgeless graphs, is the class of graphs with bounded vertex cover.) When is a minor-closed class such that each graph in has bounded maximum degree, and all obstructions of (minor-minimal graphs outside ) are connected, we obtain an recognition algorithm for , where g and f are constants (modest and quantified) depending on the class . If is the class of graphs with maximum degree bounded by (not closed under minors), we can still obtain a running time of for recognition of graphs in . Our results are obtained by considering bounded-degree minor-closed classes for which all obstructions are connected graphs, and showing that the size of any obstruction for is , where t is a bound on the size of obstructions for . A trivial corollary of this result is an upper bound of on the number of vertices in any obstruction of the class of graphs with vertex cover of size at most k. These results are of independent graph-theoretic interest. [Copyright &y& Elsevier]

A graph is sub-unicyclic if it contains at most one cycle. A graph G is k -apex sub-unicyclic if it can become sub-unicyclic by removing k of its vertices. We identify 29 graphs that are the minor-obstructions of the class of 1-apex sub-unicyclic graphs. For bigger values of k , we give an exact structural characterization of all the cactus graphs that are minor-obstructions of k -apex sub-unicyclic graphs and we enumerate them. This implies that, for k big enough, the class of k -apex sub-unicyclic graphs has at least 0. 33 ⋅ k − 2. 5 (6. 278) k + 1 minor-obstructions. [ABSTRACT FROM AUTHOR]

The Disjoint Paths Problem asks, given a graph G and a set of pairs of terminals ( s 1 , t 1 ) , … , ( s k , t k ) , whether there is a collection of k pairwise vertex-disjoint paths linking s i and t i , for i = 1 , … , k . In their f ( k ) ⋅ n 3 algorithm for this problem, Robertson and Seymour introduced the irrelevant vertex technique according to which in every instance of treewidth greater than g ( k ) there is an “irrelevant” vertex whose removal creates an equivalent instance of the problem. This fact is based on the celebrated Unique Linkage Theorem , whose – very technical – proof gives a function g ( k ) that is responsible for an immense parameter dependence in the running time of the algorithm. In this paper we give a new and self-contained proof of this result that strongly exploits the combinatorial properties of planar graphs and achieves g ( k ) = O ( k 3 / 2 ⋅ 2 k ) . Our bound is radically better than the bounds known for general graphs. [ABSTRACT FROM AUTHOR]

Abstract: The -Minor containment problem asks whether a graph contains some fixed graph as a minor, that is, whether can be obtained by some subgraph of after contracting edges. The derivation of a polynomial-time algorithm for -Minor containment is one of the most important and technical parts of the Graph Minor Theory of Robertson and Seymour and it is a cornerstone for most of the algorithmic applications of this theory. -Minor containment for graphs of bounded branchwidth is a basic ingredient of this algorithm. The currently fastest solution to this problem, based on the ideas introduced by Robertson and Seymour, was given by Hicks in [I.V. Hicks, Branch decompositions and minor containment, Networks 43 (1) (2004) 1–9], providing an algorithm that in time decides if a graph with edges and branchwidth , contains a fixed graph on vertices as a minor. In this work we improve the dependence on of Hicks’ result by showing that checking if is a minor of can be done in time . We set up an approach based on a combinatorial object called rooted packing, which captures the properties of the subgraphs of that we seek in our dynamic programming algorithm. This formulation with rooted packings allows us to speed up the algorithm when is embedded in a fixed surface, obtaining the first algorithm for minor containment testing with single-exponential dependence on branchwidth. Namely, it runs in time , with . Finally, we show that slight modifications of our algorithm permit to solve some related problems within the same time bounds, like induced minor or contraction containment. [Copyright &y& Elsevier]

A graph is called a pseudoforest if none of its connected components contains more than one cycle. A graph is an apex-pseudoforest if it can become a pseudoforest by removing one of its vertices. We identify 33 graphs that form the minor obstruction set of the class of apex-pseudoforests, i.e., the set of all minor-minimal graphs that are not apex-pseudoforests. [ABSTRACT FROM AUTHOR]