On the tractability of optimization problems on
H-graphs∗

arXiv:1709.09737v2 [cs.DS] 16 Feb 2018

Fedor V. Fomin†

Petr A. Golovach†

Jean-Florent Raymond‡

Abstract
For a graph H, a graph G is an H-graph if it is an intersection graph of connected
subgraphs of some subdivision of H. H-graphs naturally generalize several important
graph classes like interval graphs or circular-arc graph. This class was introduced in
the early 1990s by Bı́ró, Hujter, and Tuza. Recently, Chaplick et al. initiated the
algorithmic study of H-graphs by showing that a number of fundamental optimization
problems like Maximum Clique, Maximum Independent Set, or Minimum Dominating Set are solvable in polynomial time on H-graphs. We extend and complement
these algorithmic findings in several directions.
First we show that for every fixed H, the class of H-graphs is of logarithmicallybounded boolean-width. Pipelined with the plethora of known algorithms on graphs of
bounded boolean-width, this describes a large class of problems solvable in polynomial
time on H-graphs. We also observe that H-graphs are graphs with polynomially many
minimal separators. Combined with the work of Fomin, Todinca and Villanger on
algorithmic properties of such classes of graphs, this identify another wide class of
problems solvable in polynomial time on H-graphs.
The most fundamental optimization problems among the problems solvable in polynomial time on H-graphs are Maximum Clique, Maximum Independent Set, and
Minimum Dominating Set. We provide a more refined complexity analysis of these
problems from the perspective of parameterized complexity. We show that Maximum
Independent Set and Minimum Dominating Set are W[1]-hard being parameterized by the size of H plus the size of the solution. On the other hand, we prove that
when H is a tree, then Minimum Dominating Set is fixed-parameter tractable (FPT)
parameterized by the size of H.
For Maximum Clique we show that it admits a polynomial kernel parameterized
by H and the solution size.
∗

Emails of authors: {fedor.fomin, petr.golovach}@ii.uib.no, raymond@tu-berlin.de.
The
third author has been supported by the Polish National Science Centre grant PRELUDIUM DEC2013/11/N/ST6/02706 and by the European Research Council (ERC) under the European Union’s Horizon
2020 research and innovation programme, ERC consolidator grant DISTRUCT, agreement No 648527.
†
Department of Informatics, University of Bergen, Norway.
‡
Technische Universität Berlin, Germany.

1

1

Introduction

The notion of H-graph was introduced in the work of Bı́ró, Hujter, and Tuza [BHT92] on
precoloring extensions of graphs. H-graphs nicely generalize several popular and widely
studied classes of graphs. For example, the classical definition of an interval graph is as a
graph which is an intersection graph of intervals of a line. Equivalently, a graph is interval if
it is an intersection graph of some subpaths of a path. Or, equivalently, if it is an intersection
graph of some subgraphs of some subdivision (which is a graph obtained by placing vertices
of degree 2 on the edges) of P2 , the graph with two adjacent vertices. Similarly, every chordal
graph is an intersection graph of subtrees of some tree. More generally, for a fixed graph H,
a graph G is an H-graph if it is an intersection graph of some connected subgraphs of some
subdivision of H. Thus for example, an interval graph is a P2 -graph, a circular-arc graph is
a C2 -graph, where C2 is a double-edge with two endpoints, a split graph is a K1,d -graph for
some d ≥ 0, where K1,d is a star with d leaves, etc..
The main motivation behind the study of H-graphs is the following. It is well-known
that on interval, chordal, circular-arc, and other graphs with “simple” intersection models
many NP-hard optimization problems are solvable in polynomial time, see e.g. the book
of Golumbic [Gol04] for an overview. It is a natural question whether at least some of
these algorithmic results can be extended to more general classes of intersection graphs.
Chaplick et al. [CTVZ17] and Chaplick and Zeman [CZ17] initiated the systematic study of
algorithmic properties of H-graphs. They showed that a number of fundamental optimization
problems like Maximum Independent Set and Minimum Dominating Set are solvable
in polynomial time on H-graphs for any fixed H. Most of the algorithms developed on
H-graphs in [CTVZ17, CZ17] run in time nf (H) , where n is the number of vertices in the
input graph and f is some function. In other words, being parameterized by H most of the
problems are known to be in the class XP.
Our work is driven by the following question.
• Are there generic explanations why many problems admit polynomial time algorithms
on H-graphs?
We address the first question by proving the following combinatorial results. We show
first that every n-vertex H-graph has boolean-width at most 2|E(H)| · log n. Moreover,
a decomposition of boolean-width 2|E(H)| · log n can be found in polynomial time. This
combinatorial result extends the results of Belmonte and Vatshelle [BV13, BV10] on the
boolean-width of interval (resp. circular-arc) graphs to H-graphs. Together with the algorithms for a vast class of problems called LC-VSP problems [BXTV11, BV13], which are
solvable on n-vertex graphs of boolean-width b in time 2b nO(1) , this implies immediately
that all these problems are solvable in polynomial time on H-graphs. The illustrative problems solvable in polynomial time on H-graphs by making use of this approach are Maximum
Weight Independent Set, Minimum Weight Dominating Set, Total Dominating
Set, Induced Matching, and many others. We also obtain polynomial-time algorithms
for problems related to induced paths such as Longest Induced Path and Disjoint
Induced Paths using the results of Jaffke, Kwon, and Telle [JKT17b].
2

Then we prove that every n-vertex H-graph has at most (2n + 1)|E(H)| + |E(H)| · (2n)2
minimal separators.1 Pipelining the bound on the number of minimal separators in H-graphs
with meta-algorithmic results of Fomin, Todinca and Villanger [FTV15], we obtained another
wide class of problems solvable in polynomial time on H-graphs. Examples of such problems
are Treewidth, Minimum Feedback Vertex Set, Maximum Induced Subgraph
excluding a planar minor, and various packing problems.
All these generic algorithmic results provide XP algorithms when parameterized by the
size of H. This brings us immediately to the second question defining the direction of our
research.
• What is the parameterized complexity of the fundamental optimization problems being
parameterized by the size of H?
The first steps in this direction were done by Chaplick et al. in [CTVZ17] who showed
that Minimum Dominating Set is fixed-parameter tractable (FPT) on K1,d -graphs parameterized by d. In this paper we show that Minimum Dominating Set is W[1]-hard
parameterized by H and the size of the solution. Thus the existence of an FPT algorithm for
a general graph H is very unlikely. (We refer to books [DF13, CFK+ 15] for definitions from
parameterized complexity and algorithms.) We also prove a similar lower bound for Maximum Independent Set parameterized by the size of H plus the solution size. Combined
with our combinatorial results, these lower-bounds show that Maximum Independent Set
and Minimum Dominating Set are also W[1]-hard when parameterized by mim-width (a
graph parameter to be defined in the corresponding section) of the input and the solution
size. On the positive side, we show that when H is a tree, then Minimum Dominating Set
is FPT parameterized by the size of H. This significantly extends the result from [CTVZ17]
for stars to arbitrary trees. We actually prove a slightly more general result, namely that
Minimum Dominating Set is FPT on chordal graphs G parameterized by the leafage of
the graph, i.e. the minimum number of leaves in the clique tree of G.
Finally we show that Clique admits a polynomial kernel when parameterized by the size
of H plus the solution size. This strengthens the result of Chaplick and Zeman who showed
that Clique is FPT for such a parameterization. Our algorithmic results about H-graphs
are summarized in Table 1.
Organization of the paper. Section 2 contains the necessary definitions. In Section 3,
we upper-bound the boolean-width of H-graphs and provide algorithmic applications. Section 4 is devoted to the study of minimal separators in H-graphs, again with algorithmic
consequences. Last, Section 5 contains our results on the parameterized complexity of some
classic optimization problems on H-graphs.
1

It was reported to us by Steven Chaplick and Peter Zeman that they also obtained this result independently and that it will be included in the journal version of their paper.

3

Problem
any LC-VSP-problem
Induced path problems
OIS(P, t), P is CMSOL

Parameters
kHk
kHk
kHk
none

Dominating Set

kHk

Independent Set

kHk + k
none
kHk
kHk + k
none
kHk

Restrictions
none
none
none
H is a tree
H is a star
H is a tree
none
none
H is a tree
none
none
H is a tree
none

kHk + k

none

Clique

Repr. Complexity
Y
XP
Y
XP
N
XP
N
NP-hard
N
FPT
N
FPT
Y
XP
Y
W[1]-hard
N
polynomial
Y
XP
Y
W[1]-hard
N
polynomial
Y
para-NP-hard
N
FPT
Y
poly. kernel

Ref.
Theorem 4
Theorem 5
Corollary 3
[BJ82]
[CTVZ17]
Theorem 9
[CTVZ17]
Theorem 8
[Gav72]
[CTVZ17]
Theorem 8
[Gav72]
[CZ17]
[CZ17]
Theorem 10

Table 1: Summary of algorithmic results on H-graphs, including the classic results on chordal
graphs (H is a tree). The fourth column indicates whether a representation of the input as
an H-graph is given. For each of the mentioned problems, k denotes the solution size. See
Sections 3 and 4, for details about the three first problem.

2

Definitions

Basics. All graphs in this paper are finite, undirected, loopless, and may have multiple
edges. If G is a graph, we respectively denote by |G| and kGk its numbers of vertices and
edges (counting multiplicities). For every graph G, we denote by ω(G) the largest order
of a complete subgraph of G. If X, Y ⊆ V (G), X is the complement of X in V (G) (i.e.
X = V (G) \ X), G[X] is the subgraph of G induced by the vertices of X, and G[X, Y ] is the
bipartite subgraph of G induced by those edges that have one endpoint in X and the other
in Y . Unless otherwise specified, logarithms are binary.
H-graphs. Let H be a (multi) graph. We say that a graph G is an H-graph if there
is a subdivision H 0 of H and a collection M = {Mv }v∈V (G) (called an H-representation
or, simply, representation) of subsets of V (H 0 ), each inducing a connected subgraph, such
that G is isomorphic to the intersection graph of M. To avoid confusion, we refer to the
vertices of H 0 as nodes. We also say that the nodes of H are branching nodes of H 0 and the
other nodes are subdivision nodes. If v is a vertex of G, then Mv is the model of v in the
representation M.
S
For every set A ⊆ V (G), we define MA = v∈A Mv . For every node u of H 0 , we denote
by Vu the set of vertices of G whose model contains u, that is,
Vu = {v ∈ V (G), u ∈ Mv }.
4

For a nonempty U ⊆ V (H), we say that v ∈ V (G) is a U -vertex if Mv ∩ V (H) = U .
If U = {u}, we write u-vertex instead of {u}-vertex. We denote the set of U -vertices by
VG (U ) and VG (u) if U = {u}. For e ∈ E(H), we say that v ∈ V (G) is an e-vertex if Mv
contains only subdivision nodes of H 0 from the path in H 0 corresponding to e in H. The set
of e-vertices is denoted by VG (e).

3

H-graphs have logarithmic boolean-width

Boolean-width is a graph invariant that has been introduced in [BXTV11] and which is
related to the number of different neighborhoods along a cut. Belmonte and Vatshelle showed
in [BV13] that n-vertex interval graphs and circular-arc graphs have boolean-width O(log n).
In this section, we generalize their result by proving that, for any fixed graph H, n-vertex Hgraphs have boolean-width O(log n). Using the results of [BXTV13], we obtain polynomial
algorithms for a vast class of optimization problems on H-graphs. Before we proceed with
the proofs, we need to introduce some notions specific to this section.
Definition 1 (Graph decompositions). A tree decomposition of a graph G is a pair (T, δ)
where T is a full binary rooted tree (that is, every non-leaf vertex has degree 3) and δ is a
bijection from the leaves of T to the vertices of G. A tree decomposition (T, δ) is a caterpillar
decomposition if T can be obtained from a path by adding a vertex of degree one adjacent to
every internal vertex. If w ∈ V (T ), let us denote by Vw the set of vertices of G in bijection
with the leaves of the subtree of T rooted at w.
Definition 2 (Maximum induced matching over a cut). A set of vertices of a graph G is
an induced matching if it induces a disjoint union of edges. If X ⊆ V (G), we denote by
mim(X) the maximum number of edges in an induced matching of G[X, X]. If (T, δ) is a
tree decomposition of G, we denote by mim(T, δ) the maximum of mim(Vw ) taken over all
w ∈ V (T ).
Definition 3 (Neighborhood equivalence). Let G be a graph, let d ∈ N and and let A ⊆
V (G). We say that two subsets X, Y ⊆ A are d-neighborhood equivalent, denoted by X ≡dA Y ,
if for every v ∈ A, we have
min(d, |X ∩ N (v)|) = min(d, |Y ∩ N (v)|).
We write necd (A) for the number of equivalence classes of the relation ≡dA . If (T, δ) is a tree
decomposition of G, we denote by necd (T, δ) the maximum of necd (Vw ) and necd (Vw ) over
all w ∈ V (T ).
The following lemma relates maximum induced matchings to neighborhood equivalence.
Lemma 1 ( [BV13, Lemma 1 and Lemma 2]). For every n-vertex graph G and A ⊆ V (G),
(i) mim(A) ≤ k iff for every S ⊆ A there is a R ⊆ S s.t. R ≡1A S and |R| ≤ k;
5

(ii) necd (A) ≤ nd·mim(A) .
Definition 4 (Boolean-width). If (T, δ) is a tree decomposition of a graph G, the booleanwidth of (T, δ), that we write boolw(T, δ), is defined as the maximum of log(nec(≡1Vw )) over
all w ∈ V (T ). The boolean-width of G, denoted by boolw(G), is the minimum boolean-width
of a tree decomposition of G.
Our results on the boolean-width of H-graphs follow from the next result.
Theorem 1. Let H be a graph. For every H-graph G on n vertices whose intersection
model is given, we can compute in polynomial time a caterpillar decomposition (T, δ) with
mim(T, δ) ≤ 2kHk.
Proof. Let F be the subdivision of H in which G can be realized and let {Mv }v∈V (G) be the
intersection model of G. Let us arbitrarily fix a branching node r of F . Let v1 , . . . , vn be an
ordering of V (G) by non-decreasing distance of Mvi ’s to r.
Claim 1. For every prefix A of v1 , . . . , vn and every S ⊆ A, there is a set R ⊆ S of size at
most 2kHk such that N (R) ∩ A = N (S) ∩ A.
S
Proof. Let A be a prefix of v1 , . . . , vn and let S ⊆ A. Let MA = v∈A Mv and similarly
for MA and MS . Let us consider the path Pe corresponding to some edge e ∈ E(H). Let
x1 , . . . , xp be the vertices of Pe in the same order.
Let v ∈ A and notice that since, by definition, G[Mv ] is connected, the vertex set Mv ∩
V (Pe ) induces at most two connected components in Pe . Indeed if Mv ∩ V (Pe ) induced more
than two connected components, then one of them would not contains any endpoint of Pe ,
and thus would not be connected to other vertices of Mv in G[Mv ]. Let us assume that it
induces at least one connected component and let xi and xj be the first and last vertices
(wrt. the ordering x1 , . . . , xp ) of this component. If {x1 , . . . , xi−1 } is disjoint from MA , we
say that v is a left-protector of Pe . If j is maximum among all vertices that protects the
left of Pe , then v is a rightmost left-protector. (Informally, it extends the most to the right.)
Similarly, v is a right-protector the right of Pe if {xj+1 , . . . , xp } is disjoint from MA and is a
leftmost right-protector if i is minimal.
Let Ze be a set containing one (arbitrarily chosen)
S rightmost left-protector and one
leftmost right-protector of e if some exist, and let R = e∈E(H) Ze . Clearly |R| ≤ 2kHk. Let
us now show that N (S) ∩ A ⊆ N (R) ∩ A. We consider a vertex u ∈ N (S) ∩ A and we show
that it also belongs to N (R). Let v be a neighbor of u in S. As u and v are adjacent, Mu
and Mv have non-empty intersection. Let e be an edge of H such that Mu and Mv meet on
Pe , i.e. Mu ∩ Mv ∩ V (Pe ) 6= ∅. Again, we denote by x1 , . . . , xp the vertices of Pe .
Claim 2. Let w ∈ A. If Mw = {xi , . . . , xj } with 1 < i ≤ j < p, then one of {x1 , . . . xi−1 }
and {xj+1 , . . . , xp } is disjoint from MA .
Proof. If there are vertices u, u0 of A such that Mu and Mu0 respectively intersect {x1 , . . . xi−1 }
and {xj+1 , . . . , xp }, then one of distF (Mu , r) and distF (Mu0 , r) is smaller than distF (Mw , r).
This contradicts the fact that w ∈ A whereas u, u0 6∈ A.
6

Claim 3. Let w ∈ A. If Mw intersects V (Pe ) then it is a right-protector or a left-protector.
Proof. By definition, if x1 ∈ Mw then Mw is a left-protector of Pe (and symmetrically for
the right). The case where Mw contains none of x1 and xp follows from Claim 2.
As Mu intersects Mv on Pe , it intersects the vertex set C of one component induced by
Mv on Pe (recall that there are either one or two such components). In the case where there
are two components, we assume without loss of generality that this is the “left” one (i.e.
that with smallest indices). In the case where there is one component, we assume that v is
a left-protector of Pe (according to Claim 3, v is a left-protector or a right-protector of Pe ).
Observe that in both cases, v is a left-protector of Pe . Let z be the rightmost left-protector
of Pe that belongs to R and let xk , . . . xk0 be the vertices of the corresponding component of
Pe [Mz ∩ V (Pe )] (that is, the component used in the definition of left-protector).
Notice that C ⊆ {x1 , . . . , xk0 }, by maximality of z (informally, because it is “rightmost”).
As z is a left-protector, Mu ∩ {x1 , . . . , xk−1 } = ∅. Since Mu and C intersect, they intersect
in {xk , . . . , xk0 }. Therefore Mu ∩ Mz 6= ∅: z is adjacent to u. As z ∈ R, we are done.
According to Claim 1 and Lemma 1.(i), a caterpillar decomposition (T, δ) that follows
the ordering v1 , . . . , vn satisfies mim(T, δ) ≤ 2kHk.
The next result follows from the application to the decomposition provided by Theorem 1
of Lemma 1.(ii), with the fact that mim(A) = mim(A) for every A ⊆ V (G).
Corollary 1. Let H be a graph. For every H-graph G on n vertices whose intersection
model is given, we can compute in polynomial time a caterpillar decomposition (T, δ) with
necd (T, δ) ≤ nd·2kHk .
For the definition of boolean-width, we also get:
Corollary 2. Let H be a graph. Every n-vertex H-graph has boolean-width at most 2kHk ·
log n.
By choosing H to be a single or double edge, we recover the results of [BV13] on the
boolean-width of interval and circular-arc graphs, respectively, as special cases of Corollary 2.
As proven in the same paper, there is a infinite family of interval graphs with boolean-width
Ω(log n). Observe that unless H is edgeless (in which case H-graphs are disjoint unions of
cliques), every interval graph is an H-graph. This shows that the bound in Corollary 2 is
tight up to a constant factor.
We now provide algorithmic applications of our results. Boolean-width has been used
[BXTV11] to design parameterized algorithms for the problems Maximum Weight Independent Set and Minimum Weight Dominating Set. Later, invariants of the form
necd were used in [BXTV13] as parameters of FPT algorithms for a vast class of problems,
called LC-VSP problems, that include fundamental problems as Independent Set, Independent Dominating Set, Total Dominating Set, Induced Matching, and many
others (see [BXTV13]). The main result of [BXTV13] is the following.
7

Theorem 2 ( [BXTV13]). For every LC-VSP problem Π, there are constants d and q such
that Π can be solved in time O(n4 · q · necd (T, δ)3q ) if a decomposition (T, δ) of the input is
given.
More recently, Jaffke, Kwon, and Telle obtained polynomial-time algorithms on graphs
of bounded mim-width for problems that are not LC-VSP.
Theorem 3 ( [JKT17b]). The problems Longest Induced Path, Induced Disjoint
Paths, and H-Induced Subdivision2 can be solved in time nO(mim(T,δ)) if a decomposition
(T, δ) of the input is given.
As Theorem 1 and Corollary 1 provide, in polynomial time, decompositions where the
values of mim and necd are respectively upper-bounded by a constant and by a polynomial
in the number of vertices of the graph (for fixed d), we get the following meta-algorithmic
consequence from Theorem 2 and Theorem 3.
Theorem 4. Let H be a graph and let Π be a LC-VSP problem. Then Π can be solved in
polynomial time on H-graphs if an H-representation of the input is provided.
Theorem 5. Let H be a graph. Any of Longest Induced Path, Induced Disjoint
Paths, and H-Induced Subdivision can be solved in polynomial time on H-graphs if an
H-representation of the input is provided.

4

H-graphs have few minimal separators

Let G be a graph. If a, b ∈ V (G), we say that X ⊆ V (G) is an (a, b)-separator if a and
b are in distinct connected components of G \ X. It is a minimal (a, b)-separator if it is
inclusion-wise minimal with this property. A subset of V (G) is a minimal separator of G if
it is a minimal (a, b)-separator for some a, b ∈ V (G).
The study of minimal separators is an active line of research that found many algorithmic
applications (see e.g. [KBMK93, BBC99, BT01, FTV15]). In general, the number of minimal
separators of a graph may be as large as exponential in its number of vertices. We prove in
this section that in an H-graph, this number is upper-bounded by a polynomial (Theorem 6).
By combining this finding with meta-algorithmic results of Fomin, Todinca and Villanger
[FTV15], we deduce that a wide class of optimization problems can be solved in polynomial
time on H-graphs (Corollary 3).
Theorem 6. Let H be a graph. If G is a H-graph, it has at most (2|G|+1)kHk +kHk·(2|G|)2
minimal separators.
Proof. Let G be a H-graph and let F be a subdivision of H where G can be represented as
the intersection graph of {Mv , v ∈ V (G)}. For every subset V ⊆ V (G), the border edges of
V are the edges of F with one endpoint in MV and one endpoint in V (F ) \ MV . Let R be
2

We refer the reader to [JKT17b] for an accurate definition of these problems.

8

the union of border edges over {Mv , v ∈ V (G)}. Observe that for every V ⊆ V (G), the set
of border edges of V is a subset of R. For every edge e ∈ E(F ), we set
Ve = {v ∈ V (G), e ⊆ Mv }
and extend this notation to sets S ⊆ E(F ) as follows:
VS = {v ∈ V (G), ∃s ∈ S, s ⊆ Mv }.
Informally, VS is the set of all vertices of G whose models contain some edge of S.
Claim 4. For every minimal separator X in G, there is a S ⊆ R such that X = VS .
Proof. Let A, B be two connected components of G \ X such that N (A) = N (B) = X. As
X is an (A, B)-separator (i.e. A and B are included in the vertex sets of distinct connected
components of G \ X), MA ∩ MB = ∅. Let S be the set of border edges of MA met on all
inclusion-wise minimal paths that start in A and end in B. As noted above, S ⊆ R. First we
show VS ⊆ X. Let v ∈ VS . That is, v is a vertex G such that Mv ⊇ s for some s ∈ S. Then
Mv contains both endpoints of s, one of which belongs to MA . The vertex v is adjacent to A
but does not belong to A (as Mv contains a vertex of A), so it has to belong to the separator
X. Therefore, Vs ⊆ X. Now we show X ⊆ VS . Let x ∈ X. By definition, x has a neighbor
in both A and B. Therefore, Mx meets both MA and MB . As Mx induces a connected
subgraph of F and MA is disjoint from MB , it contains an edge s ∈ E(F ) with one endpoint
in MA and the other in V (F ) \ MA . Then s is a border edge of MA in a minimal path from
A to B: x ∈ VS . Hence X = VS .
From Claim 4 we can already deduce that the number of minimal separators of G is
at most the number of subsets of R. In order to obtain better bounds, we need other
observations.
Claim 5. For every V ⊆ V (G) such that MV induces a connected subgraph of F , and every
e ∈ E(H), the set MV has at most two border edges in E(Pe ). Hence, |R| ≤ 2|G| · kHk.
Proof. Follows from the fact that F [MV ] is connected.
Claim 6. For every minimal separator X of G, if S ⊆ R is the subset of edges of F defined
in the proof of Claim 4, then
• either |S ∩ E(Pe )| ≤ 1 for every e ∈ E(H);
• or |S| = 2 and S ⊆ E(Pe ) for some e ∈ E(H).
Proof. Let A and B be as in the proof of Claim 4. According to Claim 5 and as S is a subset
of the border edges of MA , we deduce |S ∩ E(Pe )| ≤ 2 for every e ∈ E(H). Let us assume
that |S ∩ E(Pe )| = 2 for some e ∈ E(H). Let u, u0 and v, v 0 be the endpoints of the two edges
shared by S and E(Pe ), respectively and in this order on the path. Then the model of one of
A and B has its vertices in the subpath Q of Pe delimited by u0 and v. Indeed, both {u, u0 }
9

and {v, v 0 } and have an endpoint that does not belong to MA . As MA induces a connected
subgraph of F , either these endpoints are u0 and v (intuitively, the exterior endpoints) or
they are u, v 0 (the interior endpoints). In the first case MA ⊆ E(Q) and in the second one,
MB ⊆ E(Q). From the definition of R, we can then conclude that S ⊆ E(Pe ) and we get
|S| = 2.
Therefore, for every minimal separator X of G, there is a set S ⊆ R such that:
1. either |S ∩ E(Pe )| ≤ 1 for every e ∈ E(H);
2. or |S| = 2 and S ⊆ E(Pe ) for some e ∈ E(H);
In order to upper-bound the number of possible minimal separators of G, we can consequently upper-bound the number of sets S ⊆ R that satisfy one of the two conditions above.
As noted in Claim 5, for every e ∈ E(H) we have R ∩ E(Pe ) ≤ 2|G|. Hence there are at most
(2|G|)2 possible choices of set S that satisfy (2) for each e ∈ E(H). We deduce that there
are at most kHk · (2|G|)2 distinct sets S ⊆ R satisfying (2). Let us now consider sets S ⊆ R
that satisfy (1). For every e ∈ E(H), either S contains one of the 2|G| edges of R ∩ E(Pe ) or
it does not contain any of them. This makes 2|G| + 1 possible choices for each e ∈ E(H), and
(2|G| + 1)kHk in total. Consequently, G has at most (2|G| + 1)kHk + kHk · (2|G|)2 minimal
separators.
For every r ∈ N, let θr be the graph with 2 vertices and r parallel edges. The following
shows that the exponential contribution of kHk in Theorem 6 cannot be avoided.
r

minimal separators.
Lemma 2. For every r ∈ N, there is a θr -graph G with at least |G|−2
r
Proof. Let G be the graph obtained from θr by subdividing k times each edge (see Figure 1
for an example with r = 4 and k = 3). Then G is a θr -graph and |G| = kr + 2. Notice
that any choice of r subdivision vertices, each corresponding to a 
different edge of θr , gives a
r
|G|−2
r
distinct minimal separator of G. Hence G has at least k =
minimal separators.
r
...
...
...
...
k
Figure 1: A θ4 -graph with at least k 4 minimal separators.
Our results on minimal separators have algorithmic consequences. We consider the following generic problem described in [FTV15].

10

Optimal Induced Subgraph for P and t
Input: A graph G
Task: Find sets X ⊆ F ⊆ V (G) such that X is of maximum size, the induced subgraph
G[F ] is of treewidth at most t, and P(G[F ], X) is true.
For various choices of P and t, this generic problem corresponds to natural families of
optimization meta-problems like F-minor-deletion (where F is a class of graphs containing at least one planar graph) whose goal is to delete a minimum number of vertices
in order to get an F-minor free graph3 and Independent F-packing (where F is a class
of connected graphs), which asks for a maximum number of disjoint copies of graphs in
F as pairwise independent subgraphs of the input. Fomin, Todinca, and Villanger proved
that when the property P can be expressed in Counting Monadic Second Order logic (CMSOL, see [FTV15]), the above problem can be easily solved on classes of graphs that have a
polynomial number of minimal separators.
Theorem 7 ( [FTV15]). For any fixed t and CSMO property P, problem Optimal Induced
Subgraph for P and t can be solved in polynomial time for classes of graphs with a
polynomial number of minimal separators.
We deduce the following result about H-graphs.
Corollary 3. Let H be a graph. For any fixed t and CSMO property P, the problem Optimal Induced Subgraph for P and t can be solved in polynomial time for H-graphs.

5

Parameterized complexity of basic problems for Hgraphs

In this section we investigate the parameterized complexity of some basic graph problems for
H-graphs: Dominating Set, Independent Set and Clique. First, in Subsection 5.1,
we show that Dominating Set and Independent Set are W[1]-hard when parameterized
by the solution size and the size of H. In Subsection 5.2, we show that Dominating Set is
FPT when parameterized the solution size and by the number of vertices of H if H is a tree.
In fact, we show a more general result by proving that Dominating Set is FPT for chordal
graphs if the problem is parameterized by the leafage of the input graph, that is, by the
minimum number of leaves in a clique tree for the input graph. This result is somehow tight
since Dominating Set is well-known to be W[2]-hard for split graphs when parameterized
by the solution size [RS08]. Recall also that Independent Set is polynomial for chordal
graphs [Gav72, Gol04] and, therefore, for H-graphs if H is a tree. Finally, in Subsection 5.3,
we show that Clique admits a polynomial kernel when parameterized by the solution size
and the size of H.
3

In fact, Optimal Induced Subgraph for P and t corresponds to the dual equivalent problem of
F-minor-deletion, which asks for a largest F-minor free subgraph of the input.

11

5.1

Hardness of Independent Set and Dominating Set on H-graphs

In this section we prove W[1]-hardness of Dominating Set and Independent Set for
H-graphs (Theorem 8). Recall that Dominating Set and Independent Set, given a
graph G and a positive integer k, ask whether G has a dominating set of size at most k
and independent set of size at least k respectively. To show hardness, we reduce from the
Multicolored Clique problem. This problem, given a graph G with a k-partition of
its vertex set V1 , . . . , Vk , asks whether G has a k-clique with exactly one vertex in each Vi
for i ∈ {1, . . . , k}. The problem is well-known to be W[1]-complete when parameterized by
k [FHRV09, Pie03].
Theorem 8. Dominating Set and Independent Set are W[1]-hard for H-graphs when
parameterized by k + kHk and the hardness holds even if an H-representation of G is given.
Proof. First, we show the W[1]-hardness for Independent Set and then explain how
to modify the reduction for Dominating Set. The reduction is from Multicolored
Clique.
Let (G, V1 , . . . , Vk ) be an instance of Multicolored Clique. We assume that k ≥ 2
and |Vi | = p for i ∈ {1, . . . , k}. The second assumption can be made without loss of generality
because we always can add isolated vertices to the sets V1 , . . . , Vk to ensure that they have
the same size. Denote by v1i , . . . , vpi the vertices of Vi for i ∈ {1, . . . , k}.
u2
(i,j)

ui
w2,3
w1,2

u1

w1,3
a)

y1

(i,j)

x1

(i,j)
x2

(j,i)

yp

(i,j)

yp

wi,j
(i,j)

xp

(j,i)

y1

uj
(j,i)

(j,i)

xp

x1

(j,i)
x2

u3
b)

Figure 2: The construction of H for k = 3 and the subdivision of the edges of H.
We construct the multigraph H as follows (see Figure 2 a)).
(i) Construct k nodes u1 , . . . , uk .
(ii) For every 1 ≤ i < j ≤ k, construct a node wi,j and two pairs of parallel edges ui wi,j
and uj wi,j .
Note that |V (H)| = k(k + 1)/2 and |E(H)| = 2k(k − 1).
Then we construct the subdivision H 0 of H obtained by subdividing each edge p times.
We denote the subdivision nodes for 4 edges of H constructed for each pair 0 ≤ i < j ≤ k
(i,j)
(i,j)
(i,j)
(i,j)
(j,i)
(j,i)
(j,i)
(j,i)
in (ii) by x1 , . . . , xp , y1 , . . . , yp , x1 , . . . , xp and y1 , . . . , yp as it is shown in
12

(i,j)

Figure 2 b). To simplify notations, we assume that ui = x0
(i,j)
(i,j)
(j,i)
(j,i)
wi,j = xp+1 = yp+1 = xp+1 = yp+1 .
Mzsi

Mr(i,j)
s,t

(i,j)

yp−s

(i,j)
xs−1 (i,j)
xs

ui

(i,j)
yp−s+1

wi,j

(j,i)
y
(j,i) p−t
yp−t+1
(j,i)
xt

(i,j)

= y0

(j,i)

, uj = x0

(j,i)

= y0

and

Mzj
t

(j,i)
xt−1

uj

Figure 3: The construction of G0 .
Now we construct the H-graph G0 by defining its H-representation M = {Mv }v∈V (G0 )
where the model of each vertex is a connected subset of V (H 0 ) (see Figure 3). Recall that
G is the graph of the original instance of Multicolored Clique.
(i) For each i ∈ {1, . . . , k} and s ∈ {1, . . . , p}, construct a vertex zsi with the model
(i,j)

Mzsi = ∪j∈{1,...,k},j6=i ({x0

(i,j)

(i,j)

, . . . , xs−1 } ∪ {y0

(i,j)

, . . . , yp−s }).

(ii) For each edge vsi vtj ∈ E(G) for s, t ∈ {1, . . . , p} and 1 ≤ i < j ≤ k, construct a vertex
(i,j)
rs,t with the model
(i,j)

(i,j)

(i,j)

(j,i)

Mr(i,j) = ({x(i,j)
, . . . , xp+1 })∪({yp−s+1 , . . . , yp+1 })∪({xt
s
s,t

(j,i)

(j,i)

(j,i)

, . . . , xp+1 })∪({yp−t+1 , . . . , yp+1 }).

Finally, we define k 0 = k(k + 1)/2. We claim that (G, V1 , . . . , Vk ) is a yes-instance of
Multicolored Clique if and only if G0 has an independent set of size k 0 . The proof is
based on the following crucial property of our construction, that can be easily checked.
Claim 7. For every 0 ≤ i < j ≤ k, a vertex zhi ∈ V (G0 ) (a vertex zhj ∈ V (G0 )) is not
(i,j)
adjacent to a vertex rs,t ∈ V (G0 ) corresponding to the edge vsi vtj ∈ E(G) if and only if h = s
(h = t, respectively).
Let {vh11 , . . . , vhkk } be a clique of G. Consider the set
(i,j)

I = {zh11 , . . . , zhkk } ∪ {rhi ,hj | 0 ≤ i < j ≤ k}
of vertices of G0 . It is straightforward to verify using Claim 7 that I is an independent set
of size k 0 in G0 .
Suppose now that G0 has an independent set I of size k 0 . For each i ∈ {1, . . . , k},
the set Zi = {zhi | 1 ≤ h ≤ p} is a clique of G0 , and for each 1 ≤ i < j ≤ k, the set

(i,j)
Ri,j = {rs,t | 1 ≤ s, t ≤ p, vsi vtj ∈ E(G)} is also a clique of G0 . Since all these k 0 = k + k2
cliques form a partition of V (G0 ), we have that for each i ∈ {1, . . . , k}, there is a unique
(i,j)
(i,j)
zhi i ∈ Zi ∩ I, and for every 1 ≤ i < j ≤ k, there is a unique rsi ,sj ∈ Ri,j ∩ I. Since rsi ,sj is
not adjacent to zhi i and zhj j , we obtain that si = hi and sj = hj by Claim 7. It implies that
vhi i vhj j ∈ E(G). Since it holds for every 1 ≤ i < j ≤ k, {vh11 , . . . , vhkk } is a clique in G.
13

This completes the W[1]-hardness proof for Independent Set. Now we explain how we
modify our proof to show the W[1]-hardness of Dominating Set. This time we reduce not
from Multicolored Clique but from the Multicolored Independent Set problem
that, given a graph G with a k-partition of its vertex set V1 , . . . , Vk , asks whether G has
am independent set of size k with exactly one vertex in each Vi for i ∈ {1, . . . , k}. Clearly,
the W[1]-completeness of Multicolored Clique parameterized by k [FHRV09, Pie03]
immediately implies the same for Multicolored Independent Set.
Let (G, V1 , . . . , Vk ) be an instance of Multicolored Independent Set. We assume
without loss of generality that k ≥ 2 and |Vi | = p for i ∈ {1, . . . , k}. As before, denote by
v1i , . . . , vpi the vertices of Vi for i ∈ {1, . . . , k}. We construct the same multigraph H and
its subdivision H 0 as above. We construct the H-graph G00 from the graph G0 constructed
above by adding k new vertices d1 , . . . , dk with the models Mdi = {ui } for i ∈ {1, . . . , k}.
We show that (G, V1 , . . . , Vk ) is a yes-instance of Multicolored Independent Set if
and only if G00 has a dominating set of size k.
Suppose that {vh11 , . . . , vhkk } is an independent set of G. Consider the set D = {zh11 , . . . , zhkk }.
By Claim 7 and the construction of G00 , we obtain that D is a dominating set of G00 .
Let now D be a dominating set of G00 with |D| = k. Note that each vertex di is adjacent
only to the vertices of the set Zi = {zhi | 1 ≤ h ≤ p} for i ∈ {1, . . . , k}. It implies that
D ∩ (Zi ∪ {di }) 6= ∅ for i ∈ {1, . . . , k}. Since Zi is a clique, we can assume without loss of
generality that D ∩ Zi 6= ∅ as, otherwise, we can replace di in D by an arbitrary vertex of Zi .
Since Zi ∩ Zj = ∅ if i 6= j, we conclude that D contains a unique vertex from each Zi and no
other vertices. Let D = {zh11 , . . . , zhkk }. We claim that I = {vh11 , . . . , vhkk } is an independent
set of G. To obtain a contradiction, assume that vhi i vhj j ∈ E(G) for some 1 ≤ i < j ≤ k.
(i,j)

(i,j)

Consider the vertex rhi ,hj of G00 . By Claim 7, rhi ,hj is adjacent neither to zhi i no zhj j . Because
(i,j)

(i,j)

rhi ,hj is not adjacent to zhs s for any s ∈ {1, . . . , k} such that s 6= i, j, we have that rhi ,hj is
not dominated by D. This contraction shows the claim.
We proved in Theorem 1 that for every fixed H, every H-graph has mim-width at most
2kHk. We deduce from the negative results above the following corollary.
Corollary 4. Dominating Set and Independent Set are W[1]-hard when parameterized
by the solution size plus the mim-width of the input.
We note that the construction in the proof of Theorem 8 has been adapted in [JKT17a]
to show that the Feedback Vertex Set problem is W[1]-hard on H-graphs when parameterized by the solution size plus the number of edges of H.

5.2

Dominating Set for T -graphs

In this section we show that Dominating Set is FPT for chordal graphs if the problem is
parameterized by the solution size and the leafage (hereafter defined) of the input graph.
Let G be a graph. As it is standard, we say that u ∈ V (G) dominates v ∈ V (G) if
v ∈ NG [u] and u dominates a set W ⊆ V (G) if every vertex of W is dominated by u.
14

Respectively, a set D ⊆ V (G) dominates W ⊆ V (G) if every vertex of W is dominated by
some vertex of D.
Let G be a graph. Let K be the set of (inclusion-wise) maximal cliques of G and let
Kv ⊆ K be the set of maximal cliques containing v ∈ V (G). A tree T whose node set is K
such that Kv induce a subtree of T for every v ∈ V (G) is called a clique tree of G. It is wellknown [Gav74] that G is a chordal graph if and only if G has a clique tree T . Moreover, if T
is a clique tree of G, then G is an intersection graph of subtrees of T , that is, G is a T -graph.
Note that a clique tree of a chordal graph is not necessarily unique. For a connected chordal
graph G, the leafage `(G) of G is the minimum number of leaves in its clique tree. In was
shown by Habib and Stacho in [HS09] that the leafage of a connected chordal graph G can be
found in polynomial time. Their algorithm also constructs the corresponding clique tree T
with the minimum number of leaves. In other words, given a connected chordal graph G, we
can construct in polynomial time its clique tree T with `(G) leaves and a T -representation
of G.
Let T be a tree and let G be a connected T -graph with its T -representation M =
{Mv }v∈V (G) with respect to a subdivision T 0 of T .
Recall that for nonempty U ⊆ V (T ), we say that v ∈ V (G) is a U -vertex if Mv ∩ V (T ) =
U . If U = {u}, we write u-vertex instead of {u}-vertex. Recall also that we denote the
set of U -vertices by VG (U ) and VG (u) if U = {u}. We also denote by VG (T ) the set of all
U -vertices of G for all nonempty U ⊆ V (T ). For e ∈ E(T ), v ∈ V (G) is an e-vertex if Mv
contains only subdivision nodes of T 0 from the path in T 0 corresponding to e in T . The set
of e-vertices is denoted by VG (e).
We need the following lemma that allows to upper bound the number of vertices in a
minimum dominating set whose models contain given nodes of T .
Lemma 3. Let D be a minimum dominating set of G. Let X ⊆ V (T ) be an inclusion
maximal set of nodes of T such that i) for every x ∈ X, there is u ∈ D with x ∈ Mu
and ii) for every xy ∈ E(T ) with x, y ∈ X, there is u ∈ D with x, y ∈ Mu . Then the set
U = {u ∈ D | X ∩ Mu 6= ∅} contains at most |NT [X]| − 1 vertices.
Proof. Denote by v1 , . . . , vs the vertices of NT (X). To obtain a contradiction, assume that
that |U | > |NT [X]| − 1 = s + |X| − 1. For each i ∈ {1, . . . , s}, let ui ∈ U be a vertex such
that the distance between Mui and vi in T 0 is minimum. For each xy ∈ E(T ) with x, y ∈ X,
we select arbitrary uxy ∈ U with x, y ∈ Muxy . Let U 0 = {u1 , . . . , u` } ∪ {uxy | x, y ∈ X, xy ∈
E(T )}. Note that |U 0 | ≤ s + |X| − 1 = |NT [X]| − 1. Since X induces a subtree of T , we have
that ∪u∈U Mu ⊆ ∪u∈U 0 Mu . It immediately implies that D0 = (D \ U ) ∪ U 0 is a dominating
set of G contradicting the minimality of D.
In particular, since |NT (X)| is at most the number of leaves `, we have that |U | ≤
|X| + ` − 1.
The next lemma gives an upper bound for the number of vertices in a minimum dominating set whose models contain nodes of T .
Lemma 4. Let D be a minimum dominating set of G. Then |D ∩ VG (T )| ≤ 3|V (T )| − 2.
15

Proof. Let D be a minimum dominating set of G. Consider the set W of nodes of T that
are included in the models of the vertices of D. Let X1 , . . . , Xr be the partition of W into
inclusion maximal subsets such that for each i ∈ {1, . . . , r} and adjacent x, y ∈ Xi , there is
u ∈ D with x, y ∈ Mu . By Lemma 3,
|D∩VG (T )| ≤

r
X

(|Xi |+|NT (Xi )|−1) ≤ |W |+

i=1

r
X

|NT (Xi )| ≤ |V (T )|+2|E(T )| = 3|V (T )|−2.

i=1

For an edge e ∈ E(T ), we say that G0 is obtained by contracting e in T if G0 is the
(T /e)-graph with the model obtained as follows:
(i) contract xy in T and, respectively, the (x, y)-path P in T 0 , and denote the node obtained from x and y by z,
(ii) delete all e-vertices of G,
(iii) for each remaining vertex u ∈ V (G), delete from Mu the subdivision nodes of P and
replace x and y by z if at least one of these nodes is in Mu .
Note that V (G0 ) ⊆ V (G) and G[V (G0 )] is a subgraph of G0 but not necessarily induced since
two vertices of G0 that are not adjacent in G could be adjacent in G0 .
Consider a coloring c : VG (T ) → {1, . . . , 2|V (T )| } such that for u, v ∈ VG (T ), c(u) = c(v)
if and only if u and v are U -vertices for the same U ⊆ V (T ).
The next lemmas are used to simplify the models of vertices of G by contracting edges
of T .
Lemma 5. Let C ⊆ c(VG (T )) and let A = {xy ∈ E(T ) | x, y ∈ Mu for u ∈ VG (T ), c(u) ∈
C}. Let also G0 be the graph obtained from G by consecutively contracting edges A in T .
Then for a set D ⊆ V (G), D is a minimum dominating set of G satisfying the condition
C = c(D ∩ VG (T )) if and only if D is a minimum dominating set of G0 satisfying the same
condition C = c(D ∩ VG (T )).
Proof. Before we start proving the lemma, observe that VG (T ) ⊆ G0 and VG (T ) is the set of
U -vertices of G0 for nonempty subsets U of the set of nodes of T /A. Note also that for G0
and T /A, the coloring c not necessarily has the property that if u and v are U -vertices of
the same U , then c(u) = c(v).
Suppose that D is a dominating set of of G with C = c(D ∩VG (T )) that has the minimum
size. We claim that D ⊆ V (G0 ). To see it assume that there is u ∈ D \ V (G0 ). Then u
is an e-vertex of G for some e = xy ∈ A. Then there is v ∈ VG (T ) such that x, y ∈ Mv
and c(v) ∈ C. Since D has a vertex v 0 with c(v 0 ) = c(v), we have that x, y ∈ Mv0 . Clearly,
Mu ⊆ Mv0 . It implies that D \ {u} is a dominating set of G. Since u is e-edge, u is not
colored and the obtained dominating set contains vertices with all the colors from C, but
this contradicts the choice of D. Therefore, D ⊆ V (G0 ). Because G[V (G0 )] is a subgraph of
G0 , we have that D is a dominating set of G0 .
16

Let now D be a dominating set of G0 with C = c(D ∩ VG (T )) that has the minimum size.
We show that D is a dominating set of G.
First, we prove that D dominates every u ∈ V (G) \ V (G0 ). If u ∈ V (G) \ V (G0 ), then u
is an e-vertex for some e = xy ∈ A. We have that there is v ∈ VG (T ) such that x, y ∈ Mv
and c(v) ∈ C. Because C ⊆ c(D ∩ VG (T )), there is v 0 ∈ D with c(v 0 ) = c(v). It implies that
x, y ∈ Mv0 in G and, therefore, v 0 dominates u.
Now we show that D dominates the vertices of V (G0 ) in G. To obtain a contradiction,
assume that there is u ∈ V (G0 ) that is not dominated by D in G. As D is a dominating
set of G0 , there is v ∈ D such that uv ∈ E(G0 ) and uv ∈
/ E(G). It follows that there are
x, y ∈ V (T ) such that x ∈ Mu , y ∈ Mv and for the (x, y)-path P in T , E(P ) ⊆ A. Let xy 0 be
the edge of P that is incident to x. Since xy 0 ∈ A, there is w ∈ VG (T ) such that x, y ∈ Mw in
G and c(w) ∈ C. Because C ⊆ c(D ∩ VG (T )), there is w0 ∈ D with c(w0 ) = c(w). It implies
that x ∈ Mw0 in G and, therefore, w0 dominates u.
Lemma 6. Let C ⊆ c(VG (T )) and A0 = {xy ∈ E(T ) | x, y ∈ Mu for u ∈ VG (T ), c(u) ∈
/
C and x, y ∈
/ Mv for v ∈ VG (T ), c(v) ∈ C}, and assume that for every e ∈ A0 , G has no
e-vertex. Denote by G0 be the graph obtained from G by consecutive contracting of edges of
A0 in T . Then for a set D ⊆ V (G), D is a minimum dominating set of G satisfying the
condition C = c(D ∩ VG (T )) if and only if D is a dominating set of G0 satisfying the same
condition C = c(D ∩ VG (T )).
Proof. Observe that V (G0 ) = V (G), because we do not delete e-vertices when we contract
A0 . Notice also that the model Mu of a vertex u ∈ VG (T ) with c(u) ∈ C remains the same
in the modified representation obtained by the contraction.
If D is a dominating set of G with C = c(D ∩ VG (T )), then it is straightforward to
verify that D is a dominating set of G0 . Suppose that D is a dominating set of G0 with
C = c(D ∩ VG (T )). We have that G is a subgraph of G0 . Suppose that u, v ∈ V (G) are
adjacent in G0 but are not adjacent in G. It follows that there are x, y ∈ V (T ) such that
x ∈ Mu , y ∈ Mv and there is an (x, y)-path P in T such that E(P ) ⊆ A0 . Then c(u), c(v) ∈
/C
0
by the definition of A . Hence, u, v ∈
/ D. We obtain that for every u, v ∈ V (G) that are
adjacent in G0 but are not adjacent in G, u, v ∈
/ D. Hence, D is a dominating set of G.
We say that M is a nice representation if |Mv ∩ V (T )| ≤ 1 for v ∈ V (G), i.e., each set
Mv contains at most one branching node of T 0 .
We say that a T -representation M = {Mv }v∈V (G) of G with respect to a subdivision
T 0 is an r-rooted representation if a node r of T is chosen to be a root. The root defines
the parent-child relation on V (T ) and V (T 0 ). For x ∈ V (T ) (x ∈ V (T 0 )), we denote by
Tx (Tx0 respectively) the subtree of T (T 0 respectively) induced by x and its descendants.
For x ∈ V (T ) and its child y, we denote by Txy the subtree of T induced by x, y and the
descendants of y. For x ∈ V (T ), Vx (G) = {v ∈ V (G) | Mv ∩ V (Tx0 ) 6= ∅}.
Let M = {Mv }v∈V (G) be a nice r-rooted T -representation of G with respect to T 0 . For
a vertex x ∈ V (T 0 ), we denote by dist(x) the distance between r and x in T 0 . For a set
X ⊆ V (T 0 ), we denote by dmin (X) = min{dist(x) | x ∈ X} and by dmax (X) = max{dist(x) |
x ∈ X}. Consider an edge e = xy ∈ E(T ), where y is a child of x, and denote by Pe the
17

(x, y)-path in T 0 corresponding to e. Let u, v ∈ V (G) such that Mue = Mu ∩ V (Pe ) 6= ∅ and
Mve = Mv ∩ V (Pe ) 6= ∅. We write u e v if either dmin (Mue ) < dmin (Mve ) or dmin (Mue ) =
dmin (Mue ) and dmax (Mue ) ≤ dmax (Mve ). Respectively, u ≺e v if either dmin (Mue ) < dmin (Mve ) or
dmin (Mue ) = dmin (Mve ) and dmax (Mue ) < dmax (Mve ).
We consider the following auxiliary problem for T -graphs with nice representations.
Dominating Set Extension
Input: A tree T with ` leaves and a graph G with a nice r-rooted T -representation of G
0
with
S respect to a subdivision T of T , positive integers k and d, a labeling function
c : x∈V (T ) VG (x) → N, and a collection of sets {Cx }x∈V (T ) of size at most d where
each Cx ⊆ c(VG (x)) (some sets could be empty) such that for a dominating set D
of G of minimum size with the properties that
(a) D has at most d x-vertices for x ∈ V (T ),
(b) for each x ∈ V (T ), Cx ⊆ c(D ∩ VG (x)),
it holds that the number of nodes x ∈ V (T ) such that D contains an x-vertex is
maximum and for each x ∈ V (T ), Cx = c(D ∩ VG (x)).
Task: Decide whether there is a dominating set D0 of G of size at most k containing at
most d x-vertices for x ∈ V (T ) such that for each x ∈ V (T ), Cx = c(D0 ∩ VG (x)).
Note that Dominating Set Extension is a promise problem: we are promised that
there is D with the described properties but D itself is not given. Moreover, the promise
could be false but we are not asked to verify it.
Lemma 7. Dominating Set Extension can be solved in time 2O((d+`) log d) nO(1) . Moreover, it can be done by an algorithm that either returns a correct yes-answer or (possible
incorrect) no-answer even if the promise is false.
Proof. Let G be a T -graph for a tree T rooted in r that has a nice r-rooted T -representation
M with respect to a subdivision T 0 of T . If G is disconnected, then we reduce the problem to
solving Dominating Set Extension for the components of G. Assume from now that G is
connected. Let also k and d be positive integers, c : ∪x∈V (T ) VG (x) → N is a labeling function,
and {Cx }x∈V (T ) is a collection of sets where each Cx ⊆ c(VG (x)). Since G is connected, we can
assume without loss of generality that for every x ∈ V (T 0 ), there is v ∈ V (G) with x ∈ Mv .
Otherwise, we can replace T by its subtree without increasing the number of leaves. We also
assume that |Cx | ≤ d ≤ |VG (x)| as, otherwise, we have a trivial no-instance of Dominating
Set Extension. We construct a dynamic programming algorithm for the problem that
finds the minimum size of a dominating set D of G containing at most d x-vertices for
x ∈ V (T ) such that for each x ∈ V (T ), Cx = c(D ∩ VG (x)). Our algorithm assumes that
the promise is fulfilled for the considered instance of Dominating Set Extension. The
algorithm uses the properties that every node of T has at most ` children, i.e., the number
18

of the children is bounded by the parameter, and for each edge e of T , the set of e-edges of
G composes an interval graphs for which the domination problem can be solved efficiently.
First, we construct a subroutine that solves the following auxiliary problem for each
e = xy ∈ E(T ). Let Pe be the (x, y)-path in T 0 corresponding to e. Let Ue = {v ∈ V (G) |
Mv ∩ V (P ) 6= ∅}. For X ⊆ Ue , αe (X) is the minimum size of a set S of e-vertices of G that
dominates X; we assume that αe (X) = 0 if X = ∅ and αe (X) = +∞ if such a dominating
set of e-vertices S does not exist.
Claim A. For every e ∈ E(T ) and X ⊆ Ue , αe (X) can be computed in time nO(1) .
Proof of Claim A. If X = ∅, then αe (X) = 0 by the definition. Assume that X 6= ∅. If
there is a vertex in X that is not dominated by any e-vertex of G, then we set αe (X) = +∞.
Otherwise, it is straightforward to see that S exists, and we construct S using the well-known
greedy approach for constructing a minimum dominating set in an interval graph.
Initially, we set S = ∅ and then increase it iteratively until all the vertices of X are
dominated. Denote by Y ⊆ X the set of vertices that are not dominated by the the current
S. Then we do the following:
1. Find a vertex w in Y that is maximum with respect to the ordering e .
2. Find a minimum with respect to e e-vertex v that dominates w, set S = S ∪ {v} and
recompute Y .
3. If Y 6= ∅, then return to Step 1.
It is straightforward to verify that the algorithm correctly computes αe (X) in polynomial
time.
We say that a node x ∈ V (T ) is loaded of Cx 6= ∅ and x is unloaded otherwise.
We say that a set of vertices S is extendable if there is a dominating set D such that
(a) D has at most d x-vertices for x ∈ V (T ),
(b) for each x ∈ V (T ), Cx ⊆ c(D ∩ VG (x)),
that has the minimum size and contains S and the conditions of the promise is fulfilled:
the number of nodes x ∈ V (T ) such that D contains an x-vertex is maximum and for each
x ∈ V (T ), Cx = c(D ∩ VG (x)).
We are ready to explain our dynamic programming algorithm for Dominating Set
Extension. It works on T starting from the leaves and moving towards the root. To avoid
dealing with the root that has no parent separately, we add an artificial node r0 to T and
T 0 and make r0 the parent of r and the new root. Observe that r0 is the unique node of the
tree that is not included in Mv for some v ∈ V (G).
We start with defining the tables of data that the algorithm stores for each x 6= r0 of
T . Let y be a parent of x and let e = yx. Consider the set W = {v1 , . . . , vp } of x-vertices
of G and assume that v1 e . . . e vp (note that if x = r and y = r0 , then the ordering is
arbitrary).
19

If x loaded, then for x and i ∈ {1, . . . , p}, the algorithm stores the value β(x, i) that is
either the minimum size of a set S ⊆ Vx (G) such that
(i) vi ∈ S,
(ii) S contains at most d z-vertices for each z ∈ V (Tx ),
(iii) for each z ∈ V (Tx ), Cz = c(S ∩ VG (z)), and
(iv) S dominates all the vertices of Vx (G),
or we may set β(x, i) = +∞ if we detect that there is no S ⊆ Vx (G) satisfying (i)–(iv) such
that S is extendable. In particular, it can happen if every set S satisfying (i)-(iv) contradicts
the promise of Dominating Set Extension.
Similarly, if x is unloaded, then for x and i ∈ {0, . . . , p} the algorithm stores the value
γ(x, i) that is either the minimum size of a set S ⊆ Vx (G) such that
(v) vi+1 , . . . , vp are dominated by S,
(vi) S contains at most d z-vertices for each z ∈ V (Tx ),
(vii) for each z ∈ V (Tx ), Cz = c(S ∩ VG (z)), and
(viii) S dominates all the vertices of Vx (G) \ {v1 , . . . , vp },
or we may set γ(x, i) = +∞ if we detect that there is no S ⊆ Vx (G) satisfying (v)–(viii) such
that S is extendable. Similarly to β(x, i), we do it if we detect that every set S satisfying (v)(viii) contradicts the promise of Dominating Set Extension. In particular, it happens
when we gain by including an x-vertex of G into a partial solution.
It also is assumed that β(x, i) = +∞ and γ(x, i) = +∞ if there is no any S that satisfy
the conditions (i)–(iv) or (v)–(viii) respectively.
Now we explain how we compute the values β(x, i) and γ(x, i). First, we do it for leaves.
Computing β(x, i) and γ(x, i) for leaves. Let x be a loaded leaf of T . We set
(
|Cx | if c(vi ) ∈ Cx ,
β(x, i) =
+∞ otherwise.
Let x be unloaded leaf. We set
(
0
γ(x, i) =
+∞

if i = p,
if i < p.

Now we compute the values β(x, i) and γ(x, i) for non-leaves.
Suppose that x 6= r0 is a non-leaf node of T . Let z1 , . . . , zs be the children of x in T and
let ej = xzi for j ∈ {1, . . . , s}. Assume that the functions β and γ are computed for the
children of x depending on whether they are loaded or not.
20

Computing β(x, i) for loaded x. Consider zj for j ∈ {1, . . . , s}. Let Wj = {u1 , . . . , uq }
be the set of zj -vertices of G. We assume that u1 ej . . . ej uq . For i ∈ {1, . . . , p}, we
compute the values of δj (x, i). To do it, we consider two cases.
Case 1. The vertex zj is loaded. For i0 ∈ {1, . . . , p} and h ∈ {1, . . . , q}, let
Xi0 ,h = {w ∈ V (G) | w ∈ VG (ej ), Mw ∩ (Mvi0 ∪ Muh ) = ∅}.
We set
δj (x, i0 ) = min {β(zj , h) + αej (Xi0 ,h )}.
1≤h≤q

Case 2. The vertex zj is unloaded. For i0 ∈ {1, . . . , p}, let
Yi0 = {w ∈ V (G) | w ∈ VG (ej ), Mw ∩ Mvi0 = ∅}
and for h ∈ {0, . . . , q},
Yi0 ,h

(
Yi0
=
Yi0 ∪ {uh }

if h = 0,
if h > 0.

We set
δj (x, i0 ) = min {γ(zj , h) + αej (Yi0 ,h )}.
0≤h≤q

We have that δj (x, i) is defined for both cases. For i0 ∈ {1, . . . , p} and each non-empty
J ⊆ {1, . . . , q}, we set
X
δJ (x, i0 ) =
δj (x, i0 ),
j∈J

and δ∅ (x, i0 ) = 0.
We consider all possible partitions P = {J1 , . . . , Jt } for |Cx | ≤ t ≤ d of {0, 1, . . . , s}
where 0 ∈ J1 and some other sets could be empty. We then consider all possible surjections
ϕ : {1, . . . , t} → Cx . For x and i ∈ {1, . . . , p}, we set
β(x, i) = min{t +

t
X

min{δJh (x, i0 ) | 1 ≤ i0 ≤ p, i0 = i if h = 1, c(vi0 ) = ϕ(h)} | P, ϕ}, (1)

h=1

where we assume to simplify notations that
min{δJh (x, i0 ) | 1 ≤ i0 ≤ p, c(vi0 ) = ϕ(h), i0 = i if h = 1} = +∞
if h ≥ 2 and there is no 1 ≤ i0 ≤ p such that c(vi0 ) = ϕ(h) or if h = 1 and ϕ(1) 6= c(vi ).

21

Computing γ(x, i) for unloaded x. Consider zj for j ∈ {1, . . . , s}. Let Wj = {u1 , . . . , uq }
be the set of zj -vertices of G. We assume that u1 ej . . . ej uq . Consider also the ordering
vij , . . . , vijp of the vertices of W such that vij ej . . . ej vijp . We compute the functions η(j)
1
1
and ψ(j) as follows depending on whether zj is loaded or not.
Case 1. The vertex zj is loaded. For h ∈ {1, . . . , q}, let
Xh = {w ∈ V (G) | w ∈ VG (ej ), Mw ∩ Muh = ∅},
and let
η(j) = min (β(zj , h) + αej (Xh )).

(2)

1≤h≤q

For t ∈ {1, . . . , p} and h ∈ {1, . . . , q + 1}, denote
(
Xh ∪ {vij , . . . , vijp }
t
Xh,t =
Xh

if t ≤ p,
if t = p + 1,

and let
ψ(j) = min{t | 1 ≤ t ≤ p + 1, η(j) = min (β(zj , h) + αej (Xh,t ))}.
1≤h≤q

Case 2. The vertex zj is unloaded. For h ∈ {0, . . . , q}, let
(
{w ∈ V (G) | w ∈ VG (ej )}
Yh =
{w ∈ V (G) | w ∈ VG (ej )} ∪ {u1 , . . . , uh }

(3)

if h = 0,
if h ≥ 1,

and let
η(j) = min (γ(zj , h) + αej (Yh )).
0≤h≤q

For t ∈ {1, . . . , p} and h ∈ {1, . . . , q + 1}, denote
(
Yh ∪ {vij , . . . , vijp }
t
Yh,t =
Yh

(4)

if t ≤ p,
if t = p + 1,

and let
ψ(j) = min{t | 1 ≤ t ≤ p + 1, η(j) = min (γ(zj , h) + αej (Yh,t ))}.
0≤h≤q

(5)

Now for i ∈ {0, . . . , p}, we set
(Ps
if for h ∈ {i + 1, . . . , p}, there is j ∈ {1, . . . , s} s.t. vij ej vh
j=1 η(j)
ψ(j)
γ(x, i) =
+∞
otherwise.
(6)
We compute β and γ for all nodes of T except the artificial root r0 . The algorithm is
based on the following properties of these values.
22

Claim B. If x is a loaded node, then for x and i ∈ {1, . . . , p}, the following is fulfilled: if
β(x, i) < +∞, then there is a set S ⊆ Vx (G) satisfying the conditions (i)-(iv) of size at most
β(x, i), and if there is a set S ⊆ Vx (G) satisfying the conditions (i)-(iv) that is extendable,
then |S| = β(x, i). Similarly, if x is unloaded, then for x and i ∈ {0, . . . , p}, the following is
fulfilled: if γ(x, i) < +∞, then there is a set S ⊆ Vx (G) satisfying the conditions (v)-(viii) of
size at most γ(x, i), and if there is a set S ⊆ Vx (G) of minimum size satisfying the conditions
(v)-(viii) that is extendable, then |S| = γ(x, i).
Proof of Claim B. It is straightforward to verify these properties for the leaves of T by the
definition of β and γ.
We use standard approach for proving correctness of dynamic programming algorithms.
We assume inductively that the properties of the values of β and γ are fulfilled for the children
of x using as the base of the induction the fact that we already verified the properties of β
and γ for the leaves of T .
As in the description of the algorithm, we assume that W = {v1 , . . . , vp } is the set of
x-vertices and assume that v1 e . . . e vp for e = yx where y is the parent of x. In the
same way, z1 , . . . , zs are the children of x.
First, we prove the claim for β. Let x be a loaded node and let i ∈ {1, . . . , p}.
Let β(x, i) < +∞. We show that there is a set S ⊆ Vx (G) of size at most β(x, i) such
that
(i) vi ∈ S,
(ii) S contains at most d z-vertices for each z ∈ V (Tx ),
(iii) for each z ∈ V (Tx ), Cz = c(S ∩ VG (z)), and
(iv) S dominates all the vertices of Vx (G).
Consider a partition P = {J1 , . . . , Jt } and a mapping ϕ : {1, . . . , t} → Cx for which the
minimum in the right part of (1) is achieved. Further, for each j ∈ {1, . . . , s}, let ij be a
value of i0 for which min{δJh (x, i0 ) | 1 ≤ i0 ≤ p, i0 = i if h = 1, c(vi0 ) = ϕ(h) is achieved; note
that i1 = i.
We define Sx = {vi1 , . . . , vit }; observe that some vertices could be repeated and in this
case we remove the duplicates. We have that |Sx | ≤ t ≤ d and vi ∈ Sx . Since ϕ is a
surjection, Cx = c(Sx ∩ VG (x)). We obtain (i)–(iii) are fulfilled for z = x. Clearly, all
x-vertices of G are dominated by Sx .
Consider zj for j ∈ {1, . . . , s}. As in the description of the algorithm, we assume that
Wj = {u1 , . . . , uq } is the set of zj -vertices of G. We also assume that u1 ej . . . ej uq . Let
j ∈ Ji0 . We consider two cases depending on whether zj is loaded or not.
Case 1. The vertex zj is loaded. Let h ∈ {1, . . . , q} be such that β(zj , h) + αej (Xi0 ,h ) has
the minimum value.
By the inductive assumption, there is Szj ⊆ Vzj (G) of size at most β(zj , h) such that
(i0 ) uh ∈ Sj ,
23

(ii0 ) Szj contains at most d z-vertices for each z ∈ V (Tzj ),
(iii0 ) for each z ∈ V (Tzj ), Cz = c(Szj ∩ VG (z)), and
(iv0 ) Szj dominates all the vertices of Vzj (G).
Consider Xi0 ,h = {w ∈ V (G) | w ∈ VG (ej ), Mw ∩ (Mvi0 ∪ Muh ) = ∅}. Notice that if w
is a ej -vertex and w ∈
/ Xi0 ,h , then w is dominated either by vi0 ∈ Sx or uh ∈ Szj , i.e., w is
dominated by Sx ∪ Szj . By the definition of αej (Xi0 ,h ), there is a set Sxzj of ej -vertices of
size αej (Xi0 ,h ) that dominates Xi0 ,h .
Case 2. The vertex zj is unloaded. Let h ∈ {1, . . . , q} be such that γ(zj , h) + αej (Yi0 ,h ) has
the minimum value.
By the inductive assumption, there is Szj ⊆ Vzj (G) of size at most γ(zj , h) such that
(v0 ) uh+1 , . . . , uq are dominated by Szj ,
(vi0 ) Szj contains at most d z-vertices for each z ∈ V (Tzj ),
(vii0 ) for each z ∈ V (Tzj ), Cz = c(S ∩ VG (z)), and
(viii0 ) Szj dominates all the vertices of Vzj (G) \ {u1 , . . . , uq }.
0
0
( Recall that we defined Yi = {w ∈ V (G) | w ∈ VG (ej ), Mw ∩ Mvi0 = ∅} and Yi ,h =
Yi0
if h = 0,
If w is a ej -vertex and w ∈
/ Xi0 ,h , then w is dominated by vi0 ∈ Sx ,
Yi0 ∪ {uh } if h > 0.
i.e., w is dominated by Sx ∪ Szj . By the definition of αej (Yi0 ,h ), there is a set Sxzj of ej vertices of size αej (Yi0 ,h ) that dominates Yi0 ,h . This set dominates the ej -vertices that are not
dominated by Sx and the zj -vertices u1 , . . . , uh if h ≥ 1 that are the only vertices of Vzj (G)
that (possibly) are not dominated by Szj .

Now we let
S = Sx ∪ (

s
[

(Szj ∪ Sxzj )).

j=1

We have that (i)–(iv) are fulfilled for S. It remains to notice that |S| ≤ β(x, i) by the
definition.
Assume now that S ⊆ Vx (G) is a set of minimum size satisfying (i)–(iv) and S is extendable. Since S is a set of minimum size satisfying these conditions, as we already proved,
|S| ≤ β(x, i). We prove that |S| ≥ β(x, i).
We consider the partition (Sx , Sz1 , . . . , Szs , Sxz1 , . . . , Sxzs ) of S, where Szj ⊆ Vzj (G) and
Sxzj are ej -vertices for j ∈ {1, . . . , s}; some sets in the partition could be empty.
Let t = |Sx |. For each j ∈ {1, . . . , s}, select vi(j) ∈ Sx to be a maximum with respect
to the relation ej element of Sx . Observe that the selection is not necessarily unique.
We consider a partition P = {J1 , . . . , Jt } of {0, 1, . . . , s} such that 0 ∈ J1 and it holds
that j, j 0 ∈ {1, . . . , s} are in the same set of P if and only if i(j) = i(j 0 ). We define
24

ϕ : {1, . . . , t} → Cx as follows. If Jh 6= ∅, then ϕ(h) = c(vi(j) ) for j ∈ Jh . Then we extent
ϕ on h ∈ {1, . . . , t} with Jt = ∅ greedily to ensure that ϕ is a surjection. Such a mapping
always exists because Cx = c(Sx ∩ VG (x)).
Consider zj for j ∈ {1, . . . , s}. It is assumed again Wj = {u1 , . . . , uq } is the set of zj vertices of G. We also assume that u1 ej . . . ej uq . Let j ∈ Ji0 . We consider two cases
depending on whether zj is loaded or not.
Case 1. The vertex zj is loaded. Let h ∈ {1, . . . , q} be such that uh is a minimum with
respect to ej element of Szj . By our inductive assumption, we have that β(zj , h) ≤ |Szj |,
because Szj is extendable. Consider Xi(j),h = {w ∈ V (G) | w ∈ VG (ej ), Mw ∩ (Mvi(j) ∪
Muh ) = ∅}. By the definition of i(j) and h, the vertices of Xi(j),h are not dominated by
Sx ∪ Szj . Therefore, they are dominated by Sxzj . By the definition of αej , we have that
αej (Xi(j),h ) ≤ |Sxzj |. Then
δj (x, i(j)) = min
{β(zj , h0 ) + αej (Xi0 ,h0 )} ≤ β(zj , h) + αej (Xi(j),h ) ≤ |Szj | + |Sxzj |.
0
1≤h ≤q

(7)

Case 2. The vertex zj is unloaded. Let h ∈ {0, . . . , q} be the minimum integer such that
uh+1 , . . . , uq are dominated by Szj . Clearly, if h > 0, then uh is not nominated by Szj . By the
inductive assumption, we have that β(zj , h) ≤ |Szj | as Szj is extendable. Consider the set
Yi(j),h . By the definition of this set, we obtain that the vertices of Xi(j),h are not dominated
by Sx ∪ Szj . Therefore, they are dominated by Sxzj . By the definition of αej , we have that
αej (Yi(j),h ) ≤ |Sxzj |. Then
δj (x, i(j)) = min
{γ(zj , h0 ) + αej (Yi0 ,h0 )} ≤ γ(zj , h) + αej (Yi(j),h ) ≤ |Szj | + |Sxzj |.
0

(8)

Now we combine (7) and (8) and conclude that for each h0 ∈ {1, . . . , t},
X
(|Szj | + |Sxzj |),
δJh0 (x, i0 ) ≤

(9)

0≤h ≤q

j∈Jh0

where i0 = i(j) for j ∈ Jh0 .
By (1) and (9), we obtain that
β(x, i) ≤ |Sx | +

s
X

(|Szj | + |Sxzj |) = |S|.

j=1

Our next aim is to prove Claim B for γ. Assume that x is unloaded and let i ∈ {0, . . . , p}.
We suppose that γ(x, i) < +∞ and prove that there is a set S ⊆ Vx (G) with |S| ≤ γ(x, i)
such that
(v) vi+1 , . . . , vp are dominated by S,
(vi) S contains at most d z-vertices for each z ∈ V (Tx ),
25

(vii) for each z ∈ V (Tx ), Cz = c(S ∩ VG (z)), and
(viii) S dominates all the vertices of Vx (G) \ {v1 , . . . , vp }.
P
Since γ(x, i) < +∞, γ(x, i) = sj=1 η(j). Recall that η(j) is computed differently depending on whether zj is loaded or not. We consider each j ∈ {1, . . . , s} and analyze the
corresponding cases. Recall that vij , . . . , vijp is the ordering of the vertices of W with respect
1
to ej .
Case 1. The vertex zj is loaded.
We select t ∈ {1, . . . , p + 1} for which the minimum achieved in (3), that is, ψ(j) = t. In
particular, we have that it holds
η(j) = min (β(zj , h) + αej (Xh,t )),
1≤h≤q

where
Xh,t =

(
Xh ∪ {vij , . . . , vijp }
t

Xh

(10)

if t ≤ p,
if t = p + 1

and Xh = {w ∈ V (G) | w ∈ VG (ej ), Mw ∩ Muh = ∅}. Let h ∈ {1, . . . , q} be such that the
minimum in the right part of (10) is achieved for this value.
By the inductive assumption, there is a set Szj ⊆ Vzj (G) of size at most β(zj , h) such
that
(i0 ) uh ∈ Sj ,
(ii0 ) Szj contains at most d z-vertices for each z ∈ V (Tzj ),
(iii0 ) for each z ∈ V (Tzj ), Cz = c(Szj ∩ VG (z)), and
(iv0 ) Szj dominates all the vertices of Vzj (G).
By the definition of αej (Xh,t ), there is a set of ej vertices Sxzj of size αej (Xh,t ) that dominates
Xh,t . Note that |Szj | + |Sxzj | ≤ η(j). Observe also that Szj ∪ Sxzj dominates all vertices of
Vzj (G) and the ej -vertices.
Case 2. The vertex zj is unloaded.
We select t ∈ {1, . . . , p + 1} for which the minimum achieved in (5), that is, ψ(j) = t. In
particular, we have that it holds
η(j) = min (γ(zj , h) + αej (Yh,t )),
1≤h≤q

where
Yh,t =

(
Yh ∪ {vij , . . . , vijp }
t

Yh

if t ≤ p,
if t = p + 1,

26

(11)

and

(
{w ∈ V (G) | w ∈ VG (ej )}
Yh =
{w ∈ V (G) | w ∈ VG (ej )} ∪ {u1 , . . . , uh }

if h = 0,
if h ≥ 1.

Let h ∈ {1, . . . , q} be such that the minimum in the right part of (11) is achieved for this
value.
By the inductive assumption, there is a set Szj ⊆ Vzj (G) of size at most γ(zj , h) such
that
(v0 ) uh+1 , . . . , uq are dominated by Szj ,
(vi0 ) Szj contains at most d z-vertices for each z ∈ V (Tzj ),
(vii0 ) for each z ∈ V (Tzj ), Cz = c(Szj ∩ VG (z)), and
(viii0 ) Szj dominates all the vertices of Vx (G) \ {u1 , . . . , uq }.
By the definition of αej (Yh,t ), there is a set of ej vertices Sxzj of size αej (Yh,t ) that dominates
Yh,t . We have that |Szj | + |Sxzj | ≤ η(j). Notice that Szj ∪ Sxzj dominates all vertices of
Vzj (G) and the ej -vertices.
Now we define
S = ∪sj=1 (Szj ∪ Sxzj ).
We have that
|S| =

s
X

(|Szj | + |Sxzj |) ≤

j=1

s
X

η(j) = γ(x, i).

j=1

By the definition of S, we have that (vi)–(viii) are fulfilled. To show (v), recall that γ(x, i) <
+∞. Then for each h ∈ {i + 1, . . . , p}, there is j ∈ {1, . . . , s} such that vij ej vh and,
ψ(j)
therefore, vh is dominated by Sxzj .
Assume now that S ⊆ Vx (G) is a set of minimum size satisfying (v)–(viii) for x and
i ∈ {1, . . . , p} and S is extendable. Because S is a set of minimum size satisfying these
conditions, |S| ≤ γ(x, i). We show that |S| ≥ γ(x, i).
We consider the partition (Sz1 , . . . , Szs , Sxz1 , . . . , Sxzs ) of S, where Szj ⊆ Vzj (G) and Sxzj
are ej -vertices for j ∈ {1, . . . , s}; some sets in the partition could be empty. Note that since
S extendable, all the sets in the partition are extendable as well.
First, we show that η(j) ≤ |Szj | + |Sxzj | for j ∈ {1, . . . , s}.
If xj is loaded then η(j) is computed by (2). Let h ∈ {1, . . . , q} be such that uh is a
minimum with respect to ej vertex in Szj . By induction, |Szj | ≥ β(zj , h). Since the vertices
of G that are in Xh = {w ∈ V (G) | w ∈ VG (ej ), Mw ∩ Muh = ∅} are not dominated by
Szj , they are dominated by Sxzj . By the definition of αej (Xh ), |Sxzj | ≥ αej (Xh ). Therefore,
η(j) ≤ β(zj , h) + αej (Xh ) ≤ |Szj | + |Sxzj |.

27

If zj is unloaded, then η(j) is computed by (4). We find minimum h ∈ {0, . . . , q} such
that uh+1 , . . . , uq are dominated by Szj . By induction, |Szj | ≥ γ(zj , h) We consider
(
{w ∈ V (G) | w ∈ VG (ej )}
if h = 0,
Yh =
{w ∈ V (G) | w ∈ VG (ej )} ∪ {u1 , . . . , uh } if h ≥ 1,
and observe that the vertices of Yh are not dominated by Szj . Hence, the vertices of Yh are
dominated by Sxzj . By the definition of αzj (Yh ), |Sxzj | ≥ α(Yh ). Hence, η(j) ≤ γ(zj , h) +
αej (Xh ) ≤ |Szj | + |Sxzj |.
P
Since η(j) ≤ |Szj | + |Sxzj | for all j ∈ {1, . . . , s}, we have that if γ(x, i) = sj=1 η(j), then
γ(x, i) =

s
X
j=1

s
X
η(j) ≤
(|Szj | + |Sxzj |) = |S|.
j=1

Ps

Suppose now that γ(x, i) 6= j=1 η(j). By (6), we have that there is h0 ∈ {i + 1, . . . , p}
such that vh0 ≺ej vij for all j ∈ {1, . . . , s}. The vertex vh0 is dominated by S by the
ψ(j)

condition (v). Assume that vh0 is dominated by Szj ∪ Sxzj for j ∈ {1, . . . , s}. Let vh0 = vitt
according to the ordering of x-vertices with respect to ej . We again consider two cases.
Case 1. The vertex zj is loaded.
By (3), η(j) < min1≤h≤q (β(zj , h)+αej (Xh,t )), where Xh = {w ∈ V (G) | w ∈ VG (ej ), Mw ∩
Muh = ∅} and
(
Xh ∪ {vij , . . . , vijp } if t ≤ p,
t
Xh,t =
Xh
if t = p + 1.
Let h ∈ {1, . . . , q} be such that uh is a minimum with respect to ej vertex in Szj . By
induction, |Szj | ≥ β(zj , h). Since the ej -vertices of G that are in Xh,t are not dominated by
Szj , they are dominated by Sxzj . By the definition of αej (Xh,t ), |Sxzj | ≥ αej (Xh,t ). It means
that η(j) < |Szj | + |Sxzj |.
Let h∗ ∈ {1, . . . , q} be such that the minimum in the right part of (10) is achieved for
this value, that is, η(j) = β(zj , h) + αej (Xh∗ ). By the inductive assumption, there is a set
Sz0 j ⊆ Vzj (G) of size at most β(zj , h∗ ) such that
(i0 ) uh∗ ∈ Sj0 ,
(ii0 ) Sz0 j contains at most d z-vertices for each z ∈ V (Tzj ),
(iii0 ) for each z ∈ V (Tzj ), Cz = c(Szj ∩ VG (z)), and
(iv0 ) Sz0 j dominates all the vertices of Vzj (G).
0
By the definition of αej (Xh∗ ), there is a set of ej vertices Sxz
of size αej (Xh∗ ) that dominates
j
0
0
Xh∗ . Note that |Szj | + |Sxzj | ≤ η(j). Observe also that Szj ∪ Sxz
dominates all vertices of
j
0
0
0
Vzj (G) and the ej -vertices. Let S = Szj ∪ Sxzj ∪ {v1 }. This set dominates all the vertices of
Vx (G). Note that |S 0 | ≤ |Szj ∪ Sxzj |.

28

Case 2. The vertex zj is unloaded.
By (5), η(j) < min1≤h≤q (γ(zj , h) + αej (Yh,t )), where
(
Yh ∪ {vij , . . . , vijp } if t ≤ p,
t
Yh,t =
Yh
if t = p + 1,
and

(
{w ∈ V (G) | w ∈ VG (ej )}
Yh =
{w ∈ V (G) | w ∈ VG (ej )} ∪ {u1 , . . . , uh }

if h = 0,
if h ≥ 1.

Let h ∈ {0, . . . , q} be the minimum index such that uh+1 , . . . , uq are dominated by Szj .
By induction, |Szj | ≥ γ(zj , h). Since the vertices of G that are in Yh,t are not dominated by
Szj , they are dominated by Sxzj . By the definition of αej (Xh,t ), |Sxzj | ≥ αej (Xh,t ). It means
that η(j) < |Szj | + |Sxzj |.
Let h∗ ∈ {1, . . . , q} be such that the minimum in the right part of (11) is achieved for
this value, that is, η(j) = γ(zj , h∗ ) + αej (Yh∗ ). By the inductive assumption, there is a set
Sz0 j ⊆ Vzj (G) of size at most γ(zj , h∗ ) such that
(v0 ) uh∗ +1 , . . . , uq are dominated by Szj ,
(vi0 ) Szj contains at most d z-vertices for each z ∈ V (Tzj ),
(vii0 ) for each z ∈ V (Tzj ), Cz = c(Szj ∩ VG (z)), and
(viii0 ) Szj dominates all the vertices of Vx (G) \ {u1 , . . . , uq }.
0
of size αej (Yh∗ ) that dominates
By the definition of αej (Xh ), there is a set of ej vertices Sxz
j
0
0
dominates all vertices of
Yh∗ . Note that |Szj | + |Sxzj | ≤ η(j). Observe also that Szj ∪ Sxz
j
0
0
0
Vzj (G) and the ej -vertices. Let S = Szj ∪ Sxzj ∪ {v1 }. This set dominates all the vertices of
Vx (G). Note that |S 0 | ≤ |Szj ∪ Sxzj |.

Now we use the obtained in both cases set S 0 to obtain a contradiction with the extendability of S. The set S is extendable, that is, there is a dominating set D of G such
that
(a) D has at most d x-vertices for x ∈ V (T ),
(b) for each x ∈ V (T ), Cx ⊆ c(D ∩ VG (x)),
that has the minimum size and contains C and the conditions of the promise is fulfilled:
the number of nodes z ∈ V (T ) such that D contains an z-vertex is maximum and for each
z ∈ V (T ), Cz = c(D ∩ VG (z)). Let D0 = (D \ (Szi ∪ Sxzj )) ∪ S 0 . It is straightforward to see
that D is a dominating set and |D0 | ≤ |D|. We also have that (a) and (b) are fulfilled for
D0 , because of (ii0 ), (iii0 ), (vi0 ) and (vii0 ), but this contradicts the condition that the number
of nodes x ∈ V (T ) such that DP
contains an x-vertex is maximum because D0 contains the
s
x-vertex v1 . Hence, γ(x, i) 6=
j=1 η(j) and this completes the proof of the claim that
|S| ≥ γ(x, i).
29

Now we are ready to complete the description of our algorithm for Dominating Set
Extension. The algorithm computes the table of values of β(r, i) if r is loaded and the
table of values of γ(r, i) if r is unloaded. If r is loaded, we find the minimum value β(r, i∗ )
in the table for i. By Claim B, if β(r, i∗ ) < +∞, then G has a dominating set S of size
at most β(r, i∗ ) containing at most d x-vertices for x ∈ V (T ) such that for each x ∈ V (T ),
Cx = c(S ∩ VG (x)). Moreover, if the promise is true, then β(r, i∗ ) < +∞ and the minimum
size of S is β(r, i∗ ). If r is unloaded, then we consider γ(r, 0) in the table for r. By Claim B,
if γ(r, 0) < +∞, then G has a dominating set S of size at most γ(r, 0) containing at most d
x-vertices for x ∈ V (T ) such that for each x ∈ V (T ), Cx = c(S ∩ VG (x)), and if the promise
is true, then γ(r, 0) < +∞ and the minimum size of S is γ(r, 0). It remains to check whether
β(r, i∗ ) ≤ k or γ(r, 0) ≤ k respectively and return the answer.
To evaluate the running time, observe that to compute β(x, i), we consider all possible
partitions P = {J1 , . . . , Jt } for 1 ≤ t ≤ d of {0, 1, . . . , s} into non-empty sets such that 0 ∈ J1
where s is the number of children of x. Since s ≤ `, we have that the number of partitions
is 2O(` log d) . Then for each partition P = {J1 , . . . , Jt }, we consider all possible surjections
ϕ : {1, . . . , t} → Cx . Since t ≤ d and each |Cx | ≤ d, there are 2O(d log d) choices of ϕ. Because
each value of α and γ can be computed in polynomial time, it implies that the total running
time of the algorithms is 2O((`+d) log d) nO(1) .
Now we are ready to prove the main theorem of the section.
2

Theorem 9. Dominating Set can be solved in time 2O(` ) · nO(1) for connected chordal
graphs with leafage at most `.
Proof. Let (G, k) be an instance of Dominating Set where G is a connected chordal graph.
We use the algorithm of Habib and Stacho [HS09] to compute its leafage `(G). If `(G) > `,
we stop and return a no-answer. Otherwise, we consider the clique tree T 0 of G constructed
by the algorithm. We construct the tree T from T 0 by dissolving nodes of degree two, that
is, for a node x of degree two with the neighbors y and z, we delete x and make y and z
adjacent. Observe that since T is a tree with at most ` leaves that has no node of degree
two, |V (T )| ≤ 2` − 2. We have that G is a T -graph. Note also that the algorithm of Habib
and Stacho [HS09] gives us a T -representation M = {Mv }v∈V (G) where Mv ∈ V (T 0 ) for
v ∈ V (G).
We consider 2|V (T )| − 1 ≤ 22`−2 − 1 nonempty subsets of V (T ) and construct a coloring
c : VG (T ) → {1, . . . , 2|V (T )| } such that for u, v ∈ VG (T ), c(u) = c(v) if and only if u and v are
U -vertices for the same U ⊆ V (T ).
By Lemma 4, a minimum dominating set of G contains at most 3|V (T )| − 2 ≤ 6` − 8
vertices of VG (T ). Clearly, these vertices can have at most 6` − 8 distinct colors. We consider
all sets C ⊆ {1, . . . , 2|V (T )| } of distinct colors of size at most 6` − 8 and for each C, we aim to
find a minimum dominating set of G whose vertices in VG (T ) are colored by the maximum
number of distinct colors and are colored exactly by the colors of C. Since we consider all
possible choices of C, it holds for some C.
Toward this aim, we apply the following rule.
30

Rule 1. If there is an xy-vertex w of G for xy ∈ E(T ) such that i) x, y ∈
/ Mu for u ∈ VG (T )
with c(u) ∈ C and ii) there is v ∈ VG (T ) such that x, y ∈ Mv , then discard the current choice
of C.
To see that the rule is safe, observe that if D is minimum dominating set of G whose
vertices in VG (T ) are colored exactly by the colors of C, then w is dominated by some xyvertex w0 . We have that v ∈
/ D, because c(v) ∈
/ C. Then it is straightforward to see that
D0 = (D \ {w0 }) ∪ {v} is a minimum dominating set of G whose vertices in VG (T ) are colored
by |C| + 1 colors.
Now we are looking for a dominating set D of minimum size such that c(D ∩ VG (T )) = C.
We use the following rule.
Rule 2. If there is a U -vertex u of G for nonempty U ⊆ V (T ) such that i) c(u) ∈
/ C and ii)
there is c ∈ C such that for every v ∈ VG (T ) with c(v) = c, v dominates u, then delete u.
To see that the rule is safe, observe that u cannot be included in a dominating set D
of minimum size such that c(D ∩ VG (T )) = C and u is dominated by any set D such that
c(D ∩ VG (T )) = C.
Let
A = {xy ∈ E(T ) | x, y ∈ Mu for u ∈ VG (T ), c(u) ∈ C}
A0 = {xy ∈ E(T ) | x, y ∈ Mu for u ∈ VG (T ), c(u) ∈
/ C and x, y ∈
/ Mv for v ∈ VG (T ), c(v) ∈ C}.
Observe that because of Rule 1, there is no e-vertex for e ∈ A0 . We contract the edges
e ∈ A ∪ A0 . Denote by T̂ the tree obtained from T tree and let T̂ 0 be the tree obtained from
T 0 by contracting the paths that correspond to the contracted edge. We also construct the
graph Ĝ that is obtained from G by contracting these edges of T and we also construct its
T̂ -representation M̂ = {M̂v }v∈V (Ĝ) where M̂v ∈ V (T̂ 0 ) for v ∈ V (Ĝ). We set ĉ = c|V (Ĝ) and
let Cx = {c | there is u ∈ VĜ (T̂ ) with ĉ(u) = c} for x ∈ V (Ĝ). Observe that M̂ is a nice
T̂ -representation of Ĝ. Indeed, for every xy ∈ E(T ) such that x, y ∈ Mu for u ∈ VG (T ) we
have that xy ∈ A if c(u) ∈ C and xy ∈ A0 if c(u) ∈
/ C because of Rule 2, and all such edges
xy are contracted.
Combining Lemmas 5 and 6 we obtain that D is a dominating set of minimum size with
C = c(D ∩ VG (T )) if and only if D is a dominating set of G0 of minimum size such that
C = ĉ(D ∩ VĜ (T̂ )). Note that the condition C = ĉ(D ∩ VĜ (T̂ )) is equivalent to the condition
that for every x ∈ V (T̂ ), Cx = ĉ(D ∩ VĜ (x)), because the T̂ -representation of Ĝ is nice and
Cx ∩ Cy = ∅ for distinct x, y ∈ V (T̂ ).
We set d = |V (T )| + ` − 1 ≤ 3` − 3 and apply the next rule.
Rule 3. If there is x ∈ V (T̂ ) with |Cx | > d, then discard the current choice of C.
To see that the rule is safe, assume that the input graph G has a minimum dominating
set D whose vertices in VG (T ) are colored exactly by the colors of C. By Lemma 3, we have
that if a set of nodes X of T is contracted into a single vertex x of T̂ , then D has at most
|X|+`−1 vertices whose models contain a vertex of X and, therefore, the number of vertices
colored by the colors of Cx in D is at most d.
31

We select arbitrarily a node r to be the root of T̂ and T̂ 0 respectively. Then we apply
Lemma 7 for the instance (T̂ , k, d, ĉ, {Cx }x∈V (T̂ ) ) of Dominating Set Extension.
Recall that Dominating Set Extension is a promise problem. If the algorithm from
Lemma 7 returns a yes-answer, it means that there is a dominating set D of Ĝ of size at
most k such that for each x ∈ V (T̂ ), Cx = c(D ∩ VĜ (x)). It means that the input graph G
has a dominating set of size at most k. Still, if the promise is false, the algorithm can return
an incorrect no-answer. Recall that the promise of Dominating Set Extension is the
following: for a dominating set D of Ĝ of minimum size with the properties that
(a) D has at most d x-vertices for x ∈ V (T̂ ),
(b) for each x ∈ V (T̂ ), Cx ⊆ c(D ∩ VG (x̂)),
it holds that the number of nodes x ∈ V (T̂ ) such that D contains an x-vertex is maximum
and for each x ∈ V (T̂ ), Cx = c(D ∩ VG (x̂)). By Lemmas 5 and 6, we have that if C is chosen
in such a way that G has a minimum dominating set D that has the maximum number
of vertices of VG (T ) and whose vertices in VG (T ) are colored exactly by the colors of C,
then this promise holds for the corresponding instance of Dominating Set Extension
constructed for this choice of C. Therefore, if (G, k) is a yes-instance of Dominating Set,
then for some choice of C, we obtain a yes-answer.
To evaluate the running time of the algorithm, observe that T , T 0 and the representation
M are constructed in polynomial time by the algorithm of Habib and Stacho [HS09]. The
coloring function c : VG (T ) → {1, . . . , 2|V (T )| } can be constructed in time 2O(`) · nO(1) . Then
2
we construct 2O(` ) sets C ⊆ {1, . . . , 2|V (T )| } of size at most 6` − 8 and it can be done in
2
time 2O(` ) . For each C, the Rules 1 and 2 can be applied in polynomial time. Similarly,
the construction of the instance (T̂ , k, d, ĉ, {Cx }x∈V (T̂ ) ) of Dominating Set Extension
for a given C can be done in polynomial time. Clearly, Rule 3 can be applied in polynomial
time. Then we solve the constructed instance of Dominating Set Extension in time
2
2O(` log `) · nO(1) . Hence, the total running time of the algorithm is 2O(` ) · nO(1) .
The theorem immediately gives the following corollary for T -graphs.
2

Corollary 5. Dominating Set can be solved in time 2O(|V (T )| ) · nO(1) for T -graphs if T is
a tree.

5.3

A polynomial kernel for Clique

It was observed in [CZ17] that the Clique problem is FPT for H-graphs when parameterized
by the solution size k and kHk (even when no H-representation of G is given). We show
that Clique admits a polynomial kernel.
Let G be an H-graph with an H-representation M = {Mv }v∈V (G) where Mv ⊆ V (H 0 ) for
the corresponding subdivision H 0 of H. Recall that for e ∈ E(H), v ∈ V (G) is an e-vertex if
Mv contains only subdivision nodes of H 0 from the path in H 0 corresponding to e in H. We
claim that we can find a maximum clique in G that contains some e-vertex in polynomial
time.
32

Lemma 8. Let G be an H-graph given together with its H-representation. Then a clique of
maximum size that contains at least one e-vertex for some e ∈ E(G) can be found in time
O(n3/2 m).
Proof. Let M = {Mv }v∈V (G) be an H-representation of G. For each e-vertex u of G, we find
a maximum clique K such that Mu is inclusion minimal for K, that is, there is no v ∈ K
with Mv ⊂ Mu . Let e = xy for x, y ∈ V (H) and denote by P the (x, y)-path corresponding
to e in the subdivision H 0 of G. Since u is an e-vertex, Mu ⊆ V (P ), that is, the vertices of
Mu form a subpath of P . Denote by x0 and y 0 the end-vertices of the subpath. Note that it
can happen that x0 = y 0 . Because Mu is inclusion maximal model of a vertex of K, for every
v ∈ K, x0 ∈ Mv or y 0 ∈ Mv . Consider U = {v ∈ V (G) | x0 ∈ Mv or y 0 ∈ Mv }. We have that
finding K in G is equivalent to finding a maximum clique containing u in G0 = G[U ].
Notice that U can be partitioned into two cliques K1 = {v ∈ V (G) | x0 ∈ Mv } and
K2 = {v ∈ V (G) | y 0 ∈ Mv and x0 ∈
/ Mv }. It means that G0 √
is a cobipartite graph. A
maximum clique in a cobipartite graph can be found in time O( nm) by the algorithm of
Hopcroft and Karp [HK73] as finding a maximum clique in G0 is equivalent to finding a
maximum independent set in the complement of G0 that is a bipartite graph. Note that a
maximum clique in G0 always contains u, because u is adjacent to every other vertex of G0 .
Since we consider all e-vertices to find a maximum clique containing some e-vertex for
some e ∈ E(H), the total running time is O(n3/2 m).
Now we a ready to construct our kernel.
Theorem 10. The Clique problem for H-graphs admits a kernel with at most (k−1)|V (H)|
vertices if an H-representation of the input graph is given.
Proof. Let G be an H-graph with an H-representation M = {Mv }v∈V (G) where Mv ⊆ V (H 0 )
for the corresponding subdivision H 0 of H.
First, we use Lemma 8 to check whether G has a clique of size at least k that contains
at least one e-vertex for some e ∈ E(G). If we find such a clique we return a yes-answer.
Assume that this is not the case. Let G0 be the graph obtained from G by the deletion of
all e-vertices for e ∈ E(H). We have that G has a clique of size at least k if and only if G0
has a clique of size at least k.
If there is x ∈ V (H) such that Vx = {v ∈ V (G0 ) | x ∈ Mv } has size at least k, then it
is a clique of size at least k and we return a yes-answer. Otherwise, we return G0 . Clearly,
|V (G0 )| ≤ (k − 1)|V (H)| in this case.

Acknowledgments
We thank Saket Saurabh for bringing H-graphs to our attention.

33

6

References

[BBC99]

Anne Berry, Jean-Paul Bordat, and Olivier Cogis. Generating All the Minimal Separators of a Graph, pages 167–172. Springer Berlin Heidelberg, Berlin,
Heidelberg, 1999.

[BHT92]

M. Biró, M. Hujter, and Zs. Tuza. Precoloring extension. I. Interval graphs.
Discrete Mathematics, 100(1):267 – 279, 1992.

[BJ82]

Kellogg S. Booth and J. Howard Johnson. Dominating sets in chordal graphs.
SIAM Journal on Computing, 11(1):191–199, 1982.

[BT01]

Vincent Bouchitté and Ioan Todinca. Treewidth and minimum fill-in: Grouping
the minimal separators. SIAM Journal on Computing, 31(1):212–232, 2001.

[BV10]

Rémy Belmonte and Martin Vatshelle. On graph classes with logarithmic
boolean-width. arXiv preprint, 2010. arXiv:1009.0216.

[BV13]

Rémy Belmonte and Martin Vatshelle. Graph classes with structured neighborhoods and algorithmic applications. Theoretical Computer Science, 511:54 – 65,
2013.

[BXTV11] Binh-Minh Bui-Xuan, Jan Arne Telle, and Martin Vatshelle. Boolean-width of
graphs. Theoretical Computer Science, 412(39):5187 – 5204, 2011.
[BXTV13] Binh-Minh Bui-Xuan, Jan Arne Telle, and Martin Vatshelle. Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems.
Theoretical Computer Science, 511:66 – 76, 2013. Exact and Parameterized
Computation.
[CFK+ 15] Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Dániel Lokshtanov, Daniel
Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized
Algorithms. Springer, 2015.
[CTVZ17] Steven Chaplick, Martin Töpfer, Jan Vobornı́k, and Peter Zeman. On
H-topological intersection graphs. In International Workshop on GraphTheoretic Concepts in Computer Science, pages 167–179. Springer, 2017.
arXiv:1608.02389.
[CZ17]

Steven Chaplick and Peter Zeman. Combinatorial problems on H-graphs. In
The European Conference on Combinatorics, Graph Theory and Applications
(EUROCOMB’17), Electronic Notes in Discrete Mathematics, volume 61, pages
223 – 229, 2017. arXiv:1706.00575.

[DF13]

Rodney G. Downey and Michael R. Fellows. Fundamentals of Parameterized
Complexity. Texts in Computer Science. Springer, 2013.
34

[FHRV09] Michael R. Fellows, Danny Hermelin, Frances A. Rosamond, and Stéphane
Vialette. On the parameterized complexity of multiple-interval graph problems.
Theor. Comput. Sci., 410(1):53–61, 2009.
[FTV15]

Fedor V. Fomin, Ioan Todinca, and Yngve Villanger. Large induced subgraphs
via triangulations and CMSO. SIAM J. Comput., 44(1):54–87, February 2015.
arXiv:1309.1559.

[Gav72]

Fănică Gavril. Algorithms for minimum coloring, maximum clique, minimum
covering by cliques, and maximum independent set of a chordal graph. SIAM J.
Comput., 1(2):180–187, 1972.

[Gav74]

Fănică Gavril. The intersection graphs of subtrees in trees are exactly the chordal
graphs. J. Combinatorial Theory Ser. B, 16:47–56, 1974.

[Gol04]

Martin Charles Golumbic. Algorithmic graph theory and perfect graphs, volume 57 of Annals of Discrete Mathematics. Elsevier Science B.V., Amsterdam,
second edition, 2004. With a foreword by Claude Berge.

[HK73]

John E. Hopcroft and Richard M. Karp. An n5/2 algorithm for maximum
matchings in bipartite graphs. SIAM J. Comput., 2(4):225–231, 1973.

[HS09]

Michel Habib and Juraj Stacho. Polynomial-time algorithm for the leafage of
chordal graphs. In Algorithms - ESA 2009, 17th Annual European Symposium,
Copenhagen, Denmark, September 7-9, 2009. Proceedings, volume 5757 of Lecture Notes in Computer Science, pages 290–300. Springer, 2009.

[JKT17a]

L. Jaffke, O. Kwon, and J. A. Telle. A note on the complexity of Feedback Vertex Set parameterized by mim-width. arXiv preprint, November 2017.
arXiv:1711.05157.

[JKT17b]

Lars Jaffke, O-joung Kwon, and Jan Arne Telle. Polynomial-time algorithms
for the longest induced path and induced disjoint paths problems on graphs of
bounded mim-width. arXiv preprint, 2017. arXiv:1708.04536.

[KBMK93] Ton Kloks, H Bodlaender, Haiko Müller, and Dieter Kratsch. Computing
treewidth and minimum fill-in: All you need are the minimal separators. Algorithms—ESA’93, pages 260–271, 1993.
[Pie03]

Krzysztof Pietrzak. On the parameterized complexity of the fixed alphabet
shortest common supersequence and longest common subsequence problems. J.
Comput. Syst. Sci., 67(4):757–771, 2003.

[RS08]

Venkatesh Raman and Saket Saurabh. Short cycles make W[1]-hard problems
hard: FPT algorithms for W[1]-hard problems in graphs with no short cycles.
Algorithmica, 52(2):203–225, 2008.

35

