Ben-Gurion University, Beer Sheva,
Israelmichal.wloda@gmail.comhttps://orcid.org/0000-0003-0968-8414 Supported by
the European Research Council (ERC) grant titled PARAPATH. Part of the work
has been carried out when the author was a postdoctorate student at the
Eindhoven University of Technology. Michał Włodarczyk <ccs2012> <concept>
<concept_id>10003752.10003809.10003635</concept_id> <concept_desc>Theory of
computation Graph algorithms analysis</concept_desc>
<concept_significance>500</concept_significance> </concept> <concept>
<concept_id>10003752.10003809.10010052</concept_id> <concept_desc>Theory of
computation Parameterized complexity and exact algorithms</concept_desc>
<concept_significance>500</concept_significance> </concept> </ccs2012>
[500]Theory of computation Graph algorithms analysis [500]Theory of
computation Parameterized complexity and exact algorithms Kousha Etessami,
Uriel Feige, and Gabriele Puppis 3 50th International Colloquium on Automata,
Languages, and Programming (ICALP 2023) ICALP 2023 ICALP 2023 July 10–14, 2023
Paderborn, Germany 261 3

# Tight Bounds for Chordal/Interval Vertex Deletion Parameterized by Treewidth

Michał Włodarczyk

###### Abstract

In Chordal/Interval Vertex Deletion we ask how many vertices one needs to
remove from a graph to make it chordal (respectively: interval). We study
these problems under the parameterization by treewidth tw of the input graph
$G$. On the one hand, we present an algorithm for Chordal Vertex Deletion with
running time $2^{\mathcal{O}(\mathrm{\textbf{tw}})}\cdot|V(G)|$, improving
upon the running time
$2^{\mathcal{O}(\mathrm{\textbf{tw}}^{2})}\cdot|V(G)|^{\mathcal{O}(1)}$ by
Jansen, de Kroon, and Włodarczyk (STOC’21). When a tree decomposition of width
tw is given, then the base of the exponent equals $2^{\omega-1}\cdot 3+1$. Our
algorithm is based on a novel link between chordal graphs and graphic
matroids, which allows us to employ the framework of representative families.
On the other hand, we prove that the known
$2^{\mathcal{O}(\mathrm{\textbf{tw}}\log\mathrm{\textbf{tw}})}\cdot|V(G)|$-time
algorithm for Interval Vertex Deletion cannot be improved assuming Exponential
Time Hypothesis.

###### keywords:

fixed-parameter tractability, treewidth, chordal graphs, interval graphs,
matroids, representative families

###### category:

##  1 Introduction

Treewidth [32, §7] is arguably the most extensively studied width measure in
the graph theory. Simply speaking, treewidth measures to what extent a graph
is similar to a tree, where trees and forests are exactly the graphs of
treewidth 1. It plays a crucial role in Robertson and Seymour’s Graph Minors
series [64]. The usefulness of treewidth stems from the fact that a broad
class of problems can be solved in linear time on graphs of bounded treewidth.
The celebrated Courcelle’s Theorem [30] states that any graph problem
expressible in the Counting Monadic Second Order Logic (CMSO) can be solved in
time $f(\mathrm{\textbf{tw}})\cdot|V(G)|$, where tw denotes the treewidth of
graph $G$ and $f$ is some computable function. In other words, every such
problem is fixed-parameter tractable (FPT) when parameterized by treewidth.
Furthermore, bounded-treewidth graphs appear in a wide variety of contexts,
which makes treewidth-based algorithms a ubiquitous tool in algorithm design
[36, 47, 57, 58, 63].

The function $f$ from Courcelle’s Theorem may grow very rapidly and a large
body of research has been devoted to optimize the dependency on tw for
particular problems. In the ideal scenario, we would like the function $f$ to
be single-exponential, i.e.,
$f(\mathrm{\textbf{tw}})=2^{\mathcal{O}(\mathrm{\textbf{tw}})}$, while
possibly allowing a higher (yet constant) exponent at $|V(G)|$. This is often
the best we can hope for because sub-exponential running times usually
contradict the Exponential Time Hypothesis111The Exponential Time Hypothesis
states that there exists a constant $\delta>0$ so that 3-SAT cannot be solved
in time $\mathcal{O}(2^{\delta n})$ on $n$-variable formulas.  (ETH) [42].

While the standard dynamic programming technique yields single-exponential
algorithms for problems with ‘local constraints’, such as Vertex Cover,
Dominating Set, or Bipartization, it falls short for problems with
‘connectivity constraints’, such as Feedback Vertex Set, Hamiltonian Cycle, or
Connected Vertex Cover, leading to parameter dependency
$f(\mathrm{\textbf{tw}})=2^{\mathcal{O}(\mathrm{\textbf{tw}}\log\mathrm{\textbf{tw}})}$.
On the one hand, this issue was dealt with in the landmark work of Cygan et
al. [35], who introduced the Cut & Count technique and obtained randomized
single-exponential algorithms for the problems above, among others (see also
[61]). In following works, Bodlaender et al. [19] and Fomin et al. [38]
presented alternative techniques that allow to circumvent randomization:
matrix-based approaches and representative families. On the other hand,
Lokshtanov et al. [55] provided a framework for proving ‘slightly super-
exponential’ lower bounds under ETH, which paved the way for establishing
tight lower bounds for problems that require dependency
$f(\mathrm{\textbf{tw}})=2^{\mathcal{O}(\mathrm{\textbf{tw}}\log\mathrm{\textbf{tw}})}$.
In the same work, they obtained such bounds for Disjoint Paths and Chromatic
Number. For problems with a single-exponential dependency
$f(\mathrm{\textbf{tw}})=\mathcal{O}(c^{\mathrm{\textbf{tw}}})$, further
research has been devoted to establish the optimal base of the exponent $c$
[31, 33, 35, 54, 69].

#### Vertex-deletion problems.

Many optimization graph problems can be phrased in terms of
$\mathcal{H}$-Vertex Deletion: remove the smallest number of vertices from a
graph so that the resulting graph belongs to the graph class $\mathcal{H}$.
For example, Vertex Cover corresponds to the class $\mathcal{H}$ of edge-less
graphs. There is a diverse complexity landscape of ETH-tight running times for
various vertex-deletion problems under treewidth parameterization. The classes
$\mathcal{H}$ for which tight bounds have been established include: edge-less
graphs [54], forests [35] (see also [15]), planar graphs [47, 60], classes
defined by a connected forbidden minor [9] (see also [10, 11, 12]), bipartite
graphs [54], DAGs [22], even-cycle-free graphs [15, 44], and some classes
defined by a forbidden (induced) subgraph [34, 67].

We extend this list by studying the vertex-deletion problems into the classes
of chordal and interval graphs. A graph is chordal if it does not contain an
induced cycle of length at least 4 (a hole) and a graph is interval if it is
an intersection graph of intervals on the real line. Any interval graph is
chordal and any chordal graph is perfect. Applications of these two graph
classes have been long studied in miscellaneous areas of discrete optimization
[8, 14, 25, 50, 62, 65]. On the theoretical side, the treewidth (resp.
pathwidth) of a graph $G$ equals the minimum clique number of a chordal (resp.
interval) supergraph of $G$ [32, 52]. Moreover, some hard problems become
tractable on chordal or interval graphs (or even on graphs with small vertex-
deletion distance to chordality) [26, 43, 49].

#### Our results.

The state of the art for Chordal Vertex Deletion (ChVD) is the running time
$2^{\mathcal{O}(\mathrm{\textbf{tw}}^{2})}n^{\mathcal{O}(1)}$, which follows
from a more general result for a hybrid graph measure $\mathcal{H}$-treewidth,
where $\mathcal{H}=\texttt{chordal}$ [45]. We improve the dependency on
treewidth to single-exponential.

######  Theorem 1.1.

Chordal Vertex Deletion can be solved in deterministic time
$\mathcal{O}(c^{k}k^{\omega+1}n)$ on $n$-vertex node-weighted graphs when a
tree decomposition of width $k$ is provided. The constant $c$ equals
$2^{\omega-1}\cdot 3+1$.

Here, $\omega<2.373$ stands for the matrix multiplication exponent [7]. To
prove Theorem 1.1 we establish a new link between chordal graphs and graphic
matroids, which allows us to exploit the framework of representative families
[37, 38]. ChVD is at least as hard as Feedback Vertex Set, what implies
barriers for a significant improvement in the constant $c$ (see Lemma 4.1 and
the discussion therein). Thanks to a single-exponential constant-factor FPT
approximation for treewidth [20], Theorem 1.1 gives running time
$2^{\mathcal{O}(\mathrm{\textbf{tw}})}n$ even when no tree decomposition is
provided in the input.

The best known running time for Interval Vertex Deletion is
$2^{\mathcal{O}(\mathrm{\textbf{tw}}\log\mathrm{\textbf{tw}})}n$ [66]. (While
this algorithm has been described for the edge-deletion variant, we briefly
explain in Section 5.1 how it can be adapted for vertex deletion.) We show
that, unlike the chordal case, this running time is optimal under ETH. This
gives a sharp separation between the two studied problems.

######  Theorem 1.2.

Under the assumption of ETH, Interval Vertex Deletion cannot be solved in time
$2^{o(\mathrm{\textbf{tw}}\log\mathrm{\textbf{tw}})}n^{\mathcal{O}(1)}$ on
$n$-vertex unweighted graphs of treewidth tw.

In fact, we show a stronger lower bound that rules out the same running time
with respect to a different graph parameter, called treedepth, which is never
smaller than treewidth. Our lower bound is obtained via a reduction from
$k\times k$ Permutation Clique [55], which produces an instance of size
$2^{\mathcal{O}(k)}$ and treedepth $\mathcal{O}(k)$.

#### Related work.

The two considered $\mathcal{H}$-Vertex Deletion problems have been studied in
several contexts. Both problems are FPT parameterized by the solution size
$k$, with the best-known running times $\mathcal{O}(8^{k}(n+m))$ for
$\mathcal{H}=\texttt{interval}$ [27] and $2^{\mathcal{O}(k\log
k)}n^{\mathcal{O}(1)}$ for $\mathcal{H}=\texttt{chordal}$ [28] (but the
problem becomes W[2]-hard for $\mathcal{H}=\texttt{perfect}$ [41]). There are
polynomial-time approximation algorithms with approximation factor 8 for
$\mathcal{H}=\texttt{interval}$ [27] and $k^{\mathcal{O}(1)}$ for
$\mathcal{H}=\texttt{chordal}$ [48]. Observe that, in these two regimes,
vertex deletion into chordal graphs seems harder than into interval graphs
(although no lower bounds are known to justify such a separation formally);
this contrasts our results with respect to the treewidth parameterization.

Both studied problems admit exact exponential algorithms with running times of
the form $\mathcal{O}((2-\varepsilon)^{n})$ [18] as well as polynomial
kernelizations [3, 4, 48]. The obstructions to being chordal (resp. interval)
enjoy the Erdős-Pósa property: any graph $G$ either contains $k$ vertex-
disjoint subgraphs which are not chordal (resp. not interval) or a vertex set
$X$ of size $\mathcal{O}(k^{2}\log k)$ such that $G-X$ is chordal [51] (resp.
interval [2]). Vertex deletion into other subclasses of perfect graphs has
been studied as well [1, 5, 6, 70]. For other modification variants, where
instead of vertex deletions one considers removals, insertions, or
contractions of edges, see, e.g., [17, 26, 27, 28, 39, 56, 72].

The concept of representative families, which plays an important role in our
algorithm for ChVD, has found applications outside the context of treewidth as
well [68, 73]. Our other tool, boundaried graphs, has revealed fruitful
insights for various graph classes [9, 21, 45].

#### Organization of the paper.

We begin by describing our technical contributions informally in Section 2. In
Section 3 we provide formal preliminaries. Section 4 is devoted to
establishing a connection between chordal graphs and graphic matroids, which
is followed by the proof of Theorem 1.1. In Section 5 we prove our lower bound
for Interval Vertex Deletion. We conclude in Section 6.

##  2 Techniques

#### Chordal Vertex Deletion.

The standard approach to design algorithms over a bounded-width tree
decomposition is to assign a data structure to each node $t$ in the
decomposition, which stores information about partial solutions for the
subgraph associated with the subtree of $t$. Suppose that $X\subseteq V(G)$ is
a bag of $t$, $A\subseteq V(G)\setminus X$ denote the set of vertices
appearing in the bags of the descendants of $t$ (but not in $X$), and
$B\subseteq V(G)$ is the set of remaining vertices. We say that a subset
$S\subseteq V(G)$ is a _solution_ if $G[S]$ is chordal; we want to _maximize_
the size of $S$. Next, a pair $(S_{A}\subseteq A,S_{X}\subseteq X)$ is a
_partial solution_ if $G[S_{A}\cup S_{X}]$ is chordal. A set $S_{B}\subseteq
B$ is an _extension_ of a partial solution $(S_{A},S_{X})$ if $S_{A}\cup
S_{X}\cup S_{B}$ is a solution. Since $X$ separates $S_{A}$ from $S_{B}$, the
graph $G[S_{A}\cup S_{X}\cup S_{B}]$ can be regarded as a result of _gluing_
$G[S_{A}\cup S_{X}]$ with $G[S_{B}\cup S_{X}]$ alongside the _boundary_
$S_{X}$. For a node $t$ and $S_{X}\subseteq X$, we want to store a family of
partial solutions $\mathcal{G}_{t,S_{X}}$ so that for every possible
$S_{B}\subseteq B$: if $S_{B}$ is an extension for some partial solution
$(S_{A},S_{X})$, then there exists a partial solution
$(S^{\prime}_{A},S_{X})\in\mathcal{G}_{t,S_{X}}$ for which (a) $S_{B}$ is
still a valid extension, and (b) $S^{\prime}_{A}$ is at least as large as
$S_{A}$. We say that such a family satisfies the correctness invariant for
$(t,S_{X})$.

Jansen et al. [45] showed that any chordal graph $H$ with a boundary of size
$k$ can be _condensed_ to a graph $H^{\prime}$ on $\mathcal{O}(k)$ vertices
that exhibits the same behavior in terms of gluing. More precisely, the gluing
product of $H$ with any graph $J$ is chordal if and only if the gluing product
of $H^{\prime}$ with $J$ is chordal. Since there are
$2^{\mathcal{O}(\mathrm{\textbf{tw}}^{2})}$ graphs on
$\mathcal{O}(\mathrm{\textbf{tw}})$ vertices and
$2^{\mathcal{O}(\mathrm{\textbf{tw}})}$ choices for the boundary $S_{X}$, it
suffices to store only $2^{\mathcal{O}(\mathrm{\textbf{tw}}^{2})}$ partial
solutions.

We take this idea one step further and show that it is actually sufficient to
store only $2^{\mathcal{O}(\mathrm{\textbf{tw}})}$ partial solutions. To this
end, we investigate the properties of the class of chordal graphs with respect
to the gluing operation and prove a homomorphism theorem relating it to
graphic matroids. A _graphic matroid_ of a graph $J$ is a set system
$\mathcal{I}$ over $E(J)$ where a subset $S\subseteq E(J)$ belongs to
$\mathcal{I}$ (and is called _independent_) when $S$ contains no cycles. A
_rank_ of a matroid is the largest size of an independent set; here this
coincides with the size of any spanning forest in $J$. In the following
statement, $\mathcal{G}_{X,B}$ is a family of graphs $H$ that satisfy (a)
$V(H)\supseteq X$ and (b) $H[X]=B$. For graphs
$H_{1},H_{2}\in\mathcal{G}_{X,B}$ we assume that $V(H_{1})\cap V(H_{2})=X$ and
define their gluing product as $H_{3}=(H_{1},X)\oplus(H_{2},X)$ where
$V(H_{3})=V(H_{1})\cup V(H_{2})$ and $E(H_{3})=E(H_{1})\cup E(H_{2})$.

######  Theorem 2.1.

Consider a family of graphs $\mathcal{G}_{X,B}$ for some pair $(X,B)$. There
exists a graphic matroid $M=(E,\mathcal{I})$ of rank at most $|X|-1$ and a
polynomial-time computable mapping $\sigma:\mathcal{G}_{X,B}\to 2^{E}$ such
that $(H_{1},X)\oplus(H_{2},X)$ is chordal if and only if
$\sigma(H_{1})\cap\sigma(H_{2})=\emptyset$ and
$\sigma(H_{1})\cup\sigma(H_{2})\in\mathcal{I}$.

With this criterion at hand, we can employ the machinery of representative
families to truncate the number of partial solutions to be stored for a node
of a tree decomposition. Technical details aside, for a family $\mathcal{S}$
of independent sets in a matroid $M=(E,\mathcal{I})$, a subfamily
$\widehat{\mathcal{S}}\subseteq\mathcal{S}$ is called _representative_ for
$\mathcal{S}$ if for every independent set $Y$ in $M$: if there exists
$X\in\mathcal{S}$ so that $X\cap Y=\emptyset$ and $X\cup Y\in\mathcal{I}$,
then there exists $\widehat{X}\in\widehat{\mathcal{S}}$ so that
$\widehat{X}\cap Y=\emptyset$ and $\widehat{X}\cup Y\in\mathcal{I}$. Fomin et
al. [38] showed that for any family $\mathcal{S}$ in a graphic matroid (more
generally, in a linear matroid) of rank $k$ there exists a representative
family of size at most $2^{k}$ and it can be constructed in time
$2^{\mathcal{O}(k)}$. We use Theorem 2.1 to translate this result into the
language of chordal graphs and gluing. When $\mathcal{G}_{t,S_{X}}$ is a
family of partial solutions that satisfies the correctness invariant for
$(t,S_{X})$, a representative family for $\sigma(\mathcal{G}_{t,S_{X}})$ in
the related graphic matroid $M$ corresponds to a subfamily
$\widehat{\mathcal{G}}_{t,S_{X}}\subseteq\mathcal{G}_{t,S_{X}}$ that satisfies
condition (a) of the correctness invariant and
$|\widehat{\mathcal{G}}_{t,S_{X}}|\leq 2^{\mathrm{\textbf{tw}}}$. In order to
satisfy condition (b), we need to assign weights to the elements of the
matroid $M$, encoding the size of the largest partial solution mapped to each
element. We can then utilize the weighted variant of representative families,
which preserves the largest-weight elements [38]. By storing only the
condensed forms of the partial solutions (having
$\mathcal{O}(\mathrm{\textbf{tw}})$ vertices), we also achieve a linear
dependency on $|V(G)|$.

In order to prove Theorem 2.1, we give a novel criterion for testing
chordality of a gluing product. When $G$ originates from gluing two chordal
graphs $G_{1},G_{2}$ alongside boundary $X$, then any hole in $G$ must visit
both $V(G_{1})\setminus X$ and $V(G_{2})\setminus X$, so it must traverse $X$
multiple times. We show that if a hole $H$ intersects at least two connected
components of $G[X]$, then it corresponds to a cycle in the graph obtained
from $G$ by contracting each of the connected components of $G[X]$, $G_{1}-X$,
$G_{2}-X$ into single vertices. Otherwise, let $C$ be the unique connected
component of $G[X]$ that is intersected by the hole. We prove that there
exists a vertex set $S\subseteq V(C)$ that is disjoint from $V(H)$ and $C-S$
has two connected components $C_{1},C_{2}$ satisfying
$N_{C}(C_{1})=N_{C}(C_{2})=S$ (below we refer to such components as
_relevant_) and having non-empty intersections with $V(H)$. Moreover, every
vertex from $V(H)\cap C$ belongs to some relevant component. Consider a graph
$\texttt{Aux}(G,X,S)$ obtained from $G$ by (1) removing the connected
components of $G[X]$ different than $C$, (2) contracting relevant components
of $C-S$ into single vertices while removing the irrelevant ones, and (3)
contracting the components of $G_{1}-X$, $G_{2}-X$ into single vertices. A
detailed construction is given in Definition 4.13; see also Figure 1 on page
1. Then the hole $H$ corresponds to a cycle in $\texttt{Aux}(G,X,S)$. The
first scenario can be analyzed with this approach as well, by taking
$S=\emptyset$. We prove that considering all minimal vertex separators $S$ in
$G[X]$ and checking acyclity of each auxiliary graph $\texttt{Aux}(G,X,S)$
yields a necessary and sufficient condition for $G$ to be chordal.

This criterion allows us to construct a graphic matroid encoding all the
information about each of the graphs $G_{1},G_{2}$ necessary to reconstruct
the graphs $\texttt{Aux}(G,X,S)$ and to determine whether $G$ is chordal. In
order to bound the rank of this matroid, we investigate the structure of
minimal vertex separators in a chordal graph and bound the size of a spanning
forest in a certain graph obtained from the union of $\texttt{Aux}(G,X,S)$. A
criterion of a similar kind is known for testing planarity of a gluing product
of planar graphs when the boundary has a Hamiltonian cycle; then the
corresponding auxiliary graph (defined in a different way) should be bipartite
[13].

Our criterion can be also compared to the one used by Bonnet et al. [23] in
their work on Bounded $\mathcal{P}$-Block Vertex Deletion. Here, the task is
to remove the smallest number of vertices from a graph so that every remaining
biconnected component has at most $d$ vertices and belongs to the class
$\mathcal{P}$. They showed that when $\mathcal{P}$ is a subclass of chordal
graphs then Bounded $\mathcal{P}$-Block Vertex Deletion can be solved in time
$2^{\mathcal{O}(\mathrm{\textbf{tw}}\cdot d^{2})}n^{\mathcal{O}(1)}$ and
otherwise it cannot be solved in time
$2^{o(\mathrm{\textbf{tw}}\log\mathrm{\textbf{tw}})}n^{\mathcal{O}(1)}$ for
fixed $d$ unless ETH fails. Their positive result is also based on a criterion
which determines whether a gluing product of two graphs has the desired
property by checking if a union of two certain sets is independent in a
graphic matroid. It handles cases similar to the first scenario considered in
the outline above. However, while this criterion is necessary it is not
sufficient and more information needs to be stored in a DP state, leading to
the additional factor $d^{2}$ in the exponent. In our setting the biconnected
components can be arbitrarily large so such a factor is prohibitive.

#### Interval Vertex Deletion.

In order to prove Theorem 1.2 we present a parameterized reduction from
$k\times k$ Permutation Clique. Here, the input is a graph $G$ on vertex set
$[k]\times[k]$, and we ask whether there exists a permutation
$\pi\colon[k]\to[k]$ such that $(1,\pi(1)),(2,\pi(2)),\dots,(k,\pi(k))$ forms
a clique in $G$. Lokshtanov et al. [55] proved that $k\times k$ Permutation
Clique cannot be solved in time $2^{o(k\log k)}$ under ETH. So we seek a
reduction from $k\times k$ Permutation Clique to Interval Vertex Deletion that
produces a graph of treewidth $\mathcal{O}(k)$.

Imagine an interval model of a complete graph $Y$ on vertex set $[k]$ in which
all the right endpoints of the intervals coincide and all the left endpoints
are distinct. Choosing the order of the left endpoints encodes some
permutation $\pi\colon[k]\to[k]$ (see Figure 2 on page 2). We can extend this
interval model by inserting a new vertex $v$ only if $N(v)$ corresponds to a
set of intervals intersecting at a single point. This is possible only when
$N(v)=\pi([\ell])$ for some $\ell\in[k]$. Furthermore, inserting to $Y$
independent vertices $v_{1},v_{2},\dots,v_{k}$, such that $|N(v_{i})|=i$ and
$N(v_{i})\subset N(v_{i+1})$, enforces the choice of permutation $\pi$. We can
thus encode a permutation $\pi$ by an ascending family of sets $N_{1}\subset
N_{2}\subset\dots\subset N_{k}=[k]$, satisfying $N_{i}=\pi([i])$, which
correspond to the neighborhoods of $v_{1},v_{2},\dots,v_{k}$ in $Y$. On the
other hand, any ascending family of sets for which the construction above
gives an interval graph, must encode some permutation. On an intuitive level,
a partial interval model of a size-$k$ separator can encode one of $k!$
permutations.

We need a mechanism to verify that a chosen permutation $\pi$ encodes a
clique, i.e., that it satisfies $k\choose 2$ constraints of the form
$(i,\pi(i))(j,\pi(j))\in E(G)$. To implement a single constraint, we construct
a _choice gadget_ , inspired by the reduction to Planar Vertex Deletion [60].
Such a gadget $C_{i,j}$ is defined as a path-like structure, divided into
blocks, so that each block has some special vertices adjacent to $Y$ (see
Figure 3 on page 3). We show that any minimum-size interval deletion set in
$C_{i,j}$ must ‘choose’ one block and leave its special vertices untouched
while it can remove the remaining special vertices. We use this gadget to
check if a permutation $\pi$ encoded by an ascending family of sets
$N_{1}\subset N_{2}\subset\dots\subset N_{k}$ satisfies the constraint
$(i,\pi(i))(j,\pi(j))\in E(G)$. As $\pi(i)$ is the only element in
$N_{i}\setminus N_{i-1}$, this information can be extracted from the tuple
$(N_{i-1},N_{i},N_{j-1},N_{j})$. We create a single block in $C_{i,j}$ for
each valid tuple. Since the number of such tuples is $2^{\mathcal{O}(k)}$, we
need a choice gadget of exponential length, unlike the mentioned reduction
which works in polynomial time. However, producing an instance of size
$2^{\mathcal{O}(k)}$ and treewidth $\mathcal{O}(k)$ is still sufficient to
achieve the claimed lower bound.

##  3 Preliminaries

We write $[k]=\\{1,2,\dots,k\\}$ and assume that $[0]=\emptyset$. We
abbreviate $X\setminus v=X\setminus\\{v\\}$. For a function $w\colon
X\to\mathbb{N}$ and $S\subseteq X$ we use shorthand $w(S)=\sum_{x\in S}w(x)$.

#### Graphs.

We consider finite, simple, undirected graphs. We denote the vertex and edge
sets of a graph $G$ by $V(G)$ and $E(G)$, respectively. For a set of vertices
$S\subseteq V(G)$, by $G[S]$ we denote the graph induced by $S$. We use
shorthand $G-v$ and $G-S$ for $G[V(G)\setminus v]$ and $G[V(G)\setminus S]$,
respectively. The open neighborhood $N_{G}(v)$ of $v\in V(G)$ is defined as
$\\{u\in V(G)\mid\\{u,v\\}\in E(G)\\}$. The closed neighborhood of $v$ is
$N_{G}[v]=N_{G}(v)\cup\\{v\\}$. For $S\subseteq V(G)$, we have
$N_{G}[S]=\bigcup_{v\in S}N_{G}[v]$ and $N_{G}(S)=N_{G}[S]\setminus S$. When
$C$ is a subgraph of $G$ we abbreviate $G[C]=G[V(C)]$ and
$N_{G}(C)=N_{G}(V(C))$.

For sets $S_{1},S_{2}\subseteq V(G)$ we denote by $E_{G}(S_{1},S_{2})$ the set
of edges with one endpoint in $S_{1}$ and one in $S_{2}$. We say that
$S_{1},S_{2}$ are adjacent in $G$ if $E_{G}(S_{1},S_{2})\neq\emptyset$. A
forest is a graph without cycles. A set $S\subseteq V(G)$ is called a feedback
vertex set if $G-S$ is a forest. A clique in a graph $G$ is a vertex set $S$
such that for each distinct $u,v\in S$ the edge $uv$ belongs to $E(G)$.

A contraction of $uv\in E(G)$ introduces a new vertex adjacent to all of
$N_{G}(\\{u,v\\})$, after which $u$ and $v$ are deleted. For $S\subseteq V(G)$
such that $G[S]$ is connected, we say we contract $S$ if we simultaneously
contract all edges in $G[S]$ and introduce a single new vertex adjacent to
$N_{G}(S)$.

#### Separators.

For vertices $u,v\in V(G)$ a vertex set $S\subseteq V(G)\setminus\\{u,v\\}$ is
called a $(u,v)$-separator if $u,v$ belong to different connected components
of $G-S$. A $(u,v)$-separator is minimal when no proper subset of it is a
$(u,v)$-separator. A vertex set $S$ is called a minimal vertex separator if
$S$ is a minimal $(u,v)$-separator for some $u,v\in V(G)$.

######  Lemma 3.1 ($\star$).

Let $u,v$ be vertices in a graph $G$ and $S$ be a $(u,v)$-separator in $G$.
Denote by $C_{u},C_{v}$ the connected components of $G-S$ that contain
respectively $u$ and $v$. Then $S$ is minimal if and only if
$N_{G}(C_{u})=N_{G}(C_{v})=S$.

######  Proof 3.2.

To see the first implication suppose w.l.o.g. that $N_{G}(C_{u})\subsetneq S$.
Let $w\in S\setminus N_{G}(C_{u})$. The connected component of $u$ in the
graph $G-(S\setminus w)$ is $C_{u}$ because $N_{G}(C_{u})\subseteq S\setminus
w$. Therefore $S\setminus w$ is also a $(u,v)$-separator contradicting
minimality of $S$.

To see the opposite implication suppose that $S^{\prime}\subsetneq S$ is also
a $(u,v)$-separator. Let $w\in S\setminus S^{\prime}$. But $w\in
N_{G}(C_{u})\cap N_{G}(C_{v})$ so $u,v$ belong to the same connected component
of $G-S^{\prime}$.

A vertex (or a vertex set) is called simplicial if its open neighborhood is a
clique.

######  Lemma 3.3 ($\star$).

Let $S$ be a minimal vertex separator in a graph $G$. Then $S$ does not
contain any simplicial vertices.

######  Proof 3.4.

Suppose that $S$ contains a simplicial vertex $v$. Next, suppose there are two
distinct connected components $C_{1},C_{2}$ of $G-S$ which are adjacent to
$v$. Let $w_{1}\in N_{G}(v)\cap C_{1},w_{2}\in N_{G}(v)\cap C_{2}$. But then
$w_{1}w_{2}\in E(G)$ which contradicts the assumption that $C_{1},C_{2}$ are
distinct. Therefore there is at most one connected component of $G-S$ adjacent
to $v$. But then $S\setminus v$ separates the same pairs of vertices as $S$
does. This means that $S$ is not a minimal vertex separator.

#### Chordal and interval graphs.

An interval graph is an intersection graph of intervals on the real line. In
an interval model $\mathcal{I}_{G}=\\{I(v)\mid v\in V(G)\\}$ of a graph $G$,
each vertex $v\in V(G)$ corresponds to a closed interval $I(v)$; there is an
edge between vertices $u$ and $v$ if and only if $I(v)\cap I(u)\neq\emptyset$.

A hole in a graph is an induced (i.e., chordless) cycle of length at least
four. A graph is chordal when it does not contain any hole. An equivalent
definition states that a chordal graph is an intersection graph of a family of
subtrees in a tree [40]. This implies that any interval graph is chordal. For
more background on these graph classes see surveys [16, 24].

The characterization of the two classes as intersection graphs of
intervals/subtrees leads to the following observation.

The classes of chordal and interval graphs are closed under vertex deletions
and edge contractions.

An asteroidal triple (AT) is a triple of vertices such that for any two of
them there exists a path between them avoiding the closed neighborhood of the
third. Interval graphs cannot contain ATs, which is a consequence of a linear
ordering of any interval model. It turns out that this is the only property
that separates the two graph classes.

######  Lemma 3.5 ([24]).

A graph is interval if and only if it is chordal and does not contain an AT.

We collect two more useful facts about chordal graphs.

######  Lemma 3.6 ([24]).

Every non-empty chordal graph contains a simplicial vertex.

When a chordal graph contains a cycle then it also contains a triangle. As a
bipartite graph does not have any triangles, we obtain the following.

If a graph is chordal and bipartite, then it is a forest.

A vertex set $S$ in graph $G$ is called a chordal deletion set (resp. interval
deletion set) if $G-S$ is chordal (resp. interval). The Chordal/Interval
Vertex Deletion problem is defined as follows. We are given a graph $G$, a
non-negative weight function $w\colon V(G)\to\mathbb{N}$, an integer $p$, and
we ask whether there exists a chordal (resp. interval) deletion set $S$ in $G$
such that $w(S)\leq p$.

#### Boundaried graphs.

For a set $X$ and a graph $B$ on vertex set $X$, we define a family
$\mathcal{G}_{X,B}$ of graphs $G$ that satisfy (a) $V(G)\supseteq X$, (b)
$G[X]=B$. For graphs $G_{1},G_{2}\in\mathcal{G}_{X,B}$ we define their gluing
product $(G_{1},X)\oplus(G_{2},X)$ by taking a disjoint union of $G_{1}$ and
$G_{2}$ and identifying vertices from $X$. Note that two vertices from $X$ are
adjacent in $G_{1}$ if and only if they are adjacent in $G_{2}$.

For $X\subseteq V(G)$ a pair $(G,X)$ is called a boundaried graph. We say that
two boundaried graphs $(G_{1},X),(G_{2},X)$ are compatible if
$G_{1},G_{2}\in\mathcal{G}_{X,B}$ for some $B$. We remark that it is common in
the literature to define a boundaried graph as a triple $(G,X,\lambda)$ where
$\lambda\colon X\to[|X|]$ is a labeling (cf. [9, 21]). Since we do not need to
perform gluing of abstract boundaried graphs, but only ones originating from
subgraphs of a fixed graph, this simpler definition is sufficient.

As an example, consider a graph $G$ and $X\subseteq V(G)$. Then for any
$A\subseteq V(G)\setminus X$ the graph $G[A\cup X]$ belongs to
$\mathcal{G}_{X,G[X]}$. When $A,B\subseteq V(G)\setminus X$ are disjoint and
non-adjacent then $G[A\cup B\cup X]$ is isomorphic to $(G[A\cup
X],X)\oplus(G[B\cup X],X)$.

#### Tree decompositions.

######  Definition 3.7 (Treewidth).

A _tree decomposition_ of a graph $G$ is a pair $(\mathbb{T},\chi)$ where
$\mathbb{T}$ is a tree, and $\chi\colon V(\mathbb{T})\to 2^{V(G)}$ is a
function, such that:

  1. 1.

for each $v\in V(G)$ the nodes $\\{t\mid v\in\chi(t)\\}$ form a non-empty
connected subtree of $\mathbb{T}$,

  2. 2.

for each edge $uv\in E(G)$ there is a node $t\in V(\mathbb{T})$ with
$\\{u,v\\}\subseteq\chi(t)$.

The _width_ of $(\mathbb{T},\chi)$ is defined as $\max_{t\in
V(\mathbb{T})}|\chi(t)|-1$. The _treewidth_ of a graph $G$ (denoted
$\mathrm{\textbf{tw}}(G))$ is the minimal width a tree decomposition of $G$.

######  Definition 3.8.

A tree decomposition $(\mathbb{T},\chi)$ is called _nice_ if $\mathbb{T}$ is a
rooted tree with a root $r$ where $\chi(r)=\emptyset$, each node has at most
two children, and each node is of one of the following types.

  1. 1.

Base node: a leaf $t\neq r$ in $\mathbb{T}$ with $\chi(t)=\emptyset$.

  2. 2.

Introduce node: a node $t$ having one child $t^{\prime}$ for which
$\chi(t)=\chi(t^{\prime})\cup\\{v\\}$ for some $v\not\in\chi(t^{\prime})$.

  3. 3.

Forget node: a node $t$ having one child $t^{\prime}$ for which
$\chi(t)=\chi(t^{\prime})\setminus v$ for some $v\in\chi(t^{\prime})$.

  4. 4.

Join node: a node $t$ having two children $t_{1},t_{2}$ for which
$\chi(t)=\chi(t_{1})=\chi(t_{2})$.

It is well known that any tree decomposition of $G$ of width $k$ can be
transformed in linear time into a nice tree decomposition of width $k$ and
with $\mathcal{O}(k\cdot|V(G)|)$ nodes [53]. When a rooted tree decomposition
$(\mathbb{T},\chi)$ of $G$ is clear from the context we denote by $V_{t}$ the
set of vertices occurring in the subtree rooted at $t\in V(\mathbb{T})$ and
define $U_{t}=V_{t}\setminus\chi(t)$.

######  Definition 3.9 (Treedepth).

A treedepth of a graph $G$ (denoted $\mathrm{\textbf{td}}(G))$ is defined
recursively as follows.

$\mathrm{\textbf{td}}(G)=\begin{cases}0&\mbox{if $G$ is empty}\\\ 1+\min_{v\in
V(G)}(\mathrm{\textbf{td}}(G-v))&\mbox{if $G$ is non-empty and connected}\\\
\max_{i=1}^{d}(\mathrm{\textbf{td}}(G_{i}))&\mbox{if $G$ is disconnected and
$G_{1},\dots G_{d}$ are its components}\end{cases}$

As a direct consequence of this definition, inserting a vertex into a graph
can increase its treedepth by at most one. It is well known that for every
graph $\mathrm{\textbf{tw}}(G)\leq\mathrm{\textbf{td}}(G)$.

#### Matroids.

We provide only the basic background related to our applications. For more
information about matroids we refer to the survey [59].

######  Definition 3.10 (Matroid).

A pair $M=(E,\mathcal{I})$ where $E$ is a set and $\mathcal{I}\subseteq 2^{E}$
is called a matroid if the following conditions hold.

  * •

If $X\subseteq Y$ and $Y\in\mathcal{I}$ then also $X\in\mathcal{I}$.

  * •

If $X,Y\in\mathcal{I}$ and $|X|<|Y|$ then there exists $e\in Y\setminus X$
such that $X\cup\\{e\\}\in\mathcal{I}$.

We say that a set $X\subseteq E$ is independent in $M$ when $X\in\mathcal{I}$.
The rank of $M$ is the size of the largest independent set in $M$.

The simplest example is a $k$-uniform matroid in which a set $X\subseteq E$ is
independent when $|X|\leq k$. Another important example is a linear matroid.
Let $A$ be a matrix over a field $\mathbb{F}$. We define matroid
$M=(E,\mathcal{I})$ where $E$ be the set of columns of $A$ and $X\subseteq E$
is independent in $M$ when the corresponding columns are independent over
$\mathbb{F}$. We say that the matrix $A$ is a representation of $M$ over
$\mathbb{F}$.

Given a graph $G$, we define its graphic matroid $M=(E(G),\mathcal{I})$ where
$X\subseteq E(G)$ is independent when $X$ does not contain a cycle. It is
well-known that every graphic matroid is linear and the oriented incidence
matrix of $G$ forms a representation of $M$ over any field.

######  Lemma 3.11 ([59]).

Given a graph $G$ we can find a representation matrix of its graphic matroid
over any field in polynomial time.

######  Definition 3.12 (Product family).

Given two families of independent sets $\mathcal{S}_{1},\mathcal{S}_{2}$ in a
matroid $M=(E,\mathcal{I})$ we define

$\mathcal{S}_{1}\bullet\mathcal{S}_{2}=\\{X\cup Y\mid
X\in\mathcal{S}_{1},Y\in\mathcal{S}_{2},X\cap Y=\emptyset,X\cup
Y\in\mathcal{I}\\}.$

#### Representative families.

We say that a family of sets $\mathcal{S}$ is a $p$-family if every set in
$\mathcal{S}$ has size $p$.

######  Definition 3.13 (Min/max $q$-representative family).

Let $M=(E,\mathcal{I})$ be a matroid, $\mathcal{S}$ be a family of subsets of
$E$, and $w\colon\mathcal{S}\to\mathbb{N}$ be a non-negative weight function.
A subfamily $\widehat{S}\subseteq S$ is min $q$-representative (resp. max
$q$-representative) for $S$ if for every set $Y\subseteq E$ of size at most
$q$, if there is a set $X\in S$ disjoint from $Y$ with $X\cup
Y\in\mathcal{I}$, then there is a set $\widehat{X}\in\widehat{S}$ disjoint
from $Y$ with (a) $\widehat{X}\cup Y\in\mathcal{I}$ and (b)
$w(\widehat{X})\leq w(X)$ (resp. $w(\widehat{X})\geq w(X)$).

When all weights are zero, we obtain a simpler notion of a $q$-representative
family. Observe that when $X$ is a $p$-element set in a matroid of rank $k$
and $Y$ satisfies $X\cap Y=\emptyset$ and $X\cup Y\in\mathcal{I}$ then
$|Y|\leq k-p$. We make note of this fact.

If $\mathcal{S}$ is a $p$-family in a matroid of rank $k$ and
$\widehat{\mathcal{S}}\subseteq^{k-p}_{\mathrm{maxrep}}\mathcal{S}$ then
$\widehat{\mathcal{S}}\subseteq^{k}_{\mathrm{maxrep}}\mathcal{S}$.

The following lemmas have been stated in [38] for the unweighted version of
representative families but with a remark that they work as well for the
weighted version (as stated below).

######  Lemma 3.14 ([38, Lemma 3.1]).

Let $M=(E,\mathcal{I})$ be a matroid and $\mathcal{S}$ be a family of subsets
of $E$. If $\tilde{\mathcal{S}}\subseteq^{q}_{\mathrm{maxrep}}\mathcal{S}$ and
$\widehat{\mathcal{S}}\subseteq^{q}_{\mathrm{maxrep}}\tilde{\mathcal{S}}$ then
$\widehat{\mathcal{S}}\subseteq^{q}_{\mathrm{maxrep}}\mathcal{S}$.

######  Lemma 3.15 ([38, Lemma 3.2]).

Let $M=(E,\mathcal{I})$ be a matroid and $\mathcal{S}$ be a family of subsets
of $E$. If
$\mathcal{S}=\mathcal{S}_{1}\cup\mathcal{S}_{2}\cup\dots\cup\mathcal{S}_{\ell}$
and $\widehat{\mathcal{S}}_{i}\subseteq^{q}_{\mathrm{maxrep}}\mathcal{S}_{i}$,
then
$\bigcup_{i=1}^{\ell}\widehat{\mathcal{S}}_{i}\subseteq^{q}_{\mathrm{maxrep}}\mathcal{S}$.

######  Lemma 3.16 ([38, Lemma 3.3]).

Let $M=(E,\mathcal{I})$ be a matroid or rank $k$ and $\mathcal{S}_{1}$ be a
$p_{1}$-family of independent sets, $\mathcal{S}_{2}$ be a $p_{2}$-family of
independent sets,
$\widehat{\mathcal{S}}_{1}\subseteq^{k-p_{1}}_{\mathrm{maxrep}}\mathcal{S}_{1}$,
$\widehat{\mathcal{S}}_{2}\subseteq^{k-p_{2}}_{\mathrm{maxrep}}\mathcal{S}_{2}$.
Then
$\widehat{\mathcal{S}}_{1}\bullet\widehat{\mathcal{S}}_{2}\subseteq^{k-p_{1}-p_{2}}_{\mathrm{maxrep}}\mathcal{S}_{1}\bullet\mathcal{S}_{2}$.

The following theorem is the key to employ representative families in the
design of single-exponential algorithms. We state it only in the maximization
variant.

######  Theorem 3.17 ([38, Theorem 3]).

Let $M=(E,\mathcal{I})$ be a linear matroid of rank $p+q=k$ given together
with its representation matrix $A_{M}$ over a field $\mathbb{F}$. Let
$\mathcal{S}$ be a $p$-family of independent sets in $M$. Then a max
$q$-representative family $\widehat{S}\subseteq S$ for $S$ with at most
$k\choose p$ elements can be found in
$\mathcal{O}\left(|\mathcal{S}|\cdot{k\choose p}\cdot
p^{\omega}+|\mathcal{S}|\cdot{k\choose p}^{\omega-1}\right)$ operations over
$\mathbb{F}$.

We present a more concise corollary suited for our applications.

######  Lemma 3.18.

Let $M=(E,\mathcal{I})$ be a graphic matroid of rank $k$. Let $\mathcal{S}$ be
a family of subsets of $E$. Then
$\widehat{\mathcal{S}}\subseteq^{k}_{\mathrm{maxrep}}\mathcal{S}$ with at most
$2^{k}$ elements can be found in time $\mathcal{O}\left(|\mathcal{S}|\cdot
2^{(\omega-1)k}\cdot k^{\omega}\right)$.

######  Proof 3.19.

Thanks to Lemma 3.11 we can efficiently represent $M$ over $\mathbb{F}_{2}$.
For $p\in[k]$ let $\mathcal{S}^{p}\subseteq\mathcal{S}$ be the family of
independent sets in $\mathcal{S}$ of size $p$. We apply Theorem 3.17 to
compute a max $(k-p)$-representative family
$\widehat{\mathcal{S}}^{p}\subseteq^{k-p}_{\mathrm{maxrep}}\mathcal{S}^{p}$ of
size at most $k\choose p$ for each $\mathcal{S}_{p}$. By Section 3 we can
write
$\widehat{\mathcal{S}}^{p}\subseteq^{k}_{\mathrm{maxrep}}\mathcal{S}^{p}$.
From Lemma 3.15 we know that
$\widehat{\mathcal{S}}=\bigcup_{p=1}^{k}\widehat{\mathcal{S}}^{p}$ (plus
$\emptyset$ if $\emptyset\in\mathcal{S}$) is max $k$-representative for
$\mathcal{S}$. The sizes of $\widehat{\mathcal{S}}^{p}$ sum up to $2^{k}-1$
and the total running time can be upper bounded as in the statement with a
trivial bound ${k\choose p}\leq 2^{k}$.

If the family $\mathcal{S}$ has the special form of a product family, then
instead of applying Theorem 3.17 directly, one can obtain a slightly better
running time. Such families are of special importance for treewidth-based
algorithm since they appear naturally in the computations for join nodes. In
the following theorem, the input consists of
$\mathcal{S}_{1},\mathcal{S}_{2},\mathcal{S}_{1}\bullet\mathcal{S}_{2}$, and
the weight function
$w\colon\mathcal{S}_{1}\bullet\mathcal{S}_{2}\to\mathbb{N}$, so it may have
size $\mathcal{O}(4^{k})$.

######  Theorem 3.20 ([37, Corrolary 2]).

Let $M=(E,\mathcal{I})$ be a linear matroid of rank $k$ given together with
its representation matrix $A_{M}$ over a field $\mathbb{F}$. Let
$\mathcal{S}_{1},\mathcal{S}_{2}$ be two families of independent sets of $M$
and the number of sets of size $p$ in $\mathcal{S}_{1}$ and $\mathcal{S}_{2}$
be at most ${k+c}\choose p$. Here, $c$ is a fixed constant. Let
$\mathcal{S}_{r}^{p}$ be the subfamily of $\mathcal{S}_{r}$ of sets of size
$p$, for $r\in\\{1,2\\}$, $p\in[k]$. Then for all pairs $p,q\in[k]$ we can
find
$\widehat{\mathcal{S}}^{p,q}\subseteq^{k-p-q}_{\mathrm{maxrep}}\mathcal{S}_{1}^{p}\bullet\mathcal{S}_{2}^{q}$
of size $k\choose{p+q}$ in total $\mathcal{O}\left(2^{(\omega-1)k}3^{k}\cdot
k^{\omega}\right)$ operations over $\mathbb{F}$.

We remark that in the original statement in [37] the number of operations is
upper bounded by $\mathcal{O}\left((2^{\omega}+2)^{k}\cdot
k^{\omega}+2^{(\omega-1)k}3^{k}\cdot k^{\omega}\right)$ but for every value of
$\omega\geq 2$ it holds that $2^{\omega}+2\leq 2^{\omega-1}\cdot 3$.

######  Lemma 3.21.

Let $M=(E,\mathcal{I})$ be a graphic matroid of rank $k$. Let
$\mathcal{S}_{1},\mathcal{S}_{2}$ be two families of independent sets of $M$,
each of size at most $2^{k}$. Then we can find
$\widehat{\mathcal{S}}\subseteq^{k}_{\mathrm{maxrep}}\mathcal{S}_{1}\bullet\mathcal{S}_{2}$
of size at most $2^{k}$ in time $\mathcal{O}\left(2^{(\omega-1)k}3^{k}\cdot
k^{\omega}\right)$.

######  Proof 3.22.

As observed before, we can efficiently represent $M$ over $\mathbb{F}_{2}$ and
we can assume that $\emptyset\not\in\mathcal{S}_{1}\bullet\mathcal{S}_{2}$ as
otherwise it can added in the end. For $p\in[k],r\in\\{1,2\\}$, let
$\mathcal{S}^{p}_{r}\subseteq\mathcal{S}_{r}$ be the family of independent
sets in $\mathcal{S}_{r}$ of size $p$. We first apply Theorem 3.17 for each
pair $(r,p)$ to compute
$\tilde{\mathcal{S}}^{p}_{r}\subseteq^{k-p}_{\mathrm{maxrep}}\mathcal{S}^{p}_{r}$
of size $k\choose p$. The total running time is bounded by
$\mathcal{O}(2^{\omega k}\cdot k^{\omega})$ which is bounded by
$\mathcal{O}\left(2^{(\omega-1)k}3^{k}\cdot k^{\omega}\right)$. Now we can
apply Theorem 3.20 to $\bigcup_{p=1}^{k}\tilde{\mathcal{S}}^{p}_{1}$ and
$\bigcup_{p=1}^{k}\tilde{\mathcal{S}}^{p}_{2}$. We obtain, for each pair
$p,q\in[k]$, a family
$\widehat{\mathcal{S}}^{p,q}\subseteq^{k-p-q}_{\mathrm{maxrep}}\tilde{\mathcal{S}}_{1}^{p}\bullet\tilde{\mathcal{S}}_{2}^{q}$.
By Lemmas 3.14, 3.16, and Section 3, we get that
$\widehat{\mathcal{S}}^{p,q}\subseteq^{k}_{\mathrm{maxrep}}\mathcal{S}_{1}^{p}\bullet\mathcal{S}_{2}^{q}$.
Lemma 3.15 implies that
$\widehat{\mathcal{S}}^{\prime}=\bigcup_{p,q\in[k]}\widehat{\mathcal{S}}^{p,q}\subseteq^{k}_{\mathrm{maxrep}}\mathcal{S}_{1}\bullet\mathcal{S}_{2}$.
The family $\widehat{\mathcal{S}}^{\prime}$ contains at most $k\cdot 2^{k}$
sets; we use Lemma 3.18 to find
$\widehat{\mathcal{S}}\subseteq^{k}_{\mathrm{maxrep}}\widehat{\mathcal{S}}^{\prime}$
of size at most $2^{k}$ in time $\mathcal{O}(2^{\omega k}\cdot k^{\omega+1})$
which is negligible compared to the running time from Theorem 3.20. The claim
follows from Lemma 3.14.

##  4 Chordal Deletion

We begin with a simple treewidth-preserving reduction from Feedback Vertex
Set.

######  Lemma 4.1 ($\star$).

Let $G$ be a graph and $\ell\in\mathbb{N}$. Let $G^{\prime}$ be obtained from
$G$ by subdividing each edge. Then
$\mathrm{\textbf{tw}}(G^{\prime})=\mathrm{\textbf{tw}}(G)$ and $G$ has a
feedback vertex set (FVS) of size $\ell$ if and only if $G^{\prime}$ has a
chordal deletion set of size $\ell$.

######  Proof 4.2.

When $S\subseteq V(G)$ is a FVS in $G$ then it is also a FVS in $G^{\prime}$.
Since $G^{\prime}-S$ is acyclic, it is also chordal. In the second direction,
consider a chordal deletion set $S^{\prime}\subseteq V(G^{\prime})$ in
$G^{\prime}$. As $G^{\prime}$ is bipartite, then $G^{\prime}-S^{\prime}$ is as
well, so by Section 3 it must be acyclic. So $S^{\prime}$ is a FVS in
$G^{\prime}$. If $S^{\prime}$ contains a vertex $w$ introduced by subdividing
an edge $uv\in E(G)$ then every cycle in $G^{\prime}$ going through $w$ also
goes through $u$ and $v$. Therefore $(S^{\prime}\setminus w)\cup\\{u\\}$ is
also a FVS in $G^{\prime}$. We can thus assume that $S^{\prime}\subseteq V(G)$
and it forms a FVS in $G$.

It remains to upper bound $\mathrm{\textbf{tw}}(G^{\prime})$ as clearly
$\mathrm{\textbf{tw}}(G^{\prime})\geq\mathrm{\textbf{tw}}(G)$. If
$\mathrm{\textbf{tw}}(G)=1$ then $G$ is a forest and so is $G^{\prime}$.
Suppose that $\mathrm{\textbf{tw}}(G)\geq 2$ and consider a tree decomposition
of $G$ of optimal width. We can transform it into a tree decomposition of
$G^{\prime}$ as follows: for each $uv\in E(G)$ pick a node $t$ whose bag
contains both $u,v$ and create a node $t_{uv}$, adjacent only to $t$, with a
bag $\\{u,v,w\\}$, where $w$ is a vertex introduced on the edge $uv$. Since
all the created bags have size three, the width of the decomposition does not
change.

As a consequence, the base of the exponent $c$ in Theorem 1.1 must be at least
$3$ under Strong Exponential Time Hypothesis [35] and $c$ must be at least
$2^{\omega}+1$ if the current-best deterministic algorithm for Feedback Vertex
Set parameterized by treewidth is optimal [71]. While we have no evidence that
the mentioned algorithm should be optimal for deterministic time, we provide
this comparison to indicate that breaching this gap for ChVD would imply the
same for a more heavily studied problem.

#### Minimal vertex separators.

We set the stage for the proof of Theorem 2.1. First we need to develop some
theory about minimal vertex separators in chordal graphs.

######  Definition 4.3.

Let $\texttt{MinSep}(G)$ denote the set of minimal vertex separators in a
graph $G$. For a graph $G$ and a (possibly empty) set $S\subseteq V(G)$, we
define $\texttt{Comp}(G,S)$ to be the set of connected components $C_{i}$ of
$G-S$ for which it holds that $N_{G}(C_{i})=S$.

Note that whenever $G$ is disconnected then $\emptyset\in\texttt{MinSep}(G)$
and $\texttt{Comp}(G,\emptyset)$ is just the set of connected components of
$G$. According to Lemma 3.1, the set $S$ is a minimal $(u,v)$-separator if and
only if $u,v$ belong to some (distinct) components from $\texttt{Comp}(G,S)$.
For later use, we establish a relation between sets $\texttt{MinSep}(G)$,
$\texttt{Comp}(G,S)$ in $G$ and a graph obtained by a removal of a simplicial
vertex.

######  Lemma 4.4 ($\star$).

Let $v$ be a simplicial vertex in $G$ and $S\in\texttt{MinSep}(G)$. If $S\neq
N_{G}(v)$ then $S\in\texttt{MinSep}(G-v)$ and
$|\texttt{Comp}(G,S)|=|\texttt{Comp}(G-v,S)|$.

######  Proof 4.5.

Suppose that $S\neq N_{G}(v)$. By Lemma 3.3 we know that $v\not\in S$.

First, consider the case $N_{G}(v)\subsetneq S$. Then $\\{v\\}$ forms a
connected component of $G-S$ but $\\{v\\}\not\in\texttt{Comp}(G,S)$. Next,
Lemma 3.1 implies that $S$ is not a minimal $(v,u)$-separator for any $u\in
V(G)$. Therefore $S\in\texttt{MinSep}(G-v)$ and
$|\texttt{Comp}(G,S)|=|\texttt{Comp}(G-v,S)|$.

In the second case $N_{G}(v)\not\subseteq S$. Let $u\in N_{G}(v)\setminus S$
and $C$ be the connected component of $G-S$ which contains $v$. Then $u\in
V(C)$. Since $v$ is simplicial, we have $N_{G}(v)\subseteq N_{G}[u]$.
Therefore, $C-v$ is connected, $N_{G-v}(C\setminus v)=N_{G}(C)$, and so
inserting $v$ to $(G-v)-S$ does not affect the number of connected components
nor their neighborhoods. This means that $S\in\texttt{MinSep}(G-v)$ and
$|\texttt{Comp}(G,S)|=|\texttt{Comp}(G-v,S)|$.

We need a simple technical lemma about minimal vertex separators.

######  Lemma 4.6 ($\star$).

Let $G$ be a connected graph and $V_{1},\dots,V_{k}\subseteq V(G)$, $k\geq 2$,
be disjoint sets so that $G[V_{i}]$ is connected, for $i\in[k]$, and
$E_{G}(V_{i},V_{j})=\emptyset$, for $i\neq j$. Then there exists a minimal
vertex separator $S\subseteq V(G)\setminus(V_{1}\cup\dots\cup V_{k})$ in $G$
which is a $(V_{i},V_{j})$-separator for some $i\neq j$ and each set $V_{i}$
is contained in some component $C\in\texttt{Comp}(G,S)$.

######  Proof 4.7.

Let $S\subseteq V(G)\setminus(V_{1}\cup\dots\cup V_{k})$ be an inclusion-
minimal set with the following property: $S$ separates sets $V_{i},V_{j}$ for
some $i\neq j$. Such a set $S$ must exist because $N_{G}(V_{1})$ has this
property.

We argue that $S$ satisfies the conditions of the lemma. Clearly $S$ is a
minimal $(v_{i},v_{j})$-separator for each $v_{i}\in V_{i}$, $v_{j}\in V_{j}$.
Suppose that for some $h\in[k]$ the set $V_{h}$ is not contained in any
component from $\texttt{Comp}(G,S)$. Let $C$ be the component of $G-S$ that
contains $V_{h}$. Since $C\not\in\texttt{Comp}(G,S)$, we have
$N_{G}(C)\subsetneq S$. At least one of the sets $V_{i},V_{j}$ is not
contained in $C$; assume w.l.o.g. that it is $V_{i}$. Then $N_{G}(C)$ is a
$(V_{h},V_{i})$-separator being a proper subset of $S$, which contradicts the
choice of $S$. The claim follows.

We will use the following concept which appears in the algorithm for ChVD by
Jansen et al.

######  Definition 4.8 ([46, Def. 5.55]).

For a graph $G$ and a vertex set $X\subseteq V(G)$ let the graph
$\texttt{Condense}(G,X)$ be obtained from $G$ by contracting the connected
connected components of $G-X$ into single vertices and then removing those of
them which are simplicial.

We say that $G$ is condensed with respect to $X$ if
$G=\texttt{Condense}(\widehat{G},X)$ for some graph $\widehat{G}$ or,
equivalently, $G=\texttt{Condense}(G,X)$. Due to the following facts,
condensation forms a handy tool for efficiently storing partial solutions for
ChVD.

######  Lemma 4.9 ([46, Lem. 5.57]).

Consider compatible boundaried graphs $(G,X)$, $(H,X)$ so that $G,H$ are
chordal. Let $\widehat{G}=\texttt{Condense}(G,X)$. Then $(G,X)\oplus(H,X)$ is
chordal if and only if $(\widehat{G},X)\oplus(H,X)$ is chordal.

######  Lemma 4.10 ([46, Lem. 5.53]).

Consider a chordal graph $G$ with a non-empty vertex subset $X\subseteq V(G)$.
If $G$ is condensed with respect to $X$, then $|V(G)|\leq 2|X|-1$.

Consider compatible boundaried graphs $(G,X)$, $(H,X)$. Let
$\widehat{G}=\texttt{Condense}(G,X)$ and $\widehat{H}=\texttt{Condense}(H,X)$.
Then
$\texttt{Condense}((G,X)\oplus(H,X),X)=(\widehat{G},X)\oplus(\widehat{H},X)$.

In this section we will exploit the following property of condensation.

######  Lemma 4.11 ($\star$).

Consider a graph $G$ with a vertex set $X$ so that $G[X]$ is chordal. Then $G$
is chordal if and only if the following conditions hold:

  1. 1.

for each connected component $C$ of $G-X$ the graph $G[X\cup C]$ is chordal,

  2. 2.

the graph $\texttt{Condense}(G,X)$ is chordal.

######  Proof 4.12.

The forward direction is clear as the class of chordal graph is closed under
vertex deletions and edge contractions. We prove the opposite direction by
induction on the number $k$ of the connected components in $G-X$. For $k=1$
the condition (1) suffices to obtain chordality of $G$. Suppose now that $k>1$
and consider a partition $V(G)\setminus X=A\cup B$ where $A$ induces a single
connected component of $G-X$ and $B$ induces the rest of them. Let
$\widehat{G}_{A}=\texttt{Condense}(G[A\cup X],X)$ and
$\widehat{G}_{B}=\texttt{Condense}(G[B\cup X],X)$. From Section 4 we know that
$(\widehat{G}_{A},X)\oplus(\widehat{G}_{B},X)=\texttt{Condense}(G,X)$; in
particular this implies that $\widehat{G}_{A},\widehat{G}_{B}$ are chordal.
From inductive assumption we get that $G[A\cup X],G[B\cup X]$ are chordal. We
apply Lemma 4.9 (twice) to obtain that $G=(G[A\cup X],X)\oplus(G[B\cup X],X)$
is chordal as well.

In order to turn Lemma 4.11 into a more convenient criterion, we will compress
information about a graph $G$ with a vertex subset $X$ into multiple auxiliary
graphs, one for each minimal vertex separator in $G[X]$.

######  Definition 4.13.

Consider a graph $G$ with a vertex set $X$ so that $G[X]$ is chordal. For a
set $S\in\texttt{MinSep}(G[X])$ we construct the graph $\texttt{Aux}(G,X,S)$
as follows:

  1. 1.

contract each $C\in\texttt{Comp}(G[X],S)$ into a vertex and remove the
remaining vertices of $X$ (including all of $S$),

  2. 2.

contract each connected component of $G-X$ into a vertex.

Note that $\texttt{Aux}(G,X,\emptyset)$ is obtained by just contracting each
connected component of $G[X]$ and each connected component of $G-X$. Moreover,
observe that $\texttt{Aux}(G,X,S)$ is always a bipartite graph because there
can be no edges between two components from $\texttt{Comp}(G[X],S)$ nor
between two components of $G-X$. See Figure 1 for an example of this
construction.

Figure 1: On the left: graph $G$ and set $X\subseteq V(G)$ represented by
black disks. The graph $G[X]$ is drawn with solid edges. There are two minimal
vertex separators in $G[X]$: $S_{1}=\\{v\\}$ and $S_{2}=\\{u,v\\}$, sketched
in gray. In the middle: the graph $\texttt{Aux}(G,X,S_{1})$ with thick edges
indicating a component that gets contracted into a single vertex; the gray
vertices and edges are removed. On the right: the graph
$\texttt{Aux}(G,X,S_{2})$; note that $|\texttt{Comp}(G[X],S_{2})|=2$ because
the lower vertices of $X$ are not adjacent to every vertex in $S_{2}$. The
graph $\texttt{Aux}(G,X,S_{1})$ contains a cycle and this witnesses that $G$
is not chordal. However, removing from $G$ any single vertex among $x,y,z$
results in a chordal graph.

To make a connection between holes in $G$ and cycles in $\texttt{Aux}(G,X,S)$,
we need a criterion to derive existence of a cycle from a closed walk with
certain properties. In the following lemma we consider a cyclic order on a
sequence of length $k$. We define the successor operator as $s(i)=i+1$, for
$i\in[k-1]$, and $s(k)=1$.

######  Lemma 4.14 ($\star$).

Let $G$ be a bipartite graph with vertex partition $V(G)=A\cup B$. Suppose
there exists a sequence of vertices $(v_{1},\dots,v_{k})$ in $G$ such that:

  1. 1.

for $i\in[k]$ it holds $v_{i}=v_{s(i)}$ or $v_{i}v_{s(i)}\in E(G)$,

  2. 2.

the multiset $\\{v_{1},\dots,v_{k}\\}$ contains at most one occurrence of each
vertex from $A$,

  3. 3.

the set $\\{v_{1},\dots,v_{k}\\}$ contains at least two vertices from $B$.

Then $G$ contains a cycle.

######  Proof 4.15.

We apply modifications to the sequence $(v_{1},\dots,v_{k})$ while preserving
conditions (1-3). First, if $v_{i}=v_{s(i)}$ then remove $v_{s(i)}$. This rule
is clearly safe. Second, if $v_{i}=v_{s(s(i))}\neq v_{s(i)}$ then remove
$v_{s(i)}$ and $v_{s(s(i))}$. Due to condition (2) it must be $v_{i}\in B$ and
$v_{s(i)}\in A$ so the set $\\{v_{1},\dots,v_{k}\\}\cap B$ stays invariant,
which preserves condition (3).

Each modification shortens the sequence, so after applying them exhaustively
we obtain a sequence that cannot be further reduced. Due to condition (3) the
length of the sequence cannot drop below 4. We claim that each edge from
$E(G)$ is now traversed at most once. Suppose otherwise that
$v_{i}v_{s(i)},v_{j}v_{s(j)}$ represent the same edge for $i\neq j$. The
indices $i,j$ cannot be consecutive due to the second modification rule. But
then some vertex of $A$ must occur twice in the sequence which contradicts
condition (2). As a result we obtain a non-trivial closed walk in $G$ without
repeated edges, which implies the existence of a cycle.

We are ready to prove a proposition creating a link between chordality and
acyclicity.

######  Proposition 4.16.

Consider a graph $G$ with a vertex subset $X\subseteq V(G)$ so that for each
connected component $C$ of $G-X$ the graph $G[X\cup C]$ is chordal. Then $G$
is chordal if and only if for each $S\in\texttt{MinSep}(G[X])$ the graph
$\texttt{Aux}(G,X,S)$ is acyclic.

######  Proof 4.17.

First we argue that if $G$ is chordal then all graphs $\texttt{Aux}(G,X,S)$
are acyclic. Because the class of chordal graphs is closed under vertex
deletions and edge contractions, the graphs $\texttt{Aux}(G,X,S)$ are chordal
as well. Since each graph $\texttt{Aux}(G,X,S)$ is also bipartite, by Section
3 we obtain that $\texttt{Aux}(G,X,S)$ is acyclic.

Now suppose that $G$ is not chordal. Let $G^{\prime}=\texttt{Condense}(G,X)$
(recall Definition 4.8). By Lemma 4.11, the graph $G^{\prime}$ is not chordal
as well but for each vertex $v\in V(G^{\prime})\setminus X$ the graph
$G^{\prime}[X\cup\\{v\\}]$ is chordal (because contraction preserves
chordality). Note that $\texttt{Aux}(G^{\prime},X,S)$ is an induced subgraph
of $\texttt{Aux}(G,X,S)$ for each $S\in\texttt{MinSep}(G[X])$ (they may differ
only due to removal of simplicial vertices), so it suffices to show that one
of the graphs $\texttt{Aux}(G^{\prime},X,S)$ has a cycle.

As $G^{\prime}$ is not chordal, it contains a hole $H=(u_{1},\dots,u_{k})$. We
consider two cases: either $V(H)$ intersects at least two connected components
of $G^{\prime}[X]$ or only one. In the first case, let $\phi_{0}\colon
V(G^{\prime})\to V(\texttt{Aux}(G^{\prime},X,\emptyset))$ be the mapping given
by the contractions from Definition 4.13. Recall that $V(G^{\prime})\setminus
X$ is an independent set in $G^{\prime}$ so $\phi_{0}$ is an identity on this
set. The sequence $(\phi_{0}(u_{1}),\dots,\phi_{0}(u_{k}))$ meets the
preconditions of Lemma 4.14 for $A=V(G^{\prime})\setminus X$ and
$B=\phi_{0}(X)$ so $\texttt{Aux}(G^{\prime},X,\emptyset)$ has a cycle. As
$G^{\prime}[X]=G[X]$ is disconnected, we have
$\emptyset\in\texttt{MinSep}(G[X])$.

In the second case, let $Y\subseteq X$ induce the only connected component of
$G^{\prime}[X]$ that intersects $V(H)$. Let $V_{1},\dots,V_{\ell}\subseteq Y$
be the vertex sets of maximal subpaths of $H$ within $Y$. By the definition of
a hole, we have $E_{G^{\prime}}(V_{i},V_{j})=\emptyset$ for distinct
$i,j\in[\ell]$. It must be $\ell\geq 2$ because for each $v\in
V(G^{\prime})\setminus X$ the graph $G^{\prime}[X\cup\\{v\\}]$ is chordal and
the hole $H$ must visit at least two vertices from the independent set
$V(G^{\prime})\setminus X$. By Lemma 4.6, there exists a minimal vertex
separator $S\subseteq Y\setminus V(H)$ in $G^{\prime}[Y]$ such that every set
$V_{i}$ is contained in some component from $\texttt{Comp}(G^{\prime}[Y],S)$
and at least two components from $\texttt{Comp}(G^{\prime}[Y],S)$ intersect
$V(H)$. Note that $S\in\texttt{MinSep}(G[X])$. Let $C_{S}$ be the union of the
components from $\texttt{Comp}(G^{\prime}[Y],S)$; note that $V(H)\subseteq
V(C_{S})\cup(V(G^{\prime})\setminus X)$.

Let $\phi_{S}\colon V(C_{S})\cup(V(G^{\prime})\setminus X)\to
V(\texttt{Aux}(G^{\prime},X,S))$ be the mapping given by the contractions from
Definition 4.13 which turn each component from
$\texttt{Comp}(G^{\prime}[Y],S)$ into a single vertex. Again, the sequence
$(\phi_{S}(u_{1}),\dots,\phi_{S}(u_{k}))$ meets the preconditions of Lemma
4.14 for $A=V(G^{\prime})\setminus X$ and $B=\phi_{S}(V(C_{S}))$ so
$\texttt{Aux}(G^{\prime},X,S)$ has a cycle. See Figure 1 for an illustration.

Observe that whenever a component of $G-X$ is simplicial then in every graph
$\texttt{Aux}(G,X,S)$ the corresponding vertex has degree one and so it cannot
be a part of any cycle. Therefore the simplicial components of $G-X$ does not
affect the criterion from Proposition 4.16. This agrees with the definition of
$\texttt{Condense}(G,X)$ where the simplicial components are removed as
meaningless.

#### Signatures of boundaried graphs.

The next step is to construct a graphic matroid $M_{B}$ for a chordal graph
$B$ so that for any two graphs $G_{1},G_{2}\in\mathcal{G}_{X,B}$ the
information about chordality of $(G_{1},X)\oplus(G_{2},X)$ could be read from
$M_{B}$. Proposition 4.16 already relates chordality to acyclicity but the
corresponding graphic matroids for $G_{1},G_{2}$ are disparate. To circumvent
this, we will further compress the information about cycles.

######  Definition 4.18.

Consider a graph $B$. For $S\in\texttt{MinSep}(B)$, let $\texttt{Base}(B,S)$
be the complete graph on vertex set $\texttt{Comp}(B,S)$. The graph
$\texttt{Base}(B)$ is a disjoint union of all the graphs $\texttt{Base}(B,S)$
for $S\in\texttt{MinSep}(B)$.

That is, we treat the components from $\texttt{Comp}(B,S)$ as abstract
vertices of a new graph which is a union of cliques.

The following transformation is similar to the one used in the algorithm for
Steiner Tree based on representative families [38]. For the sake of
disambiguation, in the definition below we assume an implicit linear order on
the vertices of $B$; this order may be arbitrary. Since vertices of
$\texttt{Base}(B)$ correspond to distinct subsets of $V(B)$, which can ordered
lexicographically, fixing the order on $V(B)$ yields an order on
$V(\texttt{Base}(B))$. We can thus assume that also the vertices of
$V(\texttt{Base}(B))$ are linearly ordered.

######  Definition 4.19.

Consider a chordal graph $B$ and $Y\subseteq V(B)$. We define the _spanning
signature_ $\texttt{Span}(B,Y)\subseteq E(\texttt{Base}(B))$ as follows. For
each $S\in\texttt{MinSep}(B)$ let $C_{S,Y}\subseteq V(\texttt{Base}(B,S))$ be
given by components from $\texttt{Comp}(B,S)$ with a non-empty intersection
with $Y$. Let $P_{S,Y}\subseteq E(\texttt{Base}(B,S))$ be the path connecting
the vertices of $C_{S,Y}$ in the increasing order. Then
$\texttt{Span}(B,Y)=\bigcup_{S\in\texttt{MinSep}(B)}P_{S,Y}$.

In other words, $\texttt{Span}(B,Y)$ is a disjoint union of paths in the graph
$\texttt{Base}(B)$, where each path encodes the relation between $Y$ and a
respective minimal vertex separator in $B$.

The next lemma states that under certain conditions replacing a vertex $v$
with a tree over $N(v)$ (in particular: a path) does not affect acyclicity of
the graph. Note that due to the precondition $|N(u)\cap N(v)|\leq 1$ we never
attempt to insert an edge that is already present.

######  Lemma 4.20 ($\star$).

Let $G$ be a bipartite graph with a vertex partition $V(G)=A\cup B$ so that
for each distinct $u,v\in A$ it holds that $|N_{G}(u)\cap N_{G}(v)|\leq 1$.
Consider a graph $G^{\prime}$ obtained from $G$ by replacing each vertex $v\in
A$ by an arbitrary tree on vertex set $N_{G}(v)$. Then $G$ is acyclic if and
only if $G^{\prime}$ is acyclic.

######  Proof 4.21.

For a graph $G$, let $\mu(G)$ be the multiset of integers
$(|V(C)|-|E(C)|)_{C\in\mathcal{C}}$ where $\mathcal{C}$ is the family of
connected components of $G$. A graph $G$ is acyclic if and only if $\mu(G)$
contains only 1’s. We show that the described modifications, performed in an
arbitrary order, does not affect $\mu(G)$ except for possibly removing some
1’s. Let $v\in V(G)$, $d=|N_{G}(v)|$, and $C$ denote the connected component
of $v$. If $v$ is isolated, then removing $v$ translates into removing single
1 from $\mu(G)$. Otherwise, replacing $v$ with a tree on $N_{G}(v)$ transforms
$C$ into another connected graph $C^{\prime}$. We remove one vertex and $d$
edges, so $|V(C)|-|E(C)|$ drops by $d-1$. On the other hand, any tree over
$N_{G}(C)$ has exactly $d-1$ edges. Due to the assumption $|N_{G}(u)\cap
N_{G}(v)|\leq 1$ for $u\neq v$, every inserted tree is disjoint from
previously inserted edges among $B$. Hence, we insert exactly $d-1$ new edges
and $|V(C)|-|E(C)|=|V(C^{\prime})|-|E(C^{\prime})|$. We also only remove
vertices from $A$ so we never remove an endpoint of an inserted edge. The
claim follows by observing that $\mu(G)$ contains an element different from 1
if and only if $\mu(G^{\prime})$ does.

This allows us to translate the criterion from Proposition 4.16 into a more
convenient one, in which the vertex set of the auxiliary graph depends only on
$G[X]$ rather than $G$.

######  Lemma 4.22.

Consider a graph $G$ with a vertex subset $X\subseteq V(G)$. Let $\mathcal{C}$
denote the family of connected components of $G-X$. Suppose that for each
$C\in\mathcal{C}$ the graph $G[X\cup C]$ is chordal. Then $G$ is chordal if
and only if:

  1. 1.

the sets $\texttt{Span}(G[X],N_{G}(C))$, for different $C\in\mathcal{C}$, are
pairwise disjoint,

  2. 2.

the union of sets $\texttt{Span}(G[X],N_{G}(C))$, over $C\in\mathcal{C}$,
forms an acyclic edge set in $E(\texttt{Base}(G[X]))$.

######  Proof 4.23.

From Proposition 4.16 we know that $G$ is chordal if and only if for each
$S\in\texttt{MinSep}(G[X])$ the graph $\texttt{Aux}(G,X,S)$ is acyclic. We
consider two cases.

First, suppose that for some $S\in\texttt{MinSep}(G[X])$ there are two
vertices representing distinct components $C_{1},C_{2}\in\mathcal{C}$ that
share two common neighbors $x,y$ in $\texttt{Aux}(G,X,S)$. In other words,
there are two components from $\texttt{Comp}(G[X],S)$ that intersect both
$N_{G}(C_{1})$ and $N_{G}(C_{2})$. Then $\texttt{Aux}(G,X,S)$ contains a cycle
of length 4, so $G$ is not chordal. If $\texttt{Span}(G[X],N_{G}(C_{1}))$ and
$\texttt{Span}(G[X],N_{G}(C_{2}))$ share an edge, then condition (1) fails, so
suppose this is not the case. But then the paths $P_{S,N(C_{1})}$ and
$P_{S,N(C_{2})}$ (recall Definition 4.19) are edge-disjoint and they both
visit $x$ and $y$. As a consequence, $x,y$ lie on a cycle contained in the
edge set
$\texttt{Span}(G[X],N_{G}(C_{1}))\cup\texttt{Span}(G[X],N_{G}(C_{2}))$ so
condition (2) fails. In summary, both $G$ is not chordal and one of conditions
(1, 2) does not hold.

Next, suppose that for each $S\in\texttt{MinSep}(G[X])$ and any two vertices
representing distinct components $C_{1},C_{2}\in\mathcal{C}$ the intersection
of their neighborhoods in $\texttt{Aux}(G,X,S)$ contains at most one element.
This implies condition (1). Consider a graph $H$ given by a disjoint union of
all graphs $\texttt{Aux}(G,X,S)$ over $S\in\texttt{MinSep}(G[X])$. This graph
meets the preconditions of Lemma 4.20. Replacing each
$\mathcal{C}\text{-component}$-vertex in $\texttt{Aux}(G,X,S)$ by the path
$P_{S,N(C)}$ transforms $H$ into a subgraph of $\texttt{Base}(G[X])$ with the
edge set $\bigcup_{C\in\mathcal{C}}\texttt{Span}(G[X],N_{G}(C))$. By Lemma
4.20, this graph is acyclic if and only if the graph $H$ is. By Proposition
4.16, this condition is equivalent to $G$ being chordal. The lemma follows.

We are ready to define the graphic matroid encoding all the necessary
information about where a hole can appear after gluing two chordal graphs.
Recall that a graphic matroid of a graph $G$ is a set system over $E(G)$ where
a subset $S\subseteq E(G)$ is called independent when $S$ contains no cycles.

######  Definition 4.24.

For a graph $B$ on vertex set $X$ we define matroid $M_{B}$ as the graphic
matroid of the graph $\texttt{Base}(B)$. For a graph $G\in\mathcal{G}_{X,B}$
the signature $\texttt{Sign}(G,X)\subseteq E(\texttt{Base}(B))$ is defined as
a union of $\texttt{Span}(B,N_{G}(C))$ over all connected components $C$ of
$G-X$.

It follows from Lemma 4.22 that whenever $G$ is chordal then
$\texttt{Sign}(G,X)$ is acyclic and so it forms an independent set in the
matroid $M_{G[X]}$. We can now give the existential part of Theorem 2.1. The
mapping $\sigma\colon\mathcal{G}_{X,B}\to 2^{E(M_{B})}$ therein is given here
as $\sigma(G)=\texttt{Sign}(G,X)$.

######  Lemma 4.25 ($\star$).

Let $(G_{1},X)$ and $(G_{2},X)$ be compatible boundaried chordal graphs. Then
$G=(G_{1},X)\oplus(G_{2},X)$ is chordal if and only if the sets
$\texttt{Sign}(G_{1},X)$, $\texttt{Sign}(G_{2},X)\subseteq
E(\texttt{Base}(G[X]))$ are disjoint and
$\texttt{Sign}(G_{1},X)\cup\texttt{Sign}(G_{2},X)$ is acyclic.

Furthermore,
$\texttt{Sign}(G,X)=\texttt{Sign}(G_{1},X)\cup\texttt{Sign}(G_{2},X)$.

######  Proof 4.26.

Let $C_{1},C_{2},\dots,C_{\ell}$ denote the connected components of $G_{1}-X$
and $D_{1},D_{2},\dots,D_{r}$ denote the connected components of $G_{2}-X$.
Clearly all graphs $G_{1}[X\cup C_{i}]$ and $G_{2}[X\cup D_{i}]$ are chordal.
Let $\mathcal{S}_{1}$ be the family of sets
$\\{\texttt{Span}(G[X],N_{G_{1}}(C_{i})\\}_{i=1}^{\ell}$ and $\mathcal{S}_{2}$
be $\\{\texttt{Span}(G[X],N_{G_{2}}(D_{i})\\}_{i=1}^{r}$. It follows from
Lemma 4.22 that the sets in $\mathcal{S}_{1}$ are pairwise disjoint and their
union, which is $\texttt{Sign}(G_{1},X)$, is an acyclic edge set in
$E(\texttt{Base}(G[X]))$. The same holds for $\mathcal{S}_{2}$ and
$\texttt{Sign}(G_{2},X)$. Again by Lemma 4.22, the graph
$G=(G_{1},X)\oplus(G_{2},X)$ is chordal if and only if the sets in the family
$\mathcal{S}_{1}\cup\mathcal{S}_{2}$ are pairwise disjoint and their sum is
acyclic. This is equivalent to the condition that
$\texttt{Sign}(G_{1},X),\texttt{Sign}(G_{2},X)$ are disjoint and
$\texttt{Sign}(G_{1},X)\cup\texttt{Sign}(G_{2},X)$ is acyclic, as intended. By
definition, $\texttt{Sign}(G,X)$ is the union of
$\texttt{Span}(G[X],N_{G}(C))$ over all connected components $C$ of $G-X$.
This union equals $\texttt{Sign}(G_{1},X)\cup\texttt{Sign}(G_{2},X)$.

The following lemma is the main ingredient in the running time analysis. As
the bound on the representative family’s size is exponential in the rank of a
matroid222We remark that Fomin et al. [38] also considered a case when the
rank might be large and the exponential term is governed by a different
parameter but it is not applicable in our case., it is necessary to bound the
rank of $M_{B}$. It is known that the number of minimal vertex separators in a
chordal graph is bounded by the number of vertices but we need a strengthening
of this fact.

######  Lemma 4.27.

For a non-empty chordal graph $B$, the rank of $M_{B}$ is at most $|V(B)|-1$.

######  Proof 4.28.

Let $k=|V(B)|$. The rank of $M_{B}$ equals the size of a spanning forest in
$\texttt{Base}(B)$. The vertex sets of connected components of
$\texttt{Base}(B)$ are the sets $\texttt{Comp}(B,S)$ for
$S\in\texttt{MinSep}(B)$. Therefore it suffices to estimate

$\sum_{S\in\texttt{MinSep}(B)}(|\texttt{Comp}(B,S)|-1)\leq k-1.$

We first prove the inequality for connected chordal graphs by induction on
$k$. For $k=1$ the sum is zero. Consider $k>1$. By Lemma 3.6, $B$ contains a
simplicial vertex. Let $v$ be a simplicial vertex in $B$ and suppose that the
claim holds for the graph $B-v$ (which is connected). Let $S$ be a minimal
vertex separator in $B$. By Lemma 4.4 when $S\neq N_{B}(v)$ then
$S\in\texttt{MinSep}(B-v)$ and $|\texttt{Comp}(B,S)|=|\texttt{Comp}(B-v,S)|$.
In that case the summand coming from $S$ is the same for $B$ and $B-v$.

It remains to handle the case $S=N_{B}(v)$. Clearly,
$\\{v\\}\in\texttt{Comp}(B,S)$. If $|\texttt{Comp}(B,S)|=1$ then
$S\not\in\texttt{MinSep}(B)$ (Lemma 3.1). If $|\texttt{Comp}(B,S)|=2$ then
$S\in\texttt{MinSep}(B)\setminus\texttt{MinSep}(B-v)$ and the sum grows by
one. If $|\texttt{Comp}(B,S)|\geq 3$ then
$S\in\texttt{MinSep}(B)\cap\texttt{MinSep}(B-v)$ and
$|\texttt{Comp}(B,S)|=|\texttt{Comp}(B-v,S)|+1$ so the sum again grows by one.
This concludes the proof of the inequality for connected chordal graphs.

When $B$ is disconnected, let $B_{1},B_{2},\dots,B_{t}$ denote its connected
components and let $k_{i}=|V(B_{i})|$. We have
$|\texttt{Comp}(B,\emptyset)|-1=t-1$. Together with the sums for
$B_{1},B_{2},\dots,B_{t}$ the total sum is at most
$\sum_{i=1}^{t}k_{i}-t+t-1=k-1$.

The last thing to be checked is whether we can compute the signatures
efficiently. To this end, we enumerate minimal vertex separators using Lemma
4.4.

######  Lemma 4.29 ($\star$).

There is a polynomial-time algorithm that, given a graph $G$ with a vertex
subset $X\subseteq V(G)$ such that $G[X]$ is chordal, computes
$\texttt{Sign}(G,X)$.

######  Proof 4.30.

Let $B=G[X]$. We show that one can enumerate $\texttt{MinSep}(B)$ in
polynomial time. By Lemma 3.6 the graph $B$ contains a simplicial vertex $v$.
This vertex can be found in polynomial time. We recursively enumerate
$\texttt{MinSep}(B-v)$. By Lemma 4.4, if $S\in\texttt{MinSep}(B)$ then either
$S\in\texttt{MinSep}(B-v)$ or $S=N_{B}(v)$, so the output size increases by at
most one. We can verify which elements of
$\texttt{MinSep}(B-v)\cup\\{N_{B}(v)\\}$ are minimal vertex separators in $G$
using Lemma 3.1; as a byproduct we obtain the sets $\texttt{Comp}(B,S)$. It
remains to directly follow the definition of $\texttt{Sign}(G,X)$.

Lemmas 4.25, 4.27, and 4.29 entail Theorem 2.1 but instead of working with
that abstract statement we use these three lemmas directly when describing the
final algorithm.

#### Representative families for boundaried graphs.

We translate the framework of representative families from the language of
matroids to chordal graphs and gluing.

######  Definition 4.31.

Consider a family of chordal graphs $\mathcal{G}\subseteq\mathcal{G}_{X,B}$
for some pair $(X,B)$ and a non-negative weight function
$w:\mathcal{G}\to\mathbb{N}$. We say that a subfamily
$\widehat{\mathcal{G}}\subseteq\mathcal{G}$ is max-representative for
$\mathcal{G}$ (and write
$\widehat{\mathcal{G}}\subseteq_{\mathrm{maxrep}}\mathcal{G}$) if the
following holds. For every graph $H\in\mathcal{G}_{X,B}$, if there exist
$G\in\mathcal{G}$ so that $(H,X)\oplus(G,X)$ is chordal, then there exists
$\widehat{G}\in\widehat{\mathcal{G}}$ so that $(H,X)\oplus(\widehat{G},X)$ is
chordal and $w(\widehat{G})\geq w(G)$.

######  Lemma 4.32.

Consider a family of chordal graphs $\mathcal{G}\subseteq\mathcal{G}_{X,B}$
for some pair $(X,B)$ and a non-negative weight function
$w:\mathcal{G}\to\mathbb{N}$. Suppose that the matroid $M_{B}$ has rank $r$.
Let $\mathcal{S}=\\{\texttt{Sign}(G,X)\mid G\in\mathcal{G}\\}$ and
$\tau\colon\mathcal{S}\to\mathcal{G}$ be given as
$\tau(Y)=\mathrm{argmax}\,\\{w(G)\mid
G\in\mathcal{G},\,\texttt{Sign}(G,X)=Y\\}$. Suppose that
$\widehat{\mathcal{S}}\subseteq^{r}_{\mathrm{maxrep}}\mathcal{S}$ with respect
to matroid $M_{B}$ and weight function $w_{\mathcal{S}}(Y)=w(\tau(Y))$. Then
$\tau(\widehat{\mathcal{S}})\subseteq_{\mathrm{maxrep}}\mathcal{G}$.

######  Proof 4.33.

Let $H\in\mathcal{G}_{X,B}$ and $G\in\mathcal{G}$ be such that
$(H,X)\oplus(G,X)$ is chordal. Clearly $H$ must be chordal as well. The set
$S=\texttt{Sign}(G,X)$ belongs to $\mathcal{S}$ and $w_{\mathcal{S}}(S)\geq
w(G)$. By Lemma 4.25 we have that $\texttt{Sign}(H,X)\cap S=\emptyset$ and
$\texttt{Sign}(H,X)\cup S$ is acyclic. By the definition of a max-
representative family for a graphic matroid, there exists a set
$\widehat{S}\in\widehat{\mathcal{S}}$ so that
$\texttt{Sign}(H,X)\cap\widehat{S}=\emptyset$,
$\texttt{Sign}(H,X)\cup\widehat{S}$ is acyclic, and
$w_{\mathcal{S}}(\widehat{S})\geq w_{\mathcal{S}}(S)$. Let
$\widehat{G}=\tau(\widehat{S})$. Again by Lemma 4.25 we infer that
$(H,X)\oplus(\widehat{G},X)$ is chordal. Finally,
$w(\widehat{G})=w_{\mathcal{S}}(\widehat{S})\geq w_{\mathcal{S}}(S)\geq w(G)$.

######  Lemma 4.34.

Consider a family of chordal graphs $\mathcal{G}\subseteq\mathcal{G}_{X,B}$
for some pair $(X,B)$ and a non-negative weight function
$w:\mathcal{G}\to\mathbb{N}$. Suppose that $|X|=k>0$, $|\mathcal{G}|\leq
2^{k+c}$, and each $G\in\mathcal{G}$ has at most $ck$ vertices. Here, $c$ is a
fixed constant. Then a max-representative family
$\widehat{G}\subseteq\widehat{\mathcal{G}}$ for $\mathcal{G}$ of size at most
$2^{k-1}$ can be computed in time $\mathcal{O}(2^{\omega k}\cdot k^{\omega})$.

######  Proof 4.35.

Let $\mathcal{S}=\\{\texttt{Sign}(G,X)\mid G\in\mathcal{G}\\}$. This family
can be computed in time $2^{k}\cdot k^{\mathcal{O}(1)}$ thanks to Lemma 4.29.
By Lemma 4.27 the rank $r$ of $M_{B}$ is at most $k-1$. By Lemma 4.32 if
suffices to find a max $r$-representative family for $\mathcal{S}$ of the
requested size. This can be done with Lemma 3.18 in time
$\mathcal{O}(2^{\omega k}\cdot k^{\omega})$. Since $2<2^{\omega}$ the latter
term is dominating in the running time.

We also provide an efficient algorithm for processing large families of graphs
that arise when handling a join node. For a graph family $\mathcal{G}$ we
write $\mathcal{G}\cap\texttt{chordal}$ to indicate the subfamily of chordal
graphs in $\mathcal{G}$.

######  Lemma 4.36.

Consider two families of chordal graphs
$\mathcal{G}_{1},\mathcal{G}_{2}\subseteq\mathcal{G}_{X,B}$ for some pair
$(X,B)$. Suppose that $|X|=k>0$, $|\mathcal{G}_{1}|,|\mathcal{G}_{2}|\leq
2^{k}$, and each $G\in\mathcal{G}_{1}\cup\mathcal{G}_{2}$ has $\mathcal{O}(k)$
vertices. Let $\mathcal{G}=\\{(G_{1},X)\oplus(G_{2},X)\mid
G_{1}\in\mathcal{G}_{1},G_{2}\in\mathcal{G}_{2}\\}\cap\texttt{chordal}$ and
$w:\mathcal{G}\to\mathbb{N}$ be a non-negative weight function. Then
$\widehat{\mathcal{G}}\subseteq_{\mathrm{maxrep}}\mathcal{G}$ of size at most
$2^{k-1}$ can be computed in time $\mathcal{O}(2^{(\omega-1)k}3^{k}\cdot
k^{\omega})$ when given $\mathcal{G}_{1},\mathcal{G}_{2},\mathcal{G},w$.

######  Proof 4.37.

Let $\mathcal{S}=\\{\texttt{Sign}(G,X)\mid G\in\mathcal{G}\\}$,
$\mathcal{S}_{1}=\\{\texttt{Sign}(G,X)\mid G\in\mathcal{G}_{1}\\}$, and
$\mathcal{S}_{2}=\\{\texttt{Sign}(G,X)\mid G\in\mathcal{G}_{2}\\}$. We claim
that $\mathcal{S}=\mathcal{S}_{1}\bullet\mathcal{S}_{2}$. For
$\ell\in\\{1,2\\}$ consider $S_{\ell}\in\mathcal{S}_{\ell}$ and
$G_{\ell}\in\mathcal{G}_{\ell}$ such that
$\texttt{Sign}(G_{\ell},X)=S_{\ell}$. Then $(G_{1},X)\oplus(G_{2},X)$ belongs
to $\mathcal{G}$ if and only if it is chordal what, by Lemma 4.25, is
equivalent to the condition that $S_{1}\cap S_{2}=\emptyset$ and $S_{1}\cup
S_{2}$ is independent in $M_{B}$. This justifies the claim.

By Lemma 4.27 the rank $r$ of $M_{B}$ is at most $k-1$. We proceed similarly
as in Lemma 4.34 but we use Lemma 3.21 to compute an $r$-representative family
of size $2^{k-1}$ for $\mathcal{S}_{1}\bullet\mathcal{S}_{2}$ in time
$\mathcal{O}(2^{(\omega-1)k}3^{k}\cdot k^{\omega})$. Computing the signatures
and the mapping $\tau\colon\mathcal{S}\to\mathcal{G}$ takes time
$|\mathcal{G}|\cdot k^{\mathcal{O}(1)}=4^{k}\cdot k^{\mathcal{O}(1)}$ so the
previous term is dominating in the running time.

###  4.1 Dynamic programming

We present a dynamic programming algorithm processing a tree decomposition. We
begin with describing the states of the dynamic programming routine and their
invariants. Although we do not store tables indexed by partial solutions but
rather a family of partial solutions with weights (as in [38]), we keep the
notion of ‘state’ to refer to information stored at a node of a decomposition.

#### States for DP.

A state for a node $t\in V(\mathbb{T})$ is a family of pairs
$(\mathcal{H}_{t,X},h_{t,X})$ assigned to each $X\subseteq\chi(t)$, where
$\mathcal{H}_{t,X}\subseteq\mathcal{G}_{X,G[X]}$ is a family of chordal graphs
and $h_{t,X}\colon\mathcal{H}_{t,X}\to\mathbb{N}$ is a non-negative weight
function.

Recall that $V_{t}$ denotes the set of vertices occurring in the subtree
rooted at $t\in V(\mathbb{T})$ and $U_{t}=V_{t}\setminus\chi(t)$. The intended
meaning of $H\subseteq\mathcal{H}_{t,X}$ and $h_{t,X}(H)=s$ is that there
should exists a set $A\subseteq U_{t}$ of total weight $s$ so that $(A,X)$ is
a partial solution equivalent to $H$. For each $H$ we want to keep track of
such a set $A$ of maximal weight.

For sets $X,Y$ we write concisely $(A,B)\subseteq(X,Y)$ to denote $A\subseteq
X$, $B\subseteq Y$.

#### Correctness invariant.

For $t\in V(\mathbb{T})$ and $X\subseteq\chi(t)$ we say that a pair
$(\mathcal{H},h)$ satisfies the correctness invariant for $(t,X)$ if the
following holds.

  1. 1.

For each $H\in\mathcal{H}$ there exists a set $A\subseteq U_{t}$ so that
$\texttt{Condense}(G[A\cup X],X)=H$, $G[A\cup X]$ is chordal, and $h(H)=w(A)$.

  2. 2.

For each $(A,B)\subseteq(U_{t},V(G)\setminus V_{t})$ for which $G[A\cup X\cup
B]$ is chordal there exists $H\in\mathcal{H}$ so that $(H,X)\oplus(G[B\cup
X],X)$ is chordal and $h(H)\geq w(A)$.

As a consequence of this invariant, we have that for each pair $(A,B)$ from
the second condition there exists $\widehat{A}\subseteq U_{t}$ (a replacement
for $A$) so that $w(\widehat{A})\geq w(A)$,
$\texttt{Condense}(G[\widehat{A}\cup X],X)\in\mathcal{H}$, and
$(\texttt{Condense}(G[\widehat{A}\cup X],X),X)\oplus(G[B\cup X],X])$ is
chordal which implies that $G[\widehat{A}\cup X\cup B]$ is chordal (Lemma
4.9).

Since every graph in $\mathcal{H}_{t,X}$ is condensed with respect to $X$,
Lemma 4.10 implies a bound on its size (we do not subtract one from $2|X|$ to
cover the case $X=\emptyset$).

If $t\in V(\mathbb{T})$, $X\subseteq\chi(t)$, and $(\mathcal{H},h)$ satisfies
the correctness invariant for $(t,X)$, then every graph in $\mathcal{H}$ has
at most $2|X|$ vertices.

We take advantage of the theory developed so far to keep the sizes of
$\mathcal{H}_{t,X}$ in check.

######  Lemma 4.38.

Consider $t\in V(\mathbb{T})$ and $X\subseteq\chi(t)$. If a pair
$(\mathcal{H},h)$ satisfies the correctness invariant for $(t,X)$ and
$\widehat{\mathcal{H}}\subseteq_{\mathrm{maxrep}}\mathcal{H}$ then
$(\widehat{\mathcal{H}},h)$ also satisfies the correctness invariant for
$(t,X)$.

######  Proof 4.39.

The first condition is satisfied trivially as the quantification switches to a
subset of $\mathcal{H}$. Consider $(A,B)\subseteq(U_{t},V(G)\setminus V_{t}))$
from condition (2). By the assumption, there exists $H\in\mathcal{H}$ so that
$(H,X)\oplus(G[B\cup X],X)$ is chordal and $h(H)\geq w(A)$. By the definition
of a max-representative family there exists
$\widehat{H}\subseteq\widehat{\mathcal{H}}$ so that
$(\widehat{H},X)\oplus(G[B\cup X],X)$ is chordal and $h(\widehat{H})\geq
h(H)\geq w(A)$. The claim follows.

#### Size invariant.

For $t\in V(\mathbb{T})$ and $X\subseteq\chi(t)$ we say that
$\mathcal{H}\subseteq\mathcal{G}_{X,G[X]}$ satisfies the size invariant if
$|\mathcal{H}|\leq 2^{|X|}$.

For a node $t\in\mathbb{T}$ we say that its state satisfies the correctness or
size invariant if all the pairs
$(\mathcal{H}_{t,X},h_{t,X})_{X\subseteq\chi(t)}$ satisfies it.

We move on to describing the dynamic programming routine for the three non-
trivial types of nodes in a nice tree decomposition. In each case we begin
with the algorithm, then prove the correctness invariant, and then analyze the
running time together with the size invariant.

######  Lemma 4.40 (Introduce node).

Let $(\mathbb{T},\chi)$ be a nice tree decomposition of $G$ of width $k$ and
$t\in V(\mathbb{T})$ be an introduce node with a child $t^{\prime}$. Suppose
that the state for $t^{\prime}$ satisfying the correctness and size invariants
is given. Then we can compute the state for $t$ which satisfies the
correctness and size invariants in time $3^{k}k^{\mathcal{O}(1)}$.

######  Proof 4.41.

We have $\chi(t)=\chi(t^{\prime})\cup\\{v\\}$ for some vertex $v$. Next,
$U_{t}=U_{t^{\prime}}$ and $V_{t}=V_{t^{\prime}}\cup\\{v\\}$. Note that
$N_{G}(v)\cap U_{t}=\emptyset$.

We define operation Introduce$(H,N)$ which takes a graph $H$ and a set
$N\subseteq V(H)$ and inserts to $H$ a new vertex $v$ with neighborhood $N$.

If $X\subseteq\chi(t)$ does not contain $v$, we set
$\mathcal{H}_{t,X}=\mathcal{H}_{t^{\prime},X}$ and $h_{t,X}=h_{t^{\prime},X}$.
Consider $X\subseteq\chi(t)$ containing $v$; let $X^{-}=X\setminus v$. If
$G[X]$ is not chordal we set $\mathcal{H}_{t,X}=\emptyset$. Otherwise for each
$H^{\prime}\in\mathcal{H}_{t^{\prime},X^{-}}$ we compute
$(H,X)=\texttt{Introduce}(H^{\prime},N_{G}(v)\cap X^{-})$. If $H$ is chordal
we insert it to $\mathcal{H}_{t,X}$ and set
$h_{t,X}(H)=h_{t^{\prime},X^{-}}(H^{\prime})$.

#### Correctness.

Suppose first that $v\not\in X$. We check condition (1). Let
$H\in\mathcal{H}_{t,X}$. By the construction, $H\in\mathcal{H}_{t^{\prime},X}$
and, by the inductive assumption, there is a set $A\subseteq
U_{t^{\prime}}=U_{t}$ so that $\texttt{Condense}(G[A\cup X],X)=H$, $G[A\cup
X]$ is chordal, and $h_{t,X}(H)=h_{t^{\prime},X}(H)=w(A)$. To see condition
(2), consider any $A\subseteq U_{t}$ and $B\subseteq V(G)\setminus V_{t}$.
Then $A\subseteq U_{t^{\prime}}$ and $B\subseteq V(G)\setminus V_{t^{\prime}}$
so again the claim follows directly from the invariant for $t^{\prime}$.

Suppose now that $v\in X$. We check condition (1). Every
$H\in\mathcal{H}_{t,X}$ is of the form
$H=\texttt{Introduce}(H^{\prime},N_{G}(v)\cap X^{-})$ for some
$H^{\prime}\in\mathcal{H}_{t^{\prime},X^{-}}$. Moreover, $H$ must be chordal
by the construction. By the inductive assumption there is a set $A\subseteq
U_{t^{\prime}}=U_{t}$ so that $\texttt{Condense}(G[A\cup
X^{-}],X^{-})=H^{\prime}$, $G[A\cup X^{-}]$ is chordal,
$h_{t,X}(H)=h_{t^{\prime},X}(H^{\prime})=w(A)$. Since $N_{G}(v)\cap
A=\emptyset$ the vertex $v$ does not affect which connected components of
$G[A]$ are simplicial in $G[A\cup X]$. Therefore, the graph
$\texttt{Condense}(G[A\cup X],X)$ can be obtained from
$\texttt{Condense}(G[A\cup X^{-}],X^{-})$ by simply inserting the vertex $v$,
and so it equals $H$.

Finally, we need to check that $G[A\cup X]$ is chordal. We apply criterion
from Lemma 4.11 with respect to set $X^{-}$. For every connected component $C$
of $G[A\cup X]-X^{-}$ the graph $G[C\cup X^{-}]$ is either a subgraph of
$G[A\cup X^{-}]$ or it equals $G[X]$—in both cases it is chordal. The graph
$\texttt{Condense}(G[A\cup X],X^{-})$ is either isomorphic to $H$ or can be
obtained from $H$ by removal of $v$ (when $v$ is simplicial in $H$). Therefore
this graph is also chordal what implies that $G[A\cup X]$ is chordal.

We move on to condition (2) for the case $v\in X$. Let
$(A,B)\subseteq(U_{t},V(G)\setminus V_{t})$ be such that $G[A\cup X\cup B]$ is
chordal. Note that no such pair exists when $G[X]$ is not chordal, so we only
care about the case where $G[X]$ is chordal. Let $B^{+}=B\cup\\{v\\}$; then
$(A,B^{+})\subseteq(U_{t^{\prime}},V(G)\setminus V_{t^{\prime}})$. Therefore,
there exists $H^{\prime}\in\mathcal{H}_{t^{\prime},X^{-}}$ so that
$(H^{\prime},X^{-})\oplus(G[B^{+}\cup X^{-}],X^{-})$ is chordal and
$h_{t^{\prime},X^{-}}(H^{\prime})\geq w(A)$. Let
$H=\texttt{Introduce}(H^{\prime},N_{G}(v)\cap X^{-})$. By construction we have
$h_{t,X}(H)=h_{t^{\prime},X^{-}}(H^{\prime})$. Next, $B\cup X=B^{+}\cup
X^{-}$. Since and $N_{H}(v)\subseteq X$, the gluing product
$(H,X)\oplus(G[B\cup X],X)$ is the same as $(H^{\prime},X^{-})\oplus(G[B\cup
X],X^{-})$ which is chordal, as noted above. This also implies that $H$ is
chordal so it gets inserted to $\mathcal{H}_{t,X}$. This concludes the proof
of the correctness invariant.

#### Running time.

If $v\not\in X$ then $\mathcal{H}_{t,X}=\mathcal{H}_{t^{\prime},X}$ and if
$v\in X$ then each graph from $\mathcal{H}_{t^{\prime},X^{-}}$ is mapped to a
single graph in $\mathcal{H}_{t,X}$. In both cases the size invariant is
preserved. For each $X\subseteq\chi(t)$ we process at most $2^{|X|}$ graphs
what in total gives $\sum_{X\subseteq\chi(t)}2^{|X|}\leq 3^{k+1}$ graphs. By
Section 4.1 each graph has at most $2(k+1)$ vertices and is processed in time
$k^{\mathcal{O}(1)}$.

Before describing the routine for a forget node we prove that the condensing
operation applied with respect to $X$ and then to $X\setminus v$ results in
the same graph as when applying it directly to $X\setminus v$.

######  Lemma 4.42.

Let $X\subseteq V(H)$ and $v\in X$. Next, let $H_{2}=\emph{{Condense}}(H,X)$
and $H_{3}=\emph{{Condense}}(H_{2},X\setminus v)$. Then
$H_{3}=\emph{{Condense}}(H,X\setminus v)$.

######  Proof 4.43.

Let $C$ be a connected component of $H-X$ which is non-adjacent to $v$. Then
it gets contracted into a single vertex and is present in both $H_{2},H_{3}$
as long as it is non-simplicial. Consider now the connected components of
$H-X$ which are adjacent to $v$. Let $S_{1},S_{2},\dots,S_{\ell}$ be those
among them which are simplicial in $H$ and $C_{1},C_{2},\dots,C_{r}$ are those
which are non-simplicial. Let $V_{S,C,v}=\bigcup S_{i}\cup\bigcup
D_{i}\cup\\{v\\}$ and $V_{C,v}=\bigcup C_{i}\cup\\{v\\}$. If $u\in
N_{H}(S_{i})$ then, since $v\in N_{H}(S_{i})$ and $S_{i}$ is simplicial, we
have $u\in N_{H}(v)$. This implies that $N_{H}(V_{S,C,v})=N_{H}(V_{C,v})$. In
$H_{2}$ all the components $S_{i}$ are removed and $C_{i}$ are contracted to
vertices. In $H_{3}$ the latter vertices are replaced with a new vertex
$v^{\prime}$ with neighborhood $N_{H}(V_{C,v})$. In
$\texttt{Condense}(H,X\setminus v)$ we directly replace all components
$S_{i},C_{i}$ with a new vertex $v^{\prime\prime}$ with neighborhood
$N_{H}(V_{S,C,v})$. As observed above, these neighborhoods coincide, hence
$H_{3}=\texttt{Condense}(H,X\setminus v)$.

######  Lemma 4.44 (Forget node).

Let $(\mathbb{T},\chi)$ be a nice tree decomposition of $G$ of width $k$ and
$t\in V(\mathbb{T})$ be a forget node with a child $t^{\prime}$. Suppose that
the state for $t^{\prime}$ satisfying the correctness and size invariants is
given. Then we can compute the state for $t$ which satisfies the correctness
and size invariants in time $(2^{\omega}+1)^{k}k^{\mathcal{O}(1)}$.

######  Proof 4.45.

We have $\chi(t^{\prime})=\chi(t)\cup\\{v\\}$ for some vertex $v\in V_{t}$.
Next, $V_{t}=V_{t^{\prime}}$ and $U_{t}=U_{t^{\prime}}\cup\\{v\\}$. Note that
$N_{G}(v)\subseteq V_{t}$.

Let $X\subseteq\chi(t)$, $X^{+}=X\cup\\{v\\}$, and
$\mathcal{H}^{\prime}=\\{\texttt{Condense}(H^{\prime},X)\mid
H^{\prime}\in\mathcal{H}_{t^{\prime},X^{+}}\\}$. For each
$H\in\mathcal{H}_{t^{\prime},X}\cup\mathcal{H}^{\prime}$ we define its weight
$h_{t,X}(H)$ as maximum over $h_{t^{\prime},X}(H)$ (considered only if
$H\in\mathcal{H}_{t^{\prime},X}$) and
$\max\\{h_{t^{\prime},X^{+}}(H^{\prime})+w(v))\mid
H^{\prime}\in\mathcal{H}_{t^{\prime},X^{+}}\land\texttt{Condense}(H^{\prime},X)=H\\}$.
It follows from the construction that we take maximum over a non-empty set.
Finally, we compute $\mathcal{H}_{t,X}$ with Lemma 4.34 as the max-
representative family for $\mathcal{H}_{t^{\prime},X}\cup\mathcal{H}^{\prime}$
with the weight function $h_{t,X}$.

#### Correctness.

We show that the pair
$(\mathcal{H}_{t^{\prime},X}\cup\mathcal{H}^{\prime},h_{t,X})$ satisfies the
correctness invariant. Then the claim for $(\mathcal{H}_{t,X},h_{t,X})$ will
follow from Lemma 4.38.

We check condition (1). First consider $H\in\mathcal{H}_{t^{\prime},X}$
satisfying $h_{t,X}(H)=h_{t^{\prime},X}(H)$. By the inductive assumption there
is a set $A\subseteq U_{t^{\prime}}\subset U_{t}$ so that
$\texttt{Condense}(G[A\cup X],X)=H$, $G[A\cup X]$ is chordal, and
$h_{t,X}(H)=w(A)$, as intended.

Now consider $H\in\mathcal{H}^{\prime}$ for which there exists
$H^{\prime}\in\mathcal{H}_{t^{\prime},X^{+}}$ so that
$H=\texttt{Condense}(H^{\prime},X)$ and
$h_{t,X}(H)=h_{t^{\prime},X^{+}}(H^{\prime})+w(v)$. We know that there exists
a set $A\subseteq U_{t^{\prime}}=U_{t}\setminus v$ so that
$\texttt{Condense}(G[A\cup X^{+}],X^{+})=H^{\prime}$, $G[A\cup X^{+}]$ is
chordal, and $h_{t^{\prime},X^{+}}(H^{\prime})=w(A)$. The set
$A^{+}=A\cup\\{v\\}\subseteq U_{t}$ satisfies $h_{t,X}(H)=w(A^{+})$ and
$G[A^{+}\cup X]=G[A\cup X^{+}]$ is chordal. From Lemma 4.42 we obtain that
$\texttt{Condense}(G[A^{+}\cup X],X)=\texttt{Condense}(H^{\prime},X)=H$.

We move on to condition (2). Let $(A,B)\subseteq(U_{t},V(G)\setminus V_{t})$
be that $G[A\cup X\cup B]$ is chordal. First consider the case $v\not\in A$.
Then $(A,B)\subseteq(U_{t^{\prime}},V(G)\setminus V_{t^{\prime}})$ and there
exists $H\in\mathcal{H}_{t^{\prime},X}$ so that $(H,X)\oplus(G[B\cup X],X)$ is
chordal and $h_{t^{\prime},X}(H)\geq w(A)$. By construction $h_{t,X}(H)\geq
h_{t^{\prime},X}(H)$.

Now suppose that $v\in A$ and let $A^{-}=A\setminus v$. We have
$(A^{-},B)\subseteq(U_{t^{\prime}},V(G)\setminus V_{t^{\prime}})$ and so there
exists $H^{\prime}\in\mathcal{H}_{t^{\prime},X^{+}}$ so that
$(H^{\prime},X^{+})\oplus(G[B\cup X^{+}],X^{+})$ is chordal and
$h_{t^{\prime},X^{+}}(H^{\prime})\geq w(A^{-})=w(A)-w(v)$. Let
$H=\texttt{Condense}(H^{\prime},X)\in\mathcal{H}^{\prime}$. Since
$N_{G}(v)\cap B=\emptyset$, we deduce that $(H^{\prime},X^{+})\oplus(G[B\cup
X^{+}],X^{+})=(H^{\prime},X)\oplus(G[B\cup X],X)$. The graph
$(H,X)\oplus(G[B\cup X],X)$ can be obtained from the one above by a series
edge contractions and possibly a vertex removal so it is chordal as well.
Finally, $h_{t,X}(H)\geq h_{t^{\prime},X^{+}}(H^{\prime})+w(v)\geq w(A)$.

#### Running time.

Consider a non-empty $X\subseteq\chi(t)$. By Section 4.1 each graph
$H\in\mathcal{H}_{t^{\prime},X}\cup\mathcal{H}^{\prime}$ has at most $2|X|$
vertices and is processed in time $k^{\mathcal{O}(1)}$. By the assumption
$|\mathcal{H}_{t^{\prime},X}|\leq 2^{|X|}$ and
$|\mathcal{H}_{t^{\prime},X^{+}}|\leq 2^{|X|+1}$ so the input to Lemma 4.34
has size less than $2^{|X|+2}$. The computation of the max-representative
family $\mathcal{H}_{t,X}$ takes time
$\mathcal{O}(2^{\omega\cdot|X|}\cdot|X|^{\omega})$. This family have size at
most $2^{|X|-1}$ so it satisfies the size invariant. The sum of the
exponential terms in the total running time equals
$\sum_{X\subseteq\chi(t)}2^{\omega\cdot|X|}=(2^{\omega}+1)^{|X|}$.

######  Lemma 4.46 (Join node).

Let $(\mathbb{T},\chi)$ be a nice tree decomposition of $G$ of width $k$ and
$t\in V(\mathbb{T})$ be a join node with a children $t_{1},t_{2}$. Suppose
that the states for $t_{1},t_{2}$ satisfying the correctness and size
invariants are given. Then we can compute the state for $t$ which satisfies
the correctness and size invariants in time
$\mathcal{O}\left((2^{\omega-1}\cdot 3+1)^{k}\cdot k^{\omega}\right)$.

######  Proof 4.47.

We have $\chi(t)=\chi(t_{1})=\chi(t_{2})$ and $U_{t}=U_{t_{1}}\cup U_{t_{2}}$
where the union is disjoint.

Consider $X\subseteq\chi(t)$. Let
$\mathcal{H}^{\prime}=\\{(H_{1},X)\oplus(H_{2},X)\mid
H_{1}\in\mathcal{H}_{t_{1},X},H_{1}\in\mathcal{H}_{t_{1},X}\\}\cap\texttt{chordal}$.
For each $H\in\mathcal{H}^{\prime}$ we define its weight $h_{t,X}(H)$ as
$\max\left(w_{t_{1},X}(H_{1})+w_{t_{2},X}(H_{2})\right)$ over
$\\{(H_{1},X)\oplus(H_{2},X)=H\mid
H_{1}\in\mathcal{H}_{t_{1},X},H_{1}\in\mathcal{H}_{t_{1},X}\\}$. We compute
$\mathcal{H}_{t,X}$ with Lemma 4.36 as the max-representative family for
$\mathcal{H}^{\prime}$ with respect to the weight function $h_{t,X}$.

#### Correctness.

We show the correctness invariant for the pair
$(\mathcal{H}^{\prime},h_{t,X})$. Then the claim will follow from Lemma 4.38.
Let us fix $X\subseteq\chi(t)$.

We check condition (1). Let $H\in\mathcal{H}^{\prime}$ and
$H_{1}\in\mathcal{H}_{t_{1},X},H_{2}\in\mathcal{H}_{t_{2},X}$ be such that
$H=(H_{1},X)\oplus(H_{2},X)$ and
$h_{t,X}(H)=w_{t_{1},X}(H_{1})+w_{t_{2},X}(H_{2})$. By the assumption, there
exist sets $A_{1}\subseteq U_{t_{1}},A_{2}\subseteq U_{t_{2}}$ so that for
$i\in\\{1,2\\}$ it holds that $\texttt{Condense}(G[A_{i}\cup X],X)=H_{i}$,
$G[A_{i}\cup X]$ is chordal, and $w_{t_{i},X}(H_{i})=w(A_{i})$. Observe that
there are no edges between $A_{1},A_{2}$ so $G[A_{1}\cup A_{2}\cup
X]=(G[A_{1}\cup X],X)\oplus(G[A_{2}\cup X],X)$. By Section 4 we have
$\texttt{Condense}(G[A_{1}\cup A_{2}\cup X],X)=\texttt{Condense}(G[A_{1}\cup
X],X)\oplus\texttt{Condense}(G[A_{2}\cup X],X)=(H_{1},X)\oplus(H_{2},X)=H$.
Since $H$ is chordal by the construction, Lemma 4.11 implies that $G[A_{1}\cup
A_{2}\cup X]$ is chordal. It remains to check that $w(A_{1}\cup
A_{2})=w(A_{1})+w(A_{2})=h_{t,X}(H)$.

Condition (2). Let $(A,B)\subseteq(U_{t},V(G)\setminus V_{t})$ be that
$G[A\cup X\cup B]$ is chordal, and $A_{1}=A\cap U_{t_{1}},A_{2}=A\cap
U_{t_{2}}$. Note that $B\cup A_{2}\subseteq V(G)\setminus V_{t_{1}}$ and there
are no edges between $U_{t_{1}}$ and $U_{t_{2}}$. By the assumption, there
exists $H_{1}\in\mathcal{H}_{t_{1},X}$ so that $(H_{1},X)\oplus(G[B\cup
A_{2}\cup X)$ is chordal and $h_{t_{1},X}(H_{1})\geq w(A_{1})$. From condition
(1) we obtain that there exists $\widehat{A}_{1}\subseteq U_{t_{1}}$ so that
$\texttt{Condense}(G[\widehat{A}_{1}\cup X],X)=H_{1}$, $G[\widehat{A}_{1}\cup
X]$ is chordal, and $h_{t_{1},X}(H_{1})=w(\widehat{A}_{1})$. It follows from
Lemma 4.9 that $G[\widehat{A}_{1}\cup A_{2}\cup X\cup B]$ is chordal. Next, we
consider $(A_{2},B\cup\widehat{A}_{1})\subseteq(U_{t_{2}},V(G)\setminus
V_{t_{2}})$. There exists $H_{2}\in\mathcal{H}_{t_{2},X}$ so that
$(H_{2},X)\oplus(G[B\cup\widehat{A}_{1}\cup X),X)$ is chordal and
$h_{t_{2},X}(H_{2})\geq w(A_{2})$. Again from condition (1) we obtain
$\widehat{A}_{2}\subseteq U_{t_{2}}$ so that
$\texttt{Condense}(G[\widehat{A}_{2}\cup X],X)=H_{2}$, $G[\widehat{A}_{2}\cup
X]$ is chordal, and $h_{t_{2},X}(H_{2})=w(\widehat{A}_{2})$. As before, the
graph $G[\widehat{A}_{1}\cup\widehat{A}_{2}\cup X\cup B]$ is chordal. By
Section 4 we have that $H=(H_{1},X)\oplus(H_{2},X)$ equals
$\texttt{Condense}(G[\widehat{A}_{1}\cup\widehat{A}_{2}\cup X],X)$. Then
$(H,X)\oplus(G[B\cup X],X)$ is chordal which in particular means that $H$ is
chordal and belongs to $\mathcal{H}^{\prime}$. Finally, we check that
$h_{t,X}(H)\geq h_{t_{1},X}(H_{1})+h_{t_{2},X}(H_{2})\geq
w(A_{1})+w(A_{2})=w(A)$.

#### Running time.

Consider a non-empty $X\subseteq\chi(t)$. By Section 4.1 each graph
$H\in\mathcal{H}^{\prime}$ has at most $2|X|$ vertices. By the assumption
$|\mathcal{H}_{t_{1},X}|,|\mathcal{H}_{t_{2},X}|\leq 2^{|X|}$ so we can use
Lemma 4.36 to compute the max-representative family $\mathcal{H}_{t,X}$ in
time $\mathcal{O}\left((2^{\omega-1}\cdot 3)^{|X|}\cdot|X|^{\omega}\right)$.
This family have size at most $2^{|X|-1}$ so it satisfies the size invariant.
The sum of the exponential terms in the total running time equals
$\sum_{X\subseteq\chi(t)}(2^{\omega-1}\cdot 3)^{|X|}=(2^{\omega-1}\cdot
3+1)^{|X|}$.

See 1.1

######  Proof 4.48.

Let $(\mathbb{T},\chi)$ be a tree decomposition of $G$ of width $k$. We can
assume that this is a nice tree decomposition and
$|V(\mathbb{T})|=\mathcal{O}(nk)$. We fill the states for $t\in V(\mathbb{T})$
in a standard bottom-up fashion, while maintaining the correctness and size
invariants. When $t$ is a base node, we have $\chi(t)=V_{t}=\emptyset$ and it
suffices to consider $X=\emptyset$. The family $\mathcal{H}_{t,\emptyset}$
then contains only an empty graph with weight zero. This satisfies both
invariants trivially. We proceed the remaining types of nodes using Lemmas
4.40, 4.44, and 4.46. The bottleneck for the running time comes from
processing a join node.

After filling the state of the root node $r$, we read the value of
$h_{r,\emptyset}(\bot)$, where $\bot$ denotes the empty graph. We claim that
this value equals the highest weight of a vertex set in $G$ inducing a chordal
graph. We have $\chi(r)=\emptyset$, $V_{t}=U_{t}=V(G)$. The family
$\mathcal{H}_{r,\emptyset}$ can contain only the empty graph. Let $A\subseteq
V(G)$ be a maximal-weight set inducing a chordal graph. From the correctness
condition (2) we obtain that there exists $H\in\mathcal{H}_{r,\emptyset}$
(clearly $H=\bot$) so that $h_{r,\emptyset}(H)\geq w(A)$. From the correctness
condition (1) for $H=\bot$ we get that there exists $\widehat{A}\subseteq
V(G)$ so that $G[\widehat{A}\cup\emptyset]$ is chordal and
$h_{r,\emptyset}(\bot)=w(\widehat{A})$. This implies that
$h_{r,\emptyset}(\bot)=w(A)$.

##  5 Interval Deletion

We switch our attention to Interval Vertex Deletion and show that in this case
it is unlikely to achieve any speed-up over the existing
$2^{\mathcal{O}(\mathrm{\textbf{tw}}\log\mathrm{\textbf{tw}})}\cdot n$-time
algorithm. We prove Theorem 1.2 via a parameterized reduction from $k\times k$
Permutation Clique, which is defined as follows.

$k\times k$ Permutation Clique Input: Graph $G$ over the vertex set
$[k]\times[k]$. Question: Is there a permutation $\pi\colon[k]\to[k]$ so that
$(1,\pi(1)),(2,\pi(2)),\dots,(k,\pi(k))$ forms a clique in $G$?

#### Permutation gadget.

We will encode a permutation $\pi\colon[k]\to[k]$ as a family of sets
$N_{1},N_{2},\dots,N_{k}$ so that $N_{i}=\pi([i])$ (i.e., $N_{i}$ is the set
of $i$ numbers appearing first in $\pi$). First, we need a gadget to verify
that such a family represents some permutation.

######  Definition 5.1.

For an integer $k$, let $Y_{k}$ be a graph on a vertex set
$\\{y_{1},y_{2},\dots,y_{k+2}\\}$ so that $\\{y_{1},y_{2},\dots,y_{k+1}\\}$
induces a clique and $y_{k+2}$ is adjacent only to $y_{k+1}$.

We need a simple observation that every linearly ordered family of sets can be
represented by some permutation.

######  Lemma 5.2.

Let $N_{1},\dots,N_{\ell}\subseteq[k]$. Suppose that for each $i,j\in[\ell]$
it holds that $N_{i}\subseteq N_{j}$ or $N_{j}\subseteq N_{i}$. Then there
exists a permutation $\pi\colon[k]\to[k]$ so that for each $i\in[\ell]$ it
holds that $N_{i}=\pi([n_{i}])$ where $n_{i}=|N_{i}|$.

######  Proof 5.3.

Proof by induction on $k$. For $k=1$ the claim clearly holds so consider
$k>1$. If a set $N_{i}$ is empty then $N_{i}=\pi(\emptyset)$ for any
permutation, so we can assume that all the sets are non-empty. The family
$(N_{i})_{i\in[\ell]}$ is linearly ordered so the after reordering the indices
we can assume that $N_{1}\subseteq N_{2}\subseteq\dots\subseteq N_{\ell}$. Let
$e$ be an arbitrary element from $N_{1}$ and
$\tau\colon[k]\setminus\\{e\\}\to[k-1]$ be an arbitrary bijection. We define
$N^{\prime}_{i}=\tau(N_{i}\setminus\\{e\\})$. Then $N^{\prime}_{1}\subseteq
N^{\prime}_{2}\subseteq\dots\subseteq N^{\prime}_{\ell}$. By the inductive
assumption, there exists a permutation $\pi^{\prime}\colon[k-1]\to[k-1]$ such
that $N^{\prime}_{i}=\pi^{\prime}([n_{i}-1])$. We define $\pi(1)=e$ and for
$i>1$ as follows: $\pi(i)=\tau^{-1}(\pi^{\prime}(i-1))$. Then
$N_{i}=\\{e\\}\cup\tau^{-1}(N^{\prime}_{i})=\\{\pi(1)\\}\cup\tau^{-1}(\pi^{\prime}([n_{i}-1]))=\\{\pi(1)\\}\cup\pi([2,n_{i}])=\pi([n_{i}])$.

Figure 2: Illustration for Lemma 5.4. The intervals for vertices of $Y_{4}$
are blank, ordered from bottom to top. They encode permutation $(2,4,3,1)$.
The black intervals represent vertices $x_{1},x_{2},x_{3},x_{4},x_{5}$ with
neighborhoods encoding sets $\\{2\\}$, $\\{2,4\\}$ (twice), $\\{2,4,3\\}$, and
$\\{2,4,3,1\\}$.

We shall enforce a linear order on $N_{1},\dots,N_{k}$ by demanding that a
particular supergraph of $Y_{k}$ is interval. The corresponding interval model
is depicted on Figure 2.

######  Lemma 5.4 ($\star$).

Let $N_{1},\dots,N_{\ell}\subseteq[k]$. Consider a graph $G$ obtained from
$Y_{k}$ by inserting an independent set of vertices $x_{1},\dots,x_{\ell}$ so
that $N_{G}(x_{i})=\\{y_{j}\mid j\in N_{i}\\}$. Then $G$ is interval if and
only if there exists a permutation $\pi\colon[k]\to[k]$ so that for each
$i\in\ell$ it holds that $N_{i}=\pi([n_{i}])$ where $n_{i}=|N_{i}|$.

######  Proof 5.5.

Suppose there is no such permutation. By Lemma 5.2 there are $i,j\in[\ell]$ so
that neither $N_{i}\subseteq N_{j}$ nor $N_{j}\subseteq N_{i}$. Fix $p_{i}\in
N_{G}(x_{i})\setminus N_{G}(x_{j})$, and $p_{j}\in N_{G}(x_{j})\setminus
N_{G}(x_{i})$. We claim that $(x_{i},x_{j},y_{k+2})$ forms an AT in $G$.
Indeed, $(x_{i},p_{i},y_{k+1},y_{k+2})$ avoids $N_{G}[x_{j}]$,
$(x_{j},p_{j},y_{k+1},y_{k+2})$ avoids $N_{G}[x_{i}]$, and
$(x_{i},p_{i},p_{j},x_{j})$ avoids $N_{G}[y_{k+2}]=\\{y_{k+1},y_{k+2}\\}$.
Since $G$ contains an AT, it is not interval.

Now suppose that a permutation $\pi$ satisfying the conditions of the lemma
exists. We construct an interval model of $G$ (see Figure 2). Let
$\varepsilon=\frac{1}{3\ell}$. A vertex $y_{i}\in V(Y_{k})$ where $i\in[k]$ is
assigned the interval $[\pi^{-1}(i),k+2]$. Vertex $y_{k+1}$ is assigned the
interval $[k+1,k+4]$ and vertex $y_{k+2}$ is assigned to $[k+3,k+4]$. For
$i\in[\ell]$ we consider the vertex $x_{i}$ with neighborhood specified by
$N_{i}=\pi([n_{i}])$. Its interval is given as
$[n_{i}+\frac{i-1}{\ell}+\varepsilon,n_{i}+\frac{i-1}{\ell}+2\varepsilon]$.
Note that the intervals of distinct $x_{i},x_{j}$ are disjoint, as intended.
The interval of $x_{i}$ is contained in $(n_{i},n_{i}+1)$ so it intersects an
interval of the form $[\pi^{-1}(j),k+2]$ exactly when $\pi^{-1}(j)\leq n_{i}$.
The latter inequality is equivalent to $j\in\pi([n_{i}])=N_{i}$. The lemma
follows.

Figure 3: Top: the choice gadget $H_{5}$ with the subgraph $Q_{1}$ highlighted
in green. The copies of $P$ are sketched symbolically with dashed lines and
the squares represent vertices $g^{\alpha}_{i}$. The red disks and squares
represent a solution constructed in Lemma 5.9(2). This solution ‘chooses’
$i=2$, leaves untouched the four vertices $g^{\alpha}_{2}$, and removes
$h^{\alpha}_{2}$ as well as $g^{\alpha}_{i}$ for $i\neq 2$. Bottom left: the
graph $P$ and vertices named $h,g$. Two vertex-disjoint non-interval subgraphs
of $P$ have green edges. Bottom right: a closer look at the first two blocks
of $H_{5}$ with two copies of $P$ drawn in detail. The subgraph highlighted in
green witnesses that if a minimum-size solution removes $g^{\alpha}_{i}$ for
at least one $\alpha\in[4]$ then it must also remove $v^{2}_{i}$, what is
exploited in Lemma 5.9(3).

#### Choice gadget.

We need to verify that $(i,\pi(i))(j,\pi(j))\in E(G)$ for each $1\leq i<j\leq
k$. As $\pi(i)$ is the only element in $N_{i}\setminus N_{i-1}$, the
information whether $(i,\pi(i)),(j,\pi(j))\in E(G)$ can be extracted from the
tuple $(N_{i-1},N_{i},N_{j-1},N_{j})$. We construct a gadget that enforces a
solution to select one such valid tuple.

We use a following convention to describe the gadgets. When $P$ is a graph
with a distinguished vertex named $v$ and a graph $H$ is constructed using
explicit vertex-disjoint copies of the graph $P$, referred to as
$P_{1},P_{2},\dots,P_{\ell}$, we refer to the copy of $v$ within the subgraph
$P_{i}$ as $P_{i}[v]$. We construct the choice gadget as a path-like structure
consisting of blocks, each equipped with four special vertices. These are the
only vertices that later get connected to the permutation gadget. On the
intuitive level, a solution should choose one block, leave its special
vertices untouched, and remove the remaining special vertices. See Figure 3
for an illustration.

######  Definition 5.6.

The graph $P$ is obtained from a path $(u_{1},u_{2},\dots,u_{9})$ by appending
to $u_{2}$ two subdivided edges, one subdivided edge to $u_{7}$, and inserting
edge $u_{4}u_{8}$.

The choice gadget of order $s$ is a graph constructed as follows. We begin
with a vertex set
$\bigcup_{i=1}^{s}\\{v^{1}_{i},v^{2}_{i},v^{3}_{i}\\}\cup\\{v_{\text{left}},v_{\text{right}}\\}$.
For each pair $(x,y)$ of the form
$(v^{1}_{i},v^{2}_{i}),(v^{2}_{i},v^{3}_{i}),(v^{3}_{i},v^{1}_{i}),(v^{3}_{i},v^{1}_{i+1})$
as well as for $(v_{\text{left}},v^{1}_{1})$, $(v^{3}_{s},v_{\text{right}})$
we create two subdivided edges between $x$ and $y$. We refer to the subgraph
given by the two subdivided edges between $x,y$ as $\langle x,y\rangle$. We
refer to the union of $\langle v^{1}_{i},v^{2}_{i}\rangle,\langle
v^{2}_{i},v^{3}_{i}\rangle,\langle v^{3}_{i},v^{1}_{i}\rangle$ as $Q_{i}$.

Next, for each $i\in[s]$ we create four copies of the graph $P$, denoted
$P^{1}_{i},P^{2}_{i},P^{3}_{i},P^{4}_{i}$. We insert edges between $v^{2}_{i}$
and $P^{1}_{i}[u_{1}],P^{2}_{i}[u_{1}],P^{3}_{i}[u_{1}],P^{4}_{i}[u_{1}]$. We
refer to vertices $P^{\alpha}_{i}[u_{8}]$, $P^{\alpha}_{i}[u_{9}]$,
$\alpha\in[4]$, as respectively $h^{\alpha}_{i}$, $g^{\alpha}_{i}$.

The choice gadget is designed to enforce a special structure of minimum-size
interval deletion sets.

######  Lemma 5.7.

Let $H_{s}$ be the choice gadget of order $s$ and $X$ be an interval deletion
set in $H_{s}$. Then for each $i\in[s]$ and $\alpha\in[4]$ it holds that
$|V(P^{\alpha}_{i})\cap X|\geq 2$ and $|V(Q_{i})\cap X|\geq 2$.

######  Proof 5.8.

The graph $P$ contains two vertex-disjoint non-interval subgraphs which is
witnessed by ATs: one induced by $u_{2},u_{3},u_{4}$ and the two subdivided
edges appended to $u_{2}$, the second one induced by
$u_{5},u_{6},u_{7},u_{8},u_{9}$ and the subdivided edge appended to $u_{7}$
(see Figure 3). Therefore any copy of $P$ in $H_{s}$ must contain at least two
vertices from $X$. Next, observe that no single vertex intersects all three
holes in $Q_{i}$. Therefore any interval deletion set must contain at least
two vertices from $V(Q_{i})$.

We prove several properties of the choice gadget which are analogous to the
properties of the gadget used by Pilipczuk in the lower bound for Planar
Vertex Deletion [60]. However, in that construction every block has only one
special vertex with edges leaving the gadget, while in our case there are four
special vertices. We also need to ensure that when the special vertices in
some block are not being removed then a solution can remove their neighbors in
the gadget. (Inserting a planar graph attached to a single vertex of $G$ does
not affect planarity of $G$ but the analogous property does not hold for the
class of interval graphs.) The special structure of the graph $P$ allows us to
resolve these two issues.

######  Lemma 5.9 ($\star$).

Let $H_{s}$ be the choice gadget of order $s$.

  1. 1.

The minimal size of an interval deletion set in $H_{s}$ is $10s$.

  2. 2.

For every $i\in[s]$ there exists a minimum-size interval deletion set $X$ in
$H_{s}$ such that $\\{h^{1}_{i},h^{2}_{i},h^{3}_{i},h^{4}_{i}\\}\subseteq X$
and $\\{g^{1}_{j},g^{2}_{j},g^{3}_{j},g^{4}_{j}\\}\subseteq X$ for each $j\neq
i$.

  3. 3.

For every minimum-size interval deletion set $X$ in $H_{s}$ there is $i\in[s]$
such that
$\\{g^{1}_{i},g^{2}_{i},g^{3}_{i},g^{4}_{i}\\}\cap X=\emptyset$.

  4. 4.

If $s\leq 2^{k}$ then
$\mathrm{\textbf{td}}(H_{s})\leq\mathrm{\textbf{td}}(H_{1})+k$, where
$\mathrm{\textbf{td}}(G)$ stands for the treedepth of $G$.

######  Proof 5.10.

Part (1). All the $4s$ copies of $P$, as well as subgraphs
$Q_{1},\dots,Q_{s}$, are vertex-disjoint in $H_{s}$. The lower bound follows
from Lemma 5.7 whereas the upper bound is a consequence of the next part of
the lemma.

Part (2). The construction is depicted on Figure 3. The set $X$ comprises:

  * •

$v^{1}_{j},v^{2}_{j}$ for $j<i$,

  * •

$v^{1}_{i},v^{3}_{i}$,

  * •

$v^{2}_{j},v^{3}_{j}$ for $j>i$,

  * •

$P^{\alpha}_{j}[u_{4}],P^{\alpha}_{j}[u_{9}]$ for $\alpha\in[4]$, $j\neq i$,

  * •

$P^{\alpha}_{i}[u_{2}],P^{\alpha}_{i}[u_{8}]$ for $\alpha\in[4]$.

One can easily verify that $|X|=10s$ and each connected component of $H_{s}-X$
is either a path or a star with at most two subdivided edges. These graphs are
interval.

Part (3). Suppose that there exists an interval deletion set $X$ of size $10s$
such that for each $i\in[s]$ there is $\alpha\in[4]$ so that
$g^{\alpha}_{i}\in X$. From Lemma 5.7 we know that $|X\cap
V(P^{\alpha}_{i})|\geq 2$. From a counting argument we infer that in fact it
must be $|X\cap V(P^{\alpha}_{i})|=2$. The vertices
$P^{\alpha}_{i}[u_{4}],P^{\alpha}_{i}[u_{5}],P^{\alpha}_{i}[u_{6}],P^{\alpha}_{i}[u_{7}],P^{\alpha}_{i}[u_{8}]$
induce $C_{5}$ so one of them must belong to $X$. Together with
$g^{\alpha}_{i}=P^{\alpha}_{i}[u_{9}]$ these are the two vertices of $X\cap
V(P^{\alpha}_{i})$.

The vertices $v^{2}_{i},P^{\alpha}_{i}[u_{1}],P^{\alpha}_{i}[u_{2}]$ and the
two subdivided edges appended to $P^{\alpha}_{i}[u_{2}]$ induce a graph with
an AT (see Figure 3). As no more vertices from $V(P^{\alpha}_{i})$ belong to
$X$ apart from the two described above, it must be $v^{2}_{i}\in X$.

This argument works for every $i\in[s]$. We count the already allocated
vertices:

$\left|\bigcup_{i\in[s],\alpha\in[4]}(X\cap
V(P_{i}^{\alpha}))\,\right|+|\\{v^{2}_{i}\mid i\in[s]\\}|=8s+s=9s.$

Since $|X|=10s$, there are exactly $s$ vertices remaining in $X$. But there
are $s+1$ vertex-disjoint holes yet to be hit: $\langle
v_{\text{left}},v^{1}_{1}\rangle,\langle v^{3}_{1},v^{1}_{2}\rangle,\langle
v^{3}_{2},v^{1}_{3}\rangle,\dots,\langle v^{3}_{s},v_{\text{right}}\rangle$.
This means that $X$ cannot be an interval deletion set in $H_{s}$.

Part (4). Clearly
$\mathrm{\textbf{td}}(H_{s})\leq\mathrm{\textbf{td}}(H_{s+1})$ so it suffices
to prove the claim for $s=2^{k}$ by induction on $k$. For $k=0$ we get
equality. For $k>0$ there exists a vertex $v\in V(H_{2^{k}})$ so that
$H_{2^{k}}-v$ has two connected components, each being a subgraph of
$H_{2^{k-1}}$. By the definition of treedepth we get
$\mathrm{\textbf{td}}(H_{2^{k}})\leq\mathrm{\textbf{td}}(H_{2^{k-1}})+1$.

Lokshtanov et al. [55] proved that $k\times k$ Permutation Clique cannot be
solved in time $2^{o(k\log k)}$ assuming ETH. According to the reduction
below, this also rules out running time of the form
$2^{o(\mathrm{\textbf{td}}\log\mathrm{\textbf{td}})}\cdot n^{\mathcal{O}(1)}$
for Interval Vertex Deletion, where td is the treedepth of the input graph. As
$\mathrm{\textbf{tw}}(G)\leq\mathrm{\textbf{td}}(G)$, this entails the same
hardness for treewidth, what proves Theorem 1.2.

######  Proposition 5.11.

There is an algorithm that, given an instance $(G,k)$ of $k\times k$
Permutation Clique, runs in time $2^{\mathcal{O}(k)}$ and returns an
equivalent unweighted instance $(H,p)$ of Interval Vertex Deletion such that
$|V(H)|=2^{\mathcal{O}(k)}$ and $\mathrm{\textbf{td}}(H)=\mathcal{O}(k)$.

######  Proof 5.12.

For $1\leq i<j\leq k$ and $x\neq y\in[k]$ let $\mathcal{S}_{i,x,j,y}$ be the
family of tuples $(S_{1},S_{2},S_{3},S_{4})$ of subsets of $[k]$ satisfying:

  * •

$S_{1}\subset S_{2}\subseteq S_{3}\subset S_{4}$,

  * •

$|S_{1}|=i-1$,

  * •

$S_{2}\setminus S_{1}=\\{x\\}$,

  * •

$|S_{3}|=j-1$,

  * •

$S_{4}\setminus S_{3}=\\{y\\}$.

Furthermore, for $1\leq i<j\leq k$, let $\mathcal{S}_{i,j}$ be the union of
$\mathcal{S}_{i,x,j,y}$ over all pairs $x\neq y\in[k]$ such that
$(i,x)(j,y)\in E(G)$. Let $s_{i,j}=|\mathcal{S}_{i,j}|$ and
$\rho_{i,j}\colon[s_{i,j}]\to\mathcal{S}_{i,j}$ be an arbitrary bijection.
Clearly $s_{i,j}\leq 4^{k}k^{2}$.

The graph $H$ consists of a permutation gadget $Y_{k}$ and, for each $1\leq
i<j\leq k$, a choice gadget $C_{i,j}$ of order $s_{i,j}$. For $S\subseteq[k]$
we use shorthand $Y_{k}[S]=\\{y_{i}\mid i\in S\\}$. For $\ell\in[s_{i,j}]$ and
$(S_{1},S_{2},S_{3},S_{4})=\rho_{i,j}(\ell)$ the vertices
$C_{i,j}[g^{1}_{\ell}]$, $C_{i,j}[g^{2}_{\ell}]$, $C_{i,j}[g^{3}_{\ell}]$,
$C_{i,j}[g^{4}_{\ell}]$ get connected to vertex sets
$Y_{k}[S_{1}],Y_{k}[S_{2}],Y_{k}[S_{3}],Y_{k}[S_{4}]$, respectively. This
finishes the construction of $H$. The number of vertices in $H$ is clearly
$2^{\mathcal{O}(k)}$ and the construction can be performed in time polynomial
in the size of $H$. We set $p=10\cdot\sum_{1\leq i<j\leq k}s_{i,j}$.

######  Claim 1.

If $(G,k)$ admits a solution, then $H$ has an interval deletion set of size
$p$.

######  Proof 5.13.

Let $\pi\colon[k]\to[k]$ be a permutation encoding a clique in $G$. By the
construction, for each $1\leq i<j\leq k$ we have
$\left(\pi([i-1]),\pi([i]),\pi([j-1]),\pi([j]\right)\in\mathcal{S}_{i,j}$. Let
$\ell\in[s_{i,j}]$ be the index mapped to this tuple by $\rho_{i,j}$. By Lemma
5.9(2) the choice gadget $C_{i,j}$ has an interval deletion set
$X_{i,j}\subseteq V(C_{i,j})$ of size $10s_{i,j}$ such that
$\\{C_{i,j}[h^{1}_{\ell}],C_{i,j}[h^{2}_{\ell}],C_{i,j}[h^{3}_{\ell}],C_{i,j}[h^{4}_{\ell}]\\}\subseteq
X_{i,j}$ and
$\\{C_{i,j}[g^{1}_{r}],C_{i,j}[g^{2}_{r}],C_{i,j}[g^{3}_{r}],C_{i,j}[g^{4}_{r}]\\}\subseteq
X_{i,j}$ for each $r\neq\ell$. In other words, $X_{i,j}$ contains all vertices
in $C_{i,j}$ which are adjacent to $Y_{k}$ except for the $C_{i,j}$-copies of
$g^{1}_{\ell},g^{2}_{\ell},g^{3}_{\ell},g^{4}_{\ell}$ and $X_{i,j}$ also
contains the neighbors of
$C_{i,j}[g^{1}_{\ell}],C_{i,j}[g^{2}_{\ell}],C_{i,j}[g^{3}_{\ell}],C_{i,j}[g^{4}_{\ell}]$
in $C_{i,j}$.

We set $X=\bigcup_{1\leq i<j\leq k}X_{i,j}$. Then the only connected component
of $H-X$ which is not a connected component of any $C_{i,j}-X_{i,j}$ is given
by $Y_{k}$ together with an independent set of the vertices described above.
The neighborhood of each such vertex in $Y_{k}$ is of the form
$Y_{k}[\pi([k^{\prime}])]$ for some $0\leq k^{\prime}\leq k$. By Lemma 5.4
this component is an interval graph. This shows that $X$ is indeed an interval
deletion set.

######  Claim 2.

If $H$ has an interval deletion set of size at most $p$, then $(G,k)$ admits a
solution.

######  Proof 5.14.

Let $X$ be an interval deletion set in $H$. By Lemma 5.9(1) a minimum-size
interval deletion set in $C_{i,j}$ has size $10s_{i,j}$. As the choice gadgets
are vertex-disjoint subgraphs of $H$, the set $X$ must contain exactly
$10s_{i,j}$ vertices from $V(C_{i,j})$. This also implies that $V(Y_{k})\cap
X=\emptyset$.

Let $X_{i,j}=V(C_{i,j})\cap X$. By Lemma 5.9(3) there exists
$\ell\in[s_{i,j}]$ such that
$\big{\\{}C_{i,j}[g^{1}_{\ell}],C_{i,j}[g^{2}_{\ell}]$,
$C_{i,j}[g^{3}_{\ell}],C_{i,j}[g^{4}_{\ell}]\,\big{\\}}\cap
X_{i,j}=\emptyset$. Therefore for each pair $(i,j)$ there is a tuple
$(S^{1}_{i,j},S^{2}_{i,j},S^{3}_{i,j},S^{4}_{i,j})\in\mathcal{S}_{i,j}$ so
that vertices from $C_{i,j}$ with neighborhoods
$Y_{k}[S^{1}_{i,j}],Y_{k}[S^{2}_{i,j}],Y_{k}[S^{3}_{i,j}],Y_{k}[S^{4}_{i,j}]$
are present in $H-X$. By Lemma 5.4 there exists a single permutation
$\pi\colon[k]\to[k]$ so that each set $S^{\alpha}_{i,j}$ is of the form
$\pi([|S^{\alpha}_{i,j}|])$. By the definition of family $\mathcal{S}_{i,j}$
this implies that $(i,\pi(i))(j,\pi(j))\in E(G)$ for each pair $(i,j)$. Hence
there is a $k$-clique in $G$.

######  Claim 3.

The treedepth of $H$ is $\mathcal{O}(k)$.

######  Proof 5.15.

The treedepth of $H$ is at most $|Y_{k}|=k+2$ plus
$\mathrm{\textbf{td}}(H-Y_{k})$, which equals the maximum of
$\mathrm{\textbf{td}}(C_{i,j})$ over all employed choice gadgets $C_{i,j}$. As
$s_{i,j}\leq 4^{k}k^{2}$, Lemma 5.9(4) implies that
$\mathrm{\textbf{td}}(C_{i,j})\leq 2k+2\log_{2}k+\mathcal{O}(1)$.

This conludes the proof of the proposition.

###  5.1 Upper bound

Saitoh et al. [66] have presented an algorithm for Interval Edge Deletion (and
for several related graphs classes) with running time
$2^{\mathcal{O}(\mathrm{\textbf{tw}}\log\mathrm{\textbf{tw}})}\cdot n$ and
stated that they expect it to also work for the vertex-deletion variant [66,
§6]. We briefly describe their approach and justify that vertex deletion can
indeed be incorporated.

Instead of working with real-line interval models, one can represent an
interval model in an abstract way. For a set $X$ its _interval representation_
is a linear order $\pi$ over the set $LR_{X}=L_{X}\cup
R_{X}\cup\\{\bot,\top\\}$ where $L_{X}=\\{\ell_{x}\mid x\in X\\}$,
$R_{X}=\\{r_{x}\mid x\in X\\}$, such that
$\bot<_{\pi}\ell_{x}<_{\pi}r_{x}<_{\pi}\top$ for each $x\in X$. An interval is
a pair of elements from $LR_{X}$. The interval graph $G_{\pi}$ of an interval
representation $\pi$ over $V$ is defined by adding an edge $uv$ whenever
$(\ell_{u},r_{u})$ and $(\ell_{v},r_{v})$ intersect in $\pi$. It is clear that
a graph $G$ is interval if and only if there exists an interval representation
$\pi$ over $V$ such that $G=G_{\pi}$.

Let $(\mathbb{T},\chi)$ be a rooted tree decomposition of $G$. The state of
$t\in V(\mathbb{T})$ is a set of triples $(\pi,I,c)$ where $\pi$ is an
interval representation over $\chi(t)$ such that $G_{\pi}$ is a subgraph of
$G[\chi(t)]$, $I$ is a set of intervals from $LR_{\chi(t)}$, and
$c\in\mathbb{N}$. For each interval representation $\tau$ over $V_{t}$, for
which $G_{\tau}$ is a subgraph of $G[V_{t}]$ we define its abstraction as a
triple $(\pi,I,c)$ where $\pi$ is a restriction of $\tau$ to $\chi(t)$, for
each connected component $C$ of $G[U_{t}]$ there is an interval
$(\ell_{c},r_{c})\in I$ so that $(\ell_{c},r_{c})$ is a inclusion-wise minimal
interval from $LR_{\chi}(t)$ that contains all the intervals from $C$, and
$c=|E(G[V_{t}])-E(G_{\tau})-E(G[\chi(t)])|$ counts the number of edges from
$G[V_{t}]$ with at most one endpoint in $\chi(t)$ which are not present in
$G_{\tau}$. We write $I\sqsubseteq_{\pi}I^{\prime}$ if every interval from $I$
is contained in some interval from $I^{\prime}$. We say that $(\pi,I,c)$
dominates $(\pi,I^{\prime},c^{\prime})$ if $I\sqsubseteq_{\pi}I^{\prime}$ and
$c\leq c^{\prime}$.

Saitoh et al. show that when $(\pi,I,c)$ dominates
$(\pi,I^{\prime},c^{\prime})$ there is no need to store
$(\pi,I^{\prime},c^{\prime})$ in the state for $t$. To see this, consider an
interval representation $\tau^{\prime}$ over $V(G)$ which corresponds to some
valid solution, so that $(\pi,I^{\prime},c^{\prime})$ is an abstraction of
$\tau^{\prime}$ restricted to $V_{t}$. Since there are no edges between
$U_{t}$ and $V(G)\setminus V_{t}$, for every $v\in V(G)\setminus V_{t}$ and
connected component $C$ of $G[U_{t}]$ the interval of $v$ must be disjoint the
interval spanned by $C$ with respect to $\tau^{\prime}$. Because
$I\sqsubseteq_{\pi}I^{\prime}$, we can modify $\tau^{\prime}$ to obtain a new
interval representation $\tau$ over $V(G)$ which coincides on $U_{t}$ with
some partial solution whose abstraction is $(\pi,I,c)$. As $c\leq c^{\prime}$
the number of edges deleted with respect to $\tau$ does not grow compared to
$\tau^{\prime}$. The last observation is that when $|\chi(t)|=k$ and no triple
stored at $t$ dominates another triple then their number is
$2^{\mathcal{O}(k\log k)}$.

In order to adapt the algorithm for vertex deletion, we can store tuples
$(X,\pi,I,c)$ where $X\subseteq\chi(t)$ is the set of vertices which are not
deleted, $\pi$ is an interval representation over $X$ so that $G_{\pi}=G[X]$,
$I$ is a set of intervals from $LR_{X}$, and $c\in\mathbb{N}$. Now a partial
solution is a triple $(A,X,\tau)$ where $A\subseteq U_{t},X\subseteq\chi(t)$,
and $\tau$ is an interval representation over $A\cup X$ so that
$G_{\tau}=G[A\cup X]$. The abstraction of $(A,X,\tau)$ is $(X,\pi,I,c)$ where
$\pi$ is a restriction of $\tau$ to $X$, for each connected component $C$ of
$G[A]$ there is an interval $(\ell_{c},r_{c})\in I$ so that $(\ell_{c},r_{c})$
is a inclusion-wise minimal interval from $LR_{X}$ that contains all the
intervals from $C$, and $c=|U_{t}|-|A|$ counts the number of vertices deleted
so far. As before, we say that $(X,\pi,I,c)$ dominates
$(X,\pi,I^{\prime},c^{\prime})$ if $I\sqsubseteq_{\pi}I^{\prime}$ and $c\leq
c^{\prime}$. By the same argument as before, we can neglect the tuples which
are dominated and bound the number of tuples stored for a pair $(t,X)$ by
$2^{\mathcal{O}(k\log k)}$. Since there are $2^{k}$ choices for $X$, the
general upper bound follows. It is easy to see that both algorithms can be
also extended to incorporate weights.

##  6 Conclusion and open problems

We have obtained ETH-tight bounds for vertex-deletion problems into the
classes of chordal and interval graphs, under the treewidth parameterization.
The status of the corresponding edge-deletion problems remains unclear (see
[66]). The related problem, Feedback Vertex Set, can be solved using
representative families within the same running time as our algorithm for ChVD
[37]. However, it admits a faster deterministic algorithm based on the
determinant approach [71] and an even faster randomized algorithm based on the
Cut & Count technique [35]. Could ChVD also be amenable to one of those
techniques?

Our algorithm for ChVD is based on a novel connection between chordal graphs
and graphic matroids, which might come in useful in other settings. In
particular, we ask whether this insight can be leveraged to improve the
running time for ChVD parameterized by the solution size $k$, where the
current-best algorithm runs in time $2^{\mathcal{O}(k\log
k)}n^{\mathcal{O}(1)}$ [29]. A direct avenue for a potential improvement would
be to reduce the problem in time $2^{\mathcal{O}(k)}n^{\mathcal{O}(1)}$ to the
case with treewidth $\mathcal{O}(k)$ and then apply Theorem 1.1. Such a
strategy has been employed in the state-of-the-art algorithm for Planar Vertex
Deletion parameterized by the solution size [47].

## References

  * [1] Akanksha Agrawal, Sudeshna Kolay, Daniel Lokshtanov, and Saket Saurabh.  A faster FPT algorithm and a smaller kernel for block graph vertex deletion.  In Evangelos Kranakis, Gonzalo Navarro, and Edgar Chávez, editors, LATIN 2016: Theoretical Informatics - 12th Latin American Symposium, Ensenada, Mexico, April 11-15, 2016, Proceedings, volume 9644 of Lecture Notes in Computer Science, pages 1–13. Springer, 2016.  doi:10.1007/978-3-662-49529-2\\_1.
  * [2] Akanksha Agrawal, Daniel Lokshtanov, Pranabendu Misra, Saket Saurabh, and Meirav Zehavi.  Erdös-Pósa property of obstructions to interval graphs.  In Rolf Niedermeier and Brigitte Vallée, editors, 35th Symposium on Theoretical Aspects of Computer Science, STACS 2018, February 28 to March 3, 2018, Caen, France, volume 96 of LIPIcs, pages 7:1–7:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018.  doi:10.4230/LIPIcs.STACS.2018.7.
  * [3] Akanksha Agrawal, Daniel Lokshtanov, Pranabendu Misra, Saket Saurabh, and Meirav Zehavi.  Feedback vertex set inspired kernel for chordal vertex deletion.  ACM Trans. Algorithms, 15(1):11:1–11:28, 2019.  doi:10.1145/3284356.
  * [4] Akanksha Agrawal, Pranabendu Misra, Saket Saurabh, and Meirav Zehavi.  Interval vertex deletion admits a polynomial kernel.  In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’19, page 1711–1730, USA, 2019. Society for Industrial and Applied Mathematics.  doi:10.1137/1.9781611975482.103.
  * [5] Jungho Ahn, Eduard Eiben, O joung Kwon, and Sang il Oum.  A Polynomial Kernel for 3-Leaf Power Deletion.  In Javier Esparza and Daniel Kráľ, editors, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020), volume 170 of Leibniz International Proceedings in Informatics (LIPIcs), pages 5:1–5:14, Dagstuhl, Germany, 2020. Schloss Dagstuhl–Leibniz-Zentrum für Informatik.  doi:10.4230/LIPIcs.MFCS.2020.5.
  * [6] Jungho Ahn, Eun Jung Kim, and Euiwoong Lee.  Towards constant-factor approximation for chordal/distance-hereditary vertex deletion.  Algorithmica, 84(7):2106–2133, 2022.  doi:10.1007/s00453-022-00963-7.
  * [7] Josh Alman and Virginia Vassilevska Williams.  A refined laser method and faster matrix multiplication.  In Proceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’21, page 522–539, USA, 2021. Society for Industrial and Applied Mathematics.  doi:10.5555/3458064.3458096.
  * [8] Amotz Bar-Noy, Reuven Bar-Yehuda, Ari Freund, Joseph (Seffi) Naor, and Baruch Schieber.  A unified approach to approximating resource allocation and scheduling.  J. ACM, 48(5):1069–1090, sep 2001.  doi:10.1145/502102.502107.
  * [9] Julien Baste, Ignasi Sau, and Dimitrios M. Thilikos.  A complexity dichotomy for hitting connected minors on bounded treewidth graphs: the chair and the banner draw the boundary.  In Shuchi Chawla, editor, Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020, pages 951–970. SIAM, 2020.  doi:10.1137/1.9781611975994.57.
  * [10] Julien Baste, Ignasi Sau, and Dimitrios M. Thilikos.  Hitting minors on bounded treewidth graphs. I. General upper bounds.  SIAM J. Discret. Math., 34(3):1623–1648, 2020.  doi:10.1137/19M1287146.
  * [11] Julien Baste, Ignasi Sau, and Dimitrios M. Thilikos.  Hitting minors on bounded treewidth graphs. II. Single-exponential algorithms.  Theor. Comput. Sci., 814:135–152, 2020.  doi:10.1016/j.tcs.2020.01.026.
  * [12] Julien Baste, Ignasi Sau, and Dimitrios M. Thilikos.  Hitting minors on bounded treewidth graphs. III. Lower bounds.  J. Comput. Syst. Sci., 109:56–77, 2020.  doi:10.1016/j.jcss.2019.11.002.
  * [13] Giuseppe Di Battista, Peter Eades, Roberto Tamassia, and Ioannis G. Tollis.  Graph Drawing: Algorithms for the Visualization of Graphs.  Prentice Hall PTR, USA, 1st edition, 1998.  URL: https://dl.acm.org/doi/10.5555/551884.
  * [14] Seymour Benzer.  On the topology of the genetic fine structure.  Proceedings of the National Academy of Sciences of the United States of America, 45(11):1607–1620, 1959.  URL: http://www.jstor.org/stable/90127.