Covering minimal separators and potential maximal cliques in $P_t$-free graphs
Andrzej Grzesik Tereza Klimošová Marcin Pilipczuk Michał Pilipczuk
cs.DM math.CO




Properties of Streamer Wave Events Observed During the STEREO Era
    [
    December 30, 2023
=================================================================



20(0, 11.0)

    < g r a p h i c s >


20(-0.25, 11.4)

    < g r a p h i c s >




A graph is called P_t-free if it does not contain a t-vertex path as an induced subgraph. 
While P_4-free graphs are exactly cographs, the structure of P_t-free graphs for t ≥ 5 remains little undestood. 
On one hand, classic computational problems such as Maximum Weight Independent Set (MWIS) and 3-Coloring are not known to be NP-hard
on P_t-free graphs for any fixed t.
On the other hand, despite significant effort, polynomial-time algorithms for MWIS in P_6-free graphs [SODA 2019] and 3-Coloring in P_7-free graphs [Combinatorica 2018] have been found  only recently. 
In both cases, the algorithms rely on deep structural insights into the considered graph classes.

One of the main tools in the algorithms for MWIS in P_5-free graphs [SODA 2014] and in P_6-free graphs [SODA 2019] is the so-called Separator Covering Lemma that asserts
that every minimal separator in the graph can be covered by the union of neighborhoods of a constant number of vertices. 
In this note we show that such a statement generalizes to P_7-free graphs and is false in P_8-free graphs. 
We also discuss analogues of such a statement for covering potential maximal cliques with unions of neighborhoods.








§ INTRODUCTION

By P_t we denote a path on t vertices. A graph is H-free if it does not contain 
an induced subgraph isomorphic to H. 

We are interested in classifying the complexity of fundamental computational problems,
such as Maximum Weight Independent Set (MWIS), 
k-Coloring for fixed or arbitrary k, or Feedback Vertex Set,
on various hereditary graph classes, in particular on H-free graphs for small fixed graphs H.
As noted by Alekseev <cit.>, MWIS is NP-hard on H-free graphs
unless every connected component of H is a tree with at most three leaves. 
Similarly, 3-Coloring is known to be NP-hard on H-free graphs
unless every connected component of H is a path <cit.>. 
On the other hand, it would be consistent with our knowledge if both MWIS and 3-Coloring were polynomial-time
solvable on P_t-free graphs for every fixed t, however this is currently unknown.
Positive results in this direction are limited only to small values of t, as explained next.

P_4-free graphs, known also as cographs, are well-understood; in particular,
they have bounded cliquewidth, which implies the existence polynomial-time algorithms 
for all the discussed problems. 
P_5-free graphs are much more mysterious and only in 2014, Lokshtanov, Vatshelle, and Villanger
proposed a novel technique that uses the framework of potential maximal cliques and proved
polynomial-time tractability of MWIS in this class <cit.>. 
This result was followed by a much more technically complex positive result
for P_6-free graphs <cit.>
and a recent algorithm for Feedback Vertex Set in P_5-free graphs <cit.>.
For coloring with few colors,
the state-of-the-art are polynomial-time algorithms for 3-Coloring
of P_7-free graphs <cit.> and
4-Coloring of P_6-free graphs <cit.>.

In full generality, the so-called Gyárfás' path argument
gives subexponential-time algorithms for both MWIS and 3-Coloring
in P_t-free graphs for any fixed t <cit.>.
Using the Gyárfás' path argument and the three-in-a-tree theorem <cit.>,
it is possible to obtain a quasi-polynomial-time approximation scheme for MWIS
in H-free graphs whenever every connected component of H is a tree with at most three leaves <cit.>. Note that this covers exactly the cases where NP-hardness is not known. 
The crucial property of P_t-free graphs that is used in all the works mentioned above is that, due to 
the aforementioned Gyárfás' path argument, every P_t-free graph admits
a balanced separator consisting of at most t-1 closed neighborhoods of a vertex.

The lack of NP-hardness results on one side, and shortage of generic algorithmic tools in P_t-free graphs on the other side, calls for a deeper understanding of the structure of P_t-free graphs for larger values of t. 
In this note we discuss one property that appeared important in the algorithms for MWIS
for P_5-free and P_6-free graphs <cit.>, namely
the possibiliy to cover a minimal separator with a small number of vertex neighborhoods.

Let G be a graph. For a set S ⊆ V(G), a connected component A of G-S
is a full component to S if N_G(A) = S. A set S is a minimal separator
if it admits at least two full components.
A set F ⊆V(G)2∖ E(G) is a chordal completion
if G+F  (V(G), E(G) ∪ F) is chordal (i.e., does not contain an induced subgraph 
isomorphic to a cycle on at least four vertices). 
A set ⊆ V(G) is a potential maximal clique (PMC) if there exists
an (inclusion-wise) minimal chordal completion F of G such that 
is a maximal clique of G+F. 
Potential maximal cliques and minimal separators are tightly connected: for example, 
a graph is chordal if and only if every its minimal separator is a clique, and if 
 is a PMC in G, then for every connected component D of G-
the set N_G(D) is a minimal separator with D being one of the full components. 

A framework of Bouchitté and Todinca <cit.>, extended by Fomin, Todinca, and Villanger <cit.>, allows solving multiple computational problems (including MWIS and Feedback Vertex Set) on graph classes where graphs have only a polynomial number of PMCs.
While P_5-free graphs do not have this property, the crucial insight of the work
of Lokshtanov, Villanger and Vatshelle <cit.> allows modifying the framework
to work for P_5-free graphs and, with more effort, for P_6-free graphs <cit.>.

A simple, but crucial in <cit.>, insight about the structure of P_5-free graphs
is the following lemma.

Let G be a P_5-free graph, let S be a minimal separator in G, and let A and B
be two full components of S.
Then for every a ∈ A and b ∈ B it holds that S ⊆ N_G(a) ∪ N_G(b).

The above statement is per se false in P_6-free graphs, but the following variant
is true and turned out to be pivotal in <cit.>:

Let G be a P_6-free graph, let S be a minimal separator in G, and let A and B
be two full components of S.
Then there exist nonempty sets A' ⊆ A and B' ⊆ B such that
|A'| ≤ 3, |B'| ≤ 3, and S ⊆ N_G(A) ∪ N_G(B).

That is, every minimal separator in a P_6-free graph has a dominating set of size at most 6,
     contained in the union of two full components of this separator.

In Section <ref> we extend the result to P_7-free graphs as follows.

Let G be a P_7-free graph and let S be a minimal separator in G.
Then there exists a set S'⊆ V(G) of size at most 22 such that S ⊆ N_G[S'].

Theorem <ref> directly generalizes a statement proved by Lokshtanov et al. <cit.>,
  which was an important ingredient of their quasi-polynomial-time algorithm for MWIS in P_6-free
  graphs.

Section <ref> discusses a modified example from <cit.>
that witnesses that no statement analogous to Theorem <ref> can be true in P_8-free graphs.
Furthermore, observe that in the statements for P_5-free and P_6-free graphs 
the dominating set for the separator is guaranteed to be contained in two full components of the separator. This is no longer the case in Theorem <ref> for a reason: 
in Section <ref> we show examples of P_7-free graphs where any constant-size dominating
set of a minimal separator needs to contain a vertex from the said separator.

The intuition behind the framework of PMCs, particularly visible in 
the quasi-polynomial-time algorithm for MWIS in P_6-free graphs <cit.>,
is that potential maximal cliques can serve as balanced separators of a graph.
Here, X ⊆ V(G) is a balanced separator of G if every connected component of G-X
has at most |V(G)|/2 vertices. 
The quasi-polynomial-time algorithm of <cit.> tried to recursively
split the graph into significantly smaller pieces by branching and deleting
as large as possible pieces of such a PMC. 
Motivated by this intuition, in Section <ref> we generalize Theorem <ref> to 
dominating potential maximal cliques:

Let G be a P_7-free graph and let  be a potential maximal clique in G.
Then there exists a set ' ⊆ V(G) of size at most 68 such that ⊆ N_G['].

Since every minimal separator is a subset of some potential maximal clique in a graph,
Theorem <ref> generalizes Theorem <ref>. For the same reason, our examples for P_8-free graphs also prohibit extending Theorem <ref>
to P_8-free graphs.



§ PRELIMINARIES


For basic graph notation, we follow the arXiv version of <cit.>.
We outline here only nonstandard notation that is not presented in the introduction.

For a set X ⊆ V(G), by (G-X) we denote the family of connected components of G-X.
A set A is complete to a set B if every vertex of A is adjacent to every vertex of B.



  
Potential maximal cliques.
A set ⊆ V(G) is a potential maximal clique (PMC)
  if:


   none of the connected components of (G-) is full to ; and

   whenever uv is a non-edge with {u,v}⊆, then there is a component D∈(G-) such that {u,v}⊆ N(D).

In the second condition, we will say that the component D covers the non-edge uv.
As announced in the introduction, we have the following.

For a graph G, a vertex subset Ω⊆ V(G) is a PMC if and only if there exists a minimal chordal completion F of G such that Ω is a maximal clique in G+F.

We will also need the following statement.

For every PMC  of G and every D ∈(G-), the
set N_G(D) is a minimal separator.




  
Modules.
Let G be a graph. A set M⊆ V(G) is a module of G if N(x)∖ M=N(y)∖ M for every x,y∈ M. 
Note that ∅, V(G) and all the singletons {x} for x ∈ V(G) are modules; we call these modules trivial. A graph is prime if all its modules are trivial.
A module M of G is strong if M ≠ V(G) and M
does not overlap with any other module of G, i.e., for every module M' of G we have
either M⊆ M', or M'⊆ M, or M ∩ M'=∅.

A partition  of V(G) is a modular partition of G if M is a module of G for every M∈. 
The quotient graph G/ is a graph with the vertex set  and with M'M∈ E(G/) if and only if m'm∈ E(G) for all m'∈ M' and m∈ M
(since M' and M are modules, m'm is an edge either for all pairs m'∈ M' and m∈ M, or for none). 

It is well-known (cf. <cit.>) that if |V(G)| > 1 
then the family of (inclusion-wise) maximal strong modules of G
forms a modular partition of G whose quotient graph is either an independent set
(if G is not connected), a clique (if the complement of G is not connected),
  or a prime graph (otherwise).
  We denote this modular partition by (G) and we let (G) G/(G).
For D ⊆ V(G), we abbreviate (G[D]) and (G[D]) with (D) and (D), respectively.



§ COVERING MINIMAL SEPARATORS IN P_7-FREE GRAPHS


This section is devoted to the proof of Theorem <ref>. 
We need the following two results from <cit.>.

Suppose X is a non-empty finite set and (X,≤_1) and (X,≤_2) are two quasi-orders.
Suppose further that every pair of two different elements of X is comparable either with respect to ≤_1 or with respect to ≤_2.
Then there exists an element x∈ X such that for every y∈ X we have either x≤_1 y or x≤_2 y.


Suppose G is a graph and D⊆ V(G) is subset of vertices such that |D|≥ 2 and G[D] is connected.
Suppose further that vertices p,q∈ D respectively belong to different elements M^p,M^q of the modular partition (D) such that M^p and M^q are adjacent in the 
quotient graph (D).
Then, for each vertex u∈ N(D) at least one of the following conditions holds:


  *  u∈ N[p,q];

  *  there exists an induced P_4 in G such that
 u is one of its endpoints, while the other three vertices belong to D;

  *  (D) is a clique and the neighborhood of u in D is the union of some collection of maximal strong modules in D.

In particular, if (D) is not a clique, then the last condition cannot hold.


Let G be a P_7-free graph, let S be a minimal separator in G, and let A_1 and A_2
be the vertex sets of two full components of S. 
If |A_i| = 1 for some i∈{1,2}, then we are done by setting S'  A_i, so assume |A_1|,|A_2| > 1.
For each i∈{1,2}, fix two different maximal strong modules M^p_i and M^q_i 
of G[A_i] that are adjacent in (A_i). 
Furthermore, pick arbitrary p_i ∈ M^p_i and q_i ∈ M^q_i.

For each i∈{1,2}, we apply Lemma <ref> to D  A_i and N(D) = S.
We say that a vertex x ∈ S is of type (<ref>)_i if x ∈ N(p_i) ∪ N(q_i).
We say that a vertex x ∈ S is of type (<ref>)_i if x is not of type (<ref>)_i
and there is an induced P_4 in G with u being one of the endpoints
and the other three vertices belonging to A_i.
Finally, we say that a vertex x ∈ S is of type (<ref>)_i if x is neither of type
(<ref>)_i nor (<ref>)_i. 
Lemma <ref> asserts that if there are vertices of type (<ref>)_i,
then (A_i) is a clique and the neighborhood in A_i of every vertex of this type
is the union of a collection of maximal strong modules of G[A_i].
For α,β∈{a,b,c}, let S_αβ be the set of vertices x ∈ S
that are of type (α)_1 and (β)_2.

We need the following claim.

Let i ∈{1,2} and let x,y ∈ S be of type (<ref>)_i.
Then A_i ∩ (N(x) ∖ N(y)) is complete to A_i ∩ (N(y) ∖ N(x)).


By Lemma <ref>,
(A_i) is a clique and both A_i ∩ (N(x) ∖ N(y))
and A_i ∩ (N(y) ∖ N(x)) are the unions of some disjoint collections of maximal strong modules of G[A_i].
The claim follows.


Since G is P_7-free, S_bb = ∅. 
Furthermore, if we set R_a {p_1,q_1,p_2,q_2}, then

    S_aa∪ S_ab∪ S_ac∪ S_ba∪ S_ca⊆ N(R_a).

In the rest of the proof, we construct sets R_bc, R_cb and R_cc such that
S_αβ⊆ N[R_αβ] for αβ∈{bc,cb,cc}.
We will conclude that S' R_a∪ R_bc∪ R_cb∪ R_cc
satisfies the statement of the lemma, because |R_a|=4
and we will ensure that |R_bc|,|R_cb|≤ 5 and |R_cc|≤ 8.



We start with constructing the set R_bc. 
If S_bc = ∅, then we set R_bc = ∅.
Otherwise, let v ∈ S_bc be a vertex with inclusion-wise minimal
set A_2 ∩ N(v). 
Furthermore, let w ∈ A_2 be an arbitrary neighbor of v in A_2;
w exists since A_2 is a full component of S.
Also, let v, u^1, u^2, u^3 be vertices of an induced P_4 with u^1,u^2,u^3 ∈ A_1; recall here that v is of type (<ref>)_1. 
We set R_bc{u^1,u^2,u^3,v,w} and claim that S_bc⊆ N[S_bc].

Assume the contrary, and let v' ∈ S_bc∖ N[R_bc]. 
By the choice of v and since w ∈ A_2 ∩ (N(v) ∖ N(v')),
there exists w' ∈ A_2 ∩ (N(v') ∖ N(v)). 
By Claim <ref>, ww' ∈ E(G). 
Then, v'-w'-w-v-u^1-u^2-u^3 is an induced P_7 in G, a contradiction.

Hence, we constructed R_bc⊆ V(G) of size at most 5
such that S_bc⊆ N[R_bc].
A symmetric reasoning yields R_cb⊆ V(G) of size at most 5
such that S_cb⊆ N[R_cb]. 



We are left with constructing R_cc. If S_cc = ∅, then we take R_cc = ∅
and conclude. In the remaining case, S_cc is non-empty, so both (A_1) and (A_2) are cliques.

For each i∈{1,2},
we define a quasi-order ≤_i on S_cc as follows. 
For x,y ∈ S_cc, x ≤_i y if A_i ∩ N(x) ⊆ A_i ∩ N(y).
An unordered pair xy ∈S_cc2 is a butterfly
if x and y are incomparable both in ≤_1 and in ≤_2, that is, 
  if each of the following four sets is nonempty:

    A_1 ∩ (N(x) ∖ N(y)),       A_1 ∩ (N(y) ∖ N(x)),
       A_2 ∩ (N(x) ∖ N(y)),       A_2 ∩ (N(y) ∖ N(x)).


See Figure <ref> for an illustration.

Lemma <ref> allows us to easily dominate subsets of S_cc that do
not contain any butterflies:

Let T ⊆ S_cc be such that there is no butterfly xy with x,y ∈ T.
Then there exist a vertex a_1 ∈ A_1 and a_2 ∈ A_2 such that T ⊆ N(a_1) ∪ N(a_2).


If T=∅, the claim is trivial, so assume otherwise.
Let us focus on quasi-orders ≤_1 and ≤_2, restricted to T.
Since there are no butterflies in T, the prerequisities of Lemma <ref> 
are satisfied for (T,≤_1) and (T,≤_2). 
Hence, there exists x ∈ T with x ≤_1 y or x ≤_2 y for every y ∈ T.
For i∈{1,2}, let a_i be an arbitrary neighbor of x in A_i
(it exists as A_i is a full component of S). 
For every y ∈ T, there exists i ∈{1,2} such that x ≤_i y,
hence a_iy ∈ E(G). 
We conclude that T ⊆ N(a_1) ∪ N(a_2), as desired.

If there is no butterfly at all, then we apply Claim <ref> to T = S_cc,
obtaining vertices a_1,a_2 and set R_cc = {a_1,a_2}. 
Thus, we are left with the case where at least one butterfly exists.

Let xy be a butterfly with inclusion-wise minimal set

    (A_1 ∪ A_2) ∩ N({x,y}).

Furthermore, pick the following four vertices

    u_1^x∈    A_1 ∩ (N(x) ∖ N(y)),    u_1^y∈   A_1 ∩ (N(y) ∖ N(x)),
    
    u_2^x∈    A_2 ∩ (N(x) ∖ N(y)),    u_2^y∈   A_2 ∩ (N(y) ∖ N(x)).

Claim <ref> ensures that u_1^xu_1^y∈ E(G) and u_2^xu_2^y∈ E(G).

Set 

    R' {x, y, u_1^x, u_1^y, u_2^x, u_2^y}.

Let T  S_cc∖ N[R']. We claim the following:

There is no butterfly x'y' with x',y' ∈ T.


Assume the contrary, and let x'y' be a butterfly with x',y' ∈ T.
By the minimality of xy, as u_1^x∈ (A_1 ∪ A_2) ∩ N({x,y})
but u_1^x∉ (A_1 ∪ A_2) ∩ N({x',y'}),
there exists w ∈ (A_1 ∪ A_2) ∩ (N({x',y'}) ∖ N({x,y})).
By symmetry, assume that w ∈ A_1 and x'w ∈ E(G); see Figure <ref>.

By Claim <ref>, wu_1^x∈ E(G) and wu_1^y∈ E(G).
If xy ∈ E(G), then x'-w-u_1^x-x-y-u_2^y-p_2 would be an induced P_7 in G.
Otherwise, 
if xy ∉ E(G), then x'-w-u_1^x-x-u_2^x-u_2^y-y would be an induced P_7 in G.
As in both cases we have obtained a contradiction, this finishes the proof.


By Claim <ref>, we can apply Claim <ref>
to T and obtain vertices a_1 ∈ A_1 and a_2 ∈ A_2 with T ⊆ N(a_1) ∪ N(a_2).
Hence, we can take R_cc R' ∪{a_1,a_2}, thus concluding the proof of Theorem <ref>.



§ COVERING PMCS IN P_7-FREE GRAPHS


We now prove the following statement which, together with Theorem <ref>
and Lemma <ref>, immediately implies Theorem <ref>.

Let G be a P_7-free graph and let  be a potential maximal clique in G.
Then there exists a set ' ⊆ of size at most 2
and a set 𝒟' ⊆(G-) of size at most 3
such that

    ⊆ N['] ∪⋃_D ∈𝒟' N(D).



Let 𝒟⊆(G-) be an inclusion-wise minimal set of components
of G- such that for every nonedge uv in  there exists a component D ∈𝒟
that covers uv. 

If 𝒟 = ∅, then  is a clique in G and thus
we can put ' = {v} and 𝒟'= ∅ for an arbitrary v ∈.
Otherwise, pick any D ∈𝒟. By the minimality of 𝒟, there exists
a nonedge uv in  that is covered by D and by no other component of 𝒟∖{D}. 

Assume that there is no component D_v ∈𝒟∖{D} with v ∈ N(D_v).
Then ∖ N(D) ⊆ N(v), so ⊆ N(v) ∪ N(D). 
Hence, we can set ' ={v} and 𝒟' = {D}. 
Symmetrically, we are done if there is no component D_u ∈𝒟∖{D}
with u ∈ N(D_u). 

In the remaining case, pick arbitrary components 
D_v ∈𝒟∖{D} with v ∈ N(D_v) and
D_u ∈𝒟∖{D} with u ∈ N(D_u).
Since D is the only component of 𝒟 that covers uv, we have u ∉ N(D_v)
and v ∉ N(D_u); in particular, D_u ≠ D_v. 
We claim that we can set ' = {u,v} and 𝒟' = {D,D_u,D_v}. That is,
   we claim that

    ⊆ N[u] ∪ N[v] ∪ N(D) ∪ N(D_u) ∪ N(D_v).

Assume the contrary, and let x ∈ be such that xu ∉ E(G), xv ∉ E(G),
x ∉ N(D), x ∉ N(D_u), and x ∉ N(D_v). 

Since xu is a nonedge of , there exists D_xu∈𝒟 that covers xu.
Similarly, there exists D_xv∈𝒟 that covers xv.
By the choice of x, we have D_xu,D_xv∉{D,D_u,D_v}.
Further, since D is the only component of 𝒟 covering uv,
v ∉ N(D_xu) and u ∉ N(D_xv); in particular, D_xu≠ D_xv.
See Figure <ref>.

Let y_u be an arbitrary neighbor of u in D_u, let y_v be an arbitrary neighbor of v in D_v, 
let P_u be a shortest path from u to x with all internal vertices in D_xu, and let P_v be a shortest path from v to x with all internal vertices in D_xv. 
Then, y_u - u - P_u - x - P_v - v - y_v is an induced path with at least
7 vertices, a contradiction. This proves (<ref>) and concludes the proof of Lemma <ref>.






§ EXAMPLES


In this section we discuss two examples showing tightness of the statement of Theorem <ref>: we show that it cannot be generalized to P_8-free graphs and that 
a small dominating set of a minimal separator may need to contain elements of the said separator. The examples are modifications of a corresponding example presented
in the conclusions of <cit.>.




  
First example. Consider the following graph G. 
We create three sets of n vertices each, A_1 = {a_1^j | 1 ≤ j ≤ n},
   A_2 = {a_2^j | 1 ≤ j ≤ n}, and S = {s^j | 1 ≤ j ≤ n}.
We set V(G) = A_1 ∪ A_2 ∪ S. 
For the edge set of G, we turn A_1 and A_2 into cliques
and add edges s^ja_1^j and s^ja_2^j, for all 1 ≤ j ≤ n. 
This concludes the description of the graph G; see Figure <ref>.
Note that S is a minimal separator in G
with A_1 and A_2 being two full components of S.

First, note that for every v ∈ V(G), |N[v] ∩ S| =1. Thus, any set dominating
S has to contain at least n vertices. 

Second, note that G is P_8-free. To see this, let P be an induced path in G.
Since A_1 and A_2 are cliques, P contains at most two vertices from each A_i, i∈{1,2},
and these vertices are consecutive on P.
Since S is an independent set in G, P cannot contain more than one vertex of S in a row.
Hence, P contains at most three vertices of S. Consequently |V(P)| ≤ 7, as desired.
Note that if n ≥ 3, then there is an induced P_7 in G, for example
s^1 - a^1_1 - a^2_1 - s^2 - a^2_2 - a^3_2 - s^3.



  
Second example.
Here, let us modify the graph G from the first example by turning S into a clique.
Still, S is a minimal separator in G with A_1 and A_2 being two full components of S.

First, note that for every v ∈ A_1 ∪ A_2, we still have |N[v] ∩ S| =1.
Thus, any set dominating S that is disjoint with S has to contain at least n vertices.

Second, note that G is P_7-free. To see this, observe that G can be partitioned into
three cliques, A_1, A_2, and S, and any induced path in G contains at most two vertices
from each of the cliques. 
Note that if n ≥ 3, then there is an induced P_6 in G, for example a_1^3 - a_1^1 - s^1 - s^2 - a_2^2 - a_2^3.

abbrv



