Odd-Cycle-Packing-Treewidth: On the Maximum Independent Set Problem in Odd-Minor-Free Graph Classes

Our main result in this category is that MIS can be solved in polynomial time on graphs of bounded OCP-treewidth.

This algorithm consists of two parts. One that finds a OCP-tree-decomposition of small width and a second that is essentially a dynamic program along this decomposition which uses the algorithm of Fiorini et al. [18, 19] for weighted MIS in graphs of bounded odd cycle packing number as a blackbox. Due to the running time of the algorithm by Fiorini et al., the running time of our algorithm from Theorem 2 is of the form $n^{f(k)}$ where $f$ is a computable function.

There are several equivalent ways to state the celebrated Grid Theorem of Robertson and Seymour [49]. One of them would be a twofold statement as follows:

1. 1.

   For every $k\ge 1$, every graph containing the $(k\times k)$-grid as a minor has treewidth at least $k$.

2. 2.

   There exists a function $f$ such that for every $k\ge 1$, every graph with treewidth at least $f(k)$ contains the $(k\times k)$-grid as a minor.

A functionally equivalent statement would be:

A minor-closed graph class has bounded treewidth if and only if it excludes a planar graph.

Planarity in the statement above can be replaced by the phrase “… $𝒞$ excludes a graph $H$ such that there is a $k\ge 1$ for which $H$ is a minor of the $(k\times k)$-grid.” It just happens to be true that the class of all graphs that are a minor of some grid is exactly the class of planar graphs.

Our structural main result is an analogue of the Grid Theorem of Robertson and Seymour for OCP-treewidth under the odd-minor relation. This provides a satisfying answer to the question about structural properties of graphs of bounded OCP-treewidth as it classifies all odd-minor-closed graph classes where OCP-treewidth is bounded, and hence, where Theorem 2 can be applied. The role of the $(k\times k)$-grid is played by two infinite families of graphs – both consisting of planar graphs – to which we will refer to as the parity grids in the following. We present both types of parity grids in their cylindrical form here, but they could easily be expressed as square grids as well.

Let $k\ge 1$ be an integer and $H_k$ be the cylindrical $(k\times 4k)$-grid.⁴⁴4The cylindrical $(n\times m)$-grid is the Cartesian (or box) product of the path $P_n$ and the cycle $C_m$. Moreover, let $X=\{x_1,\mathrm{\dots },x_{2k}\}$ be a maximum subset of vertices of the $k$th copy of $C_{4k}$ in $H_k$ such that all vertices of $X$ are pairwise at even distance. The parity handle ${\mathscr{H}}_k$ of order $k$ is the graph obtained from $H_k$ by introducing the edges $x_i{x}_{2k-i+1}$ for all $i\in [k]$. The parity vortex ${𝒱}_k$ of order $k$ is the graph obtained from $H_k$ by introducing the edges $x_{2i-1}{x}_{2i}$ for all $i\in [k]$. See Figure 1 for examples.

Our structural main theorem reads as follows.

Since $f$ is a polynomial, the algorithm guaranteed by Theorem 6 in fact yields Theorem 5.

Notably, every odd-minor of a parity handle can be embedded into the plane with at most two odd faces, while every odd-minor of the parity vortex can be embedded in the plane with a unique face that meets all odd cycles in the graph. These two properties illustrate that there exist planar graphs $H$ such that $H$-odd-minor-free graphs have unbounded OCP-treewidth.

As MIS is NP-hard on planar graphs, the core question underlying our research is the following:

To give a more concrete example of the gaps in our understanding of MIS in planar graphs, consider the following problem concerning a class of graphs with unbounded $\mathrm{𝖮𝖢𝖯}$.

In the above question $k$ can clearly be taken to be even. The case $k\le 2$ was solved by Gerards in [26]. All other cases are widely open. In Question 8 we ask explicitly for an FPT-algorithm, but even an XP-algorithm is unknown and would fully suffice to further our understanding of Question 7.

Beyond planar graphs the following question seems key to expanding our understanding of the tractability of MIS. A graph embedded in a surface $\mathrm{\Sigma }$ is said to have an even-faced embedding if all of its odd cycles describes a genus-reducing curve in $\mathrm{\Sigma }$, equivalently no odd cycle bounds a disk in $\mathrm{\Sigma }$.

Question 8 and Question 9 are not asked idly. We strongly believe that both of these questions must in some way be resolved to expand the structural understanding of odd-minor-free graph classes in which MIS is efficiently solvable beyond the results of this paper, that is the combination of Theorem 6 and Theorem 2. Notably, both questions diverge from the perspective of [12], [19], and [1] as the classes considered here all contain graphs of unbounded $\mathrm{𝖮𝖢𝖯}$ and thus the corresponding matrices have unbounded subdeterminants. As such our more structural approach to studying odd-minor-closed graph classes seems more promising. Indeed, any positive progress on the questions above is likely to yield immediate progress towards Question 7 due to the robustness of our structural tools as laid out below.

As part of the more general project outlined above, we are working on understanding the structure of odd-minor-free graphs, with a particular focus on excluding planar graphs as odd-minors. In line with this, several of the theorems and tools in this article are geared not only towards proving the results advertised in this paper, but also for further use in future parts of this project. We highlight here the advantages of our particular approach and why it is necessary to proceed this way if we wish to prove theorems constructively and with explicit bounds.

The established approach to proving a structural result when excluding an odd-minor (or in a closely related fashion an oriented or unoriented group-labelled-minor⁵⁵5We will not define the particulars of the group-labelled setting as they are not needed for our results.) is to take the existing results from the Graph Minor Series due to Robertson and Seymour (especially the Graph Minor Structure Theorem (GMST) from [52]) and then provide a tailor-made analysis of the structure provided by the GMST to solve the specific problem under consideration. Examples of this approach can be found in the work of Fiorini et al. [19] we already discussed, an approximate description of the structure of odd-minor-free graphs [15], a solution to the linkage problem for the oriented group-labelled setting [30], a structure theorem for oriented group-labelled graphs [23], and the solution to the linkage problem in the unoriented group-labelled setting (together with an associated structure theorem) [39]. We provide a rough description of what the GMST tells us about a graph excluding a given minor in Section 1.4.

This approach has two downsides. First, due to using older versions of the GMST and the associated machinery, such an approach often does not yield explicit bounds for the desired structural properties. More importantly, due to the ad-hoc nature of these individual solutions it is difficult to adapt them as tools for the further development of an efficient structure theory for odd-minors, where by efficient we mean theorems with explicit, hopefully low bounds, such as the polynomial bounds presented in this paper. This is particularly important as future progress towards resolving Question 7 will most likely heavily rely on such structural results.

We instead build robust tools that can be used in a more modular fashion. The key result here is a proof of an odd-minor version of the Society Classification Theorem (see Theorem 7.1 of the full version [10]), which is the engine behind a new constructive proof of the GMST with explicit bounds due to Kawarabayashi, Thomas, and Wollan [37, Theorem 10.1] (see also [28, Theorem 14.1]). This theorem is what allows Kawarabayashi et al. to prove the GMST constructively with explicit bounds via an induction. Our variant necessarily features more outcomes than the original Society Classification but importantly can be adapted to prove further results regarding excluded odd-minors and (in line with the variant in [28]) features polynomial bounds on the order of the structural elements involved.

As a second example, we provide a proof of an odd-minor variant of the Flat Wall Theorem (again see Section 1.4 for more details) with polynomial bounds, contrasting the worse than exponential bounds one would derive from the more general Flat Wall Theorem variant Thomas and Yoo prove in [58] for group-labelled graphs.

It is easy to see that a graph is bipartite if and only if it does not contain $K_3$ as an odd-minor. So on $K_3$-odd-minor-free graphs MIS is famously tractable. Moreover, Gerards [26] has proven a min-max duality for the MIS-problem on $K_4$-odd-minor-free graphs that implies a polynomial-time algorithm. For any $t\ge 5$, the class of $K_t$-odd-minor-free graphs contains the class of all planar graphs and thus, MIS becomes NP-hard. However, on the positive side, Tazari [56] showed that MIS admits a PTAS on $H$-odd-minor-free graph classes for every graph $H$.

In the following we let $ℬ$ be the class of bipartite graphs. Recall that for a graph $G$ we denote by $\mathrm{𝖮𝖢𝖯}(G)$ the largest integer $k$ such that $G$ has $k$ pairwise vertex-disjoint odd cycles. This is called the odd cycle packing number. The odd cycle transversal number of $G$, denoted by $\mathrm{𝖮𝖢𝖳}(G)$, is the smallest $k$ such that there is a set $S\subseteq V(G)$ of size at most $k$ where $G-S$ is bipartite. By the definition, $\mathrm{𝖮𝖢𝖯}(G)\le \mathrm{𝖮𝖢𝖳}(G)$ for all graphs $G$.

It is clear that $\mathrm{𝖮𝖢𝖯}(G)\le k$ if and only if $G$ does not contain $k\cdot K_3$ as an odd-minor. For the odd cycle transversal number, Reed [46] proved that $\mathrm{𝖮𝖢𝖳}(G)$ is bounded if and only if there exists a $k$ such that $G$ does not contain $k\cdot K_3$ nor the Escher grid of order $k$ (see Figure 2) as odd-minors. The Escher grid acts as an excellent example that the parameters OCT and OCP are comparable yet distinct in the sense that for every positive integer $k$, OCT of the Escher grid of order $k$ is $k$, while its OCP is equal to $1$.

Since computing $\mathrm{𝖮𝖢𝖳}(G)$ is fixed-parameter tractable (see for example [45]), MIS can be solved in polynomial-time on graphs of bounded OCT. For the odd cycle packing number, the situation is considerably more complicated. Fiorini et al. [19] proved that MIS is tractable on graphs of bounded OCP by using the graph minor structure theorem. Essentially, this algorithm is accomplished by exploiting how the graph with bounded OCP almost embeds on a surface with bounded genus. Note that Fiorini et al. converted the problem of finding an MIS to finding a minimum-cost circulation with certain property by using results of Conforti et al. [12]. Consequently, this approach alleviated the need to track the high connectivity within the near embedding that is required to find a specific minor model (see Section 7 of the full version [10]).

Two parameters that generalise the notion of OCT while maintaining both the comparability and the distinctness to OCP are the elimination distance to $ℬ$, denoted by ${\mathrm{𝖾𝖽}}_{ℬ}$, (see [8, 9]) and $ℬ$-treewidth, denoted by ${\mathrm{𝗍𝗐}}_{ℬ}$ (see [17, 34, 33]). Each of them is the minimum $k$ such that a graph $G$ has a set $X\subseteq V(G)$ such that $G-X\in ℬ$ and $𝗉(G_X)\le k$ where $G_X$ is the torso of $X$ in $G$ and $𝗉$ is the treedepth⁶⁶6Since treedepth is not used anywhere in the paper, we omit its definition. See [8, 9, 34] for further information. in the case of elimination distance to $ℬ$ and the treewidth in the case of $ℬ$-treewidth. Moreover, it holds that $\mathrm{𝖮𝖢𝖳}(G)\ge {\mathrm{𝖾𝖽}}_{ℬ}(G)\ge {\mathrm{𝗍𝗐}}_{ℬ}(G)$.

The $ℬ$-blind-treewidth, denoted by $ℬ\text{-}\mathrm{𝖻𝗅𝗂𝗇𝖽}\text{-}\mathrm{𝗍𝗐}$, of a graph $G$ is the largest treewidth over all non-bipartite blocks of $G$. Gollin and Wiederrecht [27] proved an analogue of the Grid Theorem for $ℬ$-blind-treewidth where the grid is the single parity break grid (see Figure 2). Observe that the single parity break grid of order $k$ has OCT equal to $1$ for all $k\ge 1$. The notion of bipartite treewidth as given by Jaffke et al. [32] is relatively technical, instead we give a functionally equivalent definition in terms of OCP-tree-decompositions: The bipartite treewidth, denoted by btw, of a graph $G$ is the minimum width of an OCP-tree-decomposition $(T,\beta ,\alpha )$ where $G[\beta (t)]-\alpha (t)$ is bipartite for all $t\in V(T)$. Notice that $ℬ\text{-}\mathrm{𝖻𝗅𝗂𝗇𝖽}\text{-}\mathrm{𝗍𝗐}(G)\ge \mathrm{𝖻𝗍𝗐}(G)$ and ${\mathrm{𝗍𝗐}}_{ℬ}(G)\ge \mathrm{𝖻𝗍𝗐}(G)$ for all graphs $G$. In particular, for every $k\ge 1$, the grid with odd cycle outgrowths of order $k$ (see Figure 2) has bipartite treewidth $1$, while its $ℬ$-treewidth is $k$. So with bipartite treewidth we now have a first parameter that properly subsumes both, the OCT-based parameters as well as $ℬ$-blind-treewidth.

The only parameter we have not discussed yet is OCP-treewidth itself. From the definition one can immediately deduce that $\mathrm{𝖮𝖢𝖯}\text{-}\mathrm{𝗍𝗐}(G)\le \mathrm{𝖻𝗍𝗐}(G)$. Moreover, the Escher grid of order $k$ can be seen to have bipartite treewidth $k$ while, as established above, its OCP-treewidth is $1$ for all $k\ge 1$. This makes OCP-treewidth the most general odd-minor-based parameter so far when it comes to parametrizations of MIS. In Figure 3 we give an overview of all classes and parameters discussed above and what they imply for the tractability of MIS.

With this it is now apparent that within the realm of known odd-minor-closed graph classes where MIS is tractable, there is a unique class, namely the $K_4$-odd-minor-free graphs, that does not fall under the regime of OCP-treewidth. Indeed, the parity handle grids are all $K_4$-odd-minor-free while $K_4$ is an odd-minor of ${𝒱}_3$. This raises the following question, related to Question 7.

To conclude this part, notice that we focussed here on the relevant literature for odd-minors. There are several other ongoing lines of research dealing with the computational complexity of MIS in settings of restricted structure. Among them is a recent interest in induced minors and the related tree-independence number [59, 14, 11]. Of particular interest is also the realm of $H$-vertex-minor-free graphs and classes of bounded rankwidth [43, 25]. In this area we have a particularly intriguing conjecture due to Geelen (see [40]) claiming that MIS should be tractable on all vertex-minor-closed graph classes. Finally, there exist many different kinds of “width” parameters that are fit to act as possible parametrizations for MIS (see [5] for some recent results and a good overview).

As mentioned earlier, there exist a few high-profile results on the structure of odd-minor-free and group-labelled-minor-free graphs [30, 23, 15, 58, 39], which all feature the downsides laid out earlier, namely non-constructive proofs, non-modular proof approaches, and non-explicit or huge bounds. Most other results concerning the structure of odd-minor-free graphs are more directly related to the odd-minor variant of Hadwiger’s famous colouring conjecture [29, 35] (see also [54]). Sadly, with the exception with the work of Geelen et al. in [24], these results tend to not be very helpful in pursuing the kind of characterisations of odd-minor-free classes we are after.

A central theorem of Robertson and Seymour is the Flat Wall Theorem [51]. It says that given a large wall⁷⁷7A wall is a subdivision of a hexagonal grid. $W$ in a graph $G$, there either exists a $K_t$-minor highly connected to $W$, or a small set $A\subseteq V(G)$ and a smaller but still big wall $W^{\prime }\subseteq W$ such that the part of $G-A$ attached to the “inside”⁸⁸8The “inside” is everything except for the cycle bounding the outer face in a standard planar drawing of the wall. of $W^{\prime }$ can be almost embedded into the plane without vortices. Such an embedding is called flat. We note that this is still an almost embedding and not a drawing, since we are still only embedding the graph up to 3-separations. Another key theorem for us is due to Geelen, Gerards, Reed, Seymour, and Vetta [24] stating that given a large enough complete graph as a minor in $G$, the graph $G$ either contains every graph on $t$ vertices as an odd-minor, or there is a small set $A\subseteq V(G)$ such that the part of $G-A$ that contains this complete minor is bipartite. Combining both results allows us to show that for any large enough wall $W$, we either find a set $A$ and wall $W^{\prime }$ as above such that the inside of $W^{\prime }$ is also bipartite, or we find ${\mathscr{H}}_k$ as an odd-minor. Note that a similar theorem was proven by Thomas and Yoo [58]. In the interest of deriving polynomial bounds for our results, we provide a simple and independent proof.

A core technique called society classification, crucial for proving the GMST, pioneered by Kawarabayashi, Thomas, and Wollan [37], and refined in [28], is to fix our perspective onto a disk whose boundary is protected by many concentric cycles which appear together in a “flat” embedding on the outside of the disk, whilst on the inside of the disk we have an unembedded part of the graph. In [37] it is proved that in this setting we can either find a $K_t$-minor, a large linkage resembling a handle or crosscap that has its endpoints on the boundary of the disk, or we can embed the entirety of the graph drawn on this disk in a flat way up to a small number of vortices whose internal connectivity is additionally restricted. In the last case, we in fact find an embedded, wall-like subgraph capturing each of these vortices in distinct walls that are all well-connected to a common wall living on the outside of our disk.

We refine this result by upgrading the embedding in each case to be “even-faced” in the sense described above and letting a variant of our obstructions be another outcome. In particular, we use the theorem from [24] discussed above to process the $K_t$-minor further.

Our society classification variant can be used to build a “local” form of the structure theorem based on a wall. First, the wall is made flat and bipartite via our modified flat wall theorem. Then, starting on the outside of the wall, we apply our refined society classification theorem to either find one of our obstructions, turn the block associated with our wall bipartite after the removal of a small number of vertices, embed what remains unembedded of the graph up to a handful of vortices and deleted vertices, or we find a large linkage resembling a crosscap or handle after removing a few vertices.

The last option allows us to iterate, as we can use this linkage and the structure on the boundary of our disk to cut out another disk that encompasses the previous one whilst preserving a large part of the handle or crosscap linkage. Thus we also have witnesses to the fact that we need to increase the genus of the surface we use in our even-faced almost embedding. The supporting infrastructure these linkages provide accumulates throughout the iterations, allowing us to find one of our obstructions if this process continues for too long. This procedure ends up either finding one of our obstructions or an even-faced almost embedding for the block associated with the remains of the initial wall.

Our cycles may be odd either when they are not entirely embedded, i.e. they go through a vortex, or they are embedded by going through an odd number of crosscaps. We first remove all odd cycles arising from vortices or obtain ${𝒱}_t$ as an odd-minor using a general technique exemplified in [57]. Consequently, all remaining odd cycles go through an odd number of crosscaps, allowing us to bound the odd-cycle-packing number by the maximum size of a disjoint set of such curves in our embedding via fairly simple counting arguments.

Being able to “locally” guarantee that our graph has bounded OCP, we modify a standard strategy stemming from one of the main proofs in [50] to derive the GMST from the local structure theorem to finally arrive at our desired OCP-tree-decomposition in the absence of any obstructions. This allows us to not only derive Theorem 6 at this point, but also prove Theorem 5 fairly directly.