Sparse Induced Subgraphs in ${𝑷}_{\mathrm{𝟕}}$-Free Graphs of Bounded Clique Number

Arguably, the problem that is best studied in this context is Max Weight Independent Set (MWIS) in which we are given a vertex-weighted graph and we ask for a set of pairwise non-adjacent vertices of maximum possible weight. Investigating the complexity of MWIS in restricted graph classes led to discovering numerous new tools and techniques in algorithmic graph theory [24, 21, 18, 16]. One of such general techniques is the framework of potential maximal cliques by Bouchitté and Todinca [7, 8]. Intuitively speaking, a potential maximal clique (or PMC for short) in a graph $G$ is a bag of a “reasonable” tree decomposition of $G$. The key contribution of Bouchitté and Todinca [7, 8] is showing that:

1. 1.

   the family $ℱ$ of PMCs in a graph $G$ can be enumerated in time polynomial in $|V(G)|$ and $|ℱ|$, and

2. 2.

   given a family $ℱ$ containing all PMCs of $G$ (and possibly some other sets as well), MWIS can be solved in time polynomial in $|V(G)|$ and $|ℱ|$ by mimicking natural dynamic programming on an appropriate (but unknown) tree decomposition.

Consequently, MWIS admits a polynomial-time algorithm when restricted to any class with polynomially many PMCs. (Here we say that a class $𝒳$ of graphs has polynomially many PMCs if there exists a polynomial $𝗉$, such that the number of PMCs in any $n$-vertex graph in $𝒳$ is at most $𝗉(n)$.)

Later this framework was extended by Fomin, Todinca, and Villanger [19] to the problem of finding a large “sparse” (here meaning: of bounded treewidth) induced subgraph satisfying certain CMSO₂ formula $\psi$. (CMSO₂ stands for Counting Monadic Second Order logic, which is a logic where one can use vertex/edge variables, vertex/edge set variables, quantifications over these variables, and standard propositional operands.) Formally, for a given integer $d$ and a fixed CMSO₂ formula $\psi$ with one free set variable, the $(\mathrm{tw}\le d,\psi )$-MWIS problem (here “MWIS” stands for “max weight induced subgraph”) is defined as follows.

As shown by Fomin, Todinca, and Villanger [19], every problem expressible in this formalism can be solved in polynomial time on classes of graphs with polynomially many potential maximal cliques.

Note that if $d=0$ and $\psi$ is a formula satisfied by all sets, then $(\mathrm{tw}\le d,\psi )$-MWIS is exactly MWIS. It turns out that $(\mathrm{tw}\le d,\psi )$-MWIS captures several other well known computational problems (see also the discussion in [19, 29]), e.g.;

• $\mathrm{■}$

  Feedback Vertex Set (one of Karp’s original 21 NP-complete problems [27]), equivalent by complementation to finding an induced forest of maximum weight,

• $\mathrm{■}$

  Even Cycle Transversal [34, 33, 2], equivalent by complementation to finding an induced graph whose every block is an odd cycle,

• $\mathrm{■}$

  finding a largest weight induced subgraph whose every component is a cycle,

• $\mathrm{■}$

  finding a maximum number of pairwise disjoint and non-adjacent induced cycles.

Despite all advantages of the Bouchitté-Todinca framework, its applicability is somehow limited, as there are numerous natural hereditary graph classes that do not have polynomially many PMCs. Can we use at least some parts of the framework outside its natural habitat?

A notorious open question in algorithmic graph theory is whether MWIS (and, more generally, $(\mathrm{tw}\le d,\psi )$-MWIS) can be solved in polynomial time in graphs that exclude a fixed path as an induced subgraph. It is believed that this question has an affirmative answer, which is supported by the existence of a quasipolynomial-time algorithm of Gartland, Lokshtanov, Pilipczuk, Pilipczuk, and Rzążewski [20, 36, 22]. However, if it comes to polynomial-time algorithms, we know much less.

A polynomial-time algorithm for MWIS (as well as for many other problems) in $P_4$-free graphs (i.e., graphs that exclude a 4-vertex path as an induced subgraph; analogously we define $P_t$-free graphs for any $t$), was discovered already in 1980s [14]. In today’s terms we would say that these graphs have bounded clique-width and thus polynomial-time algorithms for many natural problems, including $(\mathrm{tw}\le d,\psi )$-MWIS, follow from a celebrated theorem by Courcelle, Makowsky, and Rotics [15]. However, already the $P_5$-free case proved to be quite challenging. In 2014, Lokshtanov, Vatshelle, and Villanger [30] showed that Max Weight Independent Set admits a polynomial-time algorithm in $P_5$-free graphs – by adapting the framework of Bouchitté and Todinca. Let us emphasize that $P_5$-free graphs might have exponentially many PMCs, so the approach discussed above cannot be applied directly. Instead, Lokshtanov, Vatshelle, and Villanger proved that in polynomial time one can enumerate a family of some PMCs, and this family is sufficient to solve MWIS via dynamic programming.

By extending this method (and adding a significant layer of technical complicacy), Grzesik, Klimošová, Pilipczuk, and Pilipczuk [23] managed to show that MWIS is polynomially-solvable in $P_6$-free graphs.

Some time later, Abrishami, Chudnovsky, Pilipczuk, Rzążewski, and Seymour [1] revisited the $P_5$-free case and introduced a major twist to the method: they proved that in order to solve MWIS and its generalizations, one does not have to have PMCs exactly, but it is sufficient to enumerate their containers: supersets that do not introduce any new vertices of the (unknown) optimum solution. They also proved that containers for all PMCs in $P_5$-free graphs can be enumerated in polynomial time, circumventing the problem of exponentially many PMCs and significantly simplifying the approach of Lokshtanov, Vatshelle, and Villanger [30]. This result yields a polynomial-time algorithm for $(\mathrm{tw}\le d,\psi )$-MWIS in $P_5$-free graphs.

By further relaxing the notion of a container (to a carver), Chudnovsky, McCarty, Pilipczuk, Pilipczuk, and Rzążewski [13] managed to extend polynomial-time solvability of $(\mathrm{tw}\le d,\psi )$-MWIS to the class of $P_6$-free graphs.

In this work we push the boundary of tractability of $(\mathrm{tw}\le d,\psi )$-MWIS in $P_t$-free graphs by showing the following result.

Quite interestingly, in $P_t$-free graphs, the boundedness of treewidth is equivalent to the boundedness of degeneracy and to the boundedness of treedepth [4]. Thus, Theorem 1.1 yields a polynomial-time algorithm for problems like:

• $\mathrm{■}$

  Vertex Planarization [26, 35], which asks for a largest induced planar subgraph, or

• $\mathrm{■}$

  for constant $k$, finding a largest set of vertices inducing a subgraph of maximum degree at most $k$ (see, e.g., [25]).

Let us remark that the idea of investigating $P_t$-free graphs of bounded clique number was considered before. Pilipczuk and Rzążewski [37] showed that $P_6$-free graphs of bounded clique number have polynomially many PMCs and thus the framework of Bouchitté and Todinca can be applied here directly. However, this is no longer true for $P_7$-free graphs (even bipartite) (see the example in the Conclusions in [13]). On the other hand, Brandstädt and Mosca [9] provided a polynomial-time algorithm for MWIS in $P_7$-free triangle-free graphs. However, they used a rather ad-hoc approach that works well for MWIS, but gives little hope to generalize it to more complicated instances of $(\mathrm{tw}\le d,\psi )$-MWIS. Our work vastly extends both these results.

Following [13], the treedepth formalism is the most handy; we henceforth work with $(\mathrm{td}\le d,\psi )$-MWIS. Furthermore, it is more convenient to work not just with induced subgraphs of bounded treedepth, but with treedepth-$d$ structures: induced subgraphs of treedepth at most $d$ with a fixed elimination forest. Let us proceed with formal definitions.

The rooted forest $𝒯$ is a forest in which each component has exactly one distinguished vertex, called a root. A path in a rooted forest is called vertical if it connects a vertex and any of its ancestors. Given a vertex $v$, we define its depth as the number of vertices on the path connecting $v$ and the root (so the root has depth $1$). The height of the rooted forest $𝒯$ is equal to the maximum depth of a vertex of $𝒯$. By ${𝒯}^{\alpha }$ we denote a set of vertices of $𝒯$ of depth exactly $\alpha$. We also write ${𝒯}^{>\alpha }$ for ${\bigcup }_{{\alpha }^{\prime }>\alpha }{𝒯}^{{\alpha }^{\prime }}$.

We say that vertices $u$ and $v$ are $𝒯$-comparable if they can be connected via a vertical path. Otherwise, we say that they are $𝒯$-incomparable. An elimination forest of graph $G$ is a rooted forest $𝒯$ such that $V(𝒯)=V(G)$ and for each edge $uv\in E(G)$ vertices $u$ and $v$ are $𝒯$-comparable. The treedepth of graph $G$ is the minimum height of any possible elimination forest of graph $G$.

Given a graph $G$ and an integer $d$, a treedepth-$d$ structure (the notion first proposed in [13]) is a rooted forest $𝒯$ of height at most $d$ such that $V(𝒯)$ is a subset of $V(G)$ and $𝒯$ is an elimination forest of the subgraph of $G$ induced by $V(𝒯)$. A treedepth-$d$ structure $𝒯$ is a substructure of a treedepth-$d$ structure ${𝒯}^{\prime }$ if $𝒯$ is a subgraph of ${𝒯}^{\prime }$ (as a rooted forest) and every root of $𝒯$ is also a root of ${𝒯}^{\prime }$. A treedepth-$d$ structure $𝒯$ is called maximal if there is no treedepth-$d$ structure ${𝒯}^{\prime }$ such that $𝒯$ is a substructure of ${𝒯}^{\prime }$ and $𝒯\ne {𝒯}^{\prime }$. Equivalently, $𝒯$ is maximal if it cannot be extended by adding a leaf preserving the bound on the height of $𝒯$. To avoid notational clutter, we sometimes treat $𝒯$ as set of vertices, for example in expressions $|A\cap 𝒯|$.

Let $𝒯$ be a treedepth-$d$ structure in $G$; think of $𝒯$ as the sought solution to the $(\mathrm{td}\le d,\psi )$-MWIS problem in question. As proven in [19] (and cast onto the current setting in [13]), there exists a tree decomposition $(T,\beta )$ of $G$ whose every bag is either contained in $N[v]$ for a leaf $v$ of $𝒯$, or whose intersection with $𝒯$ is contained in a single root-to-leaf path of $𝒯$, excluding the leaf. We call the latter bags $𝒯$-avoiding.

Furthermore, the framework of [19] shows how to solve $(\mathrm{td}\le d,\psi )$-MWIS given a family $ℱ$ of subsets of $V(G)$ with the promise that all bags of such tree decomposition $(T,\beta )$ are in $ℱ$. In [1], it is shown that it suffices for $ℱ$ to contain only containers of bounded defect for bags in $(T,\beta )$: we require that there exists a universal constant $\widehat{d}$ such that for every $t\in V(T)$ there exists $A\in ℱ$ such that the bag $\beta (t)$ is contained in $A$ and $A$ contains at most $\widehat{d}$ elements of $𝒯$.

Note that if $v$ is a leaf of $𝒯$, then $N[v]$ may contain only ancestors of $v$ among the vertices of $𝒯$, so $N[v]$ is an excellent container for any bag contained in $N[v]$. Thus, it suffices to provide containers for $𝒯$-avoiding bags. This is how [1] solved $(\mathrm{td}\le d,\psi )$-MWIS in $P_5$-free graphs; by generalizing the definition of a container to a carver, the same approach is applied to $P_6$-free graphs in [13].

In fact, for a treedepth-$d$ structure $𝒯$, the tree decomposition $(T,\beta )$ of [19] is constructed as follows: it is shown that there exists a minimal chordal completion $F$ of $G$ (i.e., an inclusion-wise minimal set of edges to add to $G$ to make it chordal) whose addition keeps $𝒯$ a treedepth-$d$ structure, and $(T,\beta )$ is any clique tree of $G+F$. A potential maximal clique (abbrieviated as PMC) is a maximal clique in $G+F$ for some minimal chordal completion $F$ of $G$. Both [1] and [13] actually provide containers/carvers for every treedepth-$d$ structure in $G$ and an arbitrary choice of a $𝒯$-avoiding PMC in $G$. Furthermore, [13] provides an example of a family of $P_7$-free triangle-free graphs where such a statement is impossible (i.e., any such family of containers/carvers would need to be of exponential size).

However, the algorithmic framework of [19, 1, 13] requires only that the provided family $ℱ$ contains containers/carvers for all bags of only one “good” tree decomposition $(T,\beta )$, and only for the sought solution $𝒯$. This should be contrasted with all $𝒯$-avoiding PMCs, which is in some sense the set of all reasonable $𝒯$-avoiding bags, and for all treedepth-$d$ structures $𝒯$. Thus, if we want to tackle $P_7$-free graphs of bounded clique number, we need to significantly deviate from the path of [1, 13] and either use the power of the choice of $(T,\beta )$ or the fact that we need to handle only $𝒯$ being the optimum solution to the problem we are solving.

The assumption of bounded clique number allows us to quickly reduce the case of finding a container for a PMC to finding a container for a minimal separator. For a set $S\subseteq V(G)$, a connected component $A$ of $G-S$ is full to $S$ if $N(A)=S$; a set $S$ is a minimal separator if it has at least two full components.¹¹1Note the following equivalent definition: We say that a set of vertices $S$ is a $(u,v)$- separator if $u$ and $v$ belong to distinct components in $G-S$. A $(u,v)$-separator $S$ is called minimal if no proper subset of $S$ is a $(u,v)$-separator. A set of vertices $S$ is called a minimal separator of graph $G$ if there exists a pair of vertices $u$ and $v$ such that $S$ is a minimal $(u,v)$-separator. A classic fact about PMCs [8] is that for every potential maximal clique $\mathrm{\Omega }$ and for every connected component $D$ of $G-\mathrm{\Omega }$, the set $N(D)$ is a minimal separator. By a classic result of Gyárfás, the class of $P_t$-free graphs is $\chi$-bounded, in particular, if $G$ is $P_t$-free and $\omega (G)\le k$ (where $\omega (G)$ is the number of vertices in a largest clique in $G$), then $\chi (G)\le {(t-1)}^{k-1}$. This, combined with a VC-dimension argument based on the classic result of Ding, Seymour, and Winkler [17], shows the following:

That is, except for a simple case $N[v]=\mathrm{\Omega }$ for some $v\in \mathrm{\Omega }$, the PMC $\mathrm{\Omega }$ is a union of a constant number of minimal separators. Hence, it suffices to generate a family ${ℱ}^{\prime }$ of containers for $𝒯$-avoiding minimal separators (which are defined analogously to $𝒯$-avoiding bags) and take $ℱ$ to be the family of unions of all tuples of at most $c$ elements of ${ℱ}^{\prime }$.

Let $G$ be a $P_7$-free graph with $\omega (G)\le k$. We start as in [1, 13]: let $𝒯$ be an arbitrary treedepth-$d$ structure in $G$ and let $S$ be a minimal separator in $G$ with full components $A$ and $B$ such that $S$ is $𝒯$-avoiding. We want to design a polynomial-time algorithm that outputs a family ${ℱ}^{\prime }$ of subsets of $V(G)$ that contains a container for $S$. The algorithm naturally does not know $𝒯$ nor $S$; the convenient and natural way of describing the algorithm as performing some nondeterministic guesses about $𝒯$ and $S$, with the goal of outputting a container for $S$ in the end. We succeed if the number of subcases coming from the guesses is polynomial in the size of $G$ and the family ${ℱ}^{\prime }$ consists of all containers generated by all possible runs of the algorithm.

We almost succeed with this quest. That is, we are able to guess an “almost container” $K$ for $S$: $K$ contains a constant number of vertices of $𝒯$ and we identified a set $𝒟$ of tricky connected components of $G-K$ that are contained in $A\cup B\cup S$; all other connected components of $G-K$ are contained in $A$, in $B$, or in some other connected component of $G-S$. Every tricky component $D\in 𝒟$ is somewhat simpler: we identify a subset $\mathrm{\varnothing }\ne L(D)⊊D$ such that if $𝒞(D)$ is the family of all connected components of $G[L(D)]$ and of $G[D\setminus L(D)]$, then every $C\in 𝒞(D)$ is a module of $G[D]$. (A set $A\subseteq V(G)$ is a module in $G$ if every vertex $v\in V(G)\setminus A$ is either complete to $A$ or anti-complete to $A$.)

Observe now that every connected component $C\in 𝒞(D)$ satisfies , as $D\setminus C$ contains a vertex complete to $C$. Hence, we can recurse on $C$, understanding it fully (more precisely, finding optimum partial solutions; the definition of this “partial” requires a lot of CMSO₂ mumbling).

Furthermore, we observe that the quotient graph $G[D]/𝒞(D)$ is bipartite. Thus, if we can understand how to solve $(\mathrm{td}\le d,\psi )$-MWIS on $P_7$-free bipartite graphs, then we should be done: the partial solutions from components $C\in 𝒞(D)$, combined with the understanding of the $P_7$-free bipartite graph $G[D]/𝒞(D)$ should give all partial solutions of $G[D]$ for every $D\in 𝒟$. This, in turn, should give an understanding on how $(\mathrm{td}\le d,\psi )$-MWIS behaves on $K\cup \bigcup 𝒟$. As $S\subseteq K\cup \bigcup 𝒟$, this should suffice to solve $(\mathrm{td}\le d,\psi )$-MWIS on $G$ using $(K,𝒟,L)$ to play the role of the container for $S$.

Explaining properly all “should”s from the previous paragraph is quite involved and tedious. In this overview, let us focus on the more interesting case of solving $(\mathrm{td}\le d,\psi )$-MWIS in $P_7$-free bipartite graphs. Here, we actually prove the following result.

We remark that Theorem 2.2 is not needed if one just wants to solve the MWIS problem, as this problem can be solved in general bipartite graphs using matching or flow techniques.

On the other hand, our work identified the bipartite case as an interesting subcase in exploring tractability of $(\mathrm{td}\le d,\psi )$-MWIS in $P_t$-free graphs. To state a precise problem for future work, we propose polynomial-time tractability of Feedback Vertex Set in $P_t$-free bipartite graphs. Meanwhile, Theorem 2.2 and its proof in Section 3 can be of independent interest.

The proof of Theorem 2.2 starts from the work of Kloks, Liu, and Poon [28], who showed that chordal bipartite graphs have polynomial number of PMCs, and thus $(\mathrm{td}\le d,\psi )$-MWIS problem is solvable in this graph class by the direct application of the PMC framework of Bouchitté and Todinca. (A graph $G$ is chordal bipartite if it is bipartite and does not contain induced cycles longer than $4$.) A $P_7$-free bipartite graph is almost chordal bipartite: it can contain six-vertex cycles.

We would like to add some edges to the input graph $G$ so that it becomes chordal bipartite. Let $C=c_1-c_2-\mathrm{\dots }-c_6-c_1$ be an induced six-vertex cycle in $G$; we would like to add the edge $c_1{c}_4$ to keep $G$ bipartite but break $C$. We show that, if one chooses $C$ carefully, one can do it so that $G$ remains $P_7$-free. However, such an addition may break the sought solution $𝒯$: if $c_1,c_4\in V(𝒯)$ but are incomparable in the elimination forest $𝒯$, then $𝒯$ is no longer a treedepth-$d$ structure in $G+\{c_1{c}_4\}$.

We remedy this by a thorough investigation of the structure of the neighborhood of a six-vertex cycle in a $P_7$-free graph, loosely inspired by [5]. On a high level, we show that there is a branching process with a polynomial number of outcomes that, in some sense “correctly” completes $G$ to a chordal bipartite graph, proving Theorem 2.2.

In summary, the proof of Theorem 1.1 consists of three ingredients. First, we show the guesswork that leads to a polynomial number of candidate “almost containers” $(K,𝒟,L)$ for a minimal separator $S$ in the input graph $G$. Second, we focus on bipartite graphs and prove Theorem 2.2. Finally, we show how these two tools combine with the dynamic programming framework of [19, 1, 13].

In this extended abstract, we present a more detailed overview of the proof of one part, namely Theorem 2.2. The full version of the work can be found in the appendix.