# Domination and Cut Problems on Chordal Graphs with Bounded Leafage

Esther Galby  CISPA Helmholtz Center for Information Security, Germany  Dániel
Marx  CISPA Helmholtz Center for Information Security, Germany  Philipp
Schepper  CISPA Helmholtz Center for Information Security, Germany  Roohani
Sharma  Max Planck Institute for Informatics, SIC, Saarbrücken, Germany
Prafullkumar Tale  CISPA Helmholtz Center for Information Security, Germany

###### Abstract

The leafage of a chordal graph $G$ is the minimum integer $\ell$ such that $G$
can be realized as an intersection graph of subtrees of a tree with $\ell$
leaves. We consider structural parameterization by the leafage of classical
domination and cut problems on chordal graphs. Fomin, Golovach, and Raymond
[ESA $2018$, Algorithmica $2020$] proved, among other things, that Dominating
Set on chordal graphs admits an algorithm running in time
$2^{\mathcal{O}(\ell^{2})}\cdot n^{\mathcal{O}(1)}$. We present a conceptually
much simpler algorithm that runs in time $2^{\mathcal{O}(\ell)}\cdot
n^{\mathcal{O}(1)}$. We extend our approach to obtain similar results for
Connected Dominating Set and Steiner Tree. We then consider the two classical
cut problems MultiCut with Undeletable Terminals and Multiway Cut with
Undeletable Terminals. We prove that the former is W[1]-hard when
parameterized by the leafage and complement this result by presenting a simple
$n^{\mathcal{O}(\ell)}$-time algorithm. To our surprise, we find that Multiway
Cut with Undeletable Terminals on chordal graphs can be solved, in contrast,
in $n^{{\mathcal{O}}(1)}$-time.

##  1 Introduction

The intersection graph of a family $\mathcal{F}$ of nonempty sets is the graph
whose vertices are the elements of $\mathcal{F}$ with two vertices being
adjacent if and only if their corresponding sets intersect. The most natural
and famous example of such intersection graphs are _interval graphs_ where
$\mathcal{F}$ is a collection of subpaths of a path. Due to their
applicability in scheduling, interval graphs have received a considerable
attention in the realm of algorithmic graph theory. One useful
characterization of an interval graph is that its maximal cliques can be
linearly ordered such that for every vertex, the maximal cliques containing
that vertex occur consecutively [24]. This property proves very useful for the
design of polynomial-time dynamic programming based or greedy algorithms on
interval graphs.

Consider the generalization where $\mathcal{F}$ is a collection of subtrees of
a tree instead of subpaths of a path. In this case, the corresponding class of
intersection graphs is exactly that of _chordal graphs_ [45, 23, 9]. Recall
that a graph is chordal if every cycle of length at least $4$ has a chord.
Often, the algorithms of the types mentioned in the previous paragraph fail to
generalize to this superclass as witnessed by the following problems that
admit polynomial-time algorithms on interval graphs but are -complete on
chordal graphs: Dominating Set [11, 7], Connected Dominating Set [3, 46],
Steiner Tree [3, 46], Multicut with Undeletable Terminals [27, 42], Subset
Feedback Vertex Set (Subset FVS) [43, 20], Longest Cycle [32, 26]111See
Exercise $2$ in Chapter $6$ in [26]., Longest Path [31], Component Order
Connectivity [18], $s$-Club Contraction [25], Independent Set Reconfiguration
[5], Bandwidth [34], Cluster Vertex Deletion [33]. Also, Graph Isomorphism on
chordal graphs is polynomial-time equivalent to the problem on general graphs
whereas it admits a linear-time algorithm on interval graphs [38].

The problems above remain hard even on _split graphs_ , another well-studied
subclass of chordal graphs. A graph is a split graph if its vertex set can be
partitioned into a clique and an independent set. The collection of split
graphs is a (proper) subset of the class of intersection graphs where
$\mathcal{F}$ is a collection of substars of a star. As interval graphs are
intersection graphs of subpaths of a path (a tree with two leaves) and split
graphs are intersection graphs of substars of a star (a tree with arbitrary
number of leaves), a natural question to consider is what happens to these
problems on subclasses of chordal graphs that are intersection graphs of
subtrees of a tree with a bounded number of leaves. Motivated by such
questions, we consider the notion of _leafage_ introduced by Lin et al. [37]:
the leafage of a chordal graph $G$ is the minimum integer $\ell$ such that $G$
can be realized as an intersection graph of a collection $\mathcal{F}$ of
subtrees of a tree that has $\ell$ leaves. Note that the leafage of interval
graphs is at most $2$ while split graphs have unbounded leafage. Thus the
leafage measures, in some sense, how close a chordal graph is to an interval
graph. Alternately, an or algorithm parameterized by the leafage can be seen
as a generalization of the algorithm on interval graphs.

#### Related Work.

Habib and Stacho [28] showed that we can compute the leafage of a connected
chordal graph in polynomial time. Their algorithm also constructs a
corresponding _representation tree_ 222We present formal definitions of the
terms used in this section in Section 2. $T$ with the minimum number of
leaves. In recent years, researchers have studied the structural
parameterization of various graph problems on chordal graphs parameterized by
the leafage. Fomin et al. [19] and Arvind et al. [2] proved, respectively,
that the Dominating Set and Graph Isomorphism problems on chordal graphs are
parameterized by the leafage. Barnetson et al. [4] and Papadopoulos and Tzimas
[44] presented -algorithms running in time $n^{{\mathcal{O}}(\ell)}$ for Fire
Break and Subset FVS on chordal graphs, respectively. Papadopoulos and Tzimas
[44] also proved that Subset FVS is [1]-hard when parameterized by the
leafage. Hochstättler et al [30] showed that we can compute the neighborhood
polynomial of a chordal graph in $n^{{\mathcal{O}}(\ell)}$-time.

It is known that the size of _asteroidal set_ in a chordal graph is upper
bounded by its leafage [37]. See [29, 1] for the relationship between leafage
and other structural properties of chordal graphs. Kratsch and Stewart [35]
proved that we can effectively $2\ell$-approximate bandwidth of chordal graphs
of leafage $\ell$. Chaplick and Stacho [12] generalized the notion of leafage
to _vertex leafage_ and proved that, unlike leafage, it is hard to determine
the optimal vertex leafage of a given chordal graph. Figueiredo et al. [16]
proved that Dominating Set, Connected Dominating Set and Steiner Tree are on
chordal graphs when parameterized by the size of the solution plus the vertex
leafage, provided that a tree representation with optimal vertex leafage is
given as part of the input.

#### Our Results.

We consider well-studied domination and cut problems on chordal graphs. As our
first result, we prove that Dominating Set on chordal graphs of leafage at
most $\ell$ admits an algorithm running in time $2^{\mathcal{O}(\ell)}\cdot
n^{\mathcal{O}(1)}$. This improves upon the existing algorithm by Fomin et al.
[19, Theorem $9$] which runs in time $2^{{\mathcal{O}}(\ell^{2})}\cdot
n^{\mathcal{O}(1)}$. Despite being significantly simpler than the algorithm in
[19], our algorithm in fact solves the Red-Blue Dominating Set problem, a
well-known generalization of Dominating Set. In this generalized version, an
input is a graph $G$ with a partition $(R,B)$ of its vertex set and an integer
$k$, and the objective is to find a subset $D$ of $R$ that dominates every
vertex in $B$, i.e., $B\subseteq N(D)$. We further use this algorithm to solve
other related domination problems.

######  Theorem 1.1.

Dominating Set, Connected Dominating Set, and Steiner Tree can be solved in
$2^{\mathcal{O}(\ell)}\cdot n^{\mathcal{O}(1)}$ on chordal graphs of leafage
at most $\ell$.

The reductions in [7] and [46] used to prove that these problems are -complete
on chordal graphs imply that these problems do not admit $2^{o(n)}$, and hence
$2^{o(\ell)}\cdot n^{\mathcal{O}(1)}$, algorithms unless the ETH fails.

Arguably, the two most studied cut problems are MultiCut and Multiway Cut. In
the MultiCut problem, an input is graph $G$, a set of terminal pairs
$P\subseteq V(G)\times V(G)$ and an integer $k$, and the objective is to find
a subset $S\subseteq V(G)$ of size at most $k$ such that no pair of vertices
in $P$ is connected in $G-S$. In the Multiway Cut problem, instead of terminal
pairs, we are given a terminal set $P$ and the objective is to find a subset
$S\subseteq V(G)$ of size at most $k$ such that no two vertices in $P$ are
connected in $G-S$. These problems and variations of them have received a
considerable attention which lead to the development of new techniques [39,
40, 8, 14, 13]. Misra et al. [41] studied the parameterized complexity of
these problems on chordal graphs. Guo et al. [27] proved that MultiCut with
Deletable Terminals is -complete on interval graphs, thereby implying that
this problem is paraNP-hard when parameterized by the leafage. We consider the
MultiCut with Undeletable Terminals problem and prove the following result.

######  Theorem 1.2.

MultiCut with Undeletable Terminals on chordal graphs is [1]-hard when
parameterized by the leafage $\ell$ and assuming the ETH, does not admit an
algorithm running in time $f(\ell)\cdot n^{o(\ell)}$ for any computable
function $f$. However, it admits an -algorithm running in time
$n^{{\mathcal{O}}(\ell)}$.

Next, we focus on the Multiway Cut with Undeletable Terminals problem. We find
it somewhat surprising that the classical complexity of this problem on
chordal graphs was not known. Bergougnoux et al. [6], using the result in
[19], proved that the problem admits an -algorithm when parameterized by the
leafage333See the discussion after Corollary $2$ on page 1388 in [6].. Our
next result significantly improves upon this and [41, Theorem $2$] which
states that the problem admits a polynomial kernel when parameterized by the
solution size.

######  Theorem 1.3.

Multiway Cut with Undeletable Terminals can be solved in
$n^{\mathcal{O}(1)}$-time on chordal graphs.

A well-known trick to convert an instance of Multiway Cut with Deletable
Terminals into an instance of Multiway Cut with Undeletable Terminals is to
add a pendant vertex to each terminal, remove that vertex from the set of
terminals, and make the newly added vertex a terminal. As this reduction
converts a chordal graph into another chordal graph, Theorem 1.3 implies that
Multiway Cut with Deletable Terminals is also polynomial-time solvable on
chordal graphs. Another closely related problem is Subset FVS which is
-complete on split graphs [43]. To the best of our knowledge, this is the
first graph class on which the classical complexity of these two problems
differ.

Next, we revisit the problems on chordal graphs with bounded leafage and
examine how far we can generalize this class. An _asteroidal triple_ of a
graph $G$ is a set of three vertices such that each pair is connected by some
path that avoids the closed neighborhood of the third vertex. Lekkerkerker and
Boland [36] showed that a graph is an interval graph if and only if it is
chordal and does not contain an asteroidal triple. They also listed all
minimal chordal graphs that contain an asteroidal triple (see, for instance,
[10, Figure 1]). Among this list, we found the _net graph_ to be the most
natural to generalize. For a positive integer $\ell\geq 3$, we define
$H_{\ell}$ as a split graph on $2\ell$ vertices with split partition $(C,I)$
such that the only edges across $C,I$ are a perfect matching. Note that
$H_{3}$ is the net graph. As interval graphs are a proper subset of the
collection of chordal graphs that do not contain a net graph as an induced
subgraph, the collection of the chordal graph of leafage $\ell$ is a proper
subset of the collection of chordal graphs that do not contain $H_{\ell+1}$ as
an induced subgraph (see Observation 6.1). We show that, although the
considered domination problems are polynomial-time solvable for constant
$\ell$, the fixed-parameter tractability results are unlikely to extend to
this larger class.

######  Theorem 1.4.

Dominating Set, Connected Dominating Set and Steiner Tree on
$H_{\ell}$-induced-subgraph-free chordal graphs are W[1]-hard when
parameterized by $\ell$ and assuming the ETH, do not admit an algorithm
running in time $f(\ell)\cdot n^{o(\ell)}$ for any computable function $f$.
However, they all admit -algorithms running in time $n^{{\mathcal{O}}(\ell)}$.

We observe a similar trend with respect to MultiCut with Undeletable Terminals
as its parameterized complexity jumps from [1]-hard on chordal graph of
leafage $\ell$ to paraNP-hard on $H_{\ell}$-induced-subgraph-free chordal
graphs when parameterized by $\ell$.

######  Theorem 1.5.

MultiCut with Undeletable Terminals is -hard even when restricted to
$H_{3}$-induced-subgraph-free chordal graphs.

Table 1 summarises our results.

Input graph |  Dom Set, ConnDom Set, Steiner Tree |  MultiCut with UnDel Term |  MultiwayCut
---|---|---|---
Interval Graphs |  Poly-time [11, 3] |  Poly-time [27] |  Poly-time [6]
Chordal graphs of leafage $\ell$ |  $2^{{\mathcal{O}}(\ell^{2})}\cdot n^{{\mathcal{O}}(1)}$ algo [19]
$2^{{\mathcal{O}}(\ell)}\cdot n^{{\mathcal{O}}(1)}$ algo (Thm 1.1) |  [1]-hard
$n^{{\mathcal{O}}(\ell)}$ algo (Thm 1.2) |  $n^{{\mathcal{O}}(\ell)}$ algo [6]
Poly-time (Thm 1.3)
$H_{\ell}$-induced subgraph-free chordal |  [1]-hard;
$n^{{\mathcal{O}}(\ell)}$ algo (Thm 1.4) |  -hard for $\ell\geq 3$
(Thm 1.5) |  Poly-time (Thm 1.3)
Chordal graphs |  -complete [7] |  -complete [46] |  Poly-time (Thm 1.3)
Table 1: Overview of the known results and our contributions. Every graph
class mentioned in the first column is a proper subset of the graph class
mentioned below.

#### Our Methods.

We briefly discuss the methods used in our two main algorithms, namely the
algorithm for Dominating Set and the one for Multiway Cut.

##### Red-Blue Dominating Set in Chordal Graphs.

As mentioned earlier, the linear ordering of cliques in interval graphs is
particularly useful for the design of polynomial-time algorithms. Such an
ordering is not possible even if $G$ is a chordal graph whose representation
tree $T$ is a star. Consider the case where the model of every red vertex in
$G$ includes the center of the star $T$ (and possibly some leaves) and the
model of every blue vertex is (only) a leaf. We can solve this instance by
converting it to an instance of Set Cover and solving it using the algorithm
parameterized by the size of the universe. In this case, the size of the
universe is at most the number of leaves which is upper bounded by the
leafage. In the other case where the properties of red vertices and blue
vertices are reversed, we obtain a similar result by creating an equivalent
instance of Hitting Set.

These ideas can be used in a more general setting as long as the following two
properties are satisfied: (1) the model of each vertex is _local_ , that is,
it contains at most one branching node, and (2) each branching node is
contained only in models of either red vertices or blue vertices. Based on
this observation, we introduce a restricted version of the problem in which
the input graph is required to satisfy these two conditions. We then show that
the general case reduces to this restricted version: indeed, we prove that
there is a branching algorithm that constructs $2^{{\mathcal{O}}(\ell)}$ many
instances (where $\ell$ is the leafage of the input graph) of the restricted
version of the problem such that the input instance is a Yes-instance if and
only if one of these newly created instances is a Yes-instance. These two
properties ensure that the graph induced by the red and blue vertices whose
model intersect the subtree rooted at a farthest branching node (from some
fixed root) satisfies the premise of at least one of the cases mentioned in
the previous paragraph. We then present a greedy procedure, based on solving
the Set Cover and Hitting Set problems, that identifies some part of an
optimum solution. Apart from this greedy selection procedure, all other steps
of the algorithm run in polynomial time.

##### Multiway Cut in Chordal Graphs.

We give a polynomial-time algorithm for Multiway Cut on chordal graphs by
solving several instances of the $(s,t)$-Cut problem (not necessarily with
unit capacities). Our strategy is based on a bottom-up dynamic programming
(DP) on a tree representation of a chordal graph. An interesting aspect of our
DP is that we need to look-up all DP table values that are already computed to
compute a new entry. This is in contrast to typical DP-based algorithms that
do computations only based on local entries.

We remark that we do not expect to design an algorithm for Multiway Cut on
chordal graphs using much simpler arguments (like a simple dynamic programming
procedure etc.) as the problem generalizes some well-studied cut-flow based
problems. As an example, recall the Vertex Cover problem on bipartite graphs
where given a bipartite graph $G$ with bipartition $(A,B)$, the goal is to
find $A^{\prime}\subseteq A$ and $B^{\prime}\subseteq B$ such that
$|A^{\prime}\cup B^{\prime}|$ is minimum and $N(A\setminus
A^{\prime})\subseteq B^{\prime}$. The set $A^{\prime}\cup B^{\prime}$ is
called a vertex cover of $G$. The Vertex Cover problem on bipartite graphs
reduces to the Multiway Cut problem on chordal graphs: indeed, let
$G^{\prime}$ be the graph obtained from $G$ by making $B$ a clique, adding new
pendant vertex $t_{a}$ to each vertex $a\in A$, and further adding another new
vertex $t$ that is adjacent to all vertices of $B$. Then $G^{\prime}$ is a
chordal graph and letting $T=t\cup\\{t_{a}~{}|~{}a\in A\\}$, it is easy to see
that $S\subseteq V(G)$ is a vertex cover of $G$ if and only if $S$ is a
$T$-multiway-cut in $G^{\prime}$. As mentioned earlier, our algorithm solves
several instances of the $(s,t)$-Cut problem, which also sits at the heart of
some algorithms for Vertex Cover on bipartite graphs. The above reduction
suggests that an algorithm for Multiway Cut on chordal graphs using much
simpler techniques, would imply an algorithm for Vertex Cover on bipartite
graphs that uses much simpler techniques as well.

Note that a similar reduction would work from the weighted variant of the
Vertex Cover problem on bipartite graphs. This can be achieved by further
replacing each vertex of the graph $G$ by a clique of size proportional to the
weight of this vertex and making each vertex of the clique adjacent to all the
neighbors of this vertex. This reduction still preserves the chordality of the
resulting graph.

#### Organization of the Paper.

In Section 2, we define the notations and terminology used throughout the
paper. In Section 3, we present the algorithm for the generalized Red-Blue
Dominating Set problem parameterized by the leafage. In Section 4, we consider
the Multicut problem and provide the proof of Theorem 1.2. We present the
polynomial-time algorithm for Multiway Cut on chordal graphs in Section 5. In
Section 6, we revisit the aforementioned problems by restricting the input to
$H_{\ell}$-induced-subgraph-free chordal graphs and prove Theorem 1.4 for
Dominating Set as well as Theorem 1.5. Finally in Section 7, we consider the
Connected Dominating Set and the Steiner Tree problems and complete the proofs
of Theorem 1.1 and Theorem 1.4.

##  2 Preliminaries

For a positive integer $q$, we denote the set $\\{1,2,\dots,q\\}$ by $[q]$ and
for any $0\leq p\leq q$, we denote the set $\\{p,\ldots,q\\}$ by $[p,q]$. We
use $\mathbb{N}$ to denote the set of all non-negative integers. Given a
function $f:X\to Z$ and $Y\subseteq X$, $f|_{Y}$ denotes the function $f$
restricted to $Y$.

#### Graph Theory.

For a graph $G$, we denote by $V(G)$ and $E(G)$ the set of vertices and edges
of $G$, respectively. Unless specified otherwise, we use $n$ to denote the
number of vertices in $G$. We denote the edge with endpoints $u,v$ by $uv$.
For any $v\in V(G)$, $N_{G}(v)=\\{u\mid uv\in E(G)\\}$ denotes the (open)
neighbourhood of $v$, and $N_{G}[v]=N_{G}(v)\cup\\{v\\}$ denotes the closed
neighbourhood of $v$. When the graph $G$ is clear from the context, we omit
the subscript $G$. For any $S\subseteq V(G)$, $G-S$ denotes the graph obtained
from $G$ by deleting vertices in $S$. We denote the subgraph of $G$ induced by
$S$, i.e., the graph $G-(V(G)\setminus S)$, by $G[S]$. We say graph $G$
contains graph $H$ as in _induced subgraph_ if $H$ can be obtained from $G$ by
series of vertex-deletions. Recall that for a directed graph $H$, we denote by
$N_{H}^{+}(v)$ the out-neighbors of $v\in V(H)$ and by $N_{H}^{-}(v)$ the in-
neighbors of $v\in V(H)$. If $H$ is clear from the context, we omit the
subscript $H$. Given a (directed) path $P$ in a graph $G$ and two vertices
$u,v\in V(P)$, we denote by $P[u,v]$ the subpath of $P$ from $u$ to $v$. For
any further notation from basic graph theory, we refer the reader to [17].

#### Trees.

A tree $T$ is a connected acyclic graph. Consider a tree $T$ rooted at r. We
define function
$\operatorname{\mathtt{parent}}(t,T):V(T)\setminus\\{\textsf{r}\\}\mapsto
V(T)$ to specify unique parent of the nodes in rooted tree $T$. For any node
$t\in T$, we denote by $T_{t}$ the subtree rooted at $t$. A subdivided star is
a tree with at most one vertex of degree at least $3$ (in other words, it is a
tree obtained by repeatedly subdividing the edges of a star graph). The sets
$V_{\geq 3}(T)$ and $V_{=1}(T)$ denote the set of vertices of degree at least
$3$, and of degree equal to $1$, respectively. The set $V_{\geq 3}(T)$ is also
called the set of branching vertices of $T$ and the set $V_{=1}(T)$ is called
the set of leaves of $T$. Note that $|V_{\geq 3}(T)|\leq|V_{=1}(T)|-1$. Any
node of $T$ which is not a leaf is called _internal_.

#### Chordal graphs and Tree representations.

A graph is called a chordal graph if it contains no induced cycle of length at
least four. It is well-known that chordal graphs can be represented as
intersection graphs of subtrees in a tree, that is, for every chordal graph
$G$, there exists a tree $T$ and a collection ${\mathcal{M}}$ of subtrees of
$T$ in one-to-one correspondence with $V(G)$ such that two vertices in $G$ are
adjacent if and only if their corresponding subtrees intersect. The pair
$(T,{\mathcal{M}})$ is called a _tree representation_ of $G$. For every $v\in
V(G)$, we denote by $\mathcal{M}(v)$ the subtree corresponding to $v$ and
refer to $\mathcal{M}(v)$ as the model of $v$ in $T$. Throughout this article,
we use _nodes_ to refer to the vertices of the tree $T$ to avoid confusion
with the vertices of the graph $G$. Furthermore, we use the greek alphabet to
denote nodes of $T$ and the latin alphabet to denote vertices of $G$. For
notational convenience, for any node $\alpha\in V(T)$ and edge $e\in E(T)$, we
may abuse notation and write $\alpha\in\mathcal{M}(v)$ in place of $\alpha\in
V(\mathcal{M}(v))$ as well as $e\in\mathcal{M}(v)$ in place of $e\in
E(\mathcal{M}(v))$.

For every node $\alpha\in V(T)$, we let $\textnormal{{ver}}(\alpha)=\\{v\in
V(G)\mid\alpha\in\mathcal{M}(v)\\}$, that is, $\textnormal{{ver}}(\alpha)$ is
the set of vertices in $G$ that contain the node $\alpha$ is their model. A
vertex $v\in V(G)$ whose model contains $\alpha$ may also be referred to as an
_$\alpha$ -vertex_. Similarly, for every edge $e\in E(T)$, we let
$\textnormal{{ver}}(e)=\\{v\in V(G)\mid e\subseteq\mathcal{M}(v)\\}$, that is,
$\textnormal{{ver}}(e)$ is the set of vertices of $G$ that contain the edge
$e$ in their model. Given a subtree $T^{\prime}$ of $T$, we denote by
$G_{|T^{\prime}}$ the subgraph of $G$ induced by those vertices $x\in V(G)$
such that $V(\mathcal{M}(x))\subseteq V(T^{\prime})$. If $T$ is rooted, then
for each vertex $v\in V(G)$, we call the node in $\mathcal{M}(v)$ that is
closest to the root of $T$, the topmost node of $\mathcal{M}(v)$ and denoted
it by $\mathtt{top}_{\mathcal{M}}(v)$.

The _leafage_ of chordal graph $G$, denoted by $\texttt{lf}(G)$, is defined as
the minimum number of leaves in the tree of a tree representation of $G$. A
tree representation $(T,{\mathcal{M}})$ for $G$ such that the number of leaves
in $T$ is $\texttt{lf}(G)$, can be computed in time $O(|V(G)|^{3})$ [28].
Furthermore, the number of nodes in $T$ is at most $O(|V(G)|)$.

#### Parameterized Complexity.

The input of a parameterized problem comprises an instance $I$, which is an
input of the classical instance of the problem, and an integer $k$, which is
called the parameter. A parameterized problem $\Pi$ is said to be _fixed-
parameter tractable_ ( for short) if given an instance $(I,k)$ of $\Pi$, we
can decide whether $(I,k)$ is a Yes-instance of $\Pi$ in time
$f(k)\cdot|I|^{\mathcal{O}(1)}$ for some computable function $f$ depending
only on $k$. We say that an instance $(I,k)$ of a parameterized problem $\Pi$
and an instance $(I^{\prime},k^{\prime})$ of a parameterized problem
$\Pi^{\prime}$ (possibly $\Pi=\Pi^{\prime}$) are _equivalent_ if $(I,k)\in\Pi$
if and only if $(I^{\prime},k^{\prime})\in\Pi^{\prime}$. A _reduction rule_ ,
for a parameterized problem $\Pi$, is a polynomial-time algorithm that takes
as input an instance $(I,k)$ of $\Pi$ and outputs an instance
$(I^{\prime},k^{\prime})$ of $\Pi$. If $(I,k)$ and $(I^{\prime},k^{\prime})$
are equivalent then we say that the reduction rule is _safe_. For more details
on parameterized algorithms, and in particular parameterized branching
algorithms, we refer the reader to the book by Cygan et al. [15].

##  3 Dominating Set

For a graph $G$, a set $X\subseteq V(G)$ is a _dominating set_ if every vertex
in $V(G)\setminus X$ has at least one neighbor in $X$, that is, $V(G)=N[X]$.
In the Dominating Set problem (DomSet for short), the input is a graph $G$ and
an integer $k$, and the objective is to decide whether $G$ has a dominating
set of size at most $k$. We assume that the leafage of the input graph is
given as part of the input. If not, recall that it can be computed in
polynomial time [28]. We consider a generalized version of this problem as
defined below.

Red-Blue Dominating Set (Red-Blue-DomSet) Input: A graph $G$, a partition
$(R,B)$ of $V(G)$, and an integer $k$.
Question: Does there exist a set $X\subseteq R$ of size at most $k$ such that
$B\subseteq N(X)$?

We first prove that to solve DomSet, it is sufficient to solve Red-Blue-DomSet
even when the input is restricted to chordal graphs of leafage $\ell$. There
is indeed a simple reduction from the former problem to the latter that
preserves the properties in which we are interested.

######  Lemma 3.1.

There is a polynomial-time algorithm that given an instance $(G,k)$ of DomSet
constructs an equivalent instance $(G^{\prime},(R^{\prime},B^{\prime}),k)$ of
Red-Blue-DomSet such that if $G$ has leafage at most $\ell$, then so does
$G^{\prime}$.

###### Proof.

We construct $G^{\prime}$ from $G$ as follows. For every vertex $v\in V(G)$,
add two copies $v_{R}$ and $v_{B}$ to $V(G^{\prime})$ and add an edge
$v_{R}v_{B}$ to $E(G^{\prime})$. For every edge $uv\in E(G)$, add edges
$v_{R}u_{R}$, $v_{R}u_{B}$, $v_{B}u_{R}$, and $v_{B}u_{B}$ to $E(G^{\prime})$.
This completes the construction of $G^{\prime}$. Let $R^{\prime}=\\{v_{R}\mid
v\in V(G)\\}$ and $B^{\prime}=\\{v_{B}\mid v\in V(G)\\}$.

Suppose that the DomSet instance has a solution $S\subseteq V(G)$. Then the
set $S_{R}=\\{v_{R}\mid v\in S\\}$, i.e., $S_{R}$ contains the red version of
each vertex in $S$, is a solution for the Red-Blue-DomSet instance: indeed,
the blue vertices $v_{B}$ such that $v\notin S$ are dominated since $S$ is a
solution, and if $v\in S$, then $v_{B}$ is dominated because of the newly
added edges. Conversely, if $S_{R}\subseteq R^{\prime}$ is a solution for the
Red-Blue-DomSet instance, then it is easy to see that $S=\\{v\mid v_{R}\in
S_{R}\\}$ is a solution for the DomSet instance.

Finally note that a tree representation for $G^{\prime}$ can be obtained from
a tree representation for $G$ by duplicating the model of each vertex, and
making the original model a model for the blue version of the vertex, and the
copy a model for its red version. In particular, the leafage of $G^{\prime}$
is at most that of $G$. ∎

In the remainder of this section, we present an algorithm for Red-Blue-DomSet
when parameterized by the leafage $\ell$ of the input graph. The algorithm
consists of two parts. In the first part, the algorithm constructs
$2^{{\mathcal{O}}(\ell)}$ many instances of a “restricted version” of the
problem such that the input instance is a Yes-instance if and only if one of
these newly created instances is a Yes-instance. Moreover, the graphs in the
newly created instances satisfy certain properties that allow us to design a
fast algorithm. See Lemma 3.2 for the formal statement. In the second part
(cf. Lemma 3.3), the algorithm solves the restricted version of Red-Blue-
DomSet which is defined as follows.

Restricted-Red-Blue Dominating Set (Rest-Red-Blue-DomSet) Input: A chordal
graph $G$, a partition $(R,B)$ of $V(G)$, an integer $k$ and tree
representation $(T,{\mathcal{M}})$ of $G$ such that • for every vertex in $G$,
its model contains at most one branching node of $T$, and • for all branching
nodes $\gamma\in V(T)$, there are either only red $\gamma$-vertices or only
blue $\gamma$-vertices. Question: Does there exist a set $D\subseteq R$ of
size at most $k$ such that $B\subseteq N(D)$?

###  3.1 Constructing Rest-Red-Blue-DomSet Instances

In this section, we prove the following result.

######  Lemma 3.2.

Let $\mathcal{I}=(G,(R,B),k)$ be an instance of Red-Blue-DomSet where $G$ is a
chordal graph of leafage at most $\ell$. We can construct, in time
$2^{{\mathcal{O}}(\ell)}\cdot n^{\mathcal{O}(1)}$, a collection
$\\{\mathcal{I}_{i}=(G_{i},(R_{i},B_{i}),k)\mid
i\in[2^{{\mathcal{O}}(\ell)}]\\}$ of Rest-Red-Blue-DomSet instances such that

  * •

for every $i\in[2^{{\mathcal{O}}(\ell)}]$, $G_{i}$ is a chordal graph of
leafage at most $2\ell$, and

  * •

$\mathcal{I}$ is a Yes-instance of Red-Blue-DomSet if and only if at least one
of the instances in the collection is a Yes-instance of Rest-Red-Blue-DomSet.

###### Proof.

Let $G$ be a chordal graph and let $(T,{\mathcal{M}})$ be a tree
representation of $G$. We define the following functions.

  * •

Let $f_{T}(G)$ denote the number of branching nodes $\gamma\in V(T)$ such that
there exist both a red vertex and a blue vertex whose models contain $\gamma$.

  * •

Let $f_{r}(G)$ denote the number of pairs of consecutive branching nodes
$\alpha,\beta$ in $T$ (that is, no node on the unique path in $T$ from
$\alpha$ to $\beta$ is a branching node) such that there is red vertex whose
model contains both $\alpha$ and $\beta$.

  * •

Similarly, let $f_{b}(G)$ denote the number of pairs of consecutive branching
nodes $\alpha,\beta$ in $T$ such that there is blue vertex whose model
contains both $\alpha$ and $\beta$.

We further define $\mu(G):=\texttt{lf}(G)+2\cdot(f_{T}(G)+f_{r}(G)+f_{b}(G))$.
Note that, by definition, $\mu(G)\geq\texttt{lf}(G)$. We design a polynomial-
time branching algorithm whose measure $\mu$ decreases in each branch. We
first show that if $\mu(G)=\texttt{lf}(G)$ then $(G,(R,B),k)$ is in fact an
instance of Rest-Red-Blue-DomSet and then show how the branching algorithm
proceeds.

Assume therefore that $\mu(G)=\texttt{lf}(G)$. Then
$f_{T}(G)=f_{r}(G)=f_{b}(G)=0$ by definition. However, when $f_{T}(G)=0$,
then, by definition, for every branching node $\gamma\in V(T)$, all the
vertices containing $\gamma$ in their model are either red or blue; and when
$f_{r}(G)=f_{b}(G)=0$ then, considering the fact that every model is a subtree
in $T$, for every vertex in $G$, its model contains at most one branching node
in $T$. Therefore if $\mu(G)=\texttt{lf}(G)$, then $(G,(R,B),k)$ is also an
instance of Rest-Red-Blue-DomSet.

Now assume that $\mu(G)>\texttt{lf}(G)$. Then $f_{T}(G)+f_{r}(G)+f_{b}(G)>0$.
We consider the following three exhaustive cases.

#### Case-I.

_$f_{T}(G) >0$._ Let $\gamma$ be a branching node in $T$ such that there is
both a red-vertex and a blue-vertex whose models contain $\gamma$. Suppose
that $\mathcal{I}$ is a Yes-instance of Red-Blue-DomSet and let $D$ be a
solution. Consider first the case where $D$ includes a red vertex whose model
contains $\gamma$. In this case, we return the instance
$\mathcal{I}_{1}=(G_{1},(R_{1},B_{1}),k)$ which is obtained as follows.

  * •

Initialize $V(G_{1})=V(G)$, $R_{1}=R$, $B_{1}=B$.

  * •

Let $T_{1}$ be the tree obtained from $T$ by adding a node $\delta$ and making
it adjacent to $\gamma$ only. Note that
$V(T_{1})\setminus\\{\delta\\}\subseteq V(T)$.

  * •

For every red vertex $v\in V(G_{1})$ such that $\gamma\in\mathcal{M}(v)$, add
$\delta$ to its model, i.e.,
$\mathcal{M}_{1}(v)=\mathcal{M}(v)\cup\\{\delta\\}$.

  * •

For every blue vertex $v\in V(G_{1})$ such that $\gamma\in\mathcal{M}(v)$,
delete $v$ from $V(G_{1})$.

  * •

Add a new blue vertex $x$ to $V(G_{1})$ and to $B_{1}$ with
$\mathcal{M}_{1}(x)=\\{\delta\\}$.

  * •

For every (red or blue) vertex $v\in V(G)$ such that
$\gamma\not\in\mathcal{M}(v)$, define $\mathcal{M}_{1}(v_{1})=\mathcal{M}(v)$.

It is easy to verify that $(T_{1},\mathcal{M}_{1})$ is a tree representation
of $G_{1}$ and that $T_{1}$ has exactly one more leaf than $T$, i.e.,
$\texttt{lf}(G_{1})\leq\texttt{lf}(G)+1$. However, since we have deleted all
the blue vertices whose models contained $\gamma$, $f_{T}(G_{1})=f_{T}(G)-1$.
As the other parts of the measure do not change, $\mu(G_{1})<\mu(G)$.

In the second case where no vertex in $D$ contains $\gamma$ in its model, we
return the instance $\mathcal{I}_{2}=(G_{2},(R_{2},B),k)$ where $G_{2},R_{2}$
are obtained from $G,R$, respectively, by deleting red vertices whose model
contains $\gamma$. It is easy to verify that $\mu(G_{2})<\mu(G)$.

If $\mathcal{I}$ is a Yes-instance, then at least one of $\mathcal{I}_{1}$ or
$\mathcal{I}_{2}$ is a Yes-instance as these two branches are exhaustive. If
$\mathcal{I}_{1}$ is a Yes-instance, then any optimum solution must include a
red $\gamma$-vertex because of the newly added vertex $x$. As $R_{2}\subseteq
R$, if $\mathcal{I}_{2}$ is a Yes-instance, then $\mathcal{I}$ is a Yes-
instance. Hence, this branching step is correct.

#### Case-II.

_$f_{T}(G)=0$ and $f_{r}(G)>0$._ Let $\alpha,\beta$ be two consecutive
branching nodes in $T$ such that there is a red vertex whose model contains
both $\alpha$ and $\beta$. Suppose that $\mathcal{I}$ is a Yes-instance of
Red-Blue-DomSet and let $D$ be a solution. Consider the case where $D$
includes a red vertex whose model contains both $\alpha$ and $\beta$. In this
case, we return the instance $\mathcal{I}_{1}=(G_{1},(R_{1},B_{1}),k)$ which
is obtained as follows.

  * •

Initialize $V(G_{1})=R_{1}=B_{1}=\emptyset$.

  * •

Let $T_{1}$ be the tree obtained from $T$ by contracting the unique path
$P_{\alpha\beta}$ from $\alpha$ to $\beta$ in $T$ and let
$\gamma_{\alpha\beta}$ be the node resulting from this contraction. Add a node
$\delta$ to $T_{1}$ and make it adjacent to $\gamma_{\alpha\beta}$ only. Note
that $V(T_{1})\setminus\\{\gamma_{\alpha\beta},\delta\\}\subseteq V(T)$.

  * •

For every red vertex $v\in V(G)$ such that $\mathcal{M}(v)\cap
V(P_{\alpha\beta})\neq\emptyset$, add a red vertex $v_{1}$ to $V(G_{1})$ (and
to $R_{1}$) with $\mathcal{M}_{1}(v_{1})=(\mathcal{M}(v)\setminus
V(P_{\alpha\beta}))\cup\\{\gamma_{\alpha\beta},\delta\\}$.

  * •

Add a new blue vertex $x$ to $V(G_{1})$ with
$\mathcal{M}_{1}(x)=\\{\delta\\}$.

  * •

For every (red or blue) vertex $v\in V(G)$ such that $\mathcal{M}(v)\cap
V(P_{\alpha\beta})=\emptyset$, add $v_{1}$ to $G_{1}$ (and to, respectively,
either $R_{1}$ or $B_{1}$) with $\mathcal{M}_{1}(v_{1})=\mathcal{M}(v)$.

Note that for every blue vertex $v\in V(G)$ such that $\mathcal{M}(G)\cap
V(P_{\alpha\beta})\neq\emptyset$, there is no corresponding blue vertex in
$G_{1}$. It is easy to verify that $(T_{1},\mathcal{M}_{1})$ is a tree
representation of $G_{1}$ and that $T_{1}$ has one more leaf than $T$ which
implies $\texttt{lf}(G_{1})\leq\texttt{lf}(G)+1$. Since we have contracted the
path $P_{\alpha\beta}$ to obtain the node $\gamma_{\alpha\beta}$,
$f_{r}(G_{1})<f_{r}(G)$. As the other parts of the measure do not change,
$\mu(G_{1})<\mu(G)$.

In the second case where no vertex in $D$ contains both $\alpha$ and $\beta$
in its model, we return an instance $\mathcal{I}_{2}=(G_{2},(R_{2},B),k)$
where $G_{2},R_{2}$ are obtained from $G,R$, respectively, by deleting red
vertices whose model contains both $\alpha$ and $\beta$. It is easy to verify
that $\mu(G_{2})<\mu(G)$. We argue as in the previous case for the correctness
of this branching steps.

#### Case-III.

_$f_{T}(G)=0$ and $f_{b}(G)>0$._ Let $\alpha,\beta$ be two consecutive
branching nodes in $T$ such that there is a blue vertex whose model contains
both $\alpha$ and $\beta$. Note that since $f_{T}(G)=0$, for every red vertex
$v\in V(G)$ such that $\mathcal{M}(v)\cap V(P_{\alpha\beta})\neq\emptyset$, in
fact $\mathcal{M}(v)\subseteq V(P_{\alpha\beta})\setminus\\{\alpha,\beta\\}$.
Suppose that $\mathcal{I}$ is a Yes-instance of Red-Blue-DomSet and let $D$ be
a solution. Consider first the case where $D$ includes a red vertex whose
model is in $V(P_{\alpha\beta})\setminus\\{\alpha,\beta\\}$. In this case, we
return the instance $\mathcal{I}_{1}=(G_{1},(R,B_{1}),k)$ where $G_{1}$,
$B_{1}$ are obtained from $G$ and $B$ as follows.

  * •

Delete all the blue vertices whose model contains both $\alpha$ and $\beta$.

  * •

Add a blue vertex $x$ to $V(G_{1})$ (and to $B_{1}$) with
$\mathcal{M}(x)=V(P_{\alpha\beta})\setminus\\{\alpha,\beta\\}$.

It is easy to verify that $(T,\mathcal{M})$ is a tree representation of
$G_{1}$ and $f_{b}(G_{1})<f_{b}(G)$. As the other parts of the measure do not
change, $\mu(G_{1})<\mu(G)$.

In the second case where there is no vertex in $D$ whose model is in
$V(P_{\alpha\beta})\setminus\\{\alpha,\beta\\}$, we consider the following two
subcases. If there is a blue vertex $v$ such that $\mathcal{M}(v)\subseteq
V(P_{\alpha\beta})$, then we return a trivial No-instance. Otherwise, we
return the instance $\mathcal{I}_{2}=(G_{2},(R_{2},B_{2}),k)$ which is
constructed as follows.

  * •

Initialize $V(G_{2})=R_{2}=B_{2}=\emptyset$.

  * •

Let $T_{2}$ be the tree obtained from $T$ by contracting the path
$P_{\alpha\beta}$ from $\alpha$ to $\beta$ in $T$ and let
$\gamma_{\alpha\beta}$ be the node resulting from this contraction. Note that
$V(T_{2})\setminus\\{\gamma_{\alpha\beta}\\}\subseteq V(T)$.

  * •

For every (red or blue) vertex $v\in G$ such that $\mathcal{M}(v)\cap
V(P_{\alpha\beta})=\emptyset$, add a vertex $v_{2}$ to $G_{2}$ (and to,
respectively, either $R_{2}$ or $B_{2}$) with
$\mathcal{M}_{2}(v_{2})=\mathcal{M}(v)$.

  * •

For every blue vertex $v\in V(G)$ such that $\mathcal{M}(v)\cap
V(P_{\alpha\beta})\neq\emptyset$, add a blue vertex $v_{2}$ to $V(G_{2})$ (and
to $B_{2}$) with $\mathcal{M}_{2}(v_{2})=(\mathcal{M}(v_{2})\setminus
V(P_{\alpha\beta}))\cup\\{\gamma_{\alpha\beta}\\}$.

Note that for any red vertex $v\in V(G)$ such that $\mathcal{M}(v)\subseteq
V(P_{\alpha\beta})\setminus\\{\alpha,\beta\\}$, there is no corresponding red
vertex in $G_{2}$. It is easy to verify that $(T_{2},\mathcal{M}_{2})$ is a
tree representation of $G_{2}$. Furthermore, the number of leaves of $T_{2}$
is the same as $T$ and $f_{b}(G_{2})<f_{b}(G)$. As the other parts in the
measure do not change, $\mu(G_{2})<\mu(G)$.

The correctness of this branching step follows from the same arguments as in
the previous cases and the fact that in the second case, since there is no red
vertex whose model intersects $V(P_{\alpha\beta})$, it is safe to contract
that path.

#### Finishing the Proof.

The correctness of the overall algorithm follows from the correctness of
branching steps in the above three cases. To bound its running time and the
number of instances it outputs, note that $f_{T}(G)+f_{r}(G)+f_{b}(G)\leq
3\cdot\texttt{lf}(G)$ as these functions either count the number of branching
nodes or the unique paths containing exactly two (consecutive) branching
nodes. ∎

###  3.2 Solving an instance of Rest-Red-Blue-DomSet

In this section, we present an algorithm to solve Rest-Red-Blue-DomSet.
Formally, we prove the following lemma.

######  Lemma 3.3.

Rest-Red-Blue-DomSet admits an algorithm running in time
$2^{\mathcal{O}(\ell)}\cdot n^{\mathcal{O}(1)}$.

We first state some easy reduction rules before we handle two cases based on
whether the farthest branching node444We assume that the tree in the tree
representation is rooted and thus, by farthest branching node, we mean
farthest from the root. is contained only in the models of red vertices or
blue vertices. We present Greedy Select 3.9 and Greedy Select 3.12 to handle
these cases. The proof of the lemma follows from Lemma 3.10, Lemma 3.13 and
the fact that each application of the greedy selection procedure deletes some
vertices in the graph.

We first introduce some notations. Recall that an instance of Rest-Red-Blue-
DomSet contains a chordal graph $G$, a partition $(R,B)$ of $V(G)$, an integer
$k$ and tree representation $(T,{\mathcal{M}})$ of $G$ such that for every
vertex in $G$, its model contains at most one branching node of $T$, and for
all branching nodes $\gamma\in V(T)$, there are either only red
$\gamma$-vertices or only blue $\gamma$-vertices. We assume, without loss of
generality, that the tree $T$ is rooted at node r. Unless mentioned otherwise,
$\alpha$ denotes the farthest branching node in $T$ from the root, that is,
each proper subtree of $T_{\alpha}$ is a path. If there are more than one
branching node that satisfy the property, we arbitrarily select one of them.
Let $\beta$ be the closest branching ancestor of $\alpha$, that is, no
internal node in the unique path from $\alpha$ to $\beta$ is a branching node
in $T$.555 If $\alpha$ is the root of the tree, then we can add an artificial
new root $\beta$ which is not contained in the model of any vertex.  Recall
that for a vertex $v\in V(G)$, we define $\mathtt{top}_{\mathcal{M}}(v)$ as
the node $\eta\in\mathcal{M}(v)$ that is closest to the root. Likewise if a
leaf $\lambda$ is fixed, we define $\mathtt{bot}^{\lambda}_{\mathcal{M}}(v)$
as the node $\eta\in\mathcal{M}(v)$ that is closest to $\lambda$. For ease of
notation, we omit $\lambda$ as it is always clear from the context.

######  Definition 3.4.

Let $\gamma$ be a node of the tree $T$. We define the following sets of
vertices in $G$.

  * •

$B_{\gamma}^{\cap},R_{\gamma}^{\cap},V_{\gamma}^{\cap}$ are the sets of,
respectively, blue, red, all vertices $v\in V(G)$ whose models intersect the
tree rooted at $\gamma$, i.e., $\mathcal{M}(v)\cap
V(T_{\gamma})\neq\emptyset$.

  * •

$B_{\gamma}^{\subseteq},R_{\gamma}^{\subseteq},V_{\gamma}^{\subseteq}$ are the
sets of, respectively, blue, red, all vertices $v\in V(G)$ whose models are
completely contained inside the tree rooted at $\gamma$, i.e.,
$\mathcal{M}(v)\subseteq V(T_{\gamma})$.

  * •

$B_{\gamma}^{\subseteq{\dagger}},R_{\gamma}^{\subseteq{\dagger}},V_{\gamma}^{\subseteq{\dagger}}$
are the sets of blue, red, all vertices $v\in V(G)$ where the model is
completely contained inside the tree rooted at $\gamma$ but does not contain
$\gamma$, respectively, i.e. $\mathcal{M}(v)\subseteq
V(T_{\gamma}^{\dagger})=V(T_{\gamma})\setminus\\{\gamma\\}$.

  * •

$B_{\gamma}^{\in},R_{\gamma}^{\in},V_{\gamma}^{\in}$ are the sets of,
respectively, blue, red, all vertices $v\in V(G)$ whose models contains
$\gamma$, i.e., $\gamma\in\mathcal{M}(v)$.

#### Simplifications.

We first apply the following easy reduction rules whose correctness readily
follows from the definition of the problem. It is also easy to see that the
reduction rules can be applied in polynomial time and the reduced instance is
also a valid instance of Rest-Red-Blue-DomSet.

######  Reduction Rule 3.5.

If there is a blue vertex, which is not adjacent to a red vertex, or if $k<0$,
then return a trivial No-instance.

######  Reduction Rule 3.6.

  * •

If there are two blue vertices $u,v$ such that
$\mathcal{M}(u)\subseteq\mathcal{M}(v)$, then delete $v$.

  * •

If there are two red vertices $u,v$ such that
$\mathcal{M}(u)\subseteq\mathcal{M}(v)$, then delete $u$.

Consider a blue vertex $v$ in $G$ whose model is contained in the subtree
rooted at $\alpha$. Moreover, let $v$ be such a vertex for which
$\mathtt{top}_{\mathcal{M}}(v)$ is farthest from the root and $v$ is not
adjacent to a red vertex whose model contains $\alpha$. Hence, there is a
natural ordering amongst the red neighbors of $v$. Note that such an ordering
is not possible if some of its neighbors contain $\alpha$ in their models. As
any solution contains a red neighbor of $v$, it is safe to include its
neighbor $v_{r}$ for which $\mathtt{top}_{\mathcal{M}}(v_{r})$ is closest to
$\alpha$.

######  Reduction Rule 3.7.

Suppose that there is a blue vertex $v\in B_{\alpha}^{\subseteq{\dagger}}$
such that $\mathtt{top}_{\mathcal{M}}(v)$ is farthest from the root and $v$ is
not adjacent to any red $\alpha$-vertices. Moreover, amongst all the red
neighbors of $v$, let $v_{r}$ be the node such that
$\mathtt{top}_{\mathcal{M}}(v_{r})$ is closest to $\alpha$. Then, remove
$v_{r}$ and all of its blue neighbors and decrease $k$ by $1$.

We remark that the above reduction rule is applicable irrespective of the fact
whether either all $\alpha$-vertices are red or all $\alpha$-vertices are
blue.

#### Case-1: All the vertices that contain $\alpha$ in their models are red
vertices.

Let $\beta$ be the closest branching ancestor of $\alpha$. Consider the blue
vertices whose model intersect the path from $\alpha$ to $\beta$. Note that
there may not be any such blue vertex; however, we find it convenient to
present an uniform argument. With a slight abuse of notation, let
$b_{1},\dots,b_{d}$ be these blue vertices ordered according to their endpoint
in the direction of $\alpha$, that is, for $i<j$ we have either
$\mathtt{bot}_{\mathcal{M}}(b_{i})=\mathtt{bot}_{\mathcal{M}}(b_{j})$ or
$\mathtt{bot}_{\mathcal{M}}(b_{i})$ is closer to $\alpha$ than
$\mathtt{bot}_{\mathcal{M}}(b_{j})$. For each $i\in[d]$, we compute an optimal
solution for dominating the vertices whose model is in the tree rooted at
$\alpha$ (i.e., the vertices of $B_{\alpha}^{\subseteq{\dagger}}$) and the
vertex $b_{i}$ while only using red $\alpha$-vertices. Formally, we want to
compute an optimal solution for the following instance:
$\mathcal{I}_{i}\coloneqq G[R_{\alpha}^{\cap}\cup
B_{\alpha}^{\subseteq}\cup\\{b_{i}\\}]$. We also define instance
$\mathcal{I}_{0}\coloneqq G[R_{\alpha}^{\cap}\cup B_{\alpha}^{\subseteq}]$ to
handle the cases when there are no blue vertices whose model intersects the
path from $\alpha$ to $\beta$ or when $b_{1}$ (and hence, the other blue
vertices mentioned above) are not dominated by red $\alpha$-vertices in an
optimum solution. To simplify notation we set
$\textsc{OPT}_{i}\coloneqq\textsc{OPT}(\mathcal{I}_{i})$ in the following. If
$\mathcal{I}_{i}$ is not defined, then we set $\textsc{OPT}_{i}=\infty$. Note
that the solution $\textsc{OPT}_{i}$ also dominates the blue vertices
$b_{1},\dots,b_{i-1}$ due to the ordering of the $b_{i}$s. Hence, for any
$i,j\in[0,d]$ such that $i<j$, we have
$\lvert\textsc{OPT}_{i}\rvert\leq\lvert\textsc{OPT}_{j}\rvert$. We use this
monotonicity to prove the following structural lemma.

######  Lemma 3.8.

Let $q\in[0,d]$ be the largest value such that
$\lvert\textsc{OPT}_{q}\rvert=\lvert\textsc{OPT}_{0}\rvert$. If there is a
solution, then there is an optimum solution containing $\textsc{OPT}_{q}$.

###### Proof.

Let OPT be an optimum solution of $(G,(R,B),k)$. Let $S$ denote the collection
of vertices in OPT whose model contains nodes in the subtree rooted at
$\alpha$, i.e., $S\coloneqq\textsc{OPT}\cap R_{\alpha}^{\cap}$. We claim that
we can replace $S$ by a super-set $S^{\prime}$ of $\textsc{OPT}_{q}$ of equal
size to obtain another solution.

Let $j\in[0,d]$ be the largest integer such that $b_{j}$ is dominated by some
vertex in $S$. If $j\leq q$, then by our choice of $q$, $\lvert
S\rvert=\lvert\textsc{OPT}_{q}\rvert$. By the definition of the
$\mathcal{I}_{i}$s, we get that $\textsc{OPT}_{q}$ is also a solution for
$\mathcal{I}_{i}$. Hence, we can replace $S$ by $\textsc{OPT}_{q}$ to get
another optimal solution. Suppose therefore that $j>q$. By our choice of $q$,
we have $\lvert S\rvert>\lvert\textsc{OPT}_{q}\rvert$. Let $r_{j}$ be the red
$\alpha$-vertex with $\mathtt{top}_{\mathcal{M}}(r_{j})$ closest to $\beta$
such that $b_{j}$ is a neighbor of $r_{j}$. Such a vertex exists, as by
assumption, $S$ contains one of these vertices which dominates $b_{j}$. Then
we replace $S$ by $S^{\prime}=\textsc{OPT}_{q}\cup\\{r_{j}\\}$. As $\lvert
S\rvert>\lvert\textsc{OPT}_{q}\rvert$, we have $\lvert
S^{\prime}\rvert\leq\lvert S\rvert$. Moreover, observe that
$S^{\prime}\cup\textsc{OPT}\setminus S$ is still a solution as all vertices in
$B_{\alpha}^{\subseteq{\dagger}}$ and the vertices $b_{1},\dots,b_{q}$ are
dominated by some vertex in $\textsc{OPT}_{q}$, vertex $r_{j}$ dominates the
vertices $b_{q+1},\dots,b_{j}$ and, by the choice of $j$, the vertices
$b_{j+1},\dots,b_{d}$ are dominated by some vertex not contained in $S$. ∎

We devise a greedy selection step based on the above lemma.

######  Greedy Select 3.9.

Let $q\in[0,d]$ be the largest value such that
$\lvert\textsc{OPT}_{q}\rvert=\lvert\textsc{OPT}_{0}\rvert$. Include the
vertices of $\textsc{OPT}_{q}$ in the solution, i.e., delete the red vertices
in $\textsc{OPT}_{q}$, the blue vertices that are adjacent to vertices in
$\textsc{OPT}_{q}$, and decrease $k$ by $\lvert\textsc{OPT}_{q}\rvert$.

######  Lemma 3.10.

Greedy Select 3.9 step is correct and can be completed it time
$2^{{\mathcal{O}}(\ell)}\cdot n^{\mathcal{O}(1)}$.

###### Proof.

The correctness of the step follows directly from Lemma 3.8. In the remaining
proof, we show how to compute, for every $i\in[0,d]$, $\textsc{OPT}_{i}$ in
time $\mathcal{O}(\ell\cdot\lvert R\rvert\cdot 2^{\ell}\cdot n)$ by
constructing an instance of Set Cover. Before constructing such an instance,
we justify that only one blue vertex (which is farthest from $\alpha$) is
critical while constructing this Set Cover instance.

Let $\alpha^{\prime}$ be a child of $\alpha$. As $\alpha$ is a farthest
branching node of $T$ from the root, the tree rooted at $\alpha^{\prime}$ is a
path. Let $\lambda$ be the another endpoint of this path. Consider a blue
vertex $v_{\alpha^{\prime}}$ whose model is contained in
$T_{\alpha^{\prime}}$, i.e., $v_{\alpha^{\prime}}\in
B_{\alpha^{\prime}}^{\subseteq}$. Moreover, suppose that $v_{\alpha^{\prime}}$
is the vertex for which $\mathtt{top}_{\mathcal{M}}(v_{r})$ is farthest from
$\alpha^{\prime}$. As Reduction Rule 3.7 is not applicable, there exists at
least one red neighbor of $v_{\alpha^{\prime}}$ which is an $\alpha$-vertex.
Hence, an optimum solution can always include a red neighbor of
$v_{\alpha^{\prime}}$ which is also an $\alpha$-vertex. This red
$\alpha$-vertex also dominates all the blue vertices in
$B_{\alpha^{\prime}}^{\subseteq}$.

We now explain how to construct an instance $(U,\mathcal{F})$ of Set Cover.
For every child $\alpha^{\prime}$ of $\alpha$, if the vertex
$v_{\alpha^{\prime}}$ mentioned in the previous paragraph exists, then add an
element $u_{\alpha^{\prime}}$ corresponding to it to $U$. When $i\neq 0$, add
another element $u_{i}$ corresponding to $b_{i}$ to $U$. For every red
$\alpha$-vertex $v$, we define set $S_{v}\subseteq U$ as the collection of
elements corresponding to the blue vertices in $\mathcal{I}_{i}$ that are
adjacent to $v$. This completes the construction of the instance.

It is easy to see the one-to-one correspondence between the optimum solutions
of these two instances. The running time of the algorithm follows from the
known algorithms for Set Cover (see, for instance, [21]) and the fact that
$\alpha$ has at most $\ell$ many children. ∎

#### Case-2: All the vertices that contain $\alpha$ in their models are blue
vertices.

Let $\beta$ be the closest branching ancestor of $\alpha$. We consider two
cases depending on whether there is a red vertex whose model intersects the
path from $\alpha$ to $\beta$. If there is no such red vertex, then we
consider the graph induced by all the red vertices whose model is (properly)
contained in the subtree rooted at $\alpha$ and the blue vertices whose model
intersects the subtree rooted at $\alpha$. Formally, we define
$\mathcal{I}_{0}=G[R_{\alpha}^{\subseteq}\cup B_{\alpha}^{\cap}]$.

Consider the other case and suppose that there are $d\geq 1$ many red vertices
whose model intersects the path from $\alpha$ to $\beta$. Let
$r_{1},\dots,r_{d}$ be these vertices ordered according to their endpoints in
the direction of $\alpha$, that is, for $i<j$, we have either
$\mathtt{bot}_{\mathcal{M}}(r_{i})=\mathtt{bot}_{\mathcal{M}}(r_{j})$ or
$\mathtt{bot}_{\mathcal{M}}(r_{i})$ is closer to $\alpha$ than
$\mathtt{bot}_{\mathcal{M}}(r_{j})$. For each such red vertex $v_{i}$, we
compute the optimal solution to dominate the vertices in $B_{\alpha}^{\cap}$
by vertices in $R_{\alpha}^{\subseteq}$ assuming that $v_{i}$ is already
selected. Note that we only have to focus on the blue vertices in
$B_{\alpha}^{\cap}$ which are not adjacent to $v_{i}$. Formally we define
$\mathcal{I}_{i}=G[R_{\alpha}^{\subseteq}\cup(B_{\alpha}^{\cap}\setminus
N[v_{i}])]$. It is possible that the optimum solution does not include any of
the vertices in $\\{r_{1},r_{2},\dots,r_{d}\\}$. To handle this case, we
define $\mathcal{I}_{d+1}=G[R_{\alpha}^{\subseteq}\cup B_{\alpha}^{\cap}]$. To
simplify notation, we set
$\textsc{OPT}_{i}\coloneqq\textsc{OPT}(\mathcal{I}_{i})$ in the following.
Note that for the instance defined above, $R_{i}$ is same for every instance
whereas $B_{i}\subseteq B_{i+1}$ because of the ordering. Hence, for any
$i,j\in[d+1]$ such that $i<j$, we have
$|\textsc{OPT}_{i}|\leq|\textsc{OPT}_{j}|$. We use this monotonicity to prove
the following structural lemma.

######  Lemma 3.11.

If there is a red vertex whose model intersects the path from $\alpha$ to
$\beta$, let $q\in[d+1]$ be the largest value such that
$\lvert\textsc{OPT}_{q}\rvert=\lvert\textsc{OPT}_{1}\rvert$. Otherwise, define
$\textsc{OPT}_{q}=\textsc{OPT}_{0}$. If there is a solution for the instance,
then there is an optimum solution OPT such that $\textsc{OPT}\cap
R_{\alpha}^{\subseteq}=\textsc{OPT}_{q}$.

###### Proof.

If there is no red vertices whose model intersects the path from $\alpha$ to
$\beta$, then all the red vertices in $G$ that are adjacent to blue vertices
in $\mathcal{I}_{0}$ are the red vertices in $\mathcal{I}_{0}$. Hence, the
statement of the lemma follows.

We now consider the case where there are red vertices whose model intersects
the path from $\alpha$ to $\beta$. Let OPT be an optimum solution of
$(G,(R,B),k)$. Let $S$ denote the collection of vertices in OPT whose model is
(properly) contained in the subtree rooted at $\alpha$, i.e.,
$S\coloneqq\textsc{OPT}\cap R_{\alpha}^{\subseteq{\dagger}}$. We claim that we
can replace $S$ by a super-set $S^{\prime}$ of $\textsc{OPT}_{q}$ of equal
size to obtain another optimum solution.

Let $j\in[d]$ be the smallest index such that $v_{j}$ is contained in OPT.
Note that, by definition, $j\neq d+1$ as there are only $d$ red vertices with
the said property. If $j\leq q$, then by our choice of $q$, $\lvert
S\rvert\geq\lvert\textsc{OPT}_{j}\rvert$. By the definition of
$\mathcal{I}_{j}$ and the fact blue vertices in $\mathcal{I}_{j}$ are subset
of blue vertices in $\mathcal{I}_{q}$, $\textsc{OPT}_{q}$ is also a solution
for $\mathcal{I}_{j}$. Hence, we can replace $S$ by $\textsc{OPT}_{q}$ to get
another optimal solution. Suppose therefore that $j>q$. By our choice of $q$,
we have $\lvert\textsc{OPT}_{j}\rvert>\lvert\textsc{OPT}_{q}\rvert$. As OPT is
a solution, all vertices in $B_{\alpha}^{\cap}$ must be covered by OPT. Hence,
we can replace $S$ by $S^{\prime}=\textsc{OPT}_{q}\cup\\{r_{q}\\}$ and get a
solution of not larger size which still dominates all vertices in
$B_{\alpha}^{\cap}$. Indeed, the vertices which are not dominated by
$\textsc{OPT}_{q}$ are dominated by $r_{q}$. ∎

We devise a greedy selection step based on the above lemma.

######  Greedy Select 3.12.

If there is a red vertex whose model intersects the path from $\alpha$ to
$\beta$, let $q\in[d+1]$ be the largest value such that
$\lvert\textsc{OPT}_{q}\rvert=\lvert\textsc{OPT}_{1}\rvert$. Otherwise, define
$\textsc{OPT}_{q}=\textsc{OPT}_{0}$. Include $\textsc{OPT}_{q}$ in the
solution, i.e., delete the red vertices in $\textsc{OPT}_{q}$, the blue
vertices that are adjacent to vertices in $\textsc{OPT}_{q}$, and decrease $k$
by $\lvert\textsc{OPT}_{\ell}\rvert$.

######  Lemma 3.13.

Greedy Select 3.12 step is correct and can be completed in time
$2^{{\mathcal{O}}(\ell)}\cdot n^{\mathcal{O}(1)}$.

###### Proof.

The correctness of the step follows directly from Lemma 3.11. In the remaining
proof, we show how to compute $\textsc{OPT}_{i}$ for every $i\in[0,d+1]$, by
constructing an instance of Hitting Set. As in Lemma 3.10, we first argue that
only one red vertex (which is closest to $\alpha$) is critical while
constructing a Hitting Set instance.

Recall that, by assumption, none of the previous reduction rules are
applicable. As in the previous case, let $\alpha^{\prime}$ be a child of
$\alpha$. We first argue that there are no blue vertices whose path is
completely contained in the path rooted at $\alpha^{\prime}$. Assume, for the
sake of contradiction, that there exists such a blue vertex $v$. As Reduction
Rule 3.5 is not applicable, $v$ is adjacent to at least one red vertices.
However, since all $\alpha$-vertices are blue, by the property of the
instance, there are no red $\alpha$-vertices. In particular, $v$ is not
adjacent to any red $\alpha$-vertex. This contradicts the fact that Reduction
Rule 3.7 is not applicable. Hence, there is no blue vertex whose model is
contained in the path rooted at $\alpha^{\prime}$. Since this is true for any
child of $\alpha$, there are no blue vertices in
$B_{\alpha}^{\subseteq{\dagger}}$, i.e.,
$B_{\alpha}^{\subseteq{\dagger}}=\emptyset$ and
$B_{\alpha}^{\cap}=B_{\alpha}^{\in}$. Now, for a child $\alpha^{\prime}$ of
$\alpha$, let $v_{\alpha^{\prime}}\in R_{\alpha^{\prime}}^{\subseteq}$ be a
red vertex such that $\mathtt{top}_{\mathcal{M}}(v_{r})$ is closest to
$\alpha$. Since all blue vertices contain $\alpha$ in their model, the only
critical red vertex in this leg is $v_{\alpha^{\prime}}$.

We now explain how to construct an instance $(U,\mathcal{F})$ of Hitting Set.
For every child $\alpha^{\prime}$ of $\alpha$, let $v_{\alpha^{\prime}}$ be
the vertex as mentioned above. Add an element $u_{\alpha^{\prime}}$
corresponding to $v_{\alpha^{\prime}}$ in $U$. For every blue $\alpha$-vertex
$v$, we define $S_{v}\subseteq U$ as the collection of elements corresponding
to the red vertices in $\mathcal{I}_{i}$ that are adjacent to $v$. This
completes the construction of the instance.

It is easy to see the one-to-one correspondence between the optimum solutions
of these two instances. The running time of the algorithm follows from the
simple brute-force algorithm for Hitting Set parameterized by the size of the
universe and the fact that $\alpha$ has at most $\ell$ many children. ∎

##  4 Multicut with Undeletable Terminals

This section considers the MultiCut with Undeletable Terminals problem
formally defined as follows.

MultiCut with Undeletable Terminals (MultiCut with UnDel Term) Input: An
undirected graph $G$, a set $P\subseteq V(G)\times V(G)$, and an integer $k$.
Question: Is there a set $S\subseteq V(G)\setminus V(P)$ such that $\lvert
S\rvert\leq k$ and for all $(p,p^{\prime})\in P$, there is no path between $p$
and $p^{\prime}$ in $G-S$?

In the following, a set $S\subseteq V(G)\setminus V(P)$ such that for all
$(p,p^{\prime})\in P$, there is no path between $p$ and $p^{\prime}$ in $G-S$
is called a _$P$ -multicut_ in $G$. We first prove that when the input is
restricted to chordal graphs, the problem is unlikely to admit an algorithm
when parameterized by the leafage. We then complement this result with an
-algorithm parameterized by the leafage. We restate the theorem with the
precise statement for the reader’s convenience.

See 1.2

To prove that the problem is [1]-hard, we present a parameter preserving
reduction from Multicolored Clique. An instance of this problem consists of a
simple graph $G$, an integer $q$, and a partition $(V_{1},V_{2},\dots,V_{q})$
of $V(G)$. The objective is to determine whether there is a clique in $G$ that
contains exactly one vertex from each part $V_{i}$. Such a clique is called a
_multicolored clique_. We assume, without loss of generality, that each
$V_{i}$ is an independent set and that $|V_{1}|=\ldots=|V_{q}|=n$.666 Unlike
in the rest of the article, we _do not_ use $n$ to denote the total number of
vertices in $G$ to keep notation simple while presenting the reduction.  This
implies, in particular, that $|E(G)|<n^{2}\cdot q^{2}$. For every $i\in[q]$,
we denote by $v^{i}_{1},\ldots,v^{i}_{n}$ the vertex set of $V_{i}$ and for
every $i\neq j\in[q]$, we denote by $E_{i,j}\subseteq E(G)$ the set of edges
between $V_{i}$ and $V_{j}$. We define $M\coloneqq(n+1)^{2}\cdot q^{2}$.

$p_{1}$$K_{1}$$p_{2}$$K_{2}$$p_{3}$$\cdots$$p_{n}$$K_{n}$$p_{n+1}$ Figure 1:
The auxiliary graph $B$. Rectangles represent cliques and thick edges indicate
that the corresponding vertex is complete to the corresponding cliques.

#### Reduction.

The reduction takes as input an instance $(G,q,(V_{1},\dots,V_{q}))$ of
Multicolored Clique and outputs an instance $(H,P,k)$ of MultiCut with UnDel
Term which is constructed as follows.

  * •

The reduction starts by constructing an auxiliary graph $B$. The vertex set of
$B$ consists of $n+1$ vertices $p_{1},\ldots,p_{n+1}$ and $n$ vertex-disjoint
cliques $K_{1},\ldots,K_{n}$ such that $|K_{a}|=a\cdot M$ for every $a\in[n]$.
Then, it adds edges so that $p_{1}$ is complete to $K_{1}$, $p_{n+1}$ complete
to $K_{n}$, and $p_{a}$ complete to $K_{a-1}\cup K_{a}$ for every
$a\in[n]\setminus\\{1\\}$. This completes the construction of $B$ (see Figure
1).

  * •

For each $i\in[q]$, the reduction introduces two vertex-disjoint copies
$B^{i,\alpha}$ and $B^{i,\beta}$ of $B$. For every $i\in[q]$, let
$p_{1}^{i,\alpha},\dots,p_{n+1}^{i,\alpha}$ denote the copies of
$p_{1},\dots,p_{n+1}$ in $B^{i,\alpha}$ and
$K_{1}^{i,\alpha},\dots,K_{n}^{i,\alpha}$ denote the copies of
$K_{1},\ldots,K_{n}$ in $B^{i,\alpha}$. Moreover, for every $1\leq a_{1}\leq
a_{2}\leq n+1$, we define, for notational convenience,

$p^{i,\alpha}[a_{1},a_{2}]\coloneqq\\{p^{i,\alpha}_{a}\mid a_{1}\leq a\leq
a_{2}\\}$

and

$K^{i,\alpha}[a_{1},a_{2}]\coloneqq\bigcup_{a_{1}\leq a\leq
a_{2}}K^{i,\alpha}_{a}.$

We define $p^{i,\beta}_{a}$, $K^{i,\beta}_{a}$, $p^{i,\beta}[a_{1},a_{2}]$,
and $K^{i,\beta}[a_{1},a_{2}]$ in a similar way.

  * •

For $i\in[q]$ and $a\in[n]$, the reduction uses $p^{i,\alpha}_{a}$,
$p^{i,\beta}_{n+1-a}$, $K^{i,\alpha}_{a}$, and $K^{i,\beta}_{n+1-a}$ to encode
vertex $v^{i}_{a}$.

  * •

For every edge $e=v^{i}_{a_{i}}v^{j}_{a_{j}}\in E(G)$, the reduction
introduces an _edge-vertex_ $v_{e}$ and adds edges so that $v_{e}$ is complete
to the following sets.

    * –

$p^{i,\alpha}[a_{i}+1,n+1]$ and $K^{i,\alpha}[a_{i},n+1]$ in
$V(B^{i,\alpha})$.

    * –

$p^{j,\alpha}[a_{j}+1,n+1]$ and $K^{i,\alpha}[a_{j},n+1]$ in
$V(B^{j,\alpha})$.

    * –

$p^{i,\beta}[n+1-a_{i}+1,n+1]$ and $K^{i,\beta}[n+1-a_{i}+1,n+1]$ in
$V(B^{i,\beta})$.

    * –

$p^{j,\beta}[n+1-a_{j}+1,n+1]$ and $K^{i,\beta}[n+1-a_{j}+1,n+1]$ in
$V(B^{j,\beta})$.

Note that $v_{e}$ is adjacent to vertices in $K^{i,\alpha}[a_{i}]\cup
K^{j,\alpha}[a_{j}]$ but not to any vertex in $K^{i,\beta}[n+1-a_{i}]\cup
K^{j,\beta}[n+1-a_{j}]$.

  * •

The reduction introduces a central clique $K$ of size $2M^{2}$ and makes it
complete to $\\{p^{i,\alpha}_{n+1},p^{i,\beta}_{n+1}\mid i\in[q]\\}$ and
$V_{E}$ where $V_{E}=\\{v_{e}\mid e\in E(G)\\}$ is the set of edge-vertices.

This completes the construction of $H$.

  * •

The reduction further defines

$\displaystyle P$
$\displaystyle\coloneqq\\{(p_{a}^{i,\alpha},p_{n+2-a}^{i,\beta})\mid
a\in[n]\text{ and }i\in[q]\\},\text{ and }$ $\displaystyle k$
$\displaystyle\coloneqq q(n+1)M+|E(G)|-q(q-1)/2.$

The reduction returns $(H,P,k)$ as the instance of MultiCut with UnDel Term.
This completes the reduction. It is easy to see that $H$ is chordal and has
leafage at most $2q$. See Figure 2 for a tree representation of $H$.

$K_{1}^{2,\beta}$$K_{2}^{2,\beta}$$K_{3}^{2,\beta}$$K_{4}^{2,\beta}$$p_{1}^{2,\beta}$$p_{2}^{2,\beta}$$p_{3}^{2,\beta}$$p_{4}^{2,\beta}$$p_{5}^{2,\beta}$$K_{1}^{2,\alpha}$$K_{2}^{2,\alpha}$$K_{3}^{2,\alpha}$$K_{4}^{2,\alpha}$$p_{1}^{2,\alpha}$$p_{2}^{2,\alpha}$$p_{3}^{2,\alpha}$$p_{4}^{2,\alpha}$$p_{5}^{2,\alpha}$$K_{1}^{1,\beta}$$K_{2}^{1,\beta}$$K_{3}^{1,\beta}$$K_{4}^{1,\beta}$$p_{1}^{1,\beta}$$p_{2}^{1,\beta}$$p_{3}^{1,\beta}$$p_{4}^{1,\beta}$$p_{5}^{1,\beta}$$K_{1}^{1,\alpha}$$K_{2}^{1,\alpha}$$K_{3}^{1,\alpha}$$K_{4}^{1,\alpha}$$p_{1}^{1,\alpha}$$p_{2}^{1,\alpha}$$p_{3}^{1,\alpha}$$p_{4}^{1,\alpha}$$p_{5}^{1,\alpha}$$K$$v_{e^{\prime}}$$v_{e}$
Figure 2: A tree representation of the graph $H$ restricted to the gadgets
representing $V_{1}$, $V_{2}$ and $E_{1,2}$ where $n=4$ and
$E_{1,2}=\\{e=v_{3}^{1}v_{1}^{2},e^{\prime}=v_{4}^{1}v_{2}^{2}\\}$.

#### Intuition.

We first provide the intuition behind the reduction. Recall that the reduction
uses $p^{i,\alpha}_{a}$, $p^{i,\beta}_{n+1-a}$, $K^{i,\alpha}_{a}$, and
$K^{i,\beta}_{n+1-a}$ to encode vertex $v^{i}_{a}$ where $i\in[q]$ and
$a\in[n]$. Hence, for $a,b\in[n]$, if $a+b=n+1$, then $p^{i,\alpha}_{a}$ and
$p^{i,\beta}_{b}$ correspond to the same vertex. Note that the pairs in $P$
_do not_ correspond to the vertices associated with $v^{i}_{a}$. Rather,
$p^{i,\alpha}_{a+1}$ is paired with $p^{i,\beta}_{n+1-a}$. Conversely, for
$a,b\in[n]$, if $a+b=n+2$, then $(p^{i,\alpha}_{a},p^{i,\beta}_{b})\in P$. By
the construction of $H$ and $P$, for a $P$-multicut $S$ of $H$, if there is a
path from $p^{i,\alpha}_{a}$ to $p^{i,\beta}_{b}$ in $H-S$, then $a+b\geq
n+3$.

Now, consider the terminal pairs $(p^{i,\alpha}_{1},p^{i,\beta}_{n+1})$ in $P$
for some $i\in[q]$. Because of the size constraints, $S$ cannot contain all
the vertices of the central clique $K$. Since $S$ cannot contain a terminal,
it needs to include one clique from $B^{i,\alpha}$. Let $a_{i}\in[n]$ be the
largest index such that $K^{i,\alpha}_{a_{i}}\subseteq S$. Using similar
arguments, there must also exist $b_{i}\in[n]$ such that
$K^{i,\beta}_{b_{i}}\subseteq S$ and $b_{i}$ is largest such index. By
definition of $a_{i},b_{i}$ and construction of $H$, there is a path from
$p^{i,\alpha}_{a_{i}+1}$ to $p^{i,\beta}_{b_{i}+1}$ in $H-S$. The discussion
in the previous paragraph implies that $a_{i}+1+b_{i}+1\geq n+3$, i.e.,
$a_{i}+b_{i}\geq n+1$. However, by definition of the solution size $k$ and the
size of the cliques, we have $a_{i}+b_{i}\leq n+1$. Hence, the structure of
the auxiliary graphs and the terminal pairs ensure that the selected cliques
in $S\cap V(B^{i,\alpha})$ and $S\cap V(B^{i,\beta})$ encode selecting a
vertex in $V_{i}$ in $G$.

Suppose that
$\\{v_{a_{1}}^{1},v_{a_{2}}^{2},\allowbreak\ldots,v_{a_{q}}^{q}\\}$ are the
vertices in $G$ that are selected by $S$. Recall that $V_{E}$ is the
collection of edge-vertices in $H$. Considering the remaining budget, a
solution $S$ can include at most $|E(G)|-q(q-1)/2$ many vertices in $V_{E}$.
We argue that $q(q-1)/2$ edges in $G$ corresponding to vertices in
$V_{E}\setminus S$ should have their endpoints in
$\\{v_{a_{1}}^{1},v_{a_{2}}^{2},\allowbreak\ldots,v_{a_{q}}^{q}\\}$ as
otherwise some terminal pair is connected in $H-S$. Hence, a $P$-multicut $S$
of $H$ corresponds to a multicolored clique in $G$. We formalize this
intuition in the following two lemmas.

######  Lemma 4.1.

If $(G,q,(V_{1},V_{2},\dots,V_{q}))$ is a Yes-instance of Multicolored Clique,
then $(H,P,k)$ is a Yes-instance of MultiCut with UnDel Term.

###### Proof.

Assume that $(G,q,(V_{1},V_{2},\dots,V_{q}))$ is a Yes-instance of
Multicolored Clique and let
$\\{v_{a_{1}}^{1},v_{a_{2}}^{2},\allowbreak\ldots,v_{a_{q}}^{q}\\}$ be a
clique in $G$ such that $v^{i}_{a_{i}}\in V_{i}$ for every $i\in[q]$. We
construct a $P$-multicut $S$ of $H$ as follows. First, we add
$V_{E}\setminus\\{v_{e}\mid e\in\\{v_{a_{i}}^{i}v_{a_{j}}^{j}\mid
i,j\in[q]\\}\\}$ to $S$. For every $i\in[q]$, we further add
$K_{a_{i}}^{i,\alpha}$ and $K_{n+1-a_{i}}^{i,\beta}$ to $S$. It is easy to
verify that $|S|=q(n+1)M+|E(G)|-q(q-1)/2=k$.

Let us show that $S$ is indeed a $P$-multicut. Fix indices $i\in[q]$ and
$a\in[n]$, and consider the terminal pair
$(p^{i,\alpha}_{a},p^{i,\beta}_{n+2-a})$ in $P$. Suppose first that $a\leq
a_{i}$. By construction of $H$, any path from $p^{i,\alpha}_{a}$ to
$p^{i,\beta}_{n+2-a}$ in $H$ contains a vertex of $K^{i,\alpha}_{a_{i}}$ or of
$N(p^{i,\alpha}_{a_{i}})\cap V_{E}$. Recall that if edge $e\in E(G)$ is
incident on $v^{i}_{a_{i}}$, then the edge-vertex $v_{e}$ in $H$ is adjacent
only to vertices in $p^{i,\alpha}[a_{i}+1,\cdots,n+1]$ and
$K^{i,\alpha}[a_{i},\cdots,n+1]$ in $V(B^{i,\alpha})$; in particular, it is
_not_ adjacent to $p^{i,\alpha}_{a_{i}}$. As $S$ only excludes edge-vertices
in $V_{E}$ that encode edges incident on $v^{i}_{a_{i}}$, it contains every
vertex in $N(p^{i,\alpha}_{a_{i}})\cap V_{E}$. Since $S$ also contains every
vertex in $K^{i,\alpha}_{a_{i}}$, we conclude that there is no path from
$p^{i,\alpha}_{a}$ to $p^{i,\beta}_{n+2-a}$ in $H-S$.

Now, consider the case where $a_{i}<a$, i.e., $n+2-a<n+2-a_{i}$. In this case,
it is convenient to consider a path from $p^{i,\beta}_{n+2-a}$ to
$p^{i,\alpha}_{a}$. Once again, by construction of $H$, any path from
$p^{i,\beta}_{n+2-a}$ to $p^{i,\alpha}_{a}$ in $H$ contains a vertex of
$K^{i,\beta}_{n+2-(a_{i}+1)}=K^{i,\beta}_{n+1-a_{i}}$ or of
$N(p^{i,\beta}_{n+2-(a_{i}+1)})\cap V_{E}=N(p^{i,\beta}_{n+1-a_{i}})\cap
V_{E}$. Recall that if edge $e\in E(G)$ is incident on $v^{i}_{a_{i}}$, then
the corresponding edge-vertex $v_{e}$ in $H$ is adjacent only to vertices in
$p^{i,\beta}[n-a_{i}+2,\cdots n+1]$ and $K^{i,\beta}[n-a_{i}+2,\cdots,n+1]$ in
$V(B^{i,\beta})$; in particular, it is _not_ adjacent to
$p^{i,\beta}_{n+1-a_{i}}$. As $S$ only excludes edge-vertices in $V_{E}$ that
encode edges incident on $v^{i}_{a_{i}}$, it contains every vertex in
$N(p^{i,\beta}_{n+1-a_{i}})\cap V_{E}$. Since $S$ also contains every vertex
in $K^{i,\beta}_{n+1-a_{i}}$, we conclude that there is no path from
$p^{i,\beta}_{n+2-a}$ to $p^{i,\alpha}_{a}$. This implies that no terminal
pair in $P$ is connected in $H-S$ which concludes the proof. ∎

######  Lemma 4.2.

If $(H,P,k)$ is a Yes-instance of MultiCut with UnDel Term, then
$(G,q,(V_{1},V_{2},\dots,V_{q}))$ is a Yes-instance of Multicolored Clique.

###### Proof.

Assume that $(H,P,k)$ is a Yes-instance of MultiCut with UnDel Term and let
$S$ be a $P$-multicut of $H$ of size at most $k$. Recall that, by definition
of the problem, $S\cap V(P)=\emptyset$. Also, recall that the reduction adds
the clique $K$ of size $2M^{2}$ and makes it complete to
$\\{p^{i,\alpha}_{n+1},p^{i,\beta}_{n+1}\mid i\in[q]\\}$ and $V_{E}$. Note
that $K\setminus S\neq\emptyset$ as $k<2M^{2}$.

Consider an index $i\in[q]$. It is easy to see that there exists $a\in[n]$
such that $K^{i,\alpha}_{a}\subseteq S$ as otherwise, there is a path from
$p^{i,\alpha}_{1}$ to $p^{i,\beta}_{n+1}$ in $H-S$. Let $a_{i}\in[n]$ be the
largest index such that $K^{i,\alpha}_{a_{i}}\subseteq S$. Similarly, there
must exist $b\in[n]$ such that $K^{i,\beta}_{b}\subseteq S$: let $b_{i}\in[n]$
be the largest index such that $K^{i,\beta}_{b_{i}}\subseteq S$. Note that by
definition of $a_{i},b_{i}$ and the fact that $K\setminus S\neq\emptyset$,
there is path from $p^{i,\alpha}_{a_{i}+1}$ to $p^{i,\beta}_{b_{i}+1}$ in
$H-S$. Now suppose for a contradiction that $a_{i}+1+b_{i}+1\leq n+2$. Then
there exists $a^{\prime}_{i}\in[n]$ such that $a^{\prime}_{i}\geq a_{i}$ and
$a^{\prime}_{i}+1+b_{i}+1=n+2$ and so, by definition of $P$,
$(p^{i,\alpha}_{a^{\prime}_{i}+1},p^{i,\beta}_{b_{i}+1})\in P$. Moreover, by
construction of $H$, the existence of a path from $p^{i,\alpha}_{a_{i}+1}$ to
$p^{i,\beta}_{b_{i}+1}$ in $H-S$ implies that there is path from
$p^{i,\alpha}_{a^{\prime}_{i}+1}$ to $p^{i,\beta}_{b_{i}+1}$ in $H-S$; this
however, contradicts the fact that $S$ is a $P$-multicut of $H$. Therefore
$a_{i}+1+b_{i}+1\geq n+3$, i.e., $a_{i}+b_{i}\geq n+1$. Since this holds for
any $i\in[q]$, we have that

$\left|S\cap\left(\bigcup_{i\in[q]}V(B^{i,\alpha})\cup
V(B^{i,\beta})\right)\right|\geq\sum_{i\in[q]}(a_{i}M+b_{i}M)\geq q(n+1)M.$

Since $|E(G)|-q(q-1)/2<M$ and $S$ has size at most
$k=q(n+1)M+|E(G)|-q(q-1)/2$, it follows that, in fact, $a_{i}+b_{i}=n+1$ for
all $i\in[q]$. Hence, $S\cap(\bigcup_{i\in[q]}V(B^{i,\alpha})\cup
V(B^{i,\beta}))$ corresponds to a collection of vertices
$\\{v_{a_{1}}^{1},v_{a_{2}}^{2},\allowbreak\ldots,v_{a_{q}}^{q}\\}$ in $G$
such that $v^{i}_{a_{i}}\in V_{i}$ for every $i\in[q]$.

In the remaining proof, we argue that there are at least $q(q-1)/2$ edges with
endpoints in
$\\{v_{a_{1}}^{1},v_{a_{2}}^{2},\allowbreak\ldots,v_{a_{q}}^{q}\\}$. Since
$|E(G)|-q(q-1)/2<M$, and every clique in $B^{i,\alpha}$ is of size at least
$M$, for any $a\in[n]$ such that $a<a_{i}$, we have $K^{i,\alpha}_{a}\setminus
S\neq\emptyset$. In other words, there is at least one vertex in $H-S$ from
each clique $K^{i,\alpha}_{a}$ where $a<a_{i}$. Since $a_{i}$ is the largest
index such that $K^{i,\alpha}_{a_{i}}\subseteq S$, this also holds for every
$a>a_{i}$. As $S$ intersects every path from $p^{i,\alpha}_{1}$ to
$p^{i,\beta}_{n+1}$, it contains every vertex in $N(p^{i,\alpha}_{a_{i}})\cap
V_{E}$. Using similar arguments, we conclude that $S$ also contains every
vertex in $N(p^{i,\beta}_{b_{i}})\cap V_{E}=N(p^{i,\beta}_{n+1-a_{i}})\cap
V_{E}$. Now recall that if edge $e\in E(G)$ is incident on $v^{i}_{a_{i}}$,
then the corresponding edge-vertex $v_{e}$ in $H$ is adjacent to

  * •

terminals in $V(B^{i,\alpha})$ which are in $p^{i,\alpha}[a_{i}+1,n+1]$, and

  * •

terminals in $V(B^{i,\beta})$ which are in $p^{i,\beta}[n-a_{i}+2,n+1]$.

In particular, $v_{e}$ is _not_ adjacent to $p^{i,\alpha}_{a_{i}}$ and
$p^{i,\beta}_{n+1-a_{i}}$. This implies that only edges-vertices that
correspond to edges incident on $v^{i}_{a_{i}}$ can be excluded from $S$. As
this holds for any $i\in[q]$, every vertex in $V_{E}\setminus S$ has its
endpoints in
$\\{v_{a_{1}}^{1},v_{a_{2}}^{2},\allowbreak\ldots,v_{a_{q}}^{q}\\}$. As
$|S\cap(\bigcup_{i\in[q]}V(B^{i,\alpha})\cup V(B^{i,\beta}))|=q(n+1)M$ and
$k=q(n+1)M+|E(G)|-q(q-1)/2$, we have $|S\cap V_{E}|\leq|E(G)|-q(q-1)/2$ which
implies that $|V_{E}\setminus S|\geq q(q-1)/2$. Since $G$ is a simple graph,
it follows that
$\\{v_{a_{1}}^{1},v_{a_{2}}^{2},\allowbreak\ldots,v_{a_{q}}^{q}\\}$ is a
multicolored clique in $G$. This concludes the proof of the lemma. ∎

Finally, it is known that, assuming the ETH, there is no algorithm that can
solve Multicolored Clique on instance $(G,q,(V_{1},V_{2},\dots V_{q}))$ in
time $f(q)\cdot|V(G)|^{o(q)}$ for any computable function $f$ (see, e.g., [15,
Corollary 14.23]). Thus, together with the fact that the reduction takes
polynomial time in the size of the input, Lemmas 4.1 and 4.2, and arguments
that are standard for parameter preserving reductions, we conclude that the
following holds.

######  Lemma 4.3.

MultiCut with Undeletable Terminals on chordal graphs is [1]-hard when
parameterized by leafage $\ell$ and assuming the ETH, does not admit an
algorithm running in time $f(\ell)\cdot n^{o(\ell)}$ for any computable
function $f$.

The remainder of this section is devoted to the proof of the following lemma,
which together with Lemma 4.3 proves Theorem 1.2.

######  Lemma 4.4.

MultiCut with Undeletable Terminals on chordal graph of leafage at most $\ell$
admits an -algorithm running in time $n^{{\mathcal{O}}(\ell)}$.

###### Proof.

Let $(G,P)$ be an instance of MultiCut with UnDel Term where $G$ is a chordal
graph of leafage at most $\ell$. Let $(T,\mathcal{M})$ be a tree
representation of $G$ of leafage at most $\ell$. We say that a path in $T$ is
a _maximal degree- $2$ path_ if it contains no branching nodes, except for
possibly the first and last node of the path, and it cannot be extended
without violating this property (that is, it is maximal). A $P$-multicut $S$
of $G$ is said to _destroy_ an edge $e\in E(T)$ if
$\textnormal{{ver}}(e)\subseteq S$.

Let us root $T$ at an arbitrary node $\textsf{r}\in V(T)$. Since the number of
leaves of $T$ is at most $\ell$, $T$ has at most $2\ell-2$ maximal degree-$2$
paths, one starting at each each leaf or branching node (except the root) and
ending at the first ancestor in $T$ which is a branching node.

Now for each maximal degree-$2$ path $Q$ from $\alpha$ to $\beta$ in $T$,
guess the first (i.e., closest to $\alpha$) and last (i.e., closest to
$\beta$) edge of $Q$, say $e_{1}^{Q}$ and $e_{2}^{Q}$, respectively, such that
$S$ destroys $e_{1}^{Q}$ and $e_{2}^{Q}$. Note that, it might be the case that
an optimal solution does not destroy an edge of $Q$ or only destroys one edge
of $Q$ (i.e., $e_{1}^{Q}=e_{2}^{Q}$). Since the length of any maximal
degree-$2$ path is $\mathcal{O}(n)$, this creates at most $(n+1)^{2\ell}$
branches.

In each such branch, let $D\subseteq E(T)$ be the set of guessed edges of $T$.
Pick $V_{D}=\\{\textnormal{{ver}}(e)\mid e\in D\\}$ in the solution and delete
$V_{D}$ from $G$: let $(G^{\prime},P^{\prime})$ be the resulting instances and
further let $T^{\prime}$ be obtained from $T$ by deleting the edges in $D$ and
set $\mathcal{M}^{\prime}=\mathcal{M}|_{V(G^{\prime})}$. Observe that the tree
representation of each connected component of $G^{\prime}$ is given by some
tree of the forest $T^{\prime}$ together with $\mathcal{M}^{\prime}$
restricted to the vertices of the corresponding connected component. Note that
it is enough to solve the problem independently on each connected component of
$G^{\prime}$.

Thus, without loss of generality, assume that $G^{\prime}$ is connected and
let $(T^{\prime},\mathcal{M}^{\prime})$ be a tree representation of
$G^{\prime}$ as defined above. Suppose that $G^{\prime}$ has at least one
terminal pair in $P^{\prime}$, say $(s,t)\in P^{\prime}\subseteq P$. If
$T^{\prime}$ is a path, i.e., $G^{\prime}$ is an interval graph, then the
problem can be solved in polynomial time [27, Theorem 5]. Otherwise, we ignore
this branch.

The algorithm outputs a solution if there is at least one branch where a
solution was computed. Otherwise, there is no solution.

It is not difficult to see that the above algorithm indeed solves the problem,
as it considers all the possible ways a solution could intersect every maximal
degree-$2$ path. ∎

##  5 Multiway Cut with Undeletable Terminals on Chordal Graphs

In this section, we consider the Multiway Cut with Undeletable Terminals
problem formally defined below. Given a graph $G$ and a set $P\subseteq V(G)$,
a set $S\subseteq V(G)\setminus P$ is a called a _$P$ -multiway-cut_ in $G$ if
$G-S$ has no $(p,p^{\prime})$-path for any two distinct $p,p^{\prime}\in P$.

Multiway Cut with Undeletable Terminals (MWC) Input: An undirected graph $G$
and a set $P\subseteq V(G)$ of terminals. Question: Find the size of a minimum
$P$-multiway-cut in $G$.

The aim of this section is to prove Theorem 1.3 which states that Multiway Cut
with Undeletable Terminals can be solved in $n^{\mathcal{O}(1)}$-time on
chordal graphs. Before turning to the proof, we first start with a few
definitions. Let $(T,{\mathcal{M}})$ a tree representation of a chordal graph
$G$ where $T$ is rooted at an arbitrary node $\textsf{r}\in V(T)$. Given a
subtree $T^{\prime}$ of $T$ and a set $Q\subseteq V(G)$, we let
$Q_{|T^{\prime}}\subseteq Q$ be the set of vertices $x\in Q$ such that
${\mathcal{M}}(x)\subseteq V(T^{\prime})$. Now let $Q\subseteq V(G)$ be an
independent set of $G$ such that for every leaf $\eta$ of $T$,
$\textnormal{{ver}}(\eta)\cap Q\neq\emptyset$. Then the _truncated tree w.r.t.
$Q$_ is the tree $T^{\textsf{trunc}}_{Q}$ obtained from $T$ as follows. Let
$\\{\eta_{1},\ldots,\eta_{q}\\}$ be the set of leaves of $T$. For each
$i\in[q]$, let $Q_{i}\subseteq Q\setminus\textnormal{{ver}}(\textsf{r})$ be
the set of vertices $p\in Q\setminus\textnormal{{ver}}(\textsf{r})$ such that
$\mathtt{top}_{\mathcal{M}}(p)$ is on the $(\eta_{i},\textsf{r})$-path in $T$,
and let $p_{i}\in Q_{i}$ be the vertex of $Q_{i}$ such that
$\mathtt{top}_{\mathcal{M}}(p_{i})$ is closest to r. Then
$T^{\textsf{trunc}}_{Q}$ is obtained from $T$ by deleting the subtrees rooted
at the children of the nodes in
$\\{\mathtt{top}_{\mathcal{M}}(p_{i})~{}|~{}i\in[q]\\}$. Note that, by
construction, the set of leaves of $T^{\textsf{trunc}}_{Q}$ is
$\\{\mathtt{top}_{\mathcal{M}}(p_{i})~{}|~{}i\in[q]\\}$ and that, apart from
the vertices in $\\{p_{i}~{}|~{}i\in[q]\\}$, there is at most one other vertex
in $Q$ whose model intersects $V(T^{\textsf{trunc}}_{Q})$, namely the
potential vertex in $Q\cap\textnormal{{ver}}(\textsf{r})$ (note that if such a
vertex exists, its model is in fact fully contained in
$T^{\textsf{trunc}}_{Q}$). Finally, given a set $P\subseteq V(G)$, a
$P$-multiway-cut $X$ in $G$ is said to _destroy_ an edge $e\in E(T)$ if
$\textnormal{{ver}}(e)\subseteq X$.

We now turn to the proof of Theorem 1.3. Throughout the remaining of this
section, we let $(G,P)$ be an instance of MWC, where $G$ is a $n$-vertex
chordal graph, and further let $(T,\mathcal{M})$ be a tree representation of
$G$. First, we may assume that $P$ is an independent set: indeed, if there
exist $p,p^{\prime}\in P$ such that $pp^{\prime}\in E(G)$, then $(G,P)$ is a
No-instance. Furthermore, if a vertex $v\in V(G)$ does not belong to any
$(p,p^{\prime})$-path in $G$, where $p,p^{\prime}\in P$, then it can be safely
deleted as no minimal $P$-multiway-cut in $G$ may contain $v$. Hence, we
assume that every vertex in $G$ participates in some $(p,p^{\prime})$-path
where $p,p^{\prime}\in P$; in particular, we may assume that for every leaf
$\eta$ of $T$, $\textnormal{{ver}}(\eta)\cap P\neq\emptyset$. Note that,
consequently, for every internal node $\alpha\in V(T)$, the truncation of
$T_{\alpha}$ w.r.t. $P_{|T_{\alpha}}$ exists.

Now let $T_{0}$ be the tree obtained by adding a new node $\textsf{r}_{0}$ and
connecting it to an arbitrary node $\textsf{r}\in V(T)$. Observe that
$(T_{0},\mathcal{M})$ is also a tree representation of $G$. In the following,
we root $T_{0}$ at $\textsf{r}_{0}$. To prove Theorem 1.3, we design a dynamic
program that computes, in a bottom-up traversal of $T_{0}$, the entries of a
table A whose content is defined as follows. The table A is indexed over the
edges of $E(T_{0})$. For each node $\alpha\in V(T)$,
$\texttt{A}[\alpha\operatorname{\mathtt{parent}}_{T_{0}}(\alpha)]$ stores the
size of a minimum $P_{|T_{\alpha}}$-multiway-cut in $G_{|T_{\alpha}}$. The
size of a minimum $P$-multiway-cut in $G$ may then be found in
$\texttt{A}[\textsf{r}\textsf{r}_{0}]$. We describe below how to compute the
entries of A.

#### Update Procedure.

For every leaf $\eta$ of $T$, we set
$\texttt{A}[\eta\operatorname{\mathtt{parent}}_{T_{0}}(\eta)]=0$. Consider now
an internal node $\alpha$ of $T$. We show how to compute
$\texttt{A}[\alpha\operatorname{\mathtt{parent}}_{T_{0}}(\alpha)]$ assuming
that for every edge $e\in E(T_{\alpha})$, the entry $\texttt{A}[e]$ is
correctly filled.

Let $\widetilde{T}$ be the truncation of $T_{\alpha}$ w.r.t. $P_{|T_{\alpha}}$
and let $\widetilde{G}=G_{|\widetilde{T}}$. Denote by
$\eta_{1},\ldots,\eta_{q}$ the leaves of $\widetilde{T}$. Recall that, by
construction, for every $i\in[q]$, there exists $p_{i}\in P_{|T_{\alpha}}$
such that $\eta_{i}=\mathtt{top}_{\mathcal{M}}(p_{i})$: we let
$\widetilde{P}=\\{p_{i}~{}|~{}i\in[q]\\}$. Furthermore, it may be that
$P_{|T_{\alpha}}\cap\textnormal{{ver}}(\textsf{r})$ is nonempty: we let
$\widetilde{P}_{\textsf{r}}=P_{|T_{\alpha}}\cap\textnormal{{ver}}(\textsf{r})$.
Note that $|\widetilde{P}_{\textsf{r}}|\leq 1$: if
$\widetilde{P}_{\textsf{r}}\neq\emptyset$ then we refer to the terminal in
$\widetilde{P}_{\textsf{r}}$ as the _root terminal_. Observe that
$V(\widetilde{G})\cap P_{|T_{\alpha}}=V(\widetilde{G})\cap
P=\widetilde{P}\cup\widetilde{P}_{\textsf{r}}$ by construction. To compute
$\texttt{A}[\alpha\operatorname{\mathtt{parent}}_{T_{0}}(\alpha)]$, we
distinguish two cases:

  * (1)

if $\widetilde{P}_{\textsf{r}}\neq\emptyset$ then we construct a unique
instance $(H_{0},\texttt{s},\texttt{t},\texttt{wt}_{0})$ of $(s,t)$-Cut;

  * (2)

otherwise, for every $i\in[0,q]$, we construct an instance
$(H_{i},\texttt{s},\texttt{t},\texttt{wt}_{i})$ of $(s,t)$-Cut.

We describe below how such instances are constructed. First, recall that an
instance of the $(s,t)$-Cut problem consists of a digraph $D$, vertices
$s,t\in V(D)$, a weight function
$\texttt{wt}:E(D)\to\mathbb{N}\cup\\{\infty\\}$, and the goal is to find a set
$X\subseteq E(D)$ such that $D-X$ has no $(s,t)$-path and $\texttt{wt}(X)$ is
minimum with this property, where $\texttt{wt}(X)=\sum_{u\in
X}\texttt{wt}(u)$.

#### Construction of the $(s,t)$-Cut Instances.

For every $i\in[q]$, let us denote by
$\widetilde{P}_{i}=\widetilde{P}\setminus\\{p_{i}\\}$ and let
$\widetilde{P}_{0}=\widetilde{P}$. Consider $i\in[0,q]$. Before turning to the
formal construction of the instance
$(H_{i},\texttt{s},\texttt{t},\texttt{wt}_{i})$, let us first give an
intuitive idea of the construction. The digraph $H_{i}$ is obtained from
$\widetilde{T}$ by orienting all edges of $\widetilde{T}$ towards its root
$\tilde{\textsf{r}}=\alpha$ and further adding vertices and weighted arcs to
encode the graph $G_{|T_{\alpha}}$. The arcs in $H_{i}$ corresponding to the
edges of $\widetilde{T}$ are called the tree arcs and the nodes in $H_{i}$
corresponding to the nodes of $\widetilde{T}$ are called the tree nodes. The
idea is that we separate, for each terminal $p\in\widetilde{P}_{i}$, the node
$\mathtt{top}_{\mathcal{M}}(p)$ from the root $\tilde{\textsf{r}}$. To achieve
this, we add a _source_ node s and _source_ arcs from s to
$\mathtt{top}_{\mathcal{M}}(p)$ (of infinite weight) and look for an
$(\texttt{s},\tilde{\textsf{r}})$-cut in $H_{i}$. Since the edges of $T$ can
presumably not be independently destroyed in a $P$-multiway-cut, we need some
additional vertices to encode these dependencies. For each vertex $v\in
V(\widetilde{G})\setminus\widetilde{P}_{i}$, we introduce a node $\gamma(v)$
in $H_{i}$ which is reachable via _connection_ arcs (with infinite weight)
from all the tree nodes that are contained in the model of $v$. This node
$\gamma(v)$ is further connected via a _sink_ arc (of weight one) to
$\mathtt{top}_{\mathcal{M}}(v)$ which ensures that if we want to cut a tree
arc, we also have to cut all the sink arcs associated to vertices containing
the corresponding edge in their model. The index $i$ is then used to specify
which root-to-leaf path of $\widetilde{T}$ is uncut: if $i=0$ then every such
path is cut, otherwise the $(\eta_{i},\tilde{\textsf{r}})$-path is uncut. To
encode the rest of the solution, we associate with each tree arc
$(\beta,\delta)$ a weight $\texttt{wt}_{i}((\beta,\delta))$ corresponding to
the size of a minimum $P_{|\beta}$-multiway-cut in $G_{|\beta}$.

We proceed with the formal construction of $H_{i}$. The vertex set of $H_{i}$
is $V(H_{i})=V(\widetilde{T})\uplus\\{\texttt{s}\\}\uplus\\{\Gamma\\}$ where
$\Gamma=\\{\gamma(v)\mid v\in V(\widetilde{G})\setminus\widetilde{P}\\}$, that
is, $\Gamma$ contains a node of every non-terminal vertex in $\widetilde{G}$.
For every $z\in\Gamma$, we denote by $\gamma^{-1}(z)$ the corresponding vertex
in $V(\widetilde{G})\setminus\widetilde{P}$. The arc set of $H_{i}$ is
partitioned into four sets:

  * •

the set $E_{\widetilde{T}}$ of _tree arcs_ containing all the edges of
$\widetilde{T}$ oriented towards the root $\tilde{\textsf{r}}$,

  * •

the set
$E^{i}_{\texttt{source}}=\\{(\texttt{s},\mathtt{top}_{\mathcal{M}}(p))\mid
p\in\widetilde{P}_{i}\\}$ of _source_ arcs,

  * •

the set
$E_{\texttt{conn}}=\\{(\alpha,\gamma(v))\mid\gamma(v)\in\Gamma,\alpha\in\mathcal{M}(v)\cap
V(\widetilde{T})\\}$ of _connection_ arcs and

  * •

the set $E_{\texttt{sink}}=\\{(\gamma(v),\mathtt{top}_{\mathcal{M}}(v))\mid
v\in V(\widetilde{G})\setminus\widetilde{P}\\}$ of _sink_ arcs.

Furthermore, if $\widetilde{P}_{\textsf{r}}\neq\emptyset$, then we let
$E_{\texttt{rterm}}\subseteq E_{\widetilde{T}}$ be the set of tree arcs
$(\beta,\delta)\in E_{\widetilde{T}}$ such that the edge $\beta\delta$ is
contained in the model of the root terminal; otherwise, we let
$E_{\texttt{rterm}}=\emptyset$. The weight function
$\texttt{wt}_{i}:E(H_{i})\to\mathbb{N}\cup\\{\infty\\}$ is defined as follows.
For every $j\in[q]$, let $\rho_{j}$ be the path in $\widetilde{T}$ from
$\eta_{j}$ to $\tilde{\textsf{r}}$ and let $\overrightarrow{\rho_{j}}$ be the
corresponding directed path in $H_{i}$ (that is, $\overrightarrow{\rho_{j}}$
is the path in $H_{i}$ from $\eta_{j}$ to $\tilde{\textsf{r}}$ consisting only
of tree arcs). Then for every arc $e$ of $H_{i}$,

$\texttt{wt}_{i}(e)=\begin{cases}\texttt{A}[e]&\text{if }i=0\text{ and }e\in
E_{\widetilde{T}}\setminus E_{\texttt{rterm}}\\\ \texttt{A}[e]&\text{if }i\neq
0\text{, }e\in E_{\widetilde{T}}\text{ and }e\text{ does not belong to the
path }\overrightarrow{\rho_{i}}\\\ 1&\text{if }e\in E_{\texttt{sink}}\\\
\infty&\text{otherwise.}\end{cases}$

Note, in particular, that every arc in $E_{\texttt{rterm}}$ (if any) has
infinite weight. Similarly, if $i\neq 0$, then every arc of the path
$\overrightarrow{\rho_{i}}$ has infinite weight. This completes the
construction of the instance
$(H_{i},\texttt{s},\texttt{t}=\tilde{\textsf{r}},\texttt{wt}_{i})$ (see Figure
3). It is easy to see that such an instance can be constructed in
${\mathcal{O}}(n^{2})$-time.

$\eta_{1}$$\eta_{2}$$\eta_{3}$$\beta_{1}$$\beta_{2}$$\alpha=\tilde{\textsf{r}}$$p_{1}$$p_{2}$$p_{3}$$u$$w$$v$
(a) The tree representation
$(\widetilde{T},{\mathcal{M}}_{|V(\widetilde{G})})$ of $\widetilde{G}$ where
$V(\widetilde{G})=\\{p_{1},p_{2},p_{3},u,v,w\\}$ and
$\widetilde{P}_{\textsf{r}}=\emptyset$.

$\eta_{1}$$\eta_{2}$$\eta_{3}$$\beta_{1}$$\beta_{2}$$\alpha=\tilde{\textsf{r}}$$\gamma(u)$$\gamma(v)$$\gamma(w)$s$1$$1$$1$$\texttt{A}[\eta_{1}\beta_{1}]$$\texttt{A}[\eta_{3}\beta_{2}]$$\texttt{A}[\beta_{2}\alpha]$
(b) The instance $(H_{2},\texttt{s},\tilde{\textsf{r}},\texttt{wt}_{2})$
(thick arcs have infinite weight).

Figure 3: An illustration of the construction of the $(s,t)$-Cut instances.

Now let $X_{0}$ be an $(\texttt{s},\tilde{\textsf{r}})$-cut in $H_{0}$ such
that $\texttt{wt}_{0}(X_{0})$ is minimum; and if
$\widetilde{P}_{\textsf{r}}=\emptyset$, then for every $i\in[q]$, further let
$X_{i}$ be an $(\texttt{s},\tilde{\textsf{r}})$-cut in $H_{i}$ such that
$\texttt{wt}_{i}(X_{i})$ is minimum. For each $i\in[q]$, let us denote by
$\textnormal{{cost}}_{i}=\texttt{A}[\eta_{i}\operatorname{\mathtt{parent}}_{T_{0}}(\eta_{i})]$
and let $\textnormal{{cost}}_{0}=0$. Then we set

$\texttt{A}[\alpha\operatorname{\mathtt{parent}}_{T_{0}}(\alpha)]=\begin{cases}|X_{0}|&\text{if
}\widetilde{P}_{\textsf{r}}\neq\emptyset\\\
\min_{i\in[0,q]}\\{|X_{i}|+\textnormal{{cost}}_{i}\\}&\text{otherwise}\end{cases}$

In the following, for convenience, we let $I=[0,q]$ if
$\widetilde{P}_{\textsf{r}}=\emptyset$, and $I=\\{0\\}$ otherwise. We next
show that the entry
$\texttt{A}[\alpha\operatorname{\mathtt{parent}}_{T_{0}}(\alpha)]$ is updated
correctly. To this end, we show that $G_{|T_{\alpha}}$ has a
$P_{|T_{\alpha}}$-multiway-cut of size at most $k$ if and only if there exists
$i\in I$ such that $H_{i}$ has an $(\texttt{s},\tilde{\textsf{r}})$-cut of
weight at most $k-\textnormal{{cost}}_{i}$ w.r.t. $\texttt{wt}_{i}$.

######  Lemma 5.1.

For any $i\in I$, if $H_{i}$ has an $(\texttt{s},\tilde{\textsf{r}})$-cut $Y$
such that $\texttt{wt}_{i}(Y)\leq k-\textnormal{{cost}}_{i}$, then
$G_{|T_{\alpha}}$ has a $P_{|T_{\alpha}}$-multiway-cut of size at most $k$.

###### Proof.

Assume that there exists $i\in I$ such that $H_{i}$ has an
$(\texttt{s},\tilde{\textsf{r}})$-cut $Y$ where $\texttt{wt}_{i}(Y)\leq
k-\textnormal{{cost}}_{i}$. For every $j\in[q]\setminus\\{i\\}$, let $A_{j}$
be the set of tree arcs on the path $\overrightarrow{\rho_{j}}$ belonging to
$Y$ (recall that $\overrightarrow{\rho_{j}}$ is the path in $H_{i}$ from
$\eta_{j}$ to $\tilde{\textsf{r}}$ consisting only of tree arcs). Note that
since $Y$ is an $(\texttt{s},\tilde{\textsf{r}})$-cut, $A_{j}\neq\emptyset$
for every $j\in[q]\setminus\\{i\\}$.

######  Claim 5.2.

For every terminal $j\in[q]\setminus\\{i\\}$, there exists an arc $(x,y)\in
A_{j}$ such that for every $z\in
N_{H_{i}}^{+}(x)\setminus(N_{H_{i}}^{-}(x)\cup\\{y\\})$, the sink arc with
tail $z$ belongs to $Y$.

###### Proof.

Suppose for a contradiction that this does not hold for some index
$j\in[q]\setminus\\{i\\}$, that is, for every arc $(x,y)\in A_{j}$, there
exists $z\in N_{H_{i}}^{+}(x)\setminus(N_{H_{i}}^{-}(x)\cup\\{y\\})$ such that
the sink arc with tail $z$ does not belong to $Y$. Let
$(x_{1},y_{1}),\ldots,(x_{a},y_{a})$ be the arcs of $A_{j}$ ordered according
to their order of appearance when traversing the path
$\overrightarrow{\rho_{j}}$. We show that, in this case, there is a path from
s to $\tilde{\textsf{r}}$ in $H-Y$. For every $b\in[a]$, denote by
$Z_{b}\subseteq
N_{H_{i}}^{+}(x_{b})\setminus(N_{H_{i}}^{-}(x_{b})\cup\\{y_{b}\\})$ the set of
vertices $z$ such that the sink arc with tail $z$ does not belong to $Y$. Let
$b_{1},\ldots,b_{w}\in[a]$ be the longest sequence defined as follows:

  * •

$b_{1}\in[a]$ is the largest index such that $Z_{1}\cap
Z_{b_{1}}\neq\emptyset$ and

  * •

for every $l>1$, $b_{l}\in[a]$ is the largest index such that
$Z_{b_{l-1}+1}\cap Z_{b_{l}}\neq\emptyset$.

For every $l\in[w]$, consider a vertex $z_{b_{l}}\in Z_{j_{l}}$ and let
$h_{b_{l}}\in N_{H_{i}}^{+}(z_{b_{l}})$ be the head of the sink arc with tail
$z_{b_{l}}$. Then for every $l\in[w-1]$, $h_{b_{l}}$ lies on the path
$\overrightarrow{\rho_{j}}[y_{b_{l}},x_{b_{l}+1}]$: indeed, since
$z_{b_{l}}\notin Z_{b_{l}+1}$ by the choice of $b_{l}$, either
$z_{b_{l}}\notin N_{H_{i}}^{+}(x_{b_{l}+1})$ or $z_{b_{l}}\in
N_{H_{i}}^{+}(x_{b_{l}+1})\cap N_{H}^{-}(x_{b_{l}+1})$; but $z_{b_{l}}\in
N_{H_{i}}^{+}(x_{b_{l}})\setminus N_{H_{i}}^{-}(x_{b_{l}})$ by construction,
and so, $h_{b_{l}}$ necessarily lies on
$\overrightarrow{\rho_{j}}[y_{b_{l}},x_{b_{l}+1}]$.

Now observe that, by maximality of the sequence, $b_{w}=a$: indeed, if
$b_{w}<a$ then the sequence could be extended as $Z_{b_{w}+1}\neq\emptyset$ by
assumption. Since $z_{b_{w}}\notin N_{H_{i}}^{-}(x_{b_{w}})$, this implies, in
particular, that $h_{b_{w}}$ lies on the path
$\overrightarrow{\rho_{j}}[y_{b_{w}},\tilde{\textsf{r}}]$. It follows that

$\texttt{s}\overrightarrow{\rho_{j}}[\eta_{j},x_{1}]z_{b_{1}}\overrightarrow{\rho_{j}}[h_{b_{1}},x_{b_{1}+1}]z_{b_{2}}\ldots
z_{b_{l}}\overrightarrow{\rho_{j}}[h_{b_{l}},x_{b_{l}+1}]z_{b_{{l}+1}}\ldots\overrightarrow{\rho_{j}}[h_{b_{w-1}},x_{b_{w-1}+1}]z_{b_{w}}L[h_{b_{w}},\tilde{\textsf{r}}]$

is a path from s to $\tilde{\textsf{r}}$ in $H-Y$, a contradiction which
proves our claim. ∎

For every $j\in[q]\setminus\\{i\\}$, let $e_{j}=(x_{j},y_{j})\in A_{j}$ be the
arc closest to $\tilde{\textsf{r}}$ such that for every $z\in
N_{H_{i}}^{+}(x_{j})\setminus(N_{H_{i}}^{-}(x_{j})\cup\\{y_{j}\\})$, the sink
arc with tail $z$ belongs to $Y$ (note that we may have $e_{j}=e_{j^{\prime}}$
for two distinct $j,j^{\prime}\in[q]\setminus\\{i\\}$). Denote by
$E=\\{e_{j}\mid j\in[q]\setminus\\{i\\}\\}\cup\\{e^{*}\\}$ where
$e^{*}=(\eta_{i},\operatorname{\mathtt{parent}}(\eta_{i}))$. For every
$e=(x,y)\in E$, let $\widetilde{P}_{e}\subseteq\widetilde{P}_{i}$ be the set
of terminals in $\widetilde{P}_{i}$ which are also terminals in the instance
restricted to $T_{x}$. Note that $\\{P_{e}\mid e\in E\setminus\\{e^{*}\\}\\}$
is a partition of $\widetilde{P}_{i}$: indeed, by construction, every
$p\in\widetilde{P}_{i}$ belongs to at least one such set and if there exist
$e,e^{\prime}\in E\setminus\\{e^{*}\\}$ such that
$\widetilde{P}_{e}\cap\widetilde{P}_{e^{\prime}}\neq\emptyset$, then for any
$j\in[q]\setminus\\{i\\}$ such that $p_{j}\in P_{e}\cap P_{e^{\prime}}$,
$e,e^{\prime}\in A_{j}$; in particular, both $e$ and $e^{\prime}$ lie on the
path $\overrightarrow{\rho_{j}}$, a contradiction to the choice of the arc in
$A_{j}$.

Now for every $e=(x,y)\in E$, let $S_{e}$ be a minimum $P_{|T_{x}}$-multiway-
cut in $G_{|T_{x}}$ and denote by
$N_{e}=N_{H_{i}}^{+}(x)\setminus(N_{H_{i}}^{-}(x)\cup\\{y\\})$. We define

$S=S_{e^{*}}\cup\bigcup_{e\in
E\setminus\\{e^{*}\\}}S_{e}\cup\\{\gamma^{-1}(z)\mid z\in N_{e}\\}.$

######  Claim 5.3.

$S$ is a $P_{|T_{\alpha}}$-multiway-cut in $G_{|T_{\alpha}}$.

###### Proof.

Since for every $e=(x,y)\in E$, $S_{e}$ is a $P_{|T_{x}}$-multiway-cut in
$G_{|T_{x}}$, it is in fact enough to show that for every $e,e^{\prime}\in E$,
$p\in\widetilde{P}_{e}$ and $p^{\prime}\in\widetilde{P}_{e^{\prime}}$, there
is no path from $p$ to $p^{\prime}$ in $G_{|T_{\alpha}}-S$.

Consider therefore $j,j^{\prime}\in[q]\setminus\\{i\\}$ such that
$p_{j}\in\widetilde{P}_{e}$ and $p_{j^{\prime}}\in\widetilde{P}_{e^{\prime}}$
for two distinct $e,e^{\prime}\in E$. Since, as shown above,
$\\{\widetilde{P}_{f}\mid f\in E\setminus\\{e^{*}\\}\\}$ is a partition of
$\widetilde{P}_{i}$, $p_{j^{\prime}}\notin\widetilde{P}_{e}$ and
$p_{j}\notin\widetilde{P}_{e^{\prime}}$; in particular, $e^{\prime}$ does not
lie on the path $\overrightarrow{\rho_{j}}$ and $e$ does not lie on the path
$\overrightarrow{\rho_{j^{\prime}}}$. It follows that any path in
$G_{|T_{\alpha}}$ from $p_{j}$ to $p_{j^{\prime}}$ contains at least one
vertex $x$ whose model contains the edge corresponding to $e$; but then,
$\gamma(x)\in N_{e}$ and so, $x\in S$ by construction. Thus, there is no path
from $p_{j}$ to $p_{j^{\prime}}$ in $G_{|T_{\alpha}}-S$. ∎

Finally, note that, by construction,

$\begin{split}|S|&=|S_{e^{*}}|+\sum_{e\in
E\setminus\\{e^{*}\\}}|S_{e}|+\left\lvert\bigcup_{e\in
E\setminus\\{e^{*}\\}}\\{\gamma^{-1}(z)\mid z\in N_{e}\\}\right\rvert\\\
&=|S_{e^{*}}|+\sum_{e\in
E\setminus\\{e^{*}\\}}\texttt{wt}_{i}(e)+\sum_{z\in\bigcup_{e\in
E\setminus\\{e^{*}\\}}N_{e}}\texttt{wt}_{i}((z,\mathtt{top}_{\mathcal{M}}(\gamma^{-1}(z))))\\\
&\leq\textnormal{{cost}}_{i}+\texttt{wt}_{i}(Y)\leq k\end{split}$

which concludes the proof. ∎

######  Lemma 5.4.

If $G_{|T_{\alpha}}$ has a $P_{|T_{\alpha}}$-multiway-cut $X$ of size at most
$k$, then there exists $i\in I$ such that $H_{i}$ has an
$(\texttt{s},\tilde{\textsf{r}})$-cut $Y$ where $\texttt{wt}_{i}(Y)\leq
k-\textnormal{{cost}}_{i}$.

###### Proof.

Recall that for every $j\in[q]$, $\rho_{j}$ is the unique
$(\eta_{j},\tilde{\textsf{r}})$-path in $\widetilde{T}$. To prove the lemma,
we first show the following.

######  Claim 5.5.

If there exists $i\in[q]$ such that $G_{|T_{\alpha}}$ has a
$P_{|T_{\alpha}}$-multiway-cut $X$ of size at most $k$ where

  * (1)

$X$ does not destroy any edge of $\rho_{i}$ and

  * (2)

for every $j\in[q]\setminus\\{i\\}$, $X$ destroys an edge of $\rho_{j}$,

then $H_{i}$ has an $(\texttt{s},\tilde{\textsf{r}})$-cut $Y$ such that
$\texttt{wt}_{i}(Y)\leq k-\textnormal{{cost}}_{i}$.

###### Proof.

Assume that such an index $i\in[q]$ exists and let $X$ be a
$P_{|T_{\alpha}}$-multiway-cut $X$ of size at most $k$ satisfying item (1) and
(2). Note that since $X$ does not destroy any edge of $\rho_{i}$,
$\widetilde{P}_{\textsf{r}}=\emptyset$ for, otherwise, $p_{i}$ and the root
terminal would be in the same connected component of $G_{|T_{\alpha}}-X$
thereby contradicting the fact that $X$ is a $P_{|T_{\alpha}}$-multiway-cut.
For every $j\in[q]\setminus\\{i\\}$, let $e_{j}\in E(\widetilde{T})$ be the
closest edge to $\eta_{j}$ on $\rho_{j}$ such that
$\textnormal{{ver}}(e_{j})\subseteq X$ (note that the edges
$e_{1},\ldots,e_{q}$ are not necessarily pairwise distinct). Denote by
$E=\\{e_{j}~{}|~{}j\in[q]\setminus\\{i\\}\\}$. We construct an
$(\texttt{s},\tilde{\textsf{r}})$-cut $Y$ in $H_{i}$ as follows: $Y$ contains
the tree arcs of $H_{i}$ corresponding to the edges in $E$ and for each $v\in
X$ such that $\mathcal{M}(v)$ contains at least one edge of $E$ (that is,
$v\in\textnormal{{ver}}(e)$ for some edge $e\in E$), we include in $Y$ the
sink arc $(\gamma(v),\mathtt{top}_{\mathcal{M}}(v))$ of $E(H_{i})$. Let us
show that $Y$ is indeed an $(\texttt{s},\tilde{\textsf{r}})$-cut in $H_{i}$.

For every $j\in[q]\setminus\\{i\\}$, let $V_{-}^{j}\subseteq V(\widetilde{T})$
($V_{+}^{j}\subseteq V(\widetilde{T})$, respectively) be the set of nodes of
the subpath of $\rho_{j}$ from $\eta_{j}$ to the tail of $e_{j}$ (the head of
$e_{j}$ to $\tilde{\textsf{r}}$, respectively). We contend that for every
$j\in[q]\setminus\\{i\\}$, there is no $(V_{-}^{j},V_{+}^{j})$-path in
$H_{i}-Y$. Note that if true, this would prove that $Y$ is indeed an
$(\texttt{s},\tilde{\textsf{r}})$-cut in $H_{i}$. For the sake of
contradiction, suppose that, for some $j\in[q]\setminus\\{i\\}$, there is a
path $L$ in $H_{i}-Y$ from a vertex $x\in V_{-}^{j}$ to a vertex $y\in
V_{+}^{j}$. Since the tree arc in $H_{i}$ corresponding $e_{j}$ belongs to
$Y$, there must exist a vertex $z\in V(L)$ such that $N^{-}_{H_{i}}(z)\cap
V_{-}^{j}\cap V(L)\neq\emptyset$ and $N^{+}_{H_{i}}(z)\cap V_{+}^{j}\cap
V(L)\neq\emptyset$; in particular, the sink arc $e$ with tail $z$ must belong
to $L$. By construction of $H_{i}$, it must then be that
$\mathcal{M}(\gamma^{-1}(z))$ contains the edge $e_{j}$, that is,
$\gamma^{-1}(z)\in\textnormal{{ver}}(e_{j})$; but then, $\gamma^{-1}(z)\in X$
and so, $e\in Y$ by construction, a contradiction which proves our claim.

Let us finally show that $\texttt{wt}_{i}(Y)\leq k-\textnormal{{cost}}_{i}$.
To this end, for every $e\in E$, let $X_{e}\subseteq X$ be the restriction of
$X$ to $T_{t_{e}}$ where $t_{e}$ is the endpoint of $e$ the furthest from
$\tilde{\textsf{r}}$ (note that for any two distinct $e,e^{\prime}\in E$,
$X_{e}\cap X_{e^{\prime}}=\emptyset$). Then, for every $e\in E$, $X_{e}$ is a
$P_{|T_{t_{e}}}$-multiway-cut in $G_{|T_{t_{e}}}$ and so,
$\texttt{wt}_{i}(e)\leq|X_{e}|$. Similarly, the restriction $X_{i}$ of $X$ to
$T_{\eta_{i}}$ is a $P_{|T_{\eta_{i}}}$-multiway-cut in $G_{|T_{\eta_{i}}}$
and so, $|X_{i}|\geq\textnormal{{cost}}_{i}$ (note that, by construction,
$X_{i}\cap X_{e}=\emptyset$ for every $e\in E$). Letting
$X^{\prime}=\bigcup_{e\in E}\textnormal{{ver}}(e)$, it then follows from the
definition of $Y$ that

$\texttt{wt}_{i}(Y)=|X^{\prime}|+\sum_{e\in
E}\texttt{wt}_{i}(e)\leq|X^{\prime}|+\sum_{e\in E}|X_{e}|\leq|X|-|X_{i}|\leq
k-\textnormal{{cost}}_{i}$

as $X^{\prime}\cap X_{i}=\emptyset$ and for every $e\in E$, $X^{\prime}\cap
X_{e}=\emptyset$. ∎

Using similar arguments, we can also prove the following.

######  Claim 5.6.

If $G_{|T_{\alpha}}$ has a $P_{|T_{\alpha}}$-multiway-cut $X$ of size at most
$k$ such that for every $i\in[q]$, $X$ destroys an edge of $\rho_{i}$, then
$H_{0}$ has an $(\texttt{s},\tilde{\textsf{r}})$-cut $Y$ such that
$\texttt{wt}_{i}(Y)\leq k$.

To conclude the proof of Lemma 5.4, let us show that for any
$P_{|T_{\alpha}}$-multiway-cut $S$ in $G_{|T_{\alpha}}$, $S$ destroys an edge
of every root-to-leaf path of $\widetilde{T}$, except for at most one when
$\widetilde{P}_{\textsf{r}}=\emptyset$. Note that if the claim is true, the
lemma would then follow from Claims 5.5 and 5.6.

Let $S$ be a $P_{|T_{\alpha}}$-multiway-cut in $G_{|T_{\alpha}}$. Observe
first that if $\widetilde{P}_{\textsf{r}}\neq\emptyset$ then for every
$i\in[q]$, $S$ must destroy an edge of $\rho_{i}$ for, otherwise, $p_{i}$ and
the root terminal are in the same connected component of $G_{|T_{\alpha}}-S$,
thereby contradicting the fact that $S$ is a $P_{|T_{\alpha}}$-multiway-cut.
Assume therefore that $\widetilde{P}_{\textsf{r}}=\emptyset$ and suppose, for
the sake of contradiction, that there exist two distinct indices $i,j\in[q]$
such that $S$ destroys no edge of $\rho_{i}$ and no edge of $\rho_{j}$. Then
for every edge $e$ of $\rho_{i}\cup\rho_{j}$, $\textnormal{{ver}}(e)\setminus
S\neq\emptyset$: for each such edge $e$, let
$\alpha_{e}\in\textnormal{{ver}}(e)\setminus S$. It is now not difficult to
see that there is a path in $G_{|T_{\alpha}}-S$ from $p_{i}$ to $p_{j}$ using
only vertices from $\\{\alpha_{e}\mid e\text{ is an edge of
}\rho_{i}\cup\rho_{j}\\}$, a contradiction to the fact that $S$ be a
$P_{|T_{\alpha}}$-multiway-cut in $G_{|T_{\alpha}}$. ∎

We now conclude by Lemmas 5.1 and 5.4, that
$\texttt{A}[\alpha\operatorname{\mathtt{parent}}_{T_{0}}(\alpha)]$ indeed
stores the size of a minimum $P_{|T_{\alpha}}$-multiway-cut in
$G_{|T_{\alpha}}$. Since the construction of each $H_{i}$ takes polynomial-
time, an $(\texttt{s},\texttt{t})$-cut in $H_{i}$ can be computed in
polynomial time (see, for instance, [22]) and the number of $H_{i}$s is at
most $n$, it takes plynomial-time to update
$\texttt{A}[\alpha\operatorname{\mathtt{parent}}_{T_{0}}(\alpha)]$. Finally,
since the number of edges of $T$ is linear in $n$, the overall running time is
polynomial in $n$, which proves Theorem 1.3. We remark that a more careful
analysis of the running time of the algorithm leads to an upper bound of
${\mathcal{O}}(n^{4})$.

##  6 Restricting to $H_{\ell}$-induced-subgraph-free chordal graphs

In this section, we consider problems restricted to $H_{\ell}$-induced-
subgraph-free chordal graphs. Recall that $H_{\ell}$ is the split graph on
$2\ell$ vertices such that if $V(H_{\ell})=C\uplus I$ is a split partition
then $(i)$ $|C|=|I|=\ell$, $(ii)$ every vertex in $C$ is adjacent to exactly
one vertex in $I$, and $(iii)$ every vertex in $I$ is adjacent to exactly one
vertex in $C$. As mentioned in the Introduction, the class of
$H_{\ell}$-induced-subgraph-free chordal graphs is a natural generalization of
the class of chordal graphs of leafage at most $\ell$. In fact, denoting by
$\mathcal{C}_{\ell}$ the collection of all chordal graphs that have leafage at
most $\ell$ and by $\mathcal{C}^{is}_{\ell}$ the collection of all chordal
graphs that do not contain $H_{\ell}$ as a induced subgraph (that is, the
collection of $H_{\ell}$-induced-subgraph-free chordal graphs), the following
holds.

######  Observation 6.1.

$\mathcal{C}_{\ell}\subsetneq\mathcal{C}^{is}_{\ell+1}$.

Let us briefly explain why 6.1 holds true. Walter generalized the concept of
asteroidal triple in order to characterize other subclasses of chordal graphs
[45] as follows. A subset of nonadjacent vertices of $G$ is an _asteroidal
set_ if the removal of the closed neighborhood of any one of its elements does
not disconnect the remaining ones. Formally, a set of vertices $A$ of a graph
$G$ is _asteroidal_ if for each $a\in A$, the vertices in $A\setminus\\{a\\}$
belong to a common connected component of $G-N[a]$. The asteroidal number of
$G$, denoted by $\texttt{at}(G)$, is then the size of a largest asteroidal set
of $G$. Note that in the graph $H_{\ell+1}$, $I$ is an asteroidal set of size
$\ell+1$ and thus, $\texttt{at}(H_{\ell+1})\geq\ell+1$. By definition, if $H$
is a subgraph of $G$ and $H$ is connected, then
$\texttt{at}(H)\leq\texttt{at}(G)$. Lin et al. [37, Therorem $1$] proved that
for a connected chordal graph $G$, $\texttt{at}(G)\leq\texttt{lf}(G)$. Hence,
if $\texttt{lf}(G)\leq\ell$, then it cannot contain $H_{\ell+1}$ as an induced
subgraph. This implies that
$\mathcal{C}_{\ell}\subseteq\mathcal{C}^{is}_{\ell+1}$. To see that
$\mathcal{C}_{\ell}$ is proper subset of $\mathcal{C}^{is}_{\ell+1}$, consider
a graph obtained from a star by subdividing every edge once. Then it is easy
to see that this graph does not contain $H_{3}$ as induced subgraph but can
have unbounded leafage.

The remainder of this section is organized as follows. In Subsection 6.1, we
argue that the algorithms for domination problems cannot be generalized to
this larger graph class. We complement this with an -algorithm, which is
optimal under the ETH. In Subsection 6.2, we present a simple algorithm to
prove that MultiCut with UnDel Term is paraNP-hard on this graph class. This
implies that the -algorithm presented in Section 4 cannot be generalized for
this larger class.

###  6.1 Dominating Set and related problems

In this subsection, we prove Theorem 1.4. We first show the hardness results
of the theorem and provide afterwards the -algorithms for the problems.

######  Lemma 6.2.

Dominating Set, Connected Dominating Set and Steiner Tree on
$H_{\ell}$-induced-subgraph-free chordal graphs are W[1]-hard when
parameterized by $\ell$ and assuming the ETH, do not admit an algorithm
running in time $f(\ell)\cdot n^{o(\ell)}$ for any computable function $f$.

###### Proof.

We present a parameter preserving reduction from Multicolored Independent Set.
An instance of this problem consists of a graph $G$, an integer $q$, and a
partition $(V_{1},\dots,V_{q})$ of $V(G)$. The objective is to determine
whether $G$ has an independent set which contains exactly one vertex from
every part $V_{i}$. We assume, without loss of generality, that each $V_{i}$
is an independent set. We present a slight modification of a known reduction
(see [15, Theorem $13.9$]).

#### Reduction.

The reduction takes as input an instance $(G,q,(V_{1},\dots,V_{q}))$ of
Multicolored Independent Set and constructs a graph $G^{\prime}$ as follows.

  * •

For every vertex $v\in V(G)$, the reduction introduces a vertex $v$ into
$G^{\prime}$: we denote by $C$ the set of all these vertices in $G^{\prime}$.
Note that the sets $V_{i}$ carry over directly to $G^{\prime}$.

  * •

The reduction turns the set $C$ into a clique in $G^{\prime}$ by adding edges
between any two distinct vertices of $C$.

  * •

For every $i\in[q]$, the reduction introduces two new vertices $x_{i},y_{i}$
into $G^{\prime}$ and makes them adjacent to every vertex of $V_{i}$.

  * •

For every edge $e=uv\in E(G)$ with endpoints $u\in V_{i}$ and $v\in V_{j}$,
the reduction introduces a vertex $w_{e}$ into $G^{\prime}$ and makes it
adjacent to every vertex of $(V_{i}\cup V_{j})\setminus\\{u,v\\}$.

For DomSet and connDomSet the reduction returns the instance $(G^{\prime},q)$.
For Steiner Tree, it sets all the vertices in $V(G^{\prime})\setminus C$ as
terminals and returns the instance $(G^{\prime},V(G^{\prime})\setminus C,q)$.

#### Correctness.

In the following claim, we prove that the reduction produces equivalent
instances. We only prove the claim for DomSet; the correctness for the other
two problems follows immediately from the design of the graph $G^{\prime}$.

######  Claim 6.3.

$(G,q,(V_{1},\dots,V_{q}))$ is a Yes-instance for Multicolored Independent Set
if and only if $(G^{\prime},q)$ is a Yes-instance for DomSet.

###### Proof.

Assume that $(G,q,(V_{1},\dots,V_{q}))$ is a Yes-instance for Multicolored
Independent Set and let $I$ be an independent set $I$ of $G$ containing one
vertex from each $V_{i}$. We claim that $I$ is a dominating set in
$G^{\prime}$. Since for every $i\in[q]$, $I\cap V_{i}\neq\emptyset$, the set
$I$ dominates every vertex in $V_{i}\cup\\{x_{i},y_{i}\\}$. For an edge
$e=uv\in E(G)$ where $u\in V_{i}$ and $v\in V_{j}$, consider the vertex
$w_{e}$. As $u$ and $v$ are adjacent, at least one of them is not in $I$, say
$u\notin I$ without loss of generality. Since $I\cap V_{i}\neq\emptyset$,
there must then exist $w\in V_{i}\setminus\\{u\\}$ such that $w\in I$; but
$w_{e}$ is adjacent to $w$ by construction and thus, $I$ dominates $w_{e}$.

Conversely, assume that $(G^{\prime},q)$ is a Yes-instance for DomSet and let
$D$ be a dominating set of size $q$ in $G^{\prime}$. We claim that $D$ is also
an independent set in $G$. Since for every $i\in[q]$, $D$ dominates the
vertices $x_{i}$ and $y_{i}$, $D$ has to contain at least one vertex from
$V_{i}\cup\\{x_{i},y_{i}\\}$; and since $x_{i}$ and $y_{i}$ are not adjacent,
in fact $D$ must contain a vertex from $V_{i}$. As these sets are disjoint for
different values of $i$ and $|D|\leq q$, it follows that $D$ contains exactly
one vertex from each $V_{i}$: let $v_{1}\in V_{1},\dots,v_{q}\in V_{q}$ be the
vertices of $D$. Now suppose for a contradiction that $v_{i}$ and $v_{j}$ are
the endpoints of an edge $e$. By construction, vertex $w_{e}$ in $G^{\prime}$
is adjacent only to $(V_{i}\cup V_{j})\setminus\\{v_{i},v_{j}\\}$ and hence,
$D$ does not dominate $w_{e}$, a contradiction. ∎

The following claim holds for all three problems as it only depends on the
structure of the graph $G^{\prime}$.

######  Claim 6.4.

$G^{\prime}$ does not contain $H_{2q+2}$ as an induced subgraph.

###### Proof.

We first partition the vertex set of $V(G^{\prime})$. For this, let
$I=V(G^{\prime})\setminus C$. It is easy to see that $I$ is an independent set
and since $C$ is a clique in $G^{\prime}$, $G^{\prime}$ is in fact a split
graph with split partition $(C,I)$. For each integer $i\in[q]$, the vertices
in $I$ can be partitioned into the following three sets depending on their
adjacency in $V_{i}$.

  1. 1.

Vertices that are adjacent to _all_ vertices in $V_{i}$: these are the
vertices $x_{i},y_{i}$.

  2. 2.

Vertices that are adjacent to _all but one_ vertex in $V_{i}$: these are the
vertices of type $w_{e}$ for edges $e$ with one endpoint in $V_{i}$.

  3. 3.

Vertices that are adjacent to _no_ vertex in $V_{i}$: these are the vertices
of type $w_{e}$ for edges $e$ with both endpoints are outside $V_{i}$, and the
vertices $x_{i^{\prime}},y_{i^{\prime}}$ where $i\neq i^{\prime}$.

Recall that by assumption, $V_{i}$ is an independent set in $G$ and thus,
there is no edge with both endpoints in $V_{i}$.

Now suppose, for the sake of contradiction, that $G^{\prime}$ contains
$H_{2q+2}$ as an induced subgraph. Consider the (unique) split partition
$(H_{C},H_{I})$ of $H_{2q+2}$. Let $H_{C}=\\{v_{1},v_{2},\dots,v_{2q+2}\\}$
and $H_{I}=\\{u_{1},u_{2},\dots,u_{2q+2}\\}$. Moreover, for every
$i\in[2q+2]$, edge $v_{i}u_{i}$ is in $E(H_{2q+2})$. Consider the clique
$H_{C}$ in $G^{\prime}$. As $I$ is an independent set, $|H_{C}\cap I|\leq 1$.
Hence, $H_{C}$ contains at least $2q+1$ vertices of $C$. By the Pigeon-Hole
principle, there must then exist an integer $i\in[q]$ such that $|H_{C}\cap
V_{i}|\geq 3$: let $v_{1},v_{2},v_{3}$ be three vertices of $H_{C}\cap V_{i}$.

Since by construction, $u_{1}$ is not adjacent to $v_{2}$ and $v_{3}$, and
$v_{2},v_{3}$ are in $C$, it must be that $u_{1}\in I$. But then, $u_{1}$ is
adjacent to one vertex in $V_{i}$, namely $v_{1}$, and nonadjacent to two
vertices in $V_{i}$, namely $v_{2}$ and $v_{3}$, a contradiction to the fact
that vertices in $I$ can be partitioned into the three sets described above.
Therefore, $G$ does not contain $H_{2q+2}$ as an induced subgraph. ∎

It is known that, assuming the ETH, there is no algorithm that can solve
Multicolored Independent Set on instance $(G,q,(V_{1},V_{2},\dots V_{q}))$ in
time $f(q)\cdot|V(G)|^{o(q)}$ for any computable function $f$ (see, e.g., [15,
Corollary 14.23]). Note finally, that
$|V(G^{\prime})|\in{\mathcal{O}}(|V(G)|^{2})$ and $G^{\prime}$ is an
$H_{2q+2}$ induced-subgraph-free split graph. These facts, together with
arguments that are standard for parameter preserving reductions, concludes the
proof of the lemma. ∎

In the following, we give the -algorithms for the three problems. Instead of
giving the algorithm for DomSet, we give an algorithm for the more general
Red-Blue-DomSet. Recall that, from Lemma 3.1, there is a reduction from the
former to the latter problem. There remains to argue that this reduction
preserves the property of being $H_{\ell}$-induced-subgraph-free.

######  Lemma 6.5.

There is a polynomial-time algorithm that given an instance $(G,k)$ of DomSet
constructs an equivalent instance $(G^{\prime},(R^{\prime},B^{\prime}),k)$ of
Red-Blue-DomSet such that if $G$ is a $H_{\ell}$-induced-subgraph-free graph,
then so is $G^{\prime}$.

###### Proof.

As in Lemma 3.1, we construct $G^{\prime}$ from $G$ as follows. For every
vertex $v\in V(G)$, add two copies $v_{R}$ and $v_{B}$ to $V(G^{\prime})$ and
add an edge $v_{R}v_{B}$ to $E(G^{\prime})$. For every edge $uv\in E(G)$, add
edges $v_{R}u_{R}$, $v_{R}u_{B}$, $v_{B}u_{R}$, and $v_{B}u_{B}$ to
$E(G^{\prime})$. This completes the construction of $G^{\prime}$. By the proof
of Lemma 3.1, it is known that these two instances are equivalent. In the
following, we let $R^{\prime}=\\{v_{R}\mid v\in V(G)\\}$ and
$B^{\prime}=\\{v_{B}\mid v\in V(G)\\}$.

Now assume that $G$ is $H_{\ell}$-induced-subgraph-free and suppose, for the
sake of contradiction, that $G^{\prime}$ contains $H_{\ell}$ as an induced
subgraph. Let $I$ be the vertices forming the independent set and $C$ the
vertices forming the clique of $H_{\ell}$. We claim that for no vertex $v\in
V(G)$, we have that $v_{B},v_{R}\in C\cup I$. Note that if the claim holds,
then using the original version of each vertex would give an induced
$H_{\ell}$ in $G$ and thus contradict our assumption.

There remains to prove the claim. To this end, consider $v\in V(G)$. Since $I$
is an independent set, $v_{B}$ and $v_{R}$ cannot both be contained in $I$.
Moreover, it can also not be the case that $v_{B}\in I$ and $v_{R}\in C$ (or
vice-versa) as then $v_{B}$ would also be adjacent to all vertices in $C$.
Hence, assume that $v_{B},v_{R}\in C$. Assume, without loss of generality,
that $u_{B}\in I$ is the unique vertex adjacent to $v_{B}$ in $C$ (the case
where $u_{R}\in I$ is the unique adjacent vertex is symmetric). Since there is
an edge from $v_{B}$ to $u_{B}$, we know that $u$ and $v$ are adjacent in $G$.
Hence, by construction, there must also be an edge from $v_{R}$ to $u_{B}$
which contradicts the fact that we have an $H_{\ell}$ graph. ∎

We are now ready to show that Red-Blue-DomSet on chordal graphs admits an
-algorithm if the input graph does not contain $H_{\ell}$ as induced subgraph.

######  Lemma 6.6.

Red-Blue Dominating Set restricted to $H_{\ell}$-induced-subgraph-free chordal
graphs admits an algorithm running in time $n^{\mathcal{O}(\ell)}$.

###### Proof.

Let $(G,(R,B),k)$ be an instance of Red-Blue-DomSet where $G$ is an
$H_{\ell}$-induced-subgraph-free chordal graph, and let $(T,\mathcal{M})$ be a
tree representation of $G$. First, we add a node r to $T$ by connecting it to
an arbitrary node of $T$ and root $T$ at r (note that, by construction, no
model in $\mathcal{M}$ contains r). We use dynamic programming to compute the
entries of two tables $\mathsf{T_{1}}$ and $\mathsf{T_{2}}$ in a bottom-up
traversal of $T$. The contents of $\mathsf{T_{1}}$ and $\mathsf{T_{2}}$ are
defined as follows. For every node $\alpha\in V(T)$ and every _nonempty_ set
$X\subseteq R_{\alpha}^{\in}$ of size at most $\ell$,

$\displaystyle\mathsf{T_{1}}[\alpha,X]\coloneqq\min\\{\lvert S\rvert\mid
S\subseteq R_{\alpha}^{\cap},S\cap R_{\alpha}^{\in}=X,N[S]\supseteq
B_{\alpha}^{\cap}\\}$

Intuitively, this stores the (size of the) smallest set of red vertices
containing $X$ such that all blue vertices in $T_{\alpha}$ are dominated.

For every node $\alpha\in V(T)$ and every set $Y\subseteq
R_{\alpha}^{\subseteq{\dagger}}$ of size at most $\ell$,

$\displaystyle\mathsf{T_{2}}[\alpha,Y]\coloneqq\min\\{\lvert S\rvert\mid
S\subseteq R_{\alpha}^{\subseteq{\dagger}},N[S]\supseteq
B_{\alpha}^{\subseteq{\dagger}}\cup(N(Y)\cap B_{\alpha}^{\in})\\}$

Intuitively, this stores the (size of the) smallest set of red vertices
intersecting with $T_{\alpha}$ but not $\alpha$ which dominate all blue
vertices below $\alpha$ and the $\alpha$-blues that are neighbors of the red
vertices in $Y$.

Initially, every entry of $\mathsf{T_{1}}$ and $\mathsf{T_{2}}$ is set to
$+\infty$. The output is Yes if and only if
$\mathsf{T_{2}}[\textsf{r},\emptyset]\leq k$. We next show how to update the
entries of $\mathsf{T_{1}}$ and $\mathsf{T_{2}}$.

#### Updating the Leaves.

Let $\alpha\in V(T)$ be a leaf of $T$. Then set

$\mathsf{T_{2}}[\alpha,\emptyset]=0$

and for every nonempty set $X\subseteq R_{\alpha}^{\in}$ of size at most
$\ell$, set

$\mathsf{T_{1}}[\alpha,X]=|X|.$

#### Updating Internal Nodes.

Let $\alpha\in V(T)$ be an internal node of $T$ and let
$\beta_{1},\ldots,\beta_{p}$ be the children of $\alpha$. To update the
entries of $\mathsf{T_{1}}[\alpha,\cdot]$, we proceed as follows. Let
$X\subseteq R_{\alpha}^{\in}$ be a nonempty set of size at most $\ell$. Denote
by $I\subseteq[p]$ the set of indices $i\in[p]$ such that $X\cap
R_{\beta_{i}}^{\in}\neq\emptyset$ and set $\overline{I}=[p]\setminus I$. For
every $i\in I$, further let $X_{i}=X\cap R_{\beta_{i}}^{\in}$. We update
$\mathsf{T_{1}}[\alpha,X]$ according to the following procedure.

  1. 1.

For every $i\in I$, set

$m_{i}=\min_{\begin{subarray}{c}Z\subseteq R_{\beta_{i}}^{\in}\setminus
R_{\alpha}^{\in}\\\ \text{s.t.
}|Z|+|X_{i}|\leq\ell\end{subarray}}\mathsf{T_{1}}[\beta_{i},Z\cup X_{i}].$

  2. 2.

For every $i\in\overline{I}$, let

$\mathcal{Y}_{i}=\\{Z\subseteq
R_{\beta_{i}}^{\subseteq{\dagger}}\mid|Z|\leq\ell\text{ and
}B_{\beta_{i}}^{\in}\setminus B_{\alpha}^{\in}\subseteq N(Z)\\}$

and set

$m_{i}^{1}=\min_{\begin{subarray}{c}Z\subseteq R_{\beta_{i}}^{\in}\setminus
R_{\alpha}^{\in}\\\ \text{s.t.
}1\leq|Z|\leq\ell\end{subarray}}\mathsf{T_{1}}[\beta_{i},Z]\qquad\text{ and
}\qquad m_{i}^{2}=\min_{Z\in\mathcal{Y}_{i}}\mathsf{T_{2}}[\beta_{i},Z].$

  3. 3.

Set

$\mathsf{T_{1}}[\alpha,X]=|X|+\sum_{i\in
I}m_{i}-|X_{i}|+\sum_{i\in\overline{I}}\min\\{m_{i}^{1},m_{i}^{2}\\}.$

To update the entries of $\mathsf{T_{2}}[\alpha,\cdot]$, we proceed as
follows. Let $Y\subseteq R_{\alpha}^{\subseteq{\dagger}}$ be a set of size at
most $\ell$. Denote by $I\subseteq[p]$ the set of indices $i\in[p]$ such that
$Y\cap R_{\beta_{i}}^{\cap}\neq\emptyset$ and set $\overline{I}=[p]\setminus
I$. We update $\mathsf{T_{2}}[\alpha,Y]$ according to the following procedure.

  1. 1.

Initialise $\mathsf{OPT}_{\overline{I}}=0$ and $\mathsf{OPT}_{I}=+\infty$.

  2. 2.

For every $i\in\overline{I}$ do:

    1. 2.a.

Let

$\mathcal{Y}_{i}=\\{Z\subseteq
R_{\beta_{i}}^{\subseteq{\dagger}}\mid|Z|\leq\ell\text{ and
}B_{\beta_{i}}^{\in}\setminus B_{\alpha}^{\in}\subseteq N(Z)\\}$

and set

$m_{i}^{1}=\min_{\begin{subarray}{c}Z\subseteq R_{\beta_{i}}^{\in}\setminus
R_{\alpha}^{\in}\\\ \text{s.t.
}1\leq|Z|\leq\ell\end{subarray}}\mathsf{T_{1}}[\beta_{i},Z]\qquad\text{ and
}\qquad m_{i}^{2}=\min_{Z\in\mathcal{Y}_{i}}\mathsf{T_{2}}[\beta_{i},Z].$

    2. 2.b.

Set
$\mathsf{OPT}_{\overline{I}}=\mathsf{OPT}_{\overline{I}}+\min\\{m_{i}^{1},m_{i}^{2}\\}$.

  3. 3.

For every partition $N=\\{N_{i}\mid i\in I\\}$ of $N(Y)\cap B_{\alpha}^{\in}$
where for every $i\in I$, $N_{i}\subseteq N(Y_{i})\cap B_{\alpha}^{\in}$ do:

    1. 3.a.

Initialise $\mathsf{Int}_{N}=0$.

    2. 3.b.

For every $i\in I$ do:

      1. 3.b.i.

Let

$\mathcal{Y}_{i}^{N}=\\{Z\subseteq
R_{\beta_{i}}^{\subseteq{\dagger}}\mid|Z|\leq\ell\text{ and
}N_{i}\cup(B_{\beta_{i}}^{\in}\setminus B_{\alpha}^{\in})\subseteq N(Z)\\}$

and set

$m_{i}^{1}=\min_{\begin{subarray}{c}Z\subseteq R_{\beta_{i}}^{\in}\setminus
R_{\alpha}^{\in}\\\ \text{s.t.
}1\leq|Z|\leq\ell\end{subarray}}\mathsf{T_{1}}[\beta_{i},Z]\text{ and
}m_{i}^{2}=\min_{Z\in\mathcal{Y}_{i}^{N}}\mathsf{T_{2}}[\beta_{i},Z].$

      2. 3.b.ii.

Set $\mathsf{Int}_{N}=\mathsf{Int}_{N}+\min\\{m_{i}^{1},m_{i}^{2}\\}$.

    3. 3.c.

Set $\mathsf{OPT}_{I}=\min\\{\mathsf{OPT}_{I},\mathsf{Int}_{N}\\}$.

  4. 4.

Set $\mathsf{T_{2}}[\alpha,Y]=\mathsf{OPT}_{\overline{I}}+\mathsf{OPT}_{I}$.

We next show that the entries of $\mathsf{T_{1}}[\alpha,\cdot]$ and
$\mathsf{T_{2}}[\alpha,\cdot]$ are updated correctly. To this end, we first
introduce some useful notation. Given a set $X\subseteq B$, a set $S\subseteq
R$ _minimally dominates_ $X$ if $X\subseteq N(S)$ and for every $x\in S$,
$X\not\subseteq N(S\setminus\\{x\\})$. Additionally, we prove the following.

######  Claim 6.7.

For every node $\alpha\in V(T)$, the following hold.

  1. (i)

For every minimum red-blue dominating set $S$ of $G$, $|S\cap
R_{\alpha}^{\in}|\leq\ell$.

  2. (ii)

For every set $X\subseteq B_{\alpha}^{\in}$ and every set $Y\subseteq
R\setminus R_{\alpha}^{\in}$ minimally dominating $X$, $|Y|\leq\ell$.

###### Proof.

To prove item (i), let $S$ be a minimum red-blue dominating set of $G$. Since
$S$ is minimum, for every $x\in S\cap R_{\alpha}^{\in}$, there exists
$p_{x}\in N(x)\cap B$ such that $p_{x}\notin\bigcup_{y\in
S\setminus\\{x\\}}N(y)$, i.e., the blue vertex $p_{x}$ is only dominated by
$x$. Then $\\{p_{x}~{}|~{}x\in S\cap R_{\alpha}^{\in}\\}$ is an independent
set: indeed, if there exist $x,y\in S\cap R_{\alpha}^{\in}$ such that
$p_{x}p_{y}\in E(G)$ then $x,p_{x},p_{y},y$ induces a $C_{4}$, a contradiction
as $G$ is chordal. It follows that $(S\cap
R_{\alpha}^{\in})\cup\\{p_{x}~{}|~{}x\in S\cap R_{\alpha}^{\in}\\}$ induces an
$H_{|S\cap R_{\alpha}^{\in}|}$ and so, $|S\cap R_{\alpha}^{\in}|<\ell$.

To prove item (ii), let $X\subseteq B_{\alpha}^{\in}$ and let $Y\subseteq
R\setminus R_{\alpha}^{\in}$ be a set minimally dominating $X$. Since $Y$ is
minimal, for every $x\in Y$, there exists $p_{x}\in N(x)\cap X$ such that
$p_{x}\notin\bigcup_{y\in Y\setminus\\{x\\}}N(y)$, i.e., the blue vertex
$p_{x}$ is only dominated by $x$. This implies that $Y$ is an independent set:
indeed, if there exist $x,y\in Y$ such that $xy\in E(G)$ then
$x,p_{x},p_{y},y$ induces a $C_{4}$, a contradiction as $G$ is chordal. It
follows that $Y\cup\\{p_{x}~{}|~{}x\in Y\\}$ induces an $H_{|Y|}$ and so,
$|Y|<\ell$. ∎

We now move towards proving the correctness of the update procedure. We start
with the first table.

######  Claim 6.8.

For every internal node $\alpha\in V(T)$, the entries of
$\mathsf{T_{1}}[\alpha,\cdot]$ are updated correctly. Furthermore,
$\mathsf{T_{1}}[\alpha,\cdot]$ can be updated in $n^{\mathcal{O}(\ell)}$-time.

###### Proof.

Let $\alpha\in V(T)$ be an internal node of $T$ with children
$\beta_{1},\ldots,\beta_{p}$ and assume that for every $i\in[p]$,
$\mathsf{T_{1}}[\beta_{i},\cdot]$ and $\mathsf{T_{2}}[\beta_{i},\cdot]$ have
been correctly filled. Let us first show that for every nonempty set
$X\subseteq R_{\alpha}^{\in}$ of size at most $\ell$, there exists a set
$S\subseteq R_{\alpha}^{\cap}$ of size $\mathsf{T_{1}}[\alpha,X]$ such that
$S\cap R_{\alpha}^{\in}=X$ and $S$ dominates every vertex in
$B_{\alpha}^{\in}$.

Consider a nonempty set $X\subseteq R_{\alpha}^{\in}$ of size at most $\ell$.
Let $I\subseteq[p]$ be the set of indices $i\in[p]$ such that $X\cap
R_{\beta_{i}}^{\in}\neq\emptyset$ and set $\overline{I}=[p]\setminus I$. For
every $i\in I$, further let $X_{i}=X\cap R_{\beta_{i}}^{\in}$. For every $i\in
I$, let $m_{i}$ be as defined in Step 1. and let $Z_{i}\subseteq
R_{\beta_{i}}^{\in}\setminus R_{\alpha}^{\in}$ be a set such that
$|Z_{i}|+|X_{i}|\leq\ell$ and $m_{i}=\mathsf{T_{1}}[\beta_{i},Z_{i}\cup
X_{i}]$.

Then, since for every $i\in I$, $\mathsf{T_{1}}[\beta_{i},\cdot]$ has been
correctly filled, there exists a set $S_{i}\subseteq R_{\beta_{i}}^{\cap}$ of