The Price of Homogeneity Is Polynomial

Once the correctness of the Irrelevant Vertex Technique is established and one argues away the presence of a large clique minor using established techniques (see [27, 24]), one only requires a single refinement step after applying the Flat Wall Theorem to actually find an irrelevant vertex. This refinement step is referred to as homogenisation. Recall that the final flat wall $W^{\prime }$ behaves like a planar graph after deleting a small vertex set $A$. The vertices in $A$ however may arbitrarily attach to the interior of the wall. In order to argue for some vertex to be irrelevant, one needs to first tame these attachments. In this simplified setting we say that a flat wall $W$ is homogeneous for the set $A$ if for all non-boundary facial cycles $C$ of $W$, also called bricks, and every $a\in A$ it holds that $a$ has a neighbour in the interior of $C$ if and only if each member of $A$ has a neighbour in the interior of the face bounded by $C$. If one aims for a homogeneous flat wall of order $k$, current techniques²²2For an example of a sophisticated proof carrying out such a technique, see the proof of Lemma 13 in [33]. require to start with a flat wall of order $k^{𝒪(|A|)}$.

This exponential blow-up on the size of the required flat wall was dubbed the “price of homogeneity” by Sau, Stamoulis, and Thilikos [31, 32, 33]. The exponential dependency on $|A|$, and thus the exponential nature of the price of homogeneity was believed to be unavoidable when relying on the Irrelevant Vertex Technique [32, 33, 21]. Indeed, it appears that this is truly the limit of standard technique for homogenisation and in [32], it is asked whether one can prove that this price is unavoidable if one wants to apply the Irrelevant Vertex Technique.

For many algorithmic applications, the exponential bounds established as the state of the art force an additional exponentiation or a non-uniform dependency on a meta-parameter. We discuss the latter phenomenon in more detail in Section 2.2 based on an example from a recent result of Morelle, Sau, Stamoulis, and Thilikos [21].

Our main result improves the bound of $k^{𝒪(|A|)}$ to $𝒪({|A|}^4\cdot k^6)$, thereby removing any additional exponential dependency or resulting non-uniformity in the running time of all algorithms relying on the Irrelevant Vertex Technique based on homogenisation.

To make our results adaptable to a variety of settings, we state them in a more abstract form. Thus, we in particular provide a direct answer to the problem raised by Sau et al. [32], by making this part of the Irrelevant Vertex Technique more efficient. This shows that the limitations of this method are still far from completely understood, suggesting potential for further improvements.

The idea of encoding “types” as colourings in order to state a general version of the Homogeneous Wall Lemma is not new. Indeed, Sau, Stamoulis, and Thilikos state a similar lemma (Lemma 15 in [34]) with a slightly more technical definition for colourings. However, their version uses the established single-exponential bound. Let us briefly discuss how to use these colours to adapt our main result to different situations.

To see that Theorem 1 indeed allows for easy adaptation to a variety of settings and produces the desired outcome, if the initial wall $W_0$ is flat in $G-A$, where $A$ is a small vertex set, consider the following construction. Set $q:=|A|$ with $A=\{x_1,\mathrm{\dots },x_q\}\subseteq V(G)$. Now, for each vertex $v\in V(G-A)$, add the colour $i\in \{1,\mathrm{\dots },q\}$ to the set of colours carried by $v$ if and only if $v\in N_G(x_i)$. The result is a $q$-colorful graph $(G-A,\chi )$ containing the flat wall $W_0$. An application of Theorem 1 now yields a flat wall $W_1\subseteq W_0$ that is homogeneous in the sense of Theorem 1 which means that for any brick $B$ of $W_1$ and any $a\in A$, the vertex $a$ has a neighbour in the interior of $B$ if and only if $a$ has a neighbour in the interior of every brick of $W_1$ as desired.

A second scenario in which the Homogeneous Wall Lemma finds applications – this is part of Robertson and Seymour’s Graph Minor Algorithm – is as follows: The planar-like behaviour of a flat wall $W$ in a graph $G$ involves taking $G$ apart at separations of order at most three. Let $H\subseteq G$ be a subgraph of $G$. A graph $G_1$ with $H\subseteq G_1$ is an $H$-reduction of $G$ if there exists a graph $G_2$ and cliques $J_i\subseteq G_i$, $i\in \{1,2\}$, of size at most three such that $G$ can be obtained from $G_1$ and $G_2$ by identifying $J_1$ and $J_2$ into a single clique $J$ and then possibly deleting some of the edges of $J$. If $W$ is flat in $G$ and $C$ is its perimeter, then there exists a graph $G^{\prime }$ that can be obtained from $G$ by a sequence of $C$-reductions such that the union $G^{\ast }$ of $C$ and the $C$-bridge $B$ in $G^{\prime }$ with $B\cap V(W)=(V(G^{\prime })\cap V(W))\setminus V(C)$ is planar and still contains a large wall $W^{\prime }$.

In many applications one desires to homogenise the wall $W^{\prime }$ with respect to some notion of “profiles” defined⁴⁴4The precise definition of such profiles may vary depending on the application. A common one is the set of all rooted graphs of bounded size that may be found as minors rooted on the vertex set of the clique $J$ as from above. on the pieces of $G$ attaching to the cliques of size at most three inside $G^{\ast }$. We may choose our $C$-reductions such that the triangles among such cliques are now facial. If the number of possible such profiles is bounded by some integer $q$ one may simply perform the following augmentation of $G^{\prime }$: Let $𝒫$ be the set of all possible profiles and let $\psi :𝒫\to \{1,\mathrm{\dots },q\}$ be a bijection. Now, for each clique $J$ of size at most three from the interior of $C$ in $G^{\prime }$ introduce a new vertex $v_J$ adjacent to all vertices of $J$ and let $G^{\prime \prime }$ be the resulting graph. Then set $\chi (v):=\mathrm{\varnothing }$ for all $v\in V(G^{\prime })$ and $\chi (v_J)\subseteq \{1,\mathrm{\dots },q\}$ such that $i\in \chi (v_J)$ if and only if $J$ has been assigned the profile ${\psi }^{-1}(i)$. If one now applies Theorem 1 to the flat wall $W^{\prime }$ in the $q$-colorful graph $(G^{\prime \prime },\chi )$ to obtain a homogeneous wall $W^{\prime \prime }$, this homogeneity transfers directly to $G^{\prime }$. Notice that this second scenario using an abstract definition of “profiles” also contains the first example as “being a neighbour of some specified vertex from $A$” may be considered a valid definition for a profile.

To illustrate the impact of Theorem 1 on existing algorithms, we discuss an application to a recent result of Morelle et al. [21]. Due to the technical nature of the Homogeneous Wall Lemma, discussing its application requires to open procedures which are often discussed in a black-box style. This is why we present a single in-depth discussion of the applicability of Theorem 1 in order to provide guidance for interested readers on how the result may be incorporated to speed up the running time of related algorithms.

A core result of the work of Morelle et al. is a parameterized algorithm for the $k$-$\mathscr{H}$-Minor Deletion problem. Let $k$ be a non-negative integer and $\mathscr{H}$ be a finite set of graphs.

$k$-$\mathscr{H}$-Minor Deletion
Input: A graph $G$.
Objective: Find, if it exists, a set $S\subseteq V(G)$ with $|S|\le k$ such that $G-S$ does not contain a graph from $\mathscr{H}$ as a minor.

Given a finite set $\mathscr{H}$ of graphs, we denote by ${𝗁}_{\mathscr{H}}$ the value ${\sum }_{H\in \mathscr{H}}(|H|+\Vert H\Vert )$. With this notation the result of Morelle et al. we are interested reads as follows.

Notice that the running time of the algorithm in Proposition 2 is single-exponential in a polynomial in $k$. However, this polynomial is of the form $k^{𝒪(f_{\text{<a href="\#Thmtheorem2" title="Proposition 2 (Morelle, Sau, Stamoulis, Thilikos [21]). ‣ 2.2 Algorithmic consequences of our result ‣ 2 A polynomial homogeneity lemma ‣ The Price of Homogeneity Is Polynomial" class="ltx\_ref ltx\_font\_italic" style="font-size:50\%;"><span class="ltx\_text ltx\_ref\_tag">2</span></a>}}({𝗁}_{\mathscr{H}}))}$, that is, its degree depends on the choice of the meta parameter $\mathscr{H}$. This behaviour is precisely what is meant by the term “non-uniformity”.

Due to major milestones in the quest towards the creation of an efficient graph minors theory, the bounds for both the Grid Theorem [5] and the Flat Wall Theorem [4, 16, 14] are polynomial. This means that there exists a constant $c$ such that in a $K_t$-minor-free graph $G$ one may either determine that the treewidth of $G$ is at most ${(t+r)}^c$ or there exists a set $A\subseteq V(G)$ with $|A|\le t^c$ and a flat $r$-wall $W$ in $G-A$. Note that every Yes-instance of $k$-$\mathscr{H}$-Minor Deletion must exclude $K_{k+{𝗁}_{\mathscr{H}}}$ as a minor.

The variant of the Homogeneous Wall Lemma used by Morelle et al. stems from another work of Sau, Stamoulis, and Thilikos, namely Lemma 15 in [34].

The algorithm from Proposition 2 now proceeds in three recursive steps which we roughly outline below.

Step 1:

Check if the treewidth of $G$ is small. If not, find a small set $A\subseteq V(G)$ and large flat wall $W_1$ in $G-A$. Then consider several big subwalls $W^{\prime }$ of $W$. If for some $W^{\prime }$ the subset of $A$ with neighbours in the compass of $W^{\prime }$ induces a complete graph as a minor whose size depends on ${𝗁}_{\mathscr{H}}$ but not on $k$, then proceed to Step 2. Otherwise proceed to Step 3.

Step 2:

Apply the Homogeneous Wall Lemma to $W^{\prime }$ and find a vertex $v\in V(G-A)$ such that $(G-v,k)$ is equivalent to $(G,k)$ as an instance of $k$-$\mathscr{H}$-Minor Deletion. Recurse on $(G-v,k)$.

Step 3:

In this case one can show that there exists a vertex $y$ that must be contained in all optimal solutions or $(G,k)$ is a No-instance. This procedure detects a number of candidates for $y$ and branches over all of them by considering instances of the form $(G-y,k-1)$ recursively.

One may make two core observations on the origin of the dependency of the form $k^{𝒪(f_{\text{<a href="\#Thmtheorem2" title="Proposition 2 (Morelle, Sau, Stamoulis, Thilikos [21]). ‣ 2.2 Algorithmic consequences of our result ‣ 2 A polynomial homogeneity lemma ‣ The Price of Homogeneity Is Polynomial" class="ltx\_ref ltx\_font\_italic" style="font-size:50\%;"><span class="ltx\_text ltx\_ref\_tag">2</span></a>}}({𝗁}_{\mathscr{H}}))}$ in the running time of their algorithm. The first is: The only reason for the dependency of the form $k^{𝒪(f_{\text{<a href="\#Thmtheorem2" title="Proposition 2 (Morelle, Sau, Stamoulis, Thilikos [21]). ‣ 2.2 Algorithmic consequences of our result ‣ 2 A polynomial homogeneity lemma ‣ The Price of Homogeneity Is Polynomial" class="ltx\_ref ltx\_font\_italic" style="font-size:50\%;"><span class="ltx\_text ltx\_ref\_tag">2</span></a>}}({𝗁}_{\mathscr{H}}))}$ in Step 2 is the direct reliance on the Homogeneous Wall Lemma. Second: The reason for this type of dependency in Step 3 may be found behind a more involved chain of arguments. However, following along the chain of applications of different Lemmas one can see that also here the sole reason for the term $k^{𝒪(f_{\text{<a href="\#Thmtheorem2" title="Proposition 2 (Morelle, Sau, Stamoulis, Thilikos [21]). ‣ 2.2 Algorithmic consequences of our result ‣ 2 A polynomial homogeneity lemma ‣ The Price of Homogeneity Is Polynomial" class="ltx\_ref ltx\_font\_italic" style="font-size:50\%;"><span class="ltx\_text ltx\_ref\_tag">2</span></a>}}({𝗁}_{\mathscr{H}}))}$ lies within an application of the Homogeneous Wall Lemma⁵⁵5For better comparison: In the proof of Theorem 6.1 in [21] several quantities are defined. The necessary sizes for the initial flat wall in Step 3 are $r_1$ and $r_2^{\prime }$ where $r_1$ depends linearly on $r_2^{\prime }$. The definition of $r_2^{\prime }$ in turn depends on two functions where only one carries the dangerous dependency through its reliance on $r_2$. In turn, $r_3$ again inherits the dependence from $r_4$, which inherits it from the definition of $t$. The quantity $t$ finally depends on $r_5$ which is the function from the Homogeneous Wall Lemma..

Morelle et al. ask in their paper if it is possible to change the running time from their original $2^{k^{𝒪(f_{\text{<a href="\#Thmtheorem2" title="Proposition 2 (Morelle, Sau, Stamoulis, Thilikos [21]). ‣ 2.2 Algorithmic consequences of our result ‣ 2 A polynomial homogeneity lemma ‣ The Price of Homogeneity Is Polynomial" class="ltx\_ref ltx\_font\_italic" style="font-size:50\%;"><span class="ltx\_text ltx\_ref\_tag">2</span></a>}}({𝗁}_{\mathscr{H}}))}}{n}^2$ to an expression of the form $2^{f({𝗁}_{\mathscr{H}})\cdot k^d}$ for some function $f$ and some absolute constant $d$. It now follows from the discussion above that simply replacing their exponential Homogeneous Wall Lemma with Theorem 1 achieves this goal. Indeed, a more careful analysis of the proof of Proposition 2 in [21] reveals that with this change we are even able to provide a concrete bound for the degree $d$ of the polynomial.

The impact of Theorem 1 on the running time of other known parameterized algorithms is similar. The two algorithms for $k$-Elimination Distance to $𝒢$ for minor-closed graph classes $𝒢$ by Morelle et al. [21] profit from our main theorem in the same way as Proposition 2. Even graph modifications that do not fall under the umbrella of minor-friendly operations see direct improvements to the running time of their associated algorithms [22].

Beyond the scope of specialised algorithms one may also focus on the algorithm for $k$-Disjoint Paths. As described above, the algorithm has two core routines: One for graphs of bounded treewidth and one if the treewidth is large. The exact bound on the treewidth depends on four functions. The first two are the function $g_1$ from the Grid Theorem itself and the function $g_2$ from the Flat Wall Theorem, both are known to be polynomial [5, 4, 16, 14]. The third is the function $g_3$ from the Homogeneous Wall Lemma and the fourth is the so-called Unique Linkage Function $g_4$ [29, 30]. The total bound amounts to $g_1\left(g_2\left(g_3\left(g_4\left(k\right)\right)\right)\right)\in g_3{\left(g_4\left(k\right)\right)}^c$ for some universal constant $c>1$.

With previous bounds on $g_3$ this means that the bound on the treewidth distinguishing between the two cases of the $k$-Disjoint Paths algorithm is of the form $2^{𝒪(g_4(k))}$. Applying Theorem 1 reduces this bound to $g_4{(k)}^{𝒪(1)}$. As mentioned above, any application of the Irrelevant Vertex Technique relies on all four functions mentioned above. Hence, the improvement explained above applies to any application of Irrelevant Vertices in the case of $H$-minor-free graphs⁶⁶6In most cases, the presence of a large clique minor provides an irrelevant vertex in more straightforward way with very good bounds. Only few examples are known where the clique case poses a challenge on its own (see [9])..

Providing explicit and good bounds for $g_4$ is maybe one of the biggest challenges in the algorithmic theory of graph minors. Robertson and Seymour did not give any explicit bound. A first bound was found by Geelen, Huynh, and Richter [12] but their estimate is an iterated power tower function. Before that, Kawarabayashi and Wollan announced a new proof for the Unique Linkage Theorem [18] but never computed their bound. Wollan estimates this bound to be at most four-fold exponential [37]. The only known lower bound on $g_4$ is due to Adler, Kolliopoulos, Krause, Lokshtanov, Saurabh, and Thilikos [1, 2] and shows that $g_4(k)\in 2^{\mathrm{\Omega }(k)}$. With our result and the recently established polynomial bounds for the Graph Minor Structure Theorem [14], the only remaining pillar of algorithmic graph minor theory still resisting optimisation is now the Unique Linkage Function itself.

We may now imagine our mesh $M$ to be embedded on a disk $\mathrm{\Delta }$ with its perimeter drawn on the boundary of $\mathrm{\Delta }$. To further aid our intuition we imagine $\mathrm{\Delta }$ to be a rectangle where each of the four paths of $M$ making up the perimeter is drawn on its private side of the rectangle and the vertices where horizontal and vertical perimeter paths intersect are drawn in the corners.

Now, any two horizontal (or vertical) paths from $M$ carve out another rectangle – at least up to homeomorphism – from $\mathrm{\Delta }$ containing all the horizontal (or vertical) paths drawn in between them. More explicitly, $P_i$ and $P_{i+k}$ together with the boundary of $\mathrm{\Delta }$ bound a unique disk which contains $P_{i+j}$ for all $j\in \{1,\mathrm{\dots },k-1\}$. We will use this to create what we call strips, i.e. the restriction of $G$ to the part drawn in this disk defined by $P_i$ and $P_{i+k}$. Figure 2 contains a schematic illustration of a vertical strip.

To each strip $S$ – vertical or horizontal – we may associate a colour profile, which is simply the set of colours $i$ such that at least one vertex drawn in $S$ carries $i$ in its palette.

Our goal is to find the following: Suppose we have $q$ colours and are given positive integers $k$ and $r$. Our first target is to start with a large collection of wide – polynomial in $q$, $k$, and $r$ – vertical (or horizontal) and pairwise disjoint strips, and find a collection of $k$ pairwise disjoint strips $𝒮$ together with a set $I\subseteq \{1,\mathrm{\dots },q\}$ such that for each $i\in I$, at least $r$ strips from $𝒮$ contain $i$ in their profile and for each $i\in \{1,\mathrm{\dots },q\}\setminus I$ no strip in $𝒮$ carries $i$.

If we were not interested in polynomial bounds we could easily achieve something stronger. Let ${𝒮}_0$ be the initial selection of strips. For each $i\in \{1,\mathrm{\dots },q\}$, let ${𝒮}_i$ be obtained from ${𝒮}_{i-1}$ by the following selection process. If at least $\frac{|{𝒮}_{i-1}|}{2}$ strips have $i$ in their palette let ${𝒮}_i$ be all those strips with $i$ in their palette. Otherwise let ${𝒮}_i$ be all strips from ${𝒮}_{i-1}$ which do not carry $i$ in their palette. As a result we have that, if $|{𝒮}_0|\ge 2^q\cdot r$, then $|{𝒮}_q|\ge r$ and the palettes of all strips in ${𝒮}_q$ are equal.

To ensure that this process is also polynomial in $q$, we alter it slightly. Instead of considering plain strips, we split each strip into three parts: Two small strips, one on either side, acting as a buffer and a large middle strip. See Figure 2 for an illustration of such a splitting of a strip. These buffers will help us to sort out colours more efficiently and also provide sufficient infrastructure to eventually find our desired mesh. Such infrastructure is necessary as colours that occur only close to the boundary of a strip are difficult to incorporate into the middle of some mesh without leaving the confinement of the strips.

We may now alter the approach from above as follows. Starting from a collection ${𝒜}_0$ of strips, we first find a subset $I_1\subseteq \{1,\mathrm{\dots },q\}$ of colours which appear in less than $r$ strips. We then remove all strips that carry at least one colour from $I_1$, thereby losing at most $|I_1|\cdot r\le q\cdot r$ strips, set $X_1:=\{1,\mathrm{\dots },q\}\setminus I_1$, and let ${ℬ}_0$ be the collection of remaining strips. Then we select $J_1\subseteq X_1$ to be the set of colours $i$ which appear in less than $r$ middle parts of the strips from ${ℬ}_0$. In case $J_1=\mathrm{\varnothing }$ we terminate. Otherwise we first forget all strips with some colour from $J_1$ in their middle part – there are at most $q\cdot r$ many – and set $Y_1:=X_1\setminus J_1$. From each of the remaining strips we only keep their middle part, thereby forming the set ${𝒜}_1$ of remaining strips which we again partition into a middle part and two buffer zones.

Iterating this procedure eventually yields a set ${ℬ}_j$ of strips and a set $X_j$ of colours such that

1. 1.

   the profile of each strip in ${ℬ}_j$ is a subset of $X_j$,

2. 2.

   for each $i\in X_j$ there are at least $r$ strips in ${ℬ}_j$ whose middle parts carry the colour $i$, and

3. 3.

   $|{ℬ}_j|\ge |{𝒜}_0|-q^{2}r$ and each strip has shed its buffer zones at most $q$ times, meaning all strips are still as large as we desire.

The procedure from Step 1 now yields a big collection of horizontal strips which are close to being homogeneous and a big collection of vertical strips which are also close to being homogeneous. We need one further step of homogenisation before we can start constructing the homogeneous mesh we desire.

Overlaying vertical and horizontal strips gives rise to two new types of areas: Those areas where a horizontal and a vertical strip intersect (type 1), and the area exclusive to some vertical (horizontal) strip, two sides of which are bordered by the boundary of the mesh or some horizontal (vertical) strip (type 2). See Figure 3 for an illustration. We call these area tiles.

Note that some tiles are fully surrounded by buffer areas while others are surrounded by buffer areas only on three sides. The latter may be considered to be “end tiles” as this only occurs at the boundary of our mesh as indicated in Figure 3. For each tile we may now define a “middle part” as the intersection of the middle parts of the two strips involved if the tile is of type 1 and the intersection of the tile with the middle part of its strip if the tile is of type 2.

From Step 1 we know that any colour that occurs in the profile of some vertical or horizontal strip in our collection must also occur in the middle part of at least $r$ strips. Our next goal is to further refine this statement to say that any colour occurring in some strip occurs in the middle parts of at least $r$ distinct tiles which are not end tiles. However, this requires additional arguments and sacrifices as some parts of one strip now belong to the buffer areas of another and because it might be possible that some colours are confined mostly into end tiles.

To realise our desired outcome, we essentially repeat the sorting procedure from the first step, but now we incorporate a step where we also crop the entire mesh in order to dismiss end tiles (see Figure 3 for an illustration). As in Step 1, in each iteration we only throw away a bounded number of strips and we shrink each strip only by a polynomial amount in order to readjust its buffer zones. Since the total number of iterations is bounded by the number of remaining colours, the total sacrifice in number of strips and in their width remains polynomial as before.

The outcome of Step 2 is a collection of horizontal and vertical strips $𝒮$ together with a subset $X$ of the original $q$ colours such that the strips from $𝒮$ carry only the colours in $X$ and each colour in $X$ occurs in the middle parts of at least $r$ distinct non-end tiles. All that is left is to show how this situation may be utilised to construct a homogeneous mesh.

This construction is done in two steps. First, we make use of the buffer zones and infrastructure of the union of all strips in $𝒮$ to construct a new mesh $M^{\prime }$ where each face of the “middle row” of $M^{\prime }$ carries every colour in $X$. We call $M^{\prime }$ a mesh with a rainbow middle row. See Figure 4.

By choosing $r$ and $M^{\prime }$ large enough to ensure that $M^{\prime }$ has $k^2$ many faces in the middle row, we may then weave vertical paths of a new mesh $M^{\prime \prime }$ around the middle row to construct the final homogeneous mesh as illustrated in Figure 4.