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 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.

The forcing number of a graph with a perfect matching M is the minimum number of edges in M whose endpoints need to be deleted, such that the remaining graph only has a single perfect matching. This number is of great interest in theoretical chemistry, since it conveys information about the structural properties of several interesting molecules. On the other hand, in bipartite graphs the forcing number corresponds to the famous feedback vertex set problem in digraphs. Determining the complexity of finding the smallest forcing number of a given planar graph is still a widely open and important question in this area, originally proposed by Afshani, Hatami, and Mahmoodian in 2004. We take a first step towards the resolution of this question by providing an algorithm that determines the set of all possible forcing numbers of an outerplanar graph in polynomial time. This is the first polynomial-time algorithm concerning this problem for a class of graphs of comparable or greater generality.

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∶ ℕ→ℕ.