Algorithms Parameterized by Vertex Cover and Modular Width, Through Potential Maximal Cliques

(1)

https://doi.org/10.1007/s00453-017-0297-1

Algorithms Parameterized by Vertex Cover and Modular Width, Through Potential Maximal Cliques

Fedor V. Fomin¹ · Mathieu Liedloff² · Pedro Montealegre² · Ioan Todinca²

Received: 26 May 2016 / Accepted: 20 February 2017 / Published online: 27 February 2017

Abstract In this paper we give upper bounds on the number ofminimal separatorsand potential maximal cliques of graphsw.r.t. two graph parameters, namelyvertex cover (vc) andmodular width(mw). We prove that for any graph, the number of its minimal separators isO^∗(3^vc)andO^∗(1.6181^mw), and the number of potential maximal cliques isO^∗(4^vc)andO^∗(1.7347^mw), and these objects can be listed within the same running times (TheO^∗notation suppresses polynomial factors in the size of the input).

Combined with known applications of potential maximal cliques, we deduce that a large family of problems, e.g.,Treewidth,Minimum Fill- in,Longest Induced Path, Feedback vertex set and many others, can be solved in time O^∗(4^vc) orO^∗(1.7347^mw). With slightly different techniques, we prove that theTreedepth problem can be also solved in single-exponential time, for both parameters.

Keywords Parametrized algorithms·Potential maximal cliques·Treewidth·Vertex cover

Part of these results appeared in a preliminary version of this paper [17], in the proceedings of SWAT 2014. Partially supported by the ANR project GraphEn, ANR-15-CE40-0009.

B

Ioan Todinca

[email protected] Fedor V. Fomin

[email protected] Mathieu Liedloff

[email protected] Pedro Montealegre

[email protected]

1 Department of Informatics, University of Bergen, 5020 Bergen, Norway

2 Univ. Orléans, INSA Centre Val de Loire, LIFO EA 4022, BP 6759, 45067 Orléans Cedex 2, France

(2)

1 Introduction

Thevertex coverof a graphG, denoted by vc(G), is the minimum number of vertices that cover all edges of the graph. Themodular widthmw(G)of graphG =(V,E) is related to modular decompositions (see Sect.4and [30] for definitions). Amodule ofGis a set of verticesM ⊆V such that, for any vertexxoutside the module,xis either adjacent to all vertices ofM, or to none of them. Aprime graphis a graph that has only trivial modules (i.e., formed by a single vertex or the whole vertex set). The modular width ofGis the size of a largest prime induced subgraph ofG.

Minimal separatorsandpotential maximal cliquesare strongly related tominimal triangulationsof graphs. Atriangulationof an arbitrary graphG=(V,E)is a chordal supergraphH=(V,E), i.e., a supergraph on the same vertex set, having no induced cycles with strictly more than 3 vertices. We say thatHis aminimal triangulationis Ghas no triangulation strictly contained inH, as a subgraph. A set of verticesΩofG is called apotential maximal cliqueifΩinduces a maximal clique in some minimal triangulationH ofG.

The main results of this paper are of combinatorial nature: we show that the number of minimal separators and the number of potential maximal cliques of a graph are upper bounded by a single-exponential function in each of the parameters vertex cover and modular width. More specifically, we prove the number of minimal separators in a graphG is at most 3^vc⁽^G⁾ andO^∗(1.6181^mw⁽^G⁾), and the number of potential maximal cliques isO^∗(4^vc⁽^G⁾)andO^∗(1.7347^mw⁽^G⁾). Moreover, these objects can be listed within the same running time bounds. Recall that theO^∗ notation suppresses polynomial factors in the size of the input, i.e.,O^∗(f(k))should be read as f(k)· n^O(¹⁾wheren is the number of vertices of the input graph. Minimal separators and potential maximal cliques have been used for solving several classical optimization problems, e.g., Treewidth, Minimum Fill- In [16], Longest Induced Path, Feedback Vertex SetorIndependent Cycle Packing[18]. Pipelined with our combinatorial bounds, we obtain a series of algorithmic consequences in the area of FPT algorithms parameterized by the vertex cover and the modular width of the input graph. In particular, the problems mentioned above can be solved in timeO^∗(4^vc⁽^G⁾) andO^∗(1.7347^mw⁽^G⁾). These results are complementary in the sense that graphs with small vertex cover are sparse, while graphs with small modular width may be dense.

Vertex cover and modular width are strongly related to treewidth (tw) and cliquewidth (cw) parameters. It is an easy exercice to show that, since for any graphG, we have tw(G)≤vc(G)and cw(G)≤mw(G)+2; see [22] for more parameters and relations between them. The celebrated theorem of Courcelle [9] states that all problems expressible in Counting Monadic Second Order Logic (CMSO2) can be solved in time f(tw)·nfor some function f depending on the problem. A similar result for cliquewidth [11] shows that all CMSO1problems can be solved in time f(cw)·n, if the clique-decomposition is also given as part of the input (See the “Appendix 2’

for definitions of different types of logic. Informally, CMSO2allows logic formulae with quantifiers over vertices, edges, edge sets and vertex sets, and counting modulo constants. The CMSO1formulae are more restricted, we are not allowed to quantify over edge sets).

(3)

Typically function f is a tower of exponentials, and the height of the tower depends on the formula. Moreover Frick and Grohe [21] proved that this dependency on the treewidth/cliquewidth of the input graphGcannot be significantly improved in general.

Lampis [24] shows that the running time for CMSO2 problems can be improved 2²^O(vc(G))·nwhen parametrized by vertex cover, but he also shows that this cannot be improved toO^∗(2²^o⁽^vc⁽^G⁾⁾)(under the exponential time hypothesis). We are not aware of similar improvements for the modular width parameter, but we refer to [22] for discussions on problems parameterized by modular width.

Most of our algorithmic applications concern a restricted, though still large subset of CMSO2problems, but we guarantee algorithms that are single exponential in the vertex cover:O^∗(4^vc⁽^G⁾)and in the modular width:O^∗(1.7347^mw⁽^G⁾). We point out that our result for modular width extends the result of [18,19], who show a similar bound ofO^∗(1.7347ⁿ)for the number of potential maximal cliques and for the running times for these problems, but parameterized by the number of vertices of the input graph.

Maximum induced graph of bounded treewidth We use the following generic problem proposed by [18], that encompasses many classical optimization problems. Fix an integer t ≥ 0 and a CMSO2 formula ϕ. Consider the problem of finding, in the input graph G, an induced subgraph G[F] together with a vertex subset X ⊆ F, such that the treewidth ofG[F]is at mostt, the graphG[F]together with the vertex subsetXsatisfying formulaϕ, andXis of maximum size under these conditions. This optimization problem is calledMax Induced Subgraph oftw ≤t satisfiying ϕ:

Max |X|

subject to There is a setF⊆V such thatX ⊆F; The treewidth ofG[F]is at mostt; (G[F],X)|ϕ.

(1)

Note that our formulaϕ has a free variable corresponding to the vertex subsetX.

For several examples, in formulaϕthe vertex setX is actually equal toF. E.g., even whenϕ only states thatX = F, fort =0 we obtain theMaximum Independent set problem, and fort = 1 we obtain the Maximum Induced Forest(and in this caseV \F is an optimal solution forFeedback Vertex Set). Ift =1 and ϕ states that X = F andG[F]is a path we obtain theLongest Induced Path problem. Still under the assumption that X = F, we can express the problem of finding the largest induced subgraph G[F] excluding a fixed planar graph H as a minor, or the largest induced subgraph with no cycles of length 0 modl. ButXcan correspond to other parameters, e.g. we can choose the formulaϕsuch that|X|is the number of connected components ofG[F]. Based on this we can express problems likeIndependent Cycle Packing, where the goal is to find an induced subgraph with a maximum number of components, and such that each component induces a cycle.

By the result of [18],Max Induced Subgraph oftw ≤ t satisfiyingϕ is solvable in time # pmc·n^t⁺⁴·f(ϕ,t)where # pmc is the number of potential maximal

(4)

cliques of the graph, assuming that the set of all potential maximal cliques is also part of the input, and f is some function ofϕ andt only. Thanks to our combinatorial bounds, the problem Max Induced Subgraph oftw ≤ t satisfiyingϕ can be solved in timesO(4^vc⁽^G⁾n^t⁺^c)andO(1.7347^mw⁽^G⁾n^t⁺^c), for some small constantc.

Treewidth, treedepth and other parameters Several other graph problems can be solved in timeO^∗(# pmc)if the input graph is given together with the set of its potential maximal cliques. Examples of such problems areTreewidth,Minimum Fill- in [16], their weighted versions [3,23] and several problems related to phylogeny [23], or Treelength[26]. Pipelined with our main combinatorial result, we deduce that all these problems can be solved in timeO^∗(4^vc⁽^G⁾)orO^∗(1.7347^mw⁽^G⁾). Chapelle et al. [7] provided an algorithm solvingTreewidthandPathwidthinO^∗(3^vc⁽^G⁾), but those completely different techniques do not seem to work forMinimum Fill- inor Treelength. The interested reader may also refer., e.g., to [12,14] for more (layout) problems parameterized by vertex cover. The best known parameterized algorithm deciding whether a given n-vertex graph G is of treewidth at mostt runs in time O(t^t³n)[2]. The treewidth of a graph can be computed in timeO(1.7347ⁿ)[18].

Treedepth is a graph parameter that encountered a regain of interest in the area of sparse graphs, cf. the book of Nešetˇril and Ossona de Mendes [27]. Actually the parameter used to be known under different names, e.g.,vertex ranking[13]. A graph has treedepth (vertex ranking) at mosttif its vertices can be labeled from 1 tot, such that each path connecting vertices of the same labelicontains an internal vertex with a label greater thani. The parameter is NP-hard to compute, but one can decide if the treedepth of ann-vertex graph is at mostt in time 2^O(^t²⁾·n[28]. The treedepth can be also computed in timeO(1.9602ⁿ)[15].

Deogun et al. [13] provide polynomial algorithms computing the vertex ranking for several graph classes, using minimal separators. Based on their approach and new combinatorial bounds we show that the treedepth of a graph can also be computed in parameterized single-exponential time, when parameterized by the vertex cover or by the modular width of the input graph.

The paper is organized as follows. Section2introduces the preliminary results on minimal triangulations, minimal separators and potential maximal cliques. Section3 presents the combinatorial upper bounds on the number of minimal separators and potential maximal cliques, with respect to vertex cover. Section4 provides similar bounds, with respect to modular width. Applications of these results are presented in Sect.5. The results for treedepth do not rely directly on potential maximal cliques but on a different tool; they can be found in Sect.6. Conclusion section discusses further research directions.

2 Minimal Separators and potential maximal cliqueS

Let G = (V,E) be an undirected, simple graph. We denote by n its number of vertices and bymits number of edges. Theneighborhood of a vertexvis N(v)= {u∈V : {u, v} ∈E}. We say that a vertexx seesa vertex subsetS(or vice-versa) if N(x)intersectsS. For a vertex setS ⊆V we denote byN(S)the set

N(v)\S.

(5)

We writeN[S](resp.N[x]) forN(S)∪S(resp.N(x)∪ {x}). AlsoG[S]denotes the subgraph ofGinduced byS, andG−Sis the graphG[V \S].

Aconnected componentof graphGis the vertex set of a maximal induced connected subgraph ofG. Consider a vertex subset Sof graphG. Given two verticesuandv, we say thatSis au, v-separator ifuandvare in different connected components of G−S. Moreover, ifSis inclusion-minimal among allu, v-separators, we say thatS is aminimal u, v-separator. A vertex subsetSis called aminimal separatorofGifS is au, v-minimal separator for some pair of verticesuandv.

LetCbe a component ofG−S. IfN(C)=S, we say thatCis afull component associated toS.

Proposition 1 (folklore)A vertex subset S of G is a minimal separator if G−S has at least two full components associated to S. Moreover, S is a minimal x,y-separator if and only if x and y are in different full components associated to S.

A graphHischordalortriangulatedif every cycle with four or more vertices has a chord, i.e., an edge between two non-consecutive vertices of the cycle. Atriangulation of a graphG=(V,E)is a chordal graphH =(V,E)such thatE ⊆E. GraphHis aminimal triangulationofGif for every edge setEwithE ⊆E ⊂E, the graph F =(V,E)is not chordal.

A set of verticesΩ ⊆V of a graphGis called apotential maximal cliqueif there is a minimal triangulationHofGsuch thatΩ is a maximal clique ofH.

The following statement due to Bouchitté and Todinca [5] provides a characteriza- tion of potential maximal cliques, and in particular allows to test in polynomial time if a vertex subsetΩis a potential maximal clique ofG:

Proposition 2 ([5])LetΩ ⊆ V be a set of vertices of the graph G = (V,E)and {C1, . . . ,Cp}be the set of connected components of G −Ω. We denoteS(Ω) = {S1,S2, . . . ,Sp}, where Si = N(Ci)for all i ∈ {1, . . . ,p}. ThenΩ is a potential maximal clique of G if and only if

1. Each Si ∈S(Ω)is strictly contained inΩ;

2. The graph on the vertex setΩobtained from G[Ω]by completing each Si ∈S(Ω) into a clique is a complete graph.

Moreover, ifΩis a potential maximal clique, thenS(Ω)is the set of minimal separators of G contained inΩ.

Another way of stating the second condition is that for any pair of verticesu, v∈Ω, if they are not adjacent inGthen there is a componentCofG−Ωseeing bothxand y.

To illustrate Proposition 2, consider, e.g., the cube graph depicted in Fig.1. The setΩ1 = {a,e,g,c,h}is a potential maximal clique and the minimal separators contained inΩ1are{a,e,g,c}and{a,h,c}. Another potential maximal clique of the cube graph isΩ2= {a,c, f,h}containing the minimal separators{a,c, f},{a,c,h}, {a,f,h}and{c, f,h}.

Based on Propositions1and2, one can easily deduce:

(6)

Corollary 1 (see e.g., [5])There is an O(m)time algorithm testing if a given vertex subset S is a minimal separator of G, and O(nm)time algorithm testing if a given vertex subsetΩis a potential maximal clique of G.

We also need the following observation.

Proposition 3 ([5])LetΩ be a potential maximal clique of G and let S ⊂Ω be a minimal separator. ThenΩ\S is contained into a unique component C of G−S, and moreover C is a full component associated to S.

3 Relations to Vertex Cover

A vertex subsetW is avertex coverofGif each edge has at least one endpoint inW. Note that ifW is a vertex cover, thenV \W induces anindependent setinG, i.e., G−W contains no edges. We denote by vc(G)the size of a minimum vertex cover ofG. The parameter vc(G) is called thevertex cover numberor simply (by a slight abuse of language) thevertex cover ofG. After a long sequence of improvements, the current fastest parameterized algorithm for Vertex Coveris the algorithm of Chen, Kanj, and Xia, running in timeO(1.2738^vc⁽^G⁾+nvc(G))[8]. However, for our purposes even a weaker result will do the job.

Proposition 4 (folklore)There is an algorithm computing the vertex cover of the input graph G in timeO^∗(2^vc⁽^G⁾).

Let us show that any graphGhas at most 3^vc⁽^G⁾minimal separators.

Lemma 1 Let G=(V,E)be a graph, W be a vertex cover and S⊆V be a minimal separator of G. Consider a three-partition(D1,S,D2)of V such that both D1and D2are formed by a union of components of G−S, and both D1and D2contain some full component associated to S. Denote D^W₁ =D1∩W and D^W₂ =D2∩W .

Then S\W = {x∈V \W | N(x)intersects both D₁^W and D₂^W}.

Proof LetC1 ⊆ D1 andC2 ⊆ D2 be two full components associated to S. Let x∈ S\W. Vertexx must have neighbors both inC1andC2, hence both in D1and D2. Sincex∈/ W andW is a vertex cover, we haveN(x)⊆W. Consequentlyxhas neighbors both inD₁^W andD₂^W.

Conversely, letx ∈ V \W s.t.N(x)intersects both D^W₁ andD₂^W. We prove that x∈S. By contradiction, assume thatx∈/ S, thusxis in some componentCofG−S.

Suppose w.l.o.g. thatC⊆D1. SinceN(x)⊆C∪N(C), we must haveN(x)⊆D1∪S.

ThusN(x)cannot intersectD2—a contradiction.

Theorem 1 Any graph G has at most3^vc⁽^G⁾minimal separators. Moreover the set of its minimal separators can be listed inO^∗(3^vc⁽^G⁾)time.

Proof Let W be a minimum size vertex cover of G. For each three-partition (D₁^W,S^W,D₂^W)ofW, let S = S^W ∪ {x ∈ V \W | N(x)intersectsD₁^W andD₂^W}.

According to Lemma1, each minimal separator ofGwill be generated this way, by an

(7)

a b

d c

e f

h g

u v

... ... ...

Fig. 1 Cube graph (left) and watermelon graph (right)

appropriate partition(D₁^W,S^W,D₂^W)ofW. Thus the number of minimal separators is at most 3^vc⁽^G⁾, the number of three-partitions ofW.

These arguments can be easily turned into an enumeration algorithm, we simply need to compute an optimum vertex cover then test, for each setSgenerated from a three-partition, ifSis indeed a minimal separator. The former part takesO^∗(2^vc⁽^G⁾) time by Proposition 4, and the latter takes polynomial time for each set S using

Corollary1.

Observe that the bound of Theorem1is tight up to a constant factor. Indeed consider the watermelon graphWk,3formed bykdisjoint paths of three vertices plus two vertices uandvadjacent to the left, respectively right ends of the paths (see Fig.1). Note that this graph has vertex coverk+2 (the minimum vertex cover contains the middle of each path and verticesu andv) and it also has 3^kminimalu, v-separators, obtained by choosing arbitrarily one of the three vertices on each of thekpaths.

We now extend Theorem1 to a similar result on potential maximal cliques. Let us distinguish a particular family of potential maximal cliques, which haveactive separators. They have a particular structure which makes them easier to handle.

Definition 1 ([6]) LetΩ ⊆ V be a potential maximal clique of graphG =(V,E), let{C1, . . . ,Cp}be the set of connected components ofG−Ω and letSi =N(Ci), for 1≤i ≤ p.

Consider the graphG⁺obtained fromGby completing into a clique all minimal separatorsSj, 2≤ j ≤ p, such thatSj is not contained inS1.

We say thatS1is anactive separatorforΩ ifΩis not a clique in this graphG⁺. A pair of verticesx,y∈Ω that are not adjacent inG⁺is called anactive pair. Note that, by Proposition2, we must havex,y∈S1.

The following statement characterizes potential maximal cliques with active separators.

Proposition 5 LetΩbe a potential maximal clique having an active separator S⊂ Ω, with an active pair x,y∈S. Denote by C the unique component of G−S containing Ω\S. ThenΩ\S is a minimal x,y-separator in the graph G[C∪ {x,y}].

Again on the cube graph of Fig.1, for the potential maximal clique Ω1 = {a,e,g,c,h}, both minimal separators are active. E.g., for the minimal separator

(8)

x y

G

DS

Dx

Dy

S

C

Ω

W

x y

G

D^WS

D^Wx

D^Wy

S

C Ω

Fig. 2 Four-partition ofV(left) and a four-partition ofW(right)

S= {a,e,g,c}the pair{e,g}is active. Not all potential maximal cliques have active separators, as illustrated by the potential maximal cliqueΩ2= {a,c, f,h}of the same graph.

Let us first focus on potential maximal cliques having an active separator. We give a result similar to Lemma1, showing that such a potential maximal clique can be determined by a certain partition of the vertex coverW ofG.

Lemma 2 Let G = (V,E)be a graph and W be a vertex cover of G. Consider a potential maximal cliqueΩof G having an active separator S⊂Ωand an active pair x,y∈S. Let C be the unique connected component of G−S intersectingΩand let DSbe the union of all other connected components of G−S. Denote by Dxthe union of components of G−Ωcontained in C, seeing x, by Dythe union of components of G−Ω contained in C not seeing x.

Now let D_S^W =DS∩W , D_x^W =Dx ∩W and D^W_y =Dy∩W . Then one of the following holds:

1. There is a vertex t∈Ωsuch thatΩ\S=N(t)∩C.

2. There is a vertex t∈Ωsuch thatΩ =N[t]. 3. A vertex z∈/W is inΩ if and only if

(a) z sees D^W_S and D^W_x ∪D^W_y , or

(b) z does not see D^W_S but it sees D_x^W ∪ {x}, D_y^W ∪ {y}and D_x^W ∪D^W_y .

Proof Note thatDx,Dy,DSandΩform a partition of the vertex setV. This induces a four-partition of the vertex coverW (see Fig.2).

We first prove that any vertexz∈/W satisfying conditions 3a or 3b must be inΩ. Consider first the case 3a whenzseesD^W_S andD_x^W∪D^W_y . SozseesDSandC; we can apply Lemma1to partition(DS,S,C)thusz∈S. Consider now the case 3b when zseesD_x^W∪D^W_y ,Dx∪ {x}andDy∪ {y}but notD^W_S . Again by Lemma1applied to partition(DS,S,C), vertexzcannot be inS. Sincezhas a neighbor inDx∪Dy, we havez∈C. LetH=G[C∪ {x,y}]andT =Ω∩C(thus we also haveT =Ω\S).

Recall thatT is anx,y-minimal separator inHby Proposition5. By definition of set Dx, we have that Dx ∪ {x}is exactly the component of H−T containing x. Note that Dy∪ {y}is the union of the component of H−T containing yand of all other components ofH−T (that no not seexnory). By applying Lemma1on graphH,

(9)

with vertex cover(W ∩C)∪ {x,y}and with partition(Dx ∪ {x},T,Dy∪ {y})we deduce thatz∈T.

Conversely, letz∈Ω\W. We must prove that eitherzsatisfies conditions 3a or 3b, or we are in one of the first two cases of the Lemma. We distinguish the casesz∈ Sand z∈T. Whenz∈S, by Lemma1applied to partition(DS,S,C),zmust seeDSandC.

Ifzsees some vertex inC\Ω, we are done becausezseesD_x^W∪D^W_y so we are in case 3a. Assume now thatN(z)∩C ⊆Ω, we prove that actuallyN(z)∩C =Ω∩C =T, so we are in case 1. Assume there isu ∈ T \N(z). By Proposition 2, there must be a connected component DofG−Ω such thatz,u ∈ N(D). Sinceu ∈ C, this component Dmust be a subset ofC, so D⊆C\Ω. Together withz ∈ N(D), this contradicts the assumptionN(z)∩C ⊆Ω.

It remains to treat the casez∈T. Clearlyz∈Ccannot seeDSbecauseSseparates Cfrom DS. We again take graphH, with vertex cover(W ∩C)∪ {x,y}, and apply Lemma1with partition(Dx∪{x},T,Dy∪{y}). We deduce thatzsees bothD_x^W∪{x}

andD^W_y ∪ {y}. Assume thatzdoes not seeD^W_x ∪D^W_y . SoN(z)∩C\Ω = ∅thus N[z] ⊆Ω. IfΩcontains some vertexu∈/ N[z], no component ofG−Ωcan see both zandu (becauseN(z)⊆Ω), contradicting Proposition2. We conclude that eitherz sees D^W_x ∪D^W_y (so satisfies condition 3b) orΩ = N[z](thus we are in the second

case of the Lemma).

Theorem 2 Every graph G containsO^∗(4^vc⁽^G⁾)potential maximal cliques with active separators. Moreover the set of its potential maximal cliques with active separators can be listed inO^∗(4^vc⁽^G⁾)time.

Proof The number of potential maximal cliques with active separators satisfying the second condition of Lemma2is at mostn, and they can all be listed in polynomial time by checking, for each vertext, ifN[t]is a potential maximal clique.

For enumerating the potential maximal cliques with active separators satisfying the first condition of Lemma2, we enumerate all minimal separatorsSusing Theorem1;

there are at most 3^vc⁽^G⁾ such sets. Then, for eacht ∈ S and each of the at mostn componentsCofG−Swe check ifS∪(C∩N(t))is a potential maximal clique.

Recall that testing if a vertex set is a potential maximal clique can be done in polynomial time by Corollary1. Thus the whole process takesO^∗(3^vc⁽^G⁾)time, and this is also an upper bound on the number of listed objects.

It remains to enumerate the potential maximal cliques with active separators satisfying the third condition of Lemma2. For this purpose, we “guess” the sets D^W_S D_x^W,D_y^W as in the Lemma and then we computeΩ. More formally, we enumerate all four-partitions(D^W_S ,D_x^W,D^W_y , Ω^W)ofW; there are exactly 4^vc⁽^G⁾ such partitions.

For each of them we letΩ^W be the set of verticesz ∈/ W satisfying conditions 3a or 3b of Lemma 2, and we test using Corollary 1if Ω = Ω^W ∪Ω^W is indeed a potential maximal clique. If so, we store Ω in a list of potential maximal cliques.

By Lemma2, this enumerates all potential maximal cliques of this type. The running time isO^∗(4^vc⁽^G⁾)because for each four-partition (D^W_S ,D^W_x ,D^W_y , Ω^W)of W we performed a polynomial-time operation, computing the unique associated setΩ and

testing whether it is a potential maximal clique.

(10)

For counting and enumerating all potential maximal cliques of graphG=(V,E), including the ones with no active separators, we apply the same ideas as in [6], based on the following statement.

Proposition 6 ([6])Let G=(V,E)be a graph, let u be an arbitrary vertex of G and Ωbe a potential maximal clique of G. Denote by G−u the graph G[V \ {u}]. Then one of the following holds:

1. Ωhas an active minimal separator S.

2. Ωis a potential maximal clique of G−u.

3. Ω\ {u}is a potential maximal clique of G−u.

4. Ω\ {u}is a minimal separator of G.

Theorem 3 Any graph G hasO^∗(4^vc⁽^G⁾)potential maximal cliques. Moreover the set of its potential maximal cliques can be listed inO^∗(4^vc⁽^G⁾)time.

Proof Let(v1, . . . , vn)be an arbitrary ordering of the vertices ofV. Denote byGi

the graph G[{v1, . . . , vi}]induced by the firsti vertices, for alli,1 ≤ i ≤ n. Let k=vc(G). Note that for alliwe have vc(Gi)≤k. Actually, ifW is a vertex cover of G, thenWi =W∩{v1, . . . , vi}is a vertex cover ofGi. In particular, by Theorems1and 2, eachGi has at most 3^kminimal separators andO^∗(4^k)potential maximal cliques with active separators.

Fori =1, graphG1has a unique potential maximal clique equal to{v1}.

For each i from 2 ton, in increasing order, we compute the potential maximal cliques ofGi from those ofGi−1using Proposition6. Observe thatGi−1=Gi−vi. We initialize the set of potential maximal cliques ofGi with the ones having active separators. This can be done inO^∗(4^k)time by Theorem2. Then for each minimal separator S of Gi we check if Ω = S∪ {vi}is a potential maximal clique ofGi

and if so we add it to the set. This takesO^∗(3^k)time by Theorem1and Corollary1.

Eventually, for each potential maximal cliqueΩofGi−1, we test using Corollary1 ifΩ(resp.Ω∪ {vi}) is a potential maximal clique ofGi. If so, we add it to the set of potential maximal cliques ofGi. The running time of this last part is the number of potential maximal cliques ofGi−1timesnm. Altogether, it takesO^∗(4^k)time.

By Proposition6, this algorithm covers alls cases and thus lists all potential maximal cliques ofGi. Hence fori=nwe obtain all potential maximal cliques ofG, and they

have been enumerated inO^∗(4^k)time.

4 Relations to Modular Width

A module of graph G = (V,E)is a set of vertices W such that, for any vertex x∈ V \W, eitherW ⊆ N(x)orW does not intersect N(x). For the reader familiar with the modular decompositions of graphs, the modular width mw(G)of a graphG is the maximum size of a prime node in the modular decomposition tree. Equivalently, graphGis of modular width at mostkif:

1. Ghas at most one vertex (the base case).

2. Gis a disjoint union of graphs of modular width at mostk.

(11)

3. Gis ajoinof graphs of modular width at mostk. I.e.,Gis obtained from a family of disjoint graphs of modular width at mostkby taking the disjoint union and then adding all possible edges between these graphs.

4. The vertex set ofGcan be partitioned into p ≤kmodulesV1, . . . ,Vpsuch that G[Vi]is of modular width at mostk, for alli,1≤i ≤ p.

The modular width of a graph can be computed in linear time, using e.g. [30]. Moreover, this algorithm outputs the algebraic expression ofG corresponding to the grammar above. The canonical way of defining such an expression is themodular decomposition treeof graphG, which is a rooted tree with labeled nodes of different types (see [30]

for full details). IfGhas a unique vertex (first item above), the tree is reduced to a single node, of typeleaf, labeled with the vertex itself. IfGis not connected (second item), letC1, . . . ,Cpbe the connected components ofG. The modular decomposition ofGis obtained by taking a root node of typedisjoint union, whose sons are the roots of the modular decompositions ofG[C1], . . . ,G[Cp]. IfG(the complement of graph G) is not connected, then we are in the case of the third item. Let C1, . . . ,Cp be the connected components ofG. The modular decomposition ofGis obtained with a root node of typejoin, whose sons are the roots of the modular decompositions of G[C1], . . . ,G[Cp]. When bothGandGare connected (fourth item), there is a unique partition(V1, . . . ,Vp)of its vertex setV into maximal modules strictly contained in V. The modular decomposition ofGhas a root node of typeprime, whose sons are the roots of the modular decompositions ofG[V1], . . . ,G[Vp], in this order. The root is labeled with a graphG[{v1, . . . , vp}]obtained by choosing a vertexvi in eachVi

(observe that any such choice produces isomorphic labels). This label is a prime graph (hence the type of the root node). Equivalently, graphGhas modular width at mostk if all the prime nodes of its modular decomposition have at mostksons.

Let G = (V,E) be a graph with vertex set V = {v1, . . . , vk}and let Mi = (Vi,Ei)be a family of pairwise disjoint graphs, for all i, 1 ≤ i ≤ k. Denote by H the graph obtained from G by replacing each vertexvi by the module Mi. I.e., H =(V1∪ · · · ∪Vk,E1∪ · · · ∪Ek∪ {ab|a ∈ Vi,b∈ Vjs.t.vivj ∈ E}). We say that graphH has been obtained fromGbyexpandingeach vertexvi by the module Mi.

A vertex subsetWofHis anexpansionof vertex subsetWGofGifW = ∪vi∈W_GVi. Given a vertex subsetW of H, thecontractionofW is{vi |Vi intersectsW}. Lemma 3 Let S be a minimal y,z-separator of H , for y,z ∈ Vi. Then S∩Vi is a minimal separator of Mi and S\Vi =NH(Vi).

Proof Note that all vertices of NH(Vi)are in NH(y)∩NH(z), by construction of graphHand the fact thatyandzare in the same moduleVi. ThereforeNH(Vi)must be contained inS. LetSi =S∩Vi. SinceH[Vi] =Mi, we have thatSiseparateszand yin graphMi. Assume thatSi is not a minimaly,z-separator ofMi, so letS_iSibe a minimaly,z-separator in graphMi. We claim thatS_i∪NH(Vi)is ay,z-separator inH. Indeed eachy,z-path ofHis either contained inVi (in which case it intersects S_i) or intersectsNH(Vi). In both cases, it passes throughS_i∪NH(Vi), which proves the claim. SinceS_i∪NH(Vi)is a subset ofSandSis ay,z-minimal separator ofH, the only possibility is that S = S_i∪NH(Vi). This proves thatS ∩Vi is a minimal

separator ofMi andS\Vi =NH(Vi).

(12)

Lemma 4 Let S be a minimal separator of H . Assume that some Viintersects S, but is not contained in S. Then Vi intersects all full components of H −S associated to S. In particular S∩Viis a minimal separator in Mi and S\Vi =NH(Vi).

Proof Let(x,t)be a pair of vertices withx∈Vi∩Sandt ∈Vi\S. By Proposition1, there are at least two full components ofH−S, associated toS. LetCbe one of them, not containingt. Letzbe a neighbor ofxinC, we prove thatz∈Vi. Ifz∈/ Vi, then z∈ NH(Vi), and sinceViis a module inHwe also havez∈NH(t). This contradicts the fact thatt andz are in different components ofH −S. It follows thatz ∈ Vi. By applying the same arguments to the pair(x,z)instead of(x,t), it follows thatVi

intersects each full componentDofH−Sand moreoverxhas a neighbor inD∩Vi. By Proposition1,Sis a minimaly,z-separator inH, for somey,z∈NH(x)∩Vi.

The rest follows by Lemma3.

Lemma 5 Let S be a minimal separator of H . Then one of the following holds 1. S is the expansion of a minimal separator SGof G.

2. There is i ∈ {1, . . . ,k}such that S∩Viis a minimal separator of Miand S\Vi = NH(Vi).

Proof Assume there is a setVi intersectingS but not contained in it. By Lemma4, S∩Vi is a minimal separator ofMi andS\Vi =NH(Vi). Hence we are in the second case of the Lemma.

Otherwise, for anyVi intersectingS, we haveVi ⊆S. ThusSis the expansion of a vertex subsetSG ofG, formed exactly by the verticesvi ofGsuch thatVi intersects S. LetC and Dbe two full components of H −S associated to S and leta ∈ C, b∈ D. Recall that, by Proposition1,Sis a minimala,b-separator ofH. LetVkbe the set containingaandVl the set containingb. Consider first the possibility thatk=l.

Then, by Lemma3,Ssatisfies the second condition of this lemma, fori=k=l(This case may occur whenMkis disconnected andS =NH(Vk)).

Finally, we consider the casek=l. We prove thatSGis a minimalvk, vl-separator ofG. Consider avk, vlpath ofG. If this path does not intersectSGinG, then there is a path fromatobinH−S, obtained by replacing each vertexvjof the path by some vertex ofVj (vk andvl are replaced bya andbrespectively). This would contradict the fact that S separatesa andb inH. Therefore SG is indeed avk, vl-separator in G. Assume thatSGis not minimal among thevk, vl-separators ofG, and letvj ∈SG

such that SG \ {vj}separatesvk andvl inG. We claim that S\Vj also separatesa frombinH. By contradiction, assume there is a path froma ∈C∩Vktob∈ D∩Vl

inH, avoidingS\Vj. By contracting, on this path, all vertices belonging to a same Vi into vertexvi, we obtain a path (or a connected subgraph) joiningvk tovl inG.

This contradicts the fact that all such paths should intersectSG\ {vj}. ThereforeSG

is a minimal separator ofG.

Lemma5provides an injective mapping from the set of minimal separators ofH to the union of the sets of minimal separators ofG and of the graphsMi. Therefore we have:

Corollary 2 The number of minimal separators of H is at most the number of minimal separators of G plus the number of minimal separators of each M.

(13)

We now aim to prove a statement equivalent of Corollary2, for potential maximal cliques instead of minimal separators.

Lemma 6 Let Ω be a potential maximal clique of H , and let ΩG = {vi | Vi intersectsΩ}. Assume thatΩ is the expansion ofΩG, i.e.Ω = ∪_vi∈ΩGVi. Then ΩGis a potential maximal clique of G.

Proof We prove thatΩGsatisfies, in graphG, the conditions of Proposition2. For the first condition, letCG be a component ofG−ΩG and letSG = NG(CG). Assume that SG is not strictly contained inΩG, hence SG = ΩG. LetC be the expansion ofCG in H and note that NH(C)is the expansion of NG(CG), thus NH(C)= Ω.

IfCG is formed by at least two vertices, sinceG[CG]is connected then so is H[C].

Therefore, in graph H, we haveNH(C)=ΩandCis a component ofH−Ω. But this contradicts the first condition of Proposition2applied to the potential maximal cliqueΩ of H. In the case thatCG is formed by a unique vertexvk, its expansion C =Vk might not induce a connected subset inH (ifMk is disconnected). But it is sufficient to consider a connected component V_k of H[Vk], and again this is also a component of H−Ω with the property that its neighborhood inH is the whole set Ω, contradicting Proposition2applied toΩ.

For the second condition of Proposition2, letvj, vk ∈ ΩG such thatvjvk is not an edge ofG. Let a ∈ Vj andb ∈ Vk. These vertices are non-adjacent in H, so by Proposition 2 applied to the potential maximal cliqueΩ of H there must be a componentCofH−Ωseeing bothaandb. Consider ana,b-path inH[C∪ {a,b}].

The contraction of this path contains avj, vk-path inG, whose internal vertices are not inΩG. This proves thatvj andvk are in the neighborhood of a same component ofG−ΩG, thusΩGsatisfies the second condition of Proposition2.

Lemma 7 LetΩbe a potential maximal clique of H , and assume that there is some set Vithat intersectsΩbut is not contained inΩ. ThenΩ∩Viis a potential maximal clique of Mi andΩ\Vi =NH(Vi).

Proof LetVibe a vertex set that intersectsΩ, but is not contained inΩ. We distinguish two cases.

Case 1There is a minimal separatorS ⊆Ω ofH, such thatSintersectsVi. By Lemma4,S∩Viis a minimal separator ofMi andViintersects all full components ofH−Sassociated toS. LetCbe the unique component ofH−Sintersecting Ω; recall that it exists and moreover it is full w.r.t. S, by Proposition 3. Then, by Lemma4,C also intersectsVi. Also by Lemma4,S\Vi =NH(Vi). We claim that actuallyC⊆ViandCis also a full component ofMi−Si. Recall thatS\Vi =NH(Vi) separates in graphH the vertices ofVifrom the rest of the graph. SinceC intersects Vi,H[C]is connected andNH(Vi)separatesVifrom all other vertices, we must have C ⊆Vi. SinceH[C]is connected, so isMi[C], thusC is contained in some component ofMi−Si. But each such component is also a component ofH−S, henceCis both a component ofH−Sand ofMi−Si. In particularΩ∩C⊆Vi.

It remains to prove thatΩi =Ω∩Vi is a potential maximal clique ofMi. By the above observations, we also haveΩi =Ω\ NH(Vi). We show thatΩi satisfies, in graphMi, the conditions of Proposition2. LetDbe a component ofMi−Ωi. Observe

(14)

thatDis also a component ofH−Ωand letT =NM_i(D). EitherDis a component of Mi−Ωidisjoint fromC, or it is contained inC. In the former case,Tis a subset ofSi, henceT is a strict subset ofΩi(sinceSiis itself a strict subset ofΩiby Proposition2 applied to potential maximal cliqueΩof H). In the latter case, ifT =Ωi, note that NH(D)=ΩbecauseΩ\Vi =NH(Vi)is also contained in the neighborhood ofD inH. This contradicts Proposition2applied to potential maximal cliqueΩ ofH.

For the second condition, letx,y∈Ωi, non-adjacent inMi. Then there is a com- ponentFofH−Ωseeing, in graphH, bothxandy(by Proposition2applied toΩ).

Since this component seesVi, it must be contained in Vi. SoF is also a component ofMi−Ωi seeing bothxandyinMi, which concludes our proof for this case.

Case 2There is no minimal separatorS⊆ΩofH, intersectingVi.

Let us prove that, in this case, for any x ∈ Ωi we have that Ω = NH[x]. By Proposition3, ifxhas a neighbor outsideΩ, hence in some componentDofH−Ω, thenNH(D)is a minimal separator ofHcontainingx— a contradiction. Therefore NH[x] ⊆Ω. If there isy∈Ω\NH[x], then by the same proposition,xandymust see a same component ofH−Ω, contradicting the fact thatNH(x)⊆Ω. We deduce thatΩ =NH[x].

Since this holds for each vertex ofΩi, we have thatΩi is a clique in H (thus in Mi), and the vertices ofΩi cannot have neighbors inVi\Ωi. ThereforeΩiis a clique and a connected component ofMi. By Proposition3, it is a potential maximal clique ofMi. The fact thatΩ=NH[x]also implies thatΩ\Vi =NH(Vi), which concludes

our proof.

From Lemmata6and7, we directly deduce:

Lemma 8 LetΩbe a potential maximal clique of H . One of the following holds 1. Ωis the expansion of a potential maximal cliqueΩGof G.

2. There is some i∈ {1, . . . ,k}such thatΩ∩Vi is a potential maximal clique of Mi

andΩ\Vi =NH(Vi).

The previous lemma provides an injective mapping from the set of potential maximal cliques ofHto the union of the sets of potential maximal cliques ofGand of the graphsMi. Therefore we have:

Corollary 3 The number of potential maximal cliques of H is at most the number of potential maximal cliques of G plus the number of potential maximal cliques of each Mi.

The following proposition bounds the number of minimal separators and potential maximal cliques of arbitrary graphs with respect ton.

Proposition 7 ([19,20])Every n-vertex graph hasO(ρⁿ)minimal separators, where ρ <1.6181is the golden ratio, andO(1.7347ⁿ)potential maximal cliques. Moreover, these objects can be enumerated within the same running times.

We can now prove the main result of this section.

Theorem 4 For any graph G=(V,E), the number of its minimal separators isO(n· ρ^mw⁽^G⁾)whereρ <1.6181is the golden ratio. The number of its potential maximal

(15)

cliques isO(n·1.7347^mw⁽^G⁾). Moreover, the minimal separators and the potential maximal cliques can be enumerated in timeO^∗(1.6181^mw⁽^G⁾)andO^∗(1.7347^mw⁽^G⁾) time respectively.

Proof Letk =mw(G). By definition of modular width, there is a modular decomposition tree of graphG, each node corresponding to a leaf, a disjoint union, a join or a decomposition into at mostkmodules. The leaves of the decomposition tree are disjoint graphs with a single vertex, thus these vertices form a partition ofV. In particular, there are at mostnleaves and, since each internal node is of degree at least two, there areO(n)nodes in the decomposition tree. For each nodeNode, letG(Node)be the graph associated to the subtree rooted atNode. I.e.,G(Node)is the graph whose modular decomposition is the subtree rooted atNode; it is also subgraph ofGinduced by the vertices ofGmapped on leaves of the subtree rooted atNode. We prove that G(Node)hasO(n(Node)·ρ^k)minimal separators andO(n(Node)·1.7347^k)potential maximal clique, wheren(Node)is the number of nodes of the subtree rooted atNode.

We proceed by induction from bottom to top. The statement is clear whenNodeis a leaf.

LetNodebe an internal nodeNode1,Node2, . . . ,Nodepbe its children in the tree.

GraphG(Node)is the expansion of some graphG(Node)by replacing thei-th vertex with module G(Nodei). If Nodeis a join node, then G(Node)is a clique. When Nodeis adisjoint unionnode, graphG(Node)is an independent set, and in the last caseG(Node)is a graph of at mostkvertices. In all cases, by Proposition7graph G(Node)has O(ρ^k)minimal separators. Thus G(Node)has at mostO(ρ^k)more minimal separators than all graphsG(Nodei)taken together, which completes our proof for minimal separators.

Concerning potential maximal cliques, whenG(Node)is a clique it has exactly one potential maximal clique, and whenG(Node)is of size at mostkis hasO(1.7347^k) potential maximal cliques. We must be more careful in the case whenG(Node)is an independent set (i.e., Nodeis a disjoint union node), since in this case it has p potential maximal cliques, one for each vertex, and pcan be as large asn. Consider a potential maximal cliqueΩofG(Node)corresponding to an expansion of vertices ofG(Node)(see Lemma8). It follows that this potential maximal clique is exactly the vertex set of some G(Nodei), for a childNodei of Node. By construction this vertex set is disconnected from the rest ofG(Node), and by Proposition2the only possibility is that this vertex set induces a clique inG(Node). But in this caseΩ is also a potential maximal clique ofG(Nodei). This proves that, whenNodeis of type disjoint union,G(Node)has no more potential maximal cliques than the sum of the numbers of potential maximal cliques of allG(Nodei), 1≤i ≤ p. We conclude that the whole graphGhasO(n·1.7347^k)potential maximal cliques. All our arguments are constructive and can be turned directly into enumeration algorithms for these objects.

5 Applications

Thetreewidthof graphG=(V,E), denoted tw(G), is the minimum numberksuch thatGhas a triangulationH =(V,E)of clique size at mostk+1. Theminimum fill-in