We introduce the tree-decomposition-based graph parameter Odd-Cycle-Packing-treewidth (OCP-tw) as a width parameter that asks to decompose a given graph into pieces of bounded odd cycle packing number. The parameter OCP-tw is monotone under the odd-minor-relation and we provide an analogue to the celebrated Grid Theorem of Robertson and Seymour for OCP-tw. That is, we identify two infinite families of grid-like graphs whose presence as odd-minors implies large OCP-tw and prove that their absence implies bounded OCP-tw. This structural result is constructive and implies a 2^(poly(k))poly(n)-time parameterized poly(k)-approximation algorithm for OCP-tw. Moreover, we show that the (weighted) Maximum Independent Set problem (MIS) can be solved in polynomial time on graphs of bounded OCP-tw. Finally, we lift the concept of OCP-tw to a parameter for matrices of integer programs. To this end, we show that our strategy can be applied to efficiently solve integer programs whose matrices can be "tree-decomposed" into totally delta-modular matrices with at most two non-zero entries per row.

We provide proofs certifying that the structure theorem for vertex sets of bounded bidimensionality holds with polynomial bounds. The bidimensionality of vertex sets is a common generalisation of both treewidth and the face-cover-number of vertex sets in planar graphs. As such, it plays a crucial role in extensions of Courcelle’s Theorem to H-minor-free graphs. Recently, bidimensionality and similar parameters have emerged as key for extensions of known parameterized algorithms for problems defined on a terminal set R. A prominent example for such a problem is Steiner Tree, which admits efficient algorithms on planar graphs whenever R can be covered with few faces. Key to the algorithmic applications of bidimensionality is a structure theorem that explains how a graph G can be decomposed into pieces where the behaviour of R is highly controlled. One may see this structure theorem as a rooted analogue of Robertson and Seymour’s celebrated Grid Theorem. Combining recent advances in obtaining polynomial bounds in the Graph Minors framework with new techniques for handling annotated vertex sets, we show that all parameters in the structure theorem above admit polynomial bounds. As an application, we also provide a sketch showing how our techniques imply polynomial bounds for the structure theorem for graphs excluding an apex minor.

We introduce the notion of colorful minors, which generalizes the classical concept of rooted minors in graphs. A $q$-colorful graph= is defined as a pair $(G, χ),$ where $G$ is a graph and $χ$ assigns to each vertex a (possibly empty) subset of at most $q$ colors. The colorful minor relation enhances the classical minor relation by merging color sets at contracted edges and allowing the removal of colors from vertices. This framework naturally models algorithmic problems involving graphs with (possibly overlapping) annotated vertex sets. We develop a structural theory for colorful minors by establishing three core theorems characterizing $\mathcal{H}$-colorful minor-free graphs, where $\mathcal{H}$ consists either of a clique or a grid with all vertices assigned all colors, or of grids with colors segregated and ordered on the outer face. Our results reveal that when exclusion is imposed not only on graphs but also to the way colors are distributed in them, a more refined structural landscape appears. On the algorithmic side, we deduce that colorful minor testing is fixed-parameter tractable. Together with the fact that the colorful minor relation forms a well-quasi-order, this implies that every colorful minor-monotone parameter on colorful graphs admits a fixed-parameter algorithm. Furthermore, we derive two algorithmic meta-theorems (AMTs) whose structural conditions are linked to extensions of treewidth and Hadwiger number on colorful graphs. Our results suggest how known AMTs can be extended to incorporate not only the structure of the input graph but also the way the colored vertices are distributed in it.

We prove that for any circle graph \(H\) with at least one edge and for any positive integer \(k\), there exists an integer \(t = t(k,H)\) so that every graph \(G\) either has a vertex-minor isomorphic to the disjoint union of \(k\) copies of \(H\), or has a \(t\)-perturbation with no vertex-minor isomorphic to \(H\). Using the same techniques, we also prove that for any planar multigraph \(H\), every binary matroid either has a minor isomorphic to the cycle matroid of \(kH\), or is a low-rank perturbation of a binary matroid with no minor isomorphic to the cycle matroid of \(H\).

We show that every \(H\)-minor-free graph that also excludes a \((k \times k)\)-grid as a minor has treewidth/branchwidth bounded from above by a function \(f(t,k)\) that is linear in \(k\) and polynomial in \(t := |V(H)|\). Such a result was proven originally by [Demaine & Hajiaghayi, Combinatorica, 2008], where \(f\) was indeed linear in \(k\). However the dependency in \(t\) in this result was non-explicit (and huge). Later, [Kawarabayashi & Kobayashi, JCTB, 2020] showed that this bound can be estimated to be \(f(t,k) \in 2^{\mathcal O(t \log t)} \cdot k\). Wood recently asked whether \(f\) can be pushed further to be polynomial, while maintaining the linearity on \(k\). We answer this in a particularly strong sense, by showing that the treewidth/branchwidth of \(G\) is in \(\mathcal O(gk + t^{2304})\), where \(g\) is the Euler genus of \(H\). This directly yields \(f(t,k) = \mathcal O(t^2 k + t^{2304})\).

The Graph Minor Structure Theorem, originally proven by Robertson and Seymour [JCTB, 2003], asserts that there exist functions ${f_1},{f_2}:\mathbb{N} \to {\mathbb{N}}$ such that for every non-planar graph H with t := |V (H)|, every H-minor-free graph can be obtained via the clique-sum operation from graphs which embed into surfaces where H does not embed after deleting at most f1(t) many vertices with up to at most t2− 1 many "vortices" which are of "depth" at most f2(t). In the proof presented by Robertson and Seymour the functions f1and f2are non-constructive. Kawarabayashi, Thomas, and Wollan [arXiv, 2020] found a new proof showing that f1(t),f2(t) ∈ 2poly(t). While believing that this bound was the best their methods could achieve, Kawarabayashi, Thomas, and Wollan conjectured that f1and f2can be improved to be polynomials.In this paper we confirm their conjecture and prove that f1(t),f2(t) ∈ O(t2300). Our proofs are fully constructive and yield a polynomial-time algorithm that either finds H as a minor in a graph G or produces a clique-sum decomposition for G as above.

International audience

Abstract. We prove that if a graph contains the complete bipartite graph [Formula: see text] as an induced minor, then it contains a cycle of length at most 12 or a theta as an induced subgraph. With a longer and more technical proof, we prove that if a graph contains [Formula: see text] as an induced minor, then it contains a triangle or a theta as an induced subgraph. Here, a theta is a graph made of three internally vertex-disjoint chordless paths [Formula: see text], [Formula: see text], [Formula: see text], each of length at least two, such that no edges exist between the paths except the three edges incident to [Formula: see text] and the three edges incident to [Formula: see text]. A consequence is that excluding a grid and a complete bipartite graph as induced minors is not enough to guarantee a bounded tree-independence number or even that the treewidth is bounded by a function of the size of the maximum clique, because the existence of graphs with large treewidth that contain no triangles or thetas as induced subgraphs is already known (the so-called layered wheels).

Let$\mathcal{G}$and$\mathcal{H}$be minor-closed graph classes. We say that the pair$(\mathcal{H},\ \mathcal{G})$is an Erdös-Pósa pair (EP-pair) if there exists a function$f$such that for every$k$and every graph$G\in \mathcal{G}$, either$G$has$k$pairwise vertex-disjoint sub graphs which do not belong to$\mathcal{H}$, or there exists a set$S\subseteq V(G)$of size at most$f(k)$for which$G-S\in \mathcal{H}$. The classic result of Erdös and Pósa says that if$\mathcal{F}$is the class of forests, then$(\mathcal{F}, \mathcal{G})$is an EP-pair for all graph classes$\mathcal{G}$. A minor-closed graph class$\mathcal{G}$is an EP-counterexample for$\mathcal{H}$if$\mathcal{G}$is minimal with the property that$(\mathcal{H},\ \mathcal{G})$is not an EP-pair. In this paper, we prove that for every minor-closed graph class$\mathcal{H}$the set$\mathfrak{C}_{\mathcal{H}}$of all EP-counterexamples for$\mathcal{H}$is finite. In particular, we provide a complete characterization of$\mathfrak{C}_{\mathcal{H}}$for every$\mathcal{H}$and give a constructive upper bound on its size. We show that each class$\mathcal{G}$in$\mathfrak{C}_{\mathcal{H}}$can be described as the set of all minors of some, suitably defined, sequence of grid-like graphs$\langle{W}_{k}\rangle_{k\in \mathbb{N}}$. Moreover, each$\mathrm{W}_{k}$admits a half-integral packing, i.e.,$k$copies of some$H\not\in \mathcal{H}$where no vertex is used more than twice. This implies a complete delineation of the half-integrality threshold of the Erdös-Pósa property for minors and as a corollary, we obtain a constructive proof of Thomas' conjecture on the half-integral Erdös-Pósa property for minors which was recently confirmed by Liu. Our results are algorithmic. Let$h=h(\mathcal{H})$denote the maximum size of an obstruction to$\mathcal{H}$. For every minor-closed graph class$\mathcal{H}$, we construct an algorithm that, given a graph$G$and an integer$k$, either outputs a half-integral packing of$k$copies of some$H\not\in \mathcal{H}$or outputs a set of at most$2^{k^{\overline{\mathcal{O}}_{h}(1)}}$vertices whose deletion creates a graph in$\mathcal{H}$in time$2^{2^{k^{\mathcal{O}_{h}(1)}}}\cdot\vert G\vert ^{4}\log\vert G\vert$. Moreover, as a consequence of our results, for every minor-closed class$\mathcal{H}$, we obtain min-max-dualities, which may be seen as analogues of the celebrated Grid Theorem of Robertson and Seymour, for the recently introduced parameters$\mathcal{H}$-treewidth and elimination distance to$\mathcal{H}$.

In 1986 Robertson and Seymour proved a generalization of the seminal result of Erdős and Pósa on the duality of packing and covering cycles: A graph has the Erdős-Pósa property for minors if and only if it is planar. In particular, for every non-planar graph H they gave examples showing that the Erdős-Pósa property does not hold for H. Recently, Liu confirmed a conjecture of Thomas and showed that every graph has the half-integral Erdős-Pósa property for minors. Liu’s proof is non-constructive and to this date, with the exception of a small number of examples, no constructive proof is known. In this paper, we initiate the delineation of the half-integrality of the Erdős-Pósa property for minors. We conjecture that for every graph H, there exists a unique (up to a suitable equivalence relation on graph parameters) graph parameter EP_H such that H has the Erdős-Pósa property in a minor-closed graph class 𝒢 if and only if sup{EP_H(G) ∣ G ∈ 𝒢} is finite. We prove this conjecture for the class ℋ of Kuratowski-connected shallow-vortex minors by showing that, for every non-planar H ∈ ℋ, the parameter EP_H(G) is precisely the maximum order of a Robertson-Seymour counterexample to the Erdős-Pósa property of H which can be found as a minor in G. Our results are constructive and imply, for the first time, parameterized algorithms that find either a packing, or a cover, or one of the Robertson-Seymour counterexamples, certifying the existence of a half-integral packing for the graphs in ℋ.

In 1913, Pólya asked for which (0,1)-matrices A it is possible to create a new matrix A′ by changing some of the signs such that the permanent of A equals the determinant of A′. A combinatorial solution to this problem was found by Little in 1975; he found these matrices to be exactly the biadjacency matrices of bipartite graphs excluding K3,3 as a matching minor. Utilising ideas from graph minors theory, this characterisation was later shown to yield a polynomial time algorithm to compute the permanent of matrices which satisfy Little’s condition. By a seminal result of Valiant, computing the permanent of (0,1)-matrices in general is #P-hard; however, it can be observed that the tractability of the permanent is closely related to the exclusion of matchings minors in bipartite graphs.

We prove the existence of a computable function f∶ℕ→ℕ such that for every integer k and every digraph D, either D contains a collection C of k directed cycles of even length such that no vertex of D belongs to more than four cycles in C, or there exists a set S⊆ V(D) of size at most f(k) such that D−S has no directed cycle of even length. Moreover, we provide an algorithm that finds one of the two outcomes of this statement in time g(k)nO(1) for some computable function g∶ ℕ→ℕ.

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.

We introduce a new kernelization tool, called rainbow matching technique, that is appropriate for the design of polynomial kernels for packing problems. Our technique capitalizes on the powerful combinatorial results of [Graf, Harris, Haxell, SODA 2021]. We apply the rainbow matching technique on two (di)graph packing problems, namely the TRIANGLE-PACKING IN TOURNAMENT problem (TPT), where we ask for a packing of k directed triangles in a tournament, and the INDUCED 2-PATH-PACKING (I2PP) where we ask for a packing of k induced paths of length two in a graph. The existence of a sub-quadratic kernels for these problems was proven for the first time in [Fomin, Le, Lokshtanov, Saurabh, Thomassé, Zehavi. ACM Trans. Algorithms, 2019], where they gave a kernel of

By a seminal result of Valiant, computing the permanent of (0,1)-matrices is, in general, #P-hard. In 1913 Polya asked for which (0,1)-matrices A it is possible to change some signs such that the permanent of A equals the determinant of the resulting matrix. In 1975, Little showed these matrices to be exactly the biadjacency matrices of bipartite graphs excluding K3,3 as a matching minor. This was turned into a polynomial time algorithm by McCuaig, Robertson, Seymour, and Thomas in 1999. However, the relation between the exclusion of some matching minor in a bipartite graph and the tractability of the permanent extends beyond K3,3. Recently it was shown that the exclusion of any planar bipartite graph as a matching minor yields a class of bipartite graphs on which the permanent of the corresponding (0,1)-matrices can be computed efficiently. In this paper we unify the two results above into a single, more general result in the style of the celebrated structure theorem for single-crossing-minor-free graphs. We identify a class of bipartite graphs strictly generalising planar bipartite graphs and K3,3 which includes infinitely many non-Pfaffian graphs. The exclusion of any member of this class as a matching minor yields a structure that allows for the efficient evaluation of the permanent. Moreover, we show that the evaluation of the permanent remains #P-hard on bipartite graphs which exclude K5,5 as a matching minor. This establishes a first computational lower bound for the problem of counting perfect matchings on matching minor closed classes. As another application of our structure theorem, we obtain a strict generalisation of the algorithm for the k-vertex disjoint directed paths problem on digraphs of bounded directed treewidth.

We provide a “vortex-free” refinement of the seminal structure theorem for $K_{t} -$minor free graphs by Robertson and Seymour as follows: we identify a (parameterized) graph Htand we prove that if we replace Ktby Ht, then the resulting decomposition becomes “vortex-free”. Up to now, the most general classes of graphs admitting such a result were either bounded Euler genus graphs or the single-crossing minor-free graphs. This result is tight in the sense that, whenever we minor-exclude a graph that is not a minor of some Ht, the appearance of vortices is unavoidable. Using the above decomposition theorem, we design an algorithm that, given an $H_{t} -$minor-free graph G, computes the generating function of all perfect matchings of G in polynomial time. This algorithm yields, on $H_{t} -$minor-free graphs, polynomial algorithms for computational problems such as the dimer problem, the exact matching problem, and the computation of the permanent. 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 precisely those graph classes that do not contain every Htas a minor. This provides a sharp complexity dichotomy for the problem of counting perfect matchings in minor-closed classes.

We consider the SDN network update problem in which a controller wants to update the routes of k (unsplittable) flows from their old paths to the new paths, consistently, i.e., without temporary congestion. As updates communicated by the controller take effect asynchronously, the challenge is to perform these updates fast, i.e., using a minimal number of rounds (controller interactions). We present the first fast, i.e., polynomial-time solution for scheduling such congestion-free network updates, for two flows and in the node ordering model. We also show that the problem is already NP-hard for six flows. We complement our formal results with simulations.

Changing a given configuration in a graph into another one is known as a reconfiguration problem. Such problems have recently received much interest in the context of algorithmic graph theory. We initiate the theoretical study of the following reconfiguration problem: How to reroute k unsplittable flows of a certain demand in a capacitated network from their current paths to their respective new paths, in a congestion-free manner? This problem finds immediate applications, e.g., in traffic engineering in computer networks. We show that the problem is generally NP-hard already for k=2 flows, which motivates us to study rerouting on a most basic class of flow graphs, namely DAGs. Interestingly, we find that for general k, deciding whether an unsplittable multi-commodity flow rerouting schedule exists, is NP-hard even on DAGs. Our main contribution is a polynomial-time (fixed parameter tractable) algorithm to solve the route update problem for a bounded number of flows on DAGs. At the heart of our algorithm lies a novel decomposition of the flow network that allows us to express and resolve reconfiguration dependencies among flows.