A Polynomial-Time Approximation Algorithm for Complete Interval Minors

If a graph has chromatic number $t$, ordering its vertices according to the color classes directly gives an order without $K_{2t}$ interval minor. To see it, consider any partition of the vertices into $2t$ intervals. At most $t-1$ intervals can contain vertices from two different color classes, so at least $t+1$ intervals must be entirely contained in a color class. By the pigeonhole principle, two distinct intervals must be contained inside the same color class, and therefore cannot be connected by an edge. Conversely, if a graph $G$ has an ordering such that does not contain a $K_t$ interval minor, Theorem 3 implies that has bounded rank. Say that a class $𝒞$ of graphs is $\chi$-bounded if there exists a function $h$ such that every graph $G$ in $𝒞$ satisfies $\chi (G)\le h(\omega (G))$, where $\omega (G)$ is the maximum size of a clique of $G$. We speak of polynomial $\chi$-boundedness if $h$ is a polynomial.

We prove it by induction on $r$. The statement is trivial for $r=0$ since the empty graph has clique number $0$ and chromatic number $0$. For the induction step, we just have to show that the three operations preserve polynomial $\chi$-boundedness. Independent concatenation increases the chromatic number by at most one and cannot decrease the clique number. Similarly, the chromatic number of the edge union of two graphs is at most the product of their chromatic numbers, and the clique number of the edge union of two graphs is at least the maximum of the two clique numbers. The fact that the substitution closure preserves polynomial $\chi$-boundedness was shown by Chudnovsky, Penev, Scott and Trotignon [9]. $\mathrm{⊲}$

Then, if does not contain a $K_t$ interval minor then $G$ does not contain a clique of size $t$, and therefore its chromatic number is bounded. $◀$

The fact that $K_t$-interval-minor-free ordered graphs have bounded chromatic number directly implies that the class of ordered graphs which do not contain some (arbitrary but fixed) ordered matching as a subgraph has bounded chromatic number (the two statements are in fact easily equivalent). This problem was introduced in [2] by Axenovich, Rollin and Ueckerdt, where they ask the question for some specific matchings. A far-reaching generalization was announced by Briański, Davies and Walczak [8]: for any ordered matching $M$, the class of ordered graphs which do not contain $M$ as an induced ordered subgraph is $\chi$-bounded. A study of the list chromatic number of ordered graphs avoiding an induced subgraph was also conducted by Hajebi, Li and Spirkl [18].

We first show that the problem is in $\mathrm{𝖭𝖯}$. To do so, observe that we can describe a $K_t$ interval minor model of $G$ by giving the intervals. Then, it can easily be checked in polynomial time that these intervals indeed form a model of $G$.

We show that the problem is $\mathrm{𝖭𝖯}$-hard by reduction from Clique. Consider an instance $(G,k)$ of Clique: we are asked whether $G$ contains a clique of size at least $k$. We build an instance $(\widehat{G},t)$ of Complete Interval Minor as follows. Write $V(G)=\{v_1,\mathrm{\dots },v_n\}$. Consider the ordered graph defined as

• $\mathrm{■}$

  $V(\widehat{G})=\{v_1,\mathrm{\dots },v_n\}\cup \{u_1,\mathrm{\dots },u_{n-1}\}$, where the $u_i$ are fresh vertices,

• $\mathrm{■}$

  $v_i{v}_j\in E(\widehat{G})$ if and only if $v_i{v}_j\in E(G)$, $v_i{u}_j\in E(\widehat{G})$ for every $i\in [n]$ and $j\in [n-1]$, and $u_i{u}_j\in E(\widehat{G})$ for every $i\ne j\in [n-1]$,

• $\mathrm{■}$

  .

Informally, the ordered graph is obtained from $G$ by arbitrarily ordering the vertices of $G$, and then adding a universal vertex between any two vertices of $G$. See Figure 3 for an illutration. Finally, we set $t=n-1+k$. Note that can be built from $(G,k)$ in polynomial time.

We now prove that $G$ has a clique of size $k$ if and only if $K_t$ is an interval minor of . Suppose first that $G$ has a clique of size $k$ induced by the vertices $v_{i_1},\mathrm{\dots },v_{i_k}$. Then, the vertices $v_{i_1},\mathrm{\dots },v_{i_k},u_1,\mathrm{\dots },u_{n-1}$ induce a clique of size $k+n-1=t$ in $\widehat{G}$, hence contains $K_t$ as an interval minor. Conversely, suppose that $K_t$ is an interval minor of . Since there are only $n-1$ vertices $u_j$, there are at least $t-(n-1)=k$ intervals in the interval model of $K_t$ which do not contain a vertex $u_j$. By definition of the order , any interval that does not contain a vertex $u_j$ is of the form $\{v_i\}$. Let $\{v_{i_1}\},\mathrm{\dots },\{v_{i_k}\}$ be these $k$ intervals. Then, the vertices $v_{i_1},\mathrm{\dots },v_{i_k}$ induce a clique of size $k$ in $G$. $◀$

For every node $x$ of $T$, let $w(x)$ be the number of intervals of $ℐ$ which are entirely contained inside $L(x)$. Let $B(x)$ be the set of children $y$ of $x$ such that $w(y)\ne 0$. Note that $x$ is (at least) $|B(x)|$-branching, and so we can conclude if $|B(x)|\ge b$. Therefore, we can assume that for every $x\in V(T)$.

Consider a node $x$ with $w(x)\ge 2b^2$. Let ${ℐ}_1$ be the set of intervals which are contained inside some $L(y)$ for $y\in B(x)$ and ${ℐ}_2$ be the set of intervals which are contained inside $L(x)$ but are not in ${ℐ}_1$. Note that if $|{ℐ}_2|\ge 2b-1$, the node $x$ is $b$-branching. Indeed, in that case it suffices to order ${ℐ}_2$ with respect to , and to select every other interval to form a $b$-branching subfamily ${ℐ}^{\prime }$.

So there is a child $y$ of $x$ such that (using that $w(x)\ge 2b^2$ in the last inequality):

Starting from the root $r$, we define a sequence of vertices $(r=x_1,\mathrm{\dots },x_t)$ forming a descending chain in $T$, such that $w(x_{i+1})\le w(x_i)-3$ for every $i\in [t-1]$ and $w(x_i)\ge 2{(b+2)}^{t+1-i}$ for every $i\in [t]$.

Start by setting $x_1$ to be the root $r$, and note that $w(x_1)=2{(b+2)}^t$. Suppose that we already defined $x_1,\mathrm{\dots },x_{i-1}$ satisfying the desired property, with $i\le t$. Consider a descendant $x_i$ of $x_{i-1}$ with maximum $w(x_i)$, such that $w(x_i)\le w(x_{i-1})-3$, and among them one which is as close to the root as possible in $T$. By definition of $x_i$, we have:

Thus, $p(x_i)$ has a child $y$ with

Therefore, by maximality of $w(x_i)$, we have:

For every $i\in [t-1]$, since $w(x_{i+1})\le w(x_i)-3$, there are at least three intervals which are entirely contained in $L(x_i)$ and which are not entirely contained in $L(x_{i+1})$. Therefore, there is an interval $I_i$ which is entirely contained in $L(x_i)$ and such that $I_i\cap L(x_{i+1})=\mathrm{\varnothing }$. Finally, $w(x_t)\ge 2(b+2)>0$ so there exists an interval $I_t\subseteq L(x_t)$. $◀$

If is a delayed structured tree, a leaf $y$ of $T$ is $h$-heavy if there are at least $h$ ancestors $x$ of $y$ which are not isolated in the graph $G_{p^2(x)}$, where $p^2(x)$ is the grandparent of $x$ in $T$.

Let $I_1,\mathrm{\dots },I_{2t-1}$ be the intervals of the $(2t-1)$-interval path of $ℐ$ in $T$, and $x_1,\mathrm{\dots },x_{2t-1}$ be nodes of $T$ such that for all $j\in [2t-1]$, $L(x_j)$ contains $I_j\cup \mathrm{\cdots }\cup I_{2t-1}$, and for all $j\in [[2,2t-1]]$, $L(x_j)\cap I_{j-1}=\mathrm{\varnothing }$.

Let $y\in L(T)$ be any leaf in $I_{2t-1}$. We show that $y$ is $(2t-3)$-heavy. Let $i\in [2t-3]$. Since $ℐ$ forms a complete interval minor in , there is an edge between some vertex $y_i\in I_i$ and $I_{2t-1}$. Let $z_i$ be the deepest node of $T$ such that $I_{2t-1}\cup \{y_i\}\subseteq L(z_i)$. Then, $z_i$ is a descendant of $x_i$ and a proper ancestor of $x_{i+1}$ (hence all $z_i$ are distinct). Furthermore, since $z_i$ is a proper ancestor of $x_{i+1}$ then the grandchild $w_i$ of $z_i$ such that $y\in L(w_i)$ is an ancestor of $x_{i+2}$. In particular, $I_{2t-1}\subseteq L(x_{2t-1})\subseteq L(x_{i+2})\subseteq L(w_i)$. Let $w_i^{\prime }$ be the grandchild of $z_i$ such that $y_i\in L(w_i^{\prime })$. By maximality of the depth of $z_i$, $w_i$ and $w_i^{\prime }$ are cousins in $T$. Since there is an edge between $y_i$ and $I_{2t-1}$ in $G_T$, there is an edge between $w_i$ and $w_i^{\prime }$ in $G_{z_i}$. Thus, we found $2t-3$ distinct ancestors $w$ of $y$ which are not isolated in $G_{p^2(w)}$, i.e. $y$ is $(2t-3)$-heavy. $◀$

Let $y$ be a $(2t-3)$-heavy leaf of $T$. Let $x_1,\mathrm{\dots },x_{2t-3}$ be ancestors of $y$ such that each $x_i$ is not isolated in the graph $G_{p^2(x_i)}$. Up to renaming them, we can assume that $x_i$ is a proper ancestor of $x_j$ whenever . We build a sequence $(y_0,\mathrm{\dots },y_{t-1})$ of vertices of $G_T$ with the following properties:

• $\mathrm{■}$

  For every $i\in [[0,t-2]]$, $y_i$ is adjacent to every vertex in $L(x_{2i+1})$, and

• $\mathrm{■}$

  For every $i\in [t-1]$, $y_i\in L(x_{2i-1})$.

Note that these properties immediately imply that $y_0,\mathrm{\dots },y_{t-1}$ induce a clique of size $t$ in $G_T$.

Let $i\in [[0,t-2]]$ and let $x_i^{\prime }$ be a neighbor of $x_{2i+1}$ in the graph $G_{p^2(x_{2i+1})}$. Let $y_i$ be an arbitrary vertex in $L(x_i^{\prime })$. Then, $y_i$ is adjacent to all vertices in $L(x_{2i+1})$. If $i>0$ then $p^2(x_{2i+1})$ is a descendant (not necessarily proper) of $x_{2i-1}$ so $y_i\in L(x_{2i-1})$. Finally, we choose $y_{t-1}$ to be any vertex of $L(x_{2t-3})$. $◀$

Let $x$ be such a node, and $y_1,y_2$ be consecutive children of $x$. Since the delayed decomposition is distinguishing, there is some vertex $v\in V(G)\setminus L(x)$ which is adjacent to all vertices in one of $L(y_1),L(y_2)$ and none in the other. Let $u_1$ be any vertex in $L(y_1)$ and $u_2$ any vertex in $L(y_2)$. Since $v\notin L(x)$ then $u_1$ and $v$ have the same last common ancestor $z$ as $u_2$ and $v$, and $z$ is a proper ancestor of $x$. Suppose by contradiction that $z$ is a proper ancestor of $p(x)$. Then, the grandchild of $z$ which is an ancestor of $u_1$ is also the grandchild of $z$ which is an ancestor of $u_2$, call it $x^{\prime }$. Let $v^{\prime }$ be the ancestor of $v$ which is a grandchild of $z$. If $x^{\prime }{v}^{\prime }\in E(G_z)$ then $u_{1}v\in E(G)$ and $u_{2}v\in E(G)$, a contradiction. Similarly, if $x^{\prime }{v}^{\prime }\notin E(G_z)$ then $u_{1}v\notin E(G)$ and $u_{2}v\notin E(G)$, again a contradiction. Therefore, $z$ is the parent of $x$. Let $v^{\prime }$ be be the ancestor of $v$ which is a grandchild of $z$. Then, $v^{\prime }$ is a cousin of $y_1$ and $y_2$. If $i\in \{1,2\}$ is such that $v$ is adjacent to all vertices in $L(y_i)$ then $v^{\prime }{y}_i\in E(G_{p^2(y_i)})$ so one of $y_1$ and $y_2$ is not labelled with $O$. $◀$

In view of Lemma 13, if $x$ is a node of $T$ with at least 3 children, and $y$ is a child of $x$ labelled $O$ which is not the first child of $x$, then the predecessor $y^{\prime }$ of $y$ has either label $L$ or label $R$. If $y^{\prime }$ has label $L$, we refine the label of $y$ to $O_L$ and if $y^{\prime }$ has label $R$, we refine the label of $y$ to $O_R$.

Given a node $x$ of a delayed structured tree, if $y$ is a vertex of $G_x$ whose parent is labelled with $R$ then there exists some vertex $y^{\prime }>V(G_x)$ which is adjacent to $y$. This observation will be our main tool to prove that graphs with large delayed rank have large complete interval minors (see Theorem 19). For this reason, we define the type of a node $x\in V(T)$ as the label of its parent in $T$.

The delayed rank of an ordered graph is defined as follows:

• $\mathrm{■}$

  If is monotone bipartite, has delayed rank $0$,

• $\mathrm{■}$

  Otherwise, we compute the distinguishing delayed decomposition of . For each quotient graph , if is monotone bipartite we say that is a refined quotient graph of . Otherwise, note that $x$ has at least $3$ children (since there are only edges between cousins in $G_x$). In that case, if the first child of $x$ is labelled with $O$, we remove all its children from $G_x$. Then, we partition the vertices into types $R,L,O_R$ and $O_L$. Set $R^{\prime }=\{R,O_R\}$ and $L^{\prime }=\{L,O_L\}$. We partition the edges into four types, depending on whether the type of their left endpoint is in $R^{\prime }$ or $L^{\prime }$, and similarly for their right endpoint, denote these four types by $R^{\prime }{R}^{\prime },R^{\prime }{L}^{\prime },L^{\prime }{R}^{\prime }$ and $L^{\prime }{L}^{\prime }$. The refined quotient graphs of are then defined as follows:

  • –

    The graph induced by the edges $R^{\prime }{R}^{\prime }$, to which we remove all vertices before the first vertex of type $R$ and after the last vertex of type $R$.

  • –

    The graph induced by the edges $R^{\prime }{L}^{\prime }$, to which we remove all vertices before the first vertex of type $L$ and after the last vertex of type $L$.

  • –

    The graph induced by the edges $L^{\prime }{R}^{\prime }$, to which we remove all vertices before the first vertex of type $R$ and after the last vertex of type $R$.

  • –

    The graph induced by the edges $L^{\prime }{L}^{\prime }$, to which we remove all vertices before the first vertex of type $L$ and after the last vertex of type $L$.

  Then, the delayed rank of is $1$ more than the maximum delayed rank of all its refined quotient graphs.

Observe first that siblings form an independent set in $G_x$, so removing all the children of the first child of $x$ is just removing an independent set, at the beginning of the order of $G_x$. Similarly, the vertices before the first vertex of type $R$ are at the beginning of the order of $G_x$ and all have type either $L$ or $O_L$, so they cannot induce any edge of type $R^{\prime }{R}^{\prime }$ or $L^{\prime }{R}^{\prime }$. As for the vertices after the last vertex of type $R$, they are at the end of the order of $G_x$ and all have type either $L,O_L$ or $O_R$, and in the latter case they are siblings and come before the vertices of type $L$ and $O_L$. Thus, all these vertices cannot induce any edge of type $R^{\prime }{R}^{\prime }$ or $L^{\prime }{R}^{\prime }$. Similar observations hold for the vertices before the first vertex of type $L$ and after the last vertex of type $L$.

We now give some simple properties of the delayed rank. The first one gives a simple way of computing the delayed rank of an ordered graph. We first need some definitions.

If $G$ is an ordered graph, we define a sequence ${({𝒢}_i(G))}_{i\ge 0}$ of sets of graphs as follows. Set ${𝒢}_0(G)=\{G\}$. Suppose that ${𝒢}_i(G)$ is defined. Then, for every $H\in {𝒢}_i(G)$, add all the refined quotient graphs of $H$ to ${𝒢}_{i+1}(G)$.

The following results are immediate from the definitions, and can be proved easily by induction on $r$.

The following result bounds the size of each ${𝒢}_r(G)$. It will be important in the analysis of the running time of the algorithm of Theorem 4.

We prove the first property by induction on $r$. For $r=1$, Remark 9 implies that the total number of edges of all quotient graphs of $G$ is at most $m$. Since the refined quotient graphs of $G$ are obtained from the quotient graphs by partitioning the edges and removing some edges, the total number of edges of all graphs in ${𝒢}_1(G)$ is at most $m$. Suppose now that the property holds for some $r\ge 1$. By definition, ${𝒢}_{r+1}(G)={\bigcup }_{H\in {𝒢}_r(G)}{𝒢}_1(H)$. By the induction hypothesis at rank $1$, if $H$ has $m^{\prime }$ edges then the total number of edges of all graphs in ${𝒢}_1(H)$ is at most $m^{\prime }$. By the induction hypothesis at rank $r$, the total number of edges over all $H\in {𝒢}_r(G)$ is at most $m$. Thus, the total number of edges of all graphs in ${𝒢}_{r+1}(G)$ is at most $m$. This proves the first part of the statement.

If $m=0$ then $G$ is monotone bipartite so ${𝒢}_1(G)=\mathrm{\varnothing }$ and $|{𝒢}_1(G)|\le 4mn$. Otherwise, by Remark 9, $G$ has at most $n-1$ quotient graphs, each of which gives rise to at most $4$ refined quotient graphs, so $|{𝒢}_1(G)|\le 4(n-1)\le 4mn$. Now, suppose $r>1$. By the first part of the statement, there are at most $m$ graphs $H\in {𝒢}_{r-1}(G)$ with at least one edge. All other graphs in ${𝒢}_{r-1}(G)$ are monotone bipartite, hence they have no refined quotient graphs. If $H\in {𝒢}_{r-1}(G)$ then $H$ has at most $n$ vertices by Lemma 15 so, by Remark 9, $H$ has at most $n$ quotient graphs. Each of these quotient graphs gives rise to at most $4$ refined quotient graphs, so $|{𝒢}_1(H)|\le 4n$. Taking the union over all $H\in {𝒢}_{r-1}(G)$ which have at least one edge, we get $|{𝒢}_r(G)|\le 4mn$. $◀$

By Lemma 7, delayed substitution closure can alternatively be seen as substitution closure followed by edge union. Therefore, a simple inductive proof shows that the notion of delayed rank is simply a refinement of the notion of rank.

Consider an ordered graph . Compute the delayed decomposition of . By definition, there is a refined quotient graph $H$ of $G$ some type ($R^{\prime }{R}^{\prime },R^{\prime }{L}^{\prime },L^{\prime }{R}^{\prime }$ or $L^{\prime }{L}^{\prime }$) which is in ${𝒞}_r$. We consider several cases depending on the type of $H$.

• $\mathrm{■}$

  If $H$ has type $R^{\prime }{R}^{\prime }$ then $H$ is the graph induced by the edges $R^{\prime }{R}^{\prime }$, to which we remove all vertices before the first vertex of type $R$ and after the last vertex of type $R$. Suppose that $H$ contains a lazy looped $K_t$ interval minor, and let be the intervals corresponding to this interval minor. Recall that $(I_1,\mathrm{\dots },I_t)$ is a partition of $V(H)$. We argue that each interval $I_j$ contains a vertex of type $R$.

  Since the first and the last vertex of $H$ are vertices of type $R$, this is true for $I_1$ and $I_t$. Consider now any $I_j$ with . Since the $K_t$ interval minor is looped, there is an edge between two vertices of $I_j$, which means that there are two vertices in $I_j$ which are of type $R^{\prime }$ but don’t have the same parent (since siblings form an independent set in the quotient graphs). Therefore, there is a vertex of type $R$ in $I_j$. Let . If $y_j\in I_j$ is a vertex of type $R$, it follows from the definition of the type $R$ that $y_j$ has a neighbor in $I_{t+1}$.

  Using $I_{t+1}$, we can then extend any looped $K_t$ to a right lazy looped $K_{t+1}$, any left-lazy looped $K_t$ to a lazy looped $K_{t+1}$, any right-lazy looped $K_t$ to a looped $K_t$ and any lazy looped $K_t$ to a right-lazy looped $K_t$.

• $\mathrm{■}$

  If $H$ has type $R^{\prime }{L}^{\prime }$ then $H$ is the graph induced by the edges $R^{\prime }{L}^{\prime }$, to which we remove all vertices before the first vertex of type $L$ and after the last vertex of type $L$. Suppose that $H$ contains a lazy looped $K_t$ interval minor, and let be the intervals corresponding to this interval minor. Recall that $(I_1,\mathrm{\dots },I_t)$ is a partition of $V(H)$. We argue that each interval $I_j$ contains a vertex of type $L$.

  Since the first and the last vertex of $H$ are vertices of type $L$, this is true for $I_1$ and $I_t$. Consider now any $I_j$ with . Since the $K_t$ interval minor is looped, there is an edge between two vertices of $I_j$, which means that there exist such that the type of $u$ is in $R^{\prime }=\{R,O_R\}$, and the type of $v$ is in $L^{\prime }=\{L,O_L\}$. Thus, there exist consecutive vertices such that the type of $u$ is in $R^{\prime }$ and the type of $v$ is in $L^{\prime }$. This implies that the type of $v$ is $L$. Therefore, there is a vertex with type $L$ in $I_j$. Let . If $y_j\in I_j$ is a vertex of type $L$, it follows from the definition of the type $L$ that $y_j$ has a neighbor in $I_0$.

  Using $I_0$, we can extend any looped $K_t$ to a left lazy looped $K_{t+1}$, any left-lazy looped $K_t$ to a looped $K_t$, any right-lazy looped $K_t$ to a lazy looped $K_{t+1}$ and any lazy looped $K_t$ to a left-lazy looped $K_t$.

• $\mathrm{■}$

  The case $L^{\prime }{R}^{\prime }$ is similar to the case $R^{\prime }{L}^{\prime }$ (except that we prove that each $I_j$ contains a vertex of type $R$), and the case $L^{\prime }{L}^{\prime }$ is similar to the case $R^{\prime }{R}^{\prime }$ (except that we prove that each $I_j$ contains a vertex of type $L$).