11institutetext: Indian Institute of Technology Madras, India 22institutetext:
The Institute of Mathematical Sciences, HBNI, Chennai, India 33institutetext:
National Institute of Science, Education and Research, An OCC of Homi Bhabha
National Institute, Bhubaneswar 752050, Odisha, India
33email<EMAIL_ADDRESS><EMAIL_ADDRESS>
# A Polynomial Kernel for Proper Helly Circular-arc Vertex Deletion

Akanksha Agrawal 11 Satyabrata Jana 22 Abhishek Sahu 33

###### Abstract

A proper Helly circular-arc graph is an intersection graph of a set of arcs on
a circle such that none of the arcs properly contains any other arc and every
set of pairwise intersecting arcs has a common intersection. The Proper Helly
Circular-arc Vertex Deletion problem takes as input a graph $G$ and an integer
$k$, and the goal is to check if we can remove at most $k$ vertices from the
graph to obtain a proper Helly circular-arc graph; the parameter is $k$.
Recently, Cao et al. [MFCS 2023] obtained an FPT algorithm for this (and
related) problem. In this work, we obtain a polynomial kernel for the problem.

##  1 Introduction

The development of parameterized complexity is much owes much to the study of
graph modification problems, which have inspired the evolution of many
important tools and techniques. One area of parameterized complexity is data
reduction, also known as kernelization, which focuses on the family of graphs
$\mathcal{F}$ and the $\mathcal{F}$-Modification problem. Given a graph $G$
and an integer $k$, this problem asks whether it is possible to obtain a graph
in $\mathcal{F}$ using at most $k$ modifications in $G$, where the
modifications are limited to vertex deletions, edge deletions, edge additions,
and edge contractions. The problem has been extensively studied, even when
only a few of these operations are allowed.

Here we deal on the parameterization of the $\mathcal{F}$-Vertex Deletion
problem, which is a special case of $\mathcal{F}$-Modification where the
objective is to find the minimum number of vertex deletions required to obtain
a graph in $\mathcal{F}$. This problem encompasses several well-known NP-
complete problems, such as Vertex Cover, Feedback Vertex Set, Odd Cycle
Transversal, Planar Vertex Deletion, Chordal Vertex Deletion, and Interval
Vertex Deletion, which correspond to $\mathcal{F}$ being the family of graphs
that are edgeless, forests, bipartite, planar, chordal and interval,
respectively. Unfortunately, most of these problems are known to be NP-
complete, and therefore have been extensively studied in paradigms such as
parameterized complexity designed to cope with NP-hardness. There have been
many studies on this topic, including those referenced in this paper, but this
list is not exhaustive.

In this article, we focus on the $\mathcal{F}$-Vertex Deletion problem,
specifically when $\mathcal{F}$ refers to the family of proper Helly circular-
arc graphs. We refer to this problem as Proper Helly Circular-arc Vertex
Deletion (PHCAVD) for brevity. A circular-arc graph is a graph whose vertices
can be assigned to arcs on a circle such that there is an edge between two
vertices if and only if their corresponding arcs intersect. If none of the
arcs properly contains one another, the graph is a proper circular-arc graph.
These graphs have been extensively studied, and their structures and
recognition are well understood [9, 13, 17]. These graphs also arise naturally
when considering the clique graphs of a circular-arc graph. However, the lack
of the Helly property, which dictates that every set of intersecting arcs has
a common intersection, contributes to the complicated structures of circular-
arc graphs. A Helly circular-arc graph is a graph that admits a Helly arc
representation. All interval graphs are Helly circular-arc graphs since every
interval representation is Helly. The class of proper Helly circular-arc
graphs lies between proper circular-arc graphs and proper interval graphs. A
graph is a proper Helly circular-arc graph if it has a proper and Helly arc
representation. Circular-arc graphs are a well-studied graph class due to
their intriguing combinatorial properties and modeling power [12].
Additionally, there exists a linear-time algorithm to determine if a given
graph is a circular-arc graph and construct a corresponding arc representation
if so [20], even for Helly circular-arc graphs, such algorithm exists [18].
For graph modification problems, the number of allowed modifications, $k$, is
considered the parameter. With respect to $k$, such a problem is said to be
fixed-parameter tractable (FPT) if it admits an algorithm running in time
$f(k)n^{\mathcal{O}(1)}$ for some computable function $f$. Also, the problem
is said to have a polynomial kernel if in polynomial time (with respect to the
size of the instance) one can obtain an equivalent instance of polynomial size
(with respect to the parameter), i.e., for any given instance $(G,k)$ of the
problem, it can be reduced in time $n^{\mathcal{O}(1)}$ to an equivalent
instance $(G^{\prime},k^{\prime})$ where $|V(G^{\prime})|$ and $k^{\prime}$
are upper bounded by $k^{\mathcal{O}(1)}$. A kernel for a problem immediately
implies that it admits an FPT algorithm, but kernels are also interesting in
their own right. In particular, kernels allow us to model the performance of
polynomial-time preprocessing algorithms. The field of kernelization has
received considerable attention, especially after the introduction of methods
to prove kernelization lower bounds [3]. We refer to the books [5, 8], for a
detailed treatment of the area of kernelization.
Designing polynomial kernels for problems such as Chordal Vertex Deletion [1]
and Interval Vertex Deletion [2] posed several challenges. In fact, kernels
for these problems were obtained only recently, after their status being open
for quite some time. Proper Helly Circular-arc Vertex Deletion has remained an
interesting problem in this area. Recently, Cao et al. [4] studied this
problem and showed that it admits a factor $6$-approximation algorithm, as
well as an FPTalgorithm that runs in time $6^{k}\cdot n^{\mathcal{O}(1)}$.
A natural follow-up question to the prior work on this problem is to check
whether PHCAVD admits a polynomial kernel. In this paper, we resolve this
question in the affirmative way.

Proper Helly Circular-arc Vertex Deletion (PHCAVD) Input: A graph $G$ and an
integer $k$. Parameter: $k$ Output: Does there exist a subset $S\subseteq
V(G)$ of size at most $k$ such that $G-S$ is a proper Helly circular-arc
graph?

###### Theorem 1.1

Proper Helly Circular-arc Vertex Deletion admits a polynomial kernel.

###  1.1 Methods

Our kernelization heavily uses the characterization of proper Helly circular-
arc graphs in terms of their forbidden induced subgraphs, also called
obstructions. Specifically, a graph $H$ is an obstruction to the class of
proper Helly circular-arc graphs if $H$ is not proper Helly circular-arc graph
but $H-\\{v\\}$ is proper Helly circular-arc graph for every vertex $v\in
V(H)$. A graph $G$ is a proper Helly circular-arc graph if and only if it does
not contain any of the following obstructions as induced subgraphs, which are
$\overline{C_{3}^{*}}$ (claw), $S_{3}$ (tent), $\overline{S_{3}}$
(net),$W_{4}$ (wheel of size 4) , $W_{5}$ (wheel of size 5),
$\overline{C_{6}}$ as well as a family of graphs: $C_{\ell}^{*},~{}\ell\geq 4$
referred to as a Monad of size $\ell$ (see fig. 2) [4, 16]. We call any
obstruction of size less than $12$ a small obstruction, and call all other
obstructions _large obstructions_. Note that every _large obstruction_ is a
Monad of size at least $12$.

The first ingredient of our kernelization algorithm is the factor $6$
polynomial-time approximation algorithm for PHCAVD given by Cao et al. [4]. We
use this algorithm to obtain an approximate solution of size at most $6k$, or
conclude that there is no solution of size at most $k$. We grow (extend) this
approximate solution to a set $T_{1}$ of size $\mathcal{O}(k^{12})$, such that
every set $Y\subseteq V(G)$ of size at most $k$ is a minimal hitting set for
all _small_ obstructions in $G$ if and only if $Y$ is a minimal hitting set
for all _small_ obstructions in $G[T_{1}]$. Notice that $G-T_{1}$ is a proper
Helly circular-arc graph (we call $T_{1}$ as an _efficient modulator_ ,
description prescribed in lemma 1), where for any minimal (or minimum)
solution $S$ of size at most $k$, the only purpose of vertices in $S\setminus
T_{1}$ is to hit _large_ obstructions. This $T_{1}$ is the first part of the
_nice modulator_ $T$ that we want to construct. The other part is $M$, which
is a 5-redundant solution (see definition 3) of size $\mathcal{O}(k^{6})$,
which we obtain in polynomial time following the same construction procedure
given by [2]. This gives us the additional property that any obstruction of
size at least 5 contains at least 5 vertices from $M$ and hence also from
$T=T_{1}\cup M$. We bound the size of such a _nice modulator_ $T$ by
$\mathcal{O}(k^{12})$. Next, we analyze the graph $G-T$ and reduce its size by
applying various reduction rules.

For the kernelization algorithm, we look at $G-T$, which is a proper Helly
circular-arc graph and hence has a “ _nice clique partition_ ” (defined in
proposition 2). Let $\mathcal{Q}=\\{Q_{1},Q_{2},\ldots\\}$ denote such a _nice
clique partition_ of $G-T$. This partition is similar to the clique partition
used by Ke et al. [14] to design a polynomial kernel for vertex deletion to
proper interval graphs.

In the first phase, we bound the size of a clique $Q_{i}$ for each
$Q_{i}\in\mathcal{Q}$. Our clique-reduction procedure is based on “irrelevant
vertex rule” [19]. In particular, we find a vertex that is not necessary for a
solution of size at most $k$, and delete it. And after this procedure, we
reduce the size of each clique in $G-T$ to $k^{\mathcal{O}(1)}$.

In the second phase, we bound the size of each connected component in $G-T$.
Towards this, we bound the number of cliques in $Q_{1},Q_{2},\ldots,Q_{t}$
that contain a neighbor of a vertex in $T$ (say good cliques). We use _small_
obstructions, and in particular, the claw, to bound the number of good cliques
by $k^{\mathcal{O}(1)}$. This automatically divides the clique partition into
chunks. A chunk is a maximal set of non-good cliques between a pair of good
cliques where the non-good cliques along with the good cliques induce a
connected component. We show that the number of chunks is upper bounded by
$k^{\mathcal{O}(1)}$. Finally, we use a structural analysis to bound the size
of each chunk, which includes the design of a reduction rule that computes a
minimum cut between the two cliques of a certain distance from the border of
the chunk. With this, we bound the number of cliques in each chunk and hence
the size of each chunk as well as every connected component by
$k^{\mathcal{O}(1)}$.

In the third and final phase of our kernelization algorithm using the claw
obstruction, we bound the number of connected components in $G-T$ by
$k^{\mathcal{O}(1)}$. Using this bound, together with the facts that $|T|\leq
k^{\mathcal{O}(1)}$, and that each connected component is of size
$k^{\mathcal{O}(1)}$, we are able to design a polynomial kernel for PHCAVD. We
conclude this section by summarizing all the steps in our kernelization
algorithm (see fig. 1).

Figure 1: Flowchart of the Kernelization algorithm for PHCAVD.

##  2 Preliminaries

#### Sets and Graph Notations.

We denote the set of natural numbers by $\mathbb{N}$. For $n\in\mathbb{N}$, by
$[n]$ and $[n]_{0}$, we denote the sets $\\{1,2,\cdots,n\\}$ and
$\\{0,1,2,\cdots,n\\}$, respectively. For a graph $G$, $V(G)$ and $E(G)$
denote the set of vertices and edges, respectively. The neighborhood of a
vertex $v$, denoted by $N_{G}(v)$, is the set of vertices adjacent to $v$. For
$A,B\subseteq V(G)$ with $A\cap B=\emptyset$, $E(A,B)$ denotes the set of
edges with one endpoint in $A$ and the other in $B$. For a set $S\subseteq
V(G)$, $G-S$ is the graph obtained by removing $S$ from $G$ and $G[S]$ denotes
the subgraph of $G$ induced on $S$. A path $P=v_{1},\ldots,v_{\ell}$ is a
sequence of distinct vertices where every consecutive pair of vertices is
adjacent. We say that $P$ starts at $v_{1}$ and ends at $v_{\ell}$. The vertex
set of $P$, denoted by $V(P)$, is the set $\\{v_{1},\ldots,v_{\ell}\\}$. The
internal vertices of $P$ is the set $V(P)\setminus\\{v_{1},v_{\ell}\\}$. The
length of $P$ is defined as $|V(P)|-1$. A cycle is a sequence
$v_{1},\ldots,v_{\ell}$ of vertices such that $v_{1},\ldots,v_{\ell}$ is a
path and $v_{\ell}v_{1}$ is an edge. A cycle (or path) $v_{1},\ldots,v_{\ell}$
is also represented as the ordered set $\\{v_{1},\ldots,v_{\ell}\\}$. A set
$Q\subseteq V(G)$ of pairwise adjacent vertices is called a clique. A hole is
an induced cycle of length at least four. A vertex is isolated if it has
degree zero. For a pair of sets $A,B\subseteq V(G)$, we say $S$ is an $A$-$B$
cut in $G$ if there is no edge $(u,v)$ where $u\in A\setminus S,~{}v\in
B\setminus S$. Such a $S$ with minimum cardinality is called as _minimum
$A$-$B$ cut_. The _distance_ between two vertices $u$ and $v$ denoted by
$d_{G}(u,v)$ is the length of a shortest $uv$ path in the graph $G$. The
complement graph $\overline{G}$ of a graph $G$ is defined in the same set of
vertex $V(G)$ such that $(u,v)\in E(\overline{G})$ if and only if $(u,v)\notin
E(G)$. For $\ell\geq 3$, we use $C_{\ell}$ to denote an induced cycle on
$\ell$ vertices; if we add a new vertex to a $C_{\ell}$ and make it adjacent
to none or each vertex in $C_{\ell}$ we end with $C^{*}_{\ell}$ or $W_{\ell}$,
respectively. A Monad is a $C^{*}_{\ell}$ with $\ell\geq 4$. We call the
$C_{\ell}$ as M-Hole and the corresponding isolated vertex as centre of the
Monad. For graph-theoretic terms and definitions not stated explicitly here,
we refer to [6].

#### Parameterized problems and kernelization.

A parameterized problem $\Pi$ is a subset of $\Gamma^{*}\times\mathbb{N}$ for
some finite alphabet $\Gamma$. An instance of a parameterized problem consists
of $(X,k)$, where $k$ is called the parameter. The notion of kernelization is
formally defined as follows. A kernelization algorithm, or in short, a
kernelization, for a parameterized problem
$\Pi\subseteq\Gamma^{*}\times\mathbb{N}$ is an algorithm that, given
$(X,k)\in\Gamma^{*}\times\mathbb{N}$, outputs in time polynomial in $|X|+k$ a
pair $(X^{\prime},k^{\prime})\in\Gamma^{*}\times\mathbb{N}$ such that (a)
$(X,k)\in\Pi$ if and only if $(X^{\prime},k^{\prime})\in\Pi$ and (b)
$|x^{\prime}|,|k|\leq g(k)$, where $g$ is some computable function depending
only on $k$. The output of kernelization $(X^{\prime},k^{\prime})$ is referred
to as the kernel and the function $g$ is referred to as the size of the
kernel. If $g(k)\in k^{\mathcal{O}(1)}$ , then we say that $\Pi$ admits a
polynomial kernel. We refer to the monographs [7, 10, 21] for a detailed study
of the area of kernelization.

#### Proper Helly Circular-arc Graphs.

A proper Helly circular-arc graph is an intersection graph of a set of arcs on
a circle such that none of the arcs properly contains another (proper) and
every set of pairwise intersecting arcs has a common intersection (Helly). The
following is a characterization of proper Helly circular arc graphs.

Figure 2: Forbidden induced subgraphs of proper Helly circular-arc graphs.

######  Proposition 1 ([16])

A graph is a proper Helly circular-arc graph if and only if it contains
neither claw, net, tent, wheel of size 4, wheel of size 5, complement of cycle
of length 6, nor Monad of length at least 4 as induced subgraphs.

######  Proposition 2 (Theorem 1.3 [4])

PHCAVD admits a polynomial-time 6-approximation algorithm, called ApproxPHCAD.

Nice Clique Partition. For a connected graph $G$, a clique partition
${\mathbb{Q}}=(Q_{1},Q_{2},\ldots,Q_{|{\mathbb{Q}}|}(=Q_{0}))$ is called a
_nice clique partition_ of $G$ if (i) $\bigcup_{i}V(Q_{i})=V(G)$, (ii)
$V(Q_{i})\cap V(Q_{j})=\emptyset$ if $i\neq j$, and (iii)
$E(Q_{i},Q_{j})=\emptyset$ if $|i-j|>1$ holds. In such a _nice clique
partition_ every edge of $G$ is either inside a clique in $\mathbb{Q}$ or
present between vertices from adjacent cliques. For a proper circular-arc
graph such a partition always exists and can be obtained in
$n^{\mathcal{O}(1)}$ time using a procedure similar to that for a proper
interval graph [15].

##  3 Constructing an Efficient Modulator

We classify the set of obstructions for proper Helly circular-arc graphs as
follows. Any obstruction of size less than $12$ is known as a small
obstruction, while other obstructions are said to be _large_. In this section
we construct an _efficient modulator_ $T_{1}$, of size $\mathcal{O}(k^{12})$
such that $G-T_{1}$ is a proper Helly circular-arc graph with some additional
properties that are mentioned in later part.

######  Proposition 3 (Lemma 3.2 [11])

Let $\mathcal{F}$ be a family of sets of cardinality at most $d$ over a
universe $U$ and let $k$ be a positive integer. Then there is an
$\mathcal{O}(|\mathcal{F}|(k+|\mathcal{F}|))$ time algorithm that finds a non-
empty family of sets $\mathcal{F}^{\prime}\subseteq\mathcal{F}$ such that

  1. 1.

For every $Z\subseteq U$ of size at most $k$, $Z$ is a minimal hitting set of
$\mathcal{F}$ if and only if $Z$ is a minimal hitting set of
$\mathcal{F}^{\prime}$; and

  2. 2.

$|\mathcal{F}^{\prime}|\leq d!(k+1)^{d}$.

Using proposition 3 we identify a vertex subset of $V(G)$, which allows us to
forget about _small_ obstructions in $G$ and concentrate on _large_
obstructions for the kernelization algorithm for PHCAVD.

###### Lemma 1

Let $(G,k)$ be an instance of PHCAVD. In polynomial-time, either we conclude
that $(G,k)$ is a No-instance, or we can construct a vertex subset $T_{1}$
such that

  1. 1.

Every set $Y\subseteq V(G)$ of size at most $k$ is a minimal hitting set for
all _small_ obstructions in $G$ if and only if it is a minimal hitting set for
all _small_ obstructions in $G[T_{1}]$; and

  2. 2.

$|T_{1}|\leq 12!{(k+1)}^{12}+6k$.

###### Proof

Using proposition 2, in polynomial-time we construct a $6$-approximate
solution $T^{\prime}$. We also construct $\mathcal{F}_{G},U_{G}$ where $U_{G}$
consists of all the vertices in $G$ while $\mathcal{F}_{G}$ contains every
minimal set of vertices in $G$ that induces a small obstruction. Applying
proposition 3 on $\mathcal{F}_{G},U_{G}$, in polynomial-time we construct a
vertex set $T^{\prime\prime}$. If $|T^{\prime}|>6k$ or
$|T^{\prime\prime}|>(12+1)!(k+1)^{12}$, we conclude that $(G,k)$ is a No-
instance. Otherwise, we have a modulator $T_{1}=T^{\prime}\cup
T^{\prime\prime}$ of size $\mathcal{O}(k^{12})$, such that $G-T_{1}$ is a
proper Helly circular-arc graph, and every set $Y\subseteq V(G)$ of size at
most $k$ is a minimal hitting set of all _small_ obstructions in $G$ if and
only if it is a minimal hitting set for all _small_ obstructions in
$G[T_{1}]$. ∎

Let $S$ be a minimal (or minimum) solution of size at most $k$. Then, the only
purpose of the vertices in $S\cap(V(G)\setminus T_{1})$ is to hit _large_
obstructions. We call the modulator constructed above an efficient modulator.
We summarize these discussions in the next lemma.

###### Lemma 2

Let $(G,k)$ be an instance of PHCAVD. In polynomial time, we can either
construct an _efficient_ modulator $T_{1}\subseteq V(G)$ of size
$\mathcal{O}(k^{12})$, or conclude that $(G,k)$ is a No-instance.

##  4 Computing a Redundant Solution

In this section, our main purpose is to prove lemma 7. Intuitively, this lemma
asserts that in $n^{\mathcal{O}(1)}$ time we can compute an $r$-redundant
solution $M$ whose size is polynomial in $k$ (for a fixed constant $r$). Such
a set $M$ plays a crucial role in many of the reduction rules that follow this
section while designing our kernelization algorithm. We remark that in this
section we use the letter $\ell$ rather than $k$ to avoid confusion, as we
will use this result with $\ell=k+2$. Towards the definition of redundancy, we
require the following notions and definitions.

######  Definition 1 ($t$-solution)

Let $(G,k)$ be an instance of PHCAVD. A subset $S\subseteq V(G)$ of size at
most $t$ such that $G-S$ is a proper Helly circular-arc graph is called a
$t$-solution.

######  Definition 2 ($t$-necessary)

A family ${\cal W}\subseteq 2^{V(G)}$ is called $t$-necessary if and only if
every $t$-solution is a hitting set for ${\cal W}$.

Given a family ${\cal W}\subseteq 2^{V(G)}$, we say that an obstruction
$\mathbb{O}$ is covered by $\cal W$ if there exists $W\in{\cal W}$, such that
$W\subseteq V(\mathbb{O})$.

######  Definition 3 ($t$-redundant)

Given a family ${\cal W}\subseteq 2^{V(G)}$ and $t\in\mathbb{N}$, a subset
$M\subseteq V(G)$ is $t$-redundant with respect to $\cal W$ if for every
obstruction $\mathbb{O}$ that is not covered by $\cal W$, it holds that
$|M\cap V(\mathbb{O})|>t$.

###### Definition 4

Let $G$ be a graph, $U\subseteq V(G)$, and $t\in\mathbb{N}$. Then,
${\mathsf{copy}}(G,U,t)$ is defined as the graph $G^{\prime}$ in the vertex
set $V(G)\cup\\{v^{i}\mid v\in U,i\in[t]\\}$ and the edge set
$E(G)\cup\\{(u^{i},v)\mid(u,v)\in E(G),u\in
U,i\in[t]\\}\cup\\{(u^{i},v^{j})\mid(u,v)\in E(G),u,v\in
U,i,j\in[t]\\}\cup\\{(v,v^{i})\mid v\in U,i\in[t]\\}\cup\\{(v^{i},v^{j})\mid
v\in U,i,j\in[t],i\neq j\\}$.

Informally, ${\mathsf{copy}}(G,U,t)$ is simply the graph $G$ where for every
vertex $u\in U$, we add $t$ twins that (together with $u$) form a clique.
Intuitively, this operation allows us to make a vertex set “undeletable”; in
particular, this enables us to test later whether a vertex set is “redundant”
and therefore we can grow the redundancy of our solution, or whether it is
“necessary” and hence we should update $\cal W$ accordingly. Before we turn to
discuss computational issues, let us first assert that the operation in
definition 4 does not change the class of the graph, which means it remains a
proper Helly circular-arc graph. We verify this in the following lemma.

###### Lemma 3

Let $G$ be a graph, $U\subseteq V(G)$, and $t\in\mathbb{N}$. If $G$ is a
proper Helly circular-arc graph, then $G^{\prime}={\mathsf{copy}}(G,U,t)$ is
also a proper Helly circular-arc graph.

###### Proof

Suppose that $G$ is a proper Helly circular-arc graph. Then $G$ admits a
proper circular-arc representation and has Helly property (no three arcs cover
the circle [4]) i.e. all its vertices can be presented as arcs on a circle
$C$. Notice that the newly introduced vertices in $G^{\prime}$ are twin (copy)
vertices of $G$. These twin vertices are given the same arc representations on
C as the original vertices in $G$. It is easy to see that this indeed is a
proper circular-arc representation of $G^{\prime}$ with Helly property and
hence $G^{\prime}$ is also a proper Helly circular-arc graph.∎

Now, we present two simple claims that exhibit relations between the algorithm
ApproxPHCAD and definition 4. After presenting these two claims, we will be
ready to give our algorithm for computing a redundant solution. Generally
speaking, the first claim shows the meaning of a situation where ApproxPHCAD
returns a “large” solution; intuitively, for the purpose of the design of our
algorithm, we interpret this meaning as an indicator to extend ${\cal W}$.

###### Lemma 4

Let $G$ be a graph, $U\subseteq V(G)$, and $\ell\in\mathbb{N}$. If the
algorithm ApproxPHCAD returns a set $A$ of size larger than $6\ell$ when
called with $G^{\prime}={\mathsf{copy}}(G,U,6\ell)$ as input, then $\\{U\\}$
is $\ell$-necessary.

###### Proof

Suppose that ApproxPHCAD returns a set $A$ of size larger than $6\ell$ when
called with $G^{\prime}$ as input. Then, $(G^{\prime},\ell)$ is a No-instance.
If $(G,\ell)$ is a No-instance, then trivially, we can say that $\\{U\\}$ is
$\ell$-necessary (as there is no solution of size at most $\ell$, so the
statement is vacuously true). Now consider the case when $G$ has an
$\ell$-solution $S$ such that $S\cap U=\emptyset$. In particular,
$\widehat{G}=G-S$ is a proper Helly circular-arc graph such that $U\subseteq
V(\widehat{G})$. However, this means that
${\mathsf{copy}}(\widehat{G},U,6\ell)=G^{\prime}-S$, which by lemma 3 implies
that $G^{\prime}-S$ is a proper Helly circular-arc graph. Thus, $S$ is an
$\ell$-solution for $G^{\prime}$, which is a contradiction (as
$(G^{\prime},\ell)$ is a No-instance).∎

Complementing our first claim, the second claim exhibits the meaning of a
situation where ApproxPHCAD returns a “small” solution $A$; we interpret this
meaning as an indicator of growing the redundancy of our current solution $M$
by adding $A$ —- indeed, this lemma implies that every obstruction is hit one
more time by adding $A$ to a subset $U\subseteq M$ (to grow the redundancy of
$M$, every subset $U\subseteq M$ will have to be considered).

Algorithm 2: RedundantPHCAD $(G,\ell,r)$ 1. Initialization:
$M_{0}:=\texttt{ApproxPHCAD}(G)$,
${\cal W}_{0}:=\emptyset$,
${\cal T}_{0}:=\\{(v)\mid v\in M_{0}\\}$. 2. If $|M_{0}|>6\ell$, return
“$(G,\ell)$ is a No-instance”. Otherwise, $i=1$ and go to Step 3. 3. While
$i\leq r$, for every tuple $(v_{0},v_{1},\ldots,v_{i-1})\in{\cal T}_{i-1}$:
(a)
$A:=\texttt{ApproxPHCAD}({\mathsf{copy}}(G,\\{v_{0},v_{1},\ldots,v_{i-1}\\},6\ell))$.
(b) If $|A|>6\ell$, $~{}{\cal W}_{i}:={\cal
W}_{i-1}\cup\\{\\{v_{0},v_{1},\ldots,v_{i-1}\\}\\}$. (c) Otherwise,
${M}_{i}:={M}_{i-1}\cup\\{u\mid u\in(A\cap
V(G))\setminus\\{v_{0},v_{1},\ldots,v_{i-1}\\}\\}$,
${\cal T}_{i}~{}~{}:={\cal T}_{i-1}\cup\\{(v_{0},v_{1},\ldots,v_{i-1},u)\mid
u\in(A\cap V(G))\setminus\\{v_{0},v_{1},\ldots,v_{i-1}\\}\\}$. (d) $i=i+1;$ 4.
Return $(M_{r},{\cal W}_{r})$.

###### Lemma 5

Let $G$ be a graph, $U\subseteq V(G)$, and $\ell\in\mathbb{N}$. If the
algorithm ApproxPHCAD returns a set $A$ of size at most $6\ell$ when called
with $G^{\prime}={\mathsf{copy}}(G,U,6\ell)$ as input, then for every
obstruction $\mathbb{O}$ of $G$, $|V(\mathbb{O})\cap
U|+1\leq|V(\mathbb{O})\cap(U\cup(A\cap V(G)))|$.

Now, we describe our algorithm, RedundantPHCAD, which computes a redundant
solution. First, RedundantPHCAD initializes $M_{0}$ to be the 6-approximate
solution to PHCAVD with $(G,\ell)$ as input, ${\cal W}_{0}:=\emptyset$ and
${\cal T}_{0}:=\\{(v)\mid v\in M_{0}\\}$. If $|M_{0}|>6\ell$, then
RedundantPHCAD concludes that $(G,\ell)$ is a No-instance. Otherwise, for
$i=1,2,\ldots,r$ (in this order), the algorithm executes the following steps
(Step 3 in the figure below) and eventually, it outputs the pair $(M_{r},{\cal
W}_{r})$. In the RedundantPHCAD algorithm, by ApproxPHCAD ($H$) we mean the
$6$-approximate solution returned by the approximation algorithm to the input
graph $H$.

Let us comment that in this algorithm we make use of the sets ${\cal T}_{i-1}$
rather than going over all subsets of size $i$ of $M_{i-1}$ in order to obtain
a substantially better algorithm in terms of the size of the redundant
solution produced.

The properties of the algorithm RedundantPHCAD that are relevant to us are
summarized in the following lemma and observation, which are proved by
induction and by making use of Lemmata lemma 3, lemma 4 and lemma 5. Roughly
speaking, we first assert that, unless $(G,\ell)$ is concluded to be a No-
instance, we compute sets ${\cal W}_{i}$ that are $\ell$-necessary as well as
that the tuples in ${\cal T}_{i}$ “hit more vertices” of the obstructions in
the input as $i$ grows larger.

###### Lemma 6

Consider a call to RedundantPHCAD with $(G,\ell,r)$ as input that did not
conclude that $(G,\ell)$ is a No-instance. For all $i\in[r]_{0}$, the
following conditions hold:

  1. 1.

For any set $W\in{\cal W}_{i}$, every solution $S$ of size at most $\ell$
satisfies $W\cap S\neq\emptyset$.

  2. 2.

For any obstruction $\mathbb{O}$ of $G$ that is not covered by ${\cal W}_{i}$,
there exists $(v_{0},v_{1},\ldots,v_{i})\in{\cal T}_{i}$ such that
$\\{v_{0},v_{1},\ldots,v_{i}\\}\subseteq V(\mathbb{O})$.

###### Proof

The proof is by induction on $i$. In the base case, where $i=0$, Condition
item 1 trivially holds as ${\cal W}_{0}=\emptyset$, and thus there are no sets
in ${\cal W}_{0}$. Condition item 2 holds as $M_{0}$ is a solution (so each
obstruction must contain at least one vertex from $M_{0}$) and ${\cal T}_{0}$
simply contains a 1-vertex tuple for every vertex in $M_{0}$. Now, suppose
that the claim is true for $i-1\geq 0$, and let us prove it for $i$.

To prove Condition item 1, consider some set $W\in{\cal W}_{i}$. If $W\in{\cal
W}_{i-1}$, then by the inductive hypothesis, every solution of size at most
$\ell$ satisfies $W\cap S\neq\emptyset$. Thus, we next suppose that $W\in{\cal
W}_{i}\setminus{\cal W}_{i-1}$. Then, there exists a tuple
$(v_{0},v_{1},\ldots,v_{i-1})\in{\cal T}_{i-1}$ in whose iteration
RedundantPHCAD inserted $W=\\{v_{0},v_{1},\ldots,v_{i-1}\\}$ into ${\cal
W}_{i}$. In that iteration, ApproxPHCAD was called with
${\mathsf{copy}}(G,W,6\ell)$ as input, and returned a set $A$ of size larger
than $6\ell$. Thus, by lemma 4, every solution $S$ of size at most $\ell$
satisfies $W\cap S\neq\emptyset$.

To prove Condition item 2, consider some obstruction $\mathbb{O}$ of $G$ that
is not covered by ${\cal W}_{i}$. By the inductive hypothesis and since ${\cal
W}_{i-1}\subseteq{\cal W}_{i}$, there exists a tuple
$(v_{0},v_{1},\ldots,v_{i-1})\in{\cal T}_{i-1}$ such that
$\\{v_{0},v_{1},\ldots,v_{i-1}\\}\subseteq V(\mathbb{O})$. Consider the
iteration of RedundantPHCAD corresponding to this tuple, and denote
$U=\\{v_{0},v_{1},\ldots,v_{i-1}\\}$. In that iteration, ApproxPHCAD was
called with ${\mathsf{copy}}(G,U,6\ell)$ as input, and returned a set $A$ of
size at most $6\ell$. By lemma 5, $|V(\mathbb{O})\cap
U|+1\leq|V(\mathbb{O})\cap(U\cup(A\cap V(G)))|$. Thus, there exists
$v_{i}\in(A\cap V(G))\setminus U$ such that $U\cup\\{v_{i}\\}\subseteq
V(\mathbb{O})$. However, by the specification of ApproxPHCAD, this means that
there exists $(v_{0},v_{1},\ldots,v_{i})\in{\cal T}_{i}$ such that
$\\{v_{0},v_{1},\ldots,v_{i}\\}\subseteq V(\mathbb{O})$.∎

Towards showing that the output set $M_{r}$ is “small”, let us upper bound the
sizes of the sets $M_{i}$ and ${\cal T}_{i}$.

###### Observation 1

Consider a call to RedundantPHCAD with $(G,\ell,r)$ as input that did not
conclude that $(G,\ell)$ is a No-instance. For all $i\in[r]_{0}$,
$|M_{i}|\leq\sum_{j=0}^{i}(6\ell)^{j+1}$, $|{\cal T}_{i}|\leq(6\ell)^{i+1}$
and every tuple in ${\cal T}_{i}$ consists of distinct vertices.

###### Proof

The proof is by induction on $i$. In the base case, where $i=0$, the
correctness follows as ApproxPHCAD returned a set of size at most $6\ell$.
Now, suppose that the claim is true for $i-1\geq 0$, and let us prove it for
$i$. By the specification of the algorithm and inductive hypothesis, we have
that $|M_{i}|\leq|M_{i-1}|+6\ell|{\cal
T}_{i-1}|\leq\sum_{j=1}^{i+1}(6\ell)^{j}$ and $|{\cal T}_{i}|\leq 6\ell|{\cal
T}_{i-1}|\leq(6\ell)^{i+1}$. Moreover, by the inductive hypothesis, for every
tuple in ${\cal T}_{i}$, the first $i$ vertices are distinct, and by the
specification of ApproxPHCAD, the last vertex is not equal to any of them.∎

By the specification of RedundantPHCAD, as a corollary to lemma 6 and 1, we
directly obtain the following result.

###### Corollary 1

Consider a call to RedundantPHCAD with $(G,\ell,r)$ as input that did not
conclude that $(G,\ell)$ is a No-instance. For all $i\in[r]_{0}$, ${\cal
W}_{i}$ is an $\ell$-necessary family and $M_{i}$ is a
$\sum_{j=0}^{i}(6\ell)^{j+1}$-solution that is $i$-redundant with respect to
${\cal W}_{i}$.

###### Lemma 7

Let $r\in\mathbb{N}$ be a fixed constant, and $(G,\ell)$ be an instance of
PHCAVD. In polynomial-time, it is possible to either conclude that $(G,\ell)$
is a No-instance, or compute an $\ell$-necessary family ${\cal W}\subseteq
2^{V(G)}$ and a set $M\subseteq V(G)$, such that ${\cal W}\subseteq 2^{M}$ and
$M$ is a $(r+1)(6\ell)^{r+1}$-solution that is $r$-redundant with respect to
$\cal W$.

###### Proof

Clearly, RedundantPHCAD runs in polynomial-time (as $r$ is a fixed constant),
and by the correctness of ApproxPHCAD, if it concludes that $(G,\ell)$ is a
No-instance, then this decision is correct. Thus, since
$\sum_{i=0}^{r}(6\ell)^{i+1}\leq(r+1)(6\ell)^{r+1}$, the correctness of lemma
7 now directly follows as a special case of corollary 1. Thus, our proof of
lemma 7 is complete.∎

In light of lemma 7, from now on, we suppose that we have an $\ell$-necessary
family ${\cal W}\subseteq 2^{V(G)}$ along with a $(r+1)(6\ell)^{r+1}$-solution
$M$ that is $r$-redundant with respect to $\cal W$ for $r={5}$. Let us note
that, any obstruction in $G$ that is not covered by ${\mathcal{W}}$ intersects
$M$ in at least six vertices. We have the following reduction rule that
follows immediately from lemma 6.

###### Reduction Rule 1

Let $v$ be a vertex such that $\\{v\\}\in{\mathcal{W}}$. Then, output the
instance $(G-\\{v\\},k-1)$.

From here onwards we assume that each set in $\cal W$ has a size at least $2$.

Nice Modulator. Once we construct both the _efficient modulator_ $T_{1}$ and
_redundant solution_ $M$, we take their union and consider that set of
vertices as a modulator, we called it as _nice modulator_.

From here onwards, for the remaining sections, we assume that

We have a _nice modulator_ $T\subseteq V(G)$ along with $(k+2)$-necessary
family ${\mathcal{W}}\subseteq 2^{T}$ satisfying the following: $\bullet$
$G-T$ is a proper Helly circular-arc graph. $\bullet$
$|T|\leq\mathcal{O}(k^{12})$. $\bullet$ For any _large_ obstruction
${\mathbb{O}}$ containing no $W\in{\mathcal{W}}$, we have
$|V({\mathbb{O}})\cap T|\geq 6$.

##  5 Bounding the Size of each Clique

In this section, we consider a _nice modulator_ $T$ of $G$ obtained in the
previous section and we bound the size of each clique in a _nice clique
partition_ $\mathcal{Q}$ of $G-T$ in polynomial time. If there is a _large_
clique in $\mathcal{Q}$ of size more than $\mathcal{O}(k^{12})$, we can safely
find and remove an _irrelevant vertex_ from the clique, thus reducing its
size. Next, we prove a simple result that will later be used to bound the size
of each clique in $G-T$.

###### Lemma 8

Let $H$ be an induced path in $G$. Consider a vertex $v\in V(G)\setminus
V(H)$. If $v$ has more than four neighbors in $V(H)$ then $G[V(H)\cup\\{v\\}]$
contains a _small_ obstruction (claw).

###### Proof

Assume that ${|{N(v)\cap V(H)}|}\geq 5$. Let $H$ be an induced path from $x$
to $y$ for some $x,y\in V(G)$. Let $v_{1},v_{2},v_{3},v_{4},v_{5}\in V(H)$ be
the first $5$ neighbours of $v$ that appear as we traverse $H$ from $x$ to
$y$. Since the path is induced so $(v_{1},v_{3}),(v_{3},v_{5})\notin E(G)$. So
$\left\\{{v,v_{1},v_{3},v_{5}}\right\\}$ induces a $\overline{C_{3}^{*}}$
(claw), which is a _small_ obstruction.∎

#### Marking Scheme.

We start with the following marking procedure, which marks
$k^{\mathcal{O}(1)}$ vertices in each clique
${\mathcal{Q}_{i}}\in\mathcal{Q}$.

We will now bound the size of the set $T({\mathcal{Q}_{i}})$.

###### Remark 1

Observe that the procedure $\mathtt{Mark\mathchar 45\relax 1}$can be executed
in polynomial time. Also, note that ${|{T({\mathcal{Q}_{i}})}|}\leq
2(k+1){|{T}|}^{4}$.

###### Reduction Rule 2

If there exists a vertex $v\in{\mathcal{Q}_{i}}\setminus T({\mathcal{Q}_{i}})$
for some clique ${\mathcal{Q}_{i}}\in\mathcal{Q}\subseteq V(G)\setminus T$,
then delete $v$.

###### Lemma 9

Reuction Rule 2 is safe.

###### Proof

Consider an application of reduction rule 2 in which a vertex, say
$v\in{\mathcal{Q}_{i}}\setminus T({\mathcal{Q}_{i}})$ was deleted from some
clique ${\mathcal{Q}_{i}}\in\mathcal{Q}$. we claim the following.

###### Claim

$(G,k)$ is a Yes-instance of PHCAVD if and only if $(G-v,k)$ is a Yes-instance
of PHCAVD.

$(\Rightarrow)$ If $(G,k)$ is a Yes-instance, then so is $(G-v,k)$, since
$G-v$ is an induced subgraph of $G$.

$(\Leftarrow)$ To prove the other direction we use contradiction. Suppose
$(G-v,k)$ is a Yes-instance but $(G,k)$ is not. And let $X\subseteq V(G-v)$ be
a solution of size at most $k$. That is $(G-v)-X$ is a proper Helly circular-
arc graph. Since $(G,k)$ is a No-instance, $G-X$ can not be a proper Helly
circular-arc graph. Hence $G-X$ must contain an obstruction, say,
${\mathbb{O}}$. Clearly, $v$ must be a vertex in $V({\mathbb{O}})$, otherwise,
${\mathbb{O}}$ would also be an obstruction in $(G-v)-X$, which contradicts
the fact that $(G-v)-X$ is a proper Helly circular-arc graph.

We first claim that ${\mathbb{O}}$ is a _large_ obstruction. Suppose it is
not, i.e. ${\mathbb{O}}$ is a _small_ obstruction. Note that $X$ hits all
obstructions in $G-v$, and $G[T]$ is a subgraph of $G-v$ as $v\notin T$. So
$X$ also hits all obstructions in $G[T]$, in particular, also all _small_
obstructions in $G[T]$. Let $Y\subseteq X$ be a minimal hitting set for all
_small_ obstructions in $G[T]$. Then, by the definitions of $T$ and $Y$, we
can conclude that $Y$ hits all _small_ obstructions in $G$ as well (using
lemma 1). But since ${\mathbb{O}}$ is an obstruction contained in $G-X$ and
$Y\subseteq X$, ${\mathbb{O}}$ has to be a _large_ obstruction in $G-Y$, a
contradiction. Thus, ${\mathbb{O}}$ being a _large_ obstruction in $G-X$ must
be ${C_{\ell}}^{*}$ (Monad) where $\ell>12$. Also $v\in V({\mathbb{O}})$. So
there is no _small_ obstruction containing $v$ in $G-X$.

Next, we claim that such an obstruction ${\mathbb{O}}$ can not contain any
$W\in{\mathcal{W}}$. As $X\cup\\{v\\}$ is a $(k+1)$-solution for $G$,
$X\cup\\{v\\}$ is a hitting set for the $(k+2)$-necessary family
${\mathcal{W}}$. But ${\mathbb{O}}\cap(X\cup\\{v\\})\neq\emptyset$. This
implies that ${\mathbb{O}}$ does not contain any $W\in{\mathcal{W}}$. So, $M$
and hence $T$ contains at least five vertices from ${\mathbb{O}}$ i.e.
$|V({\mathbb{O}})\cap T|\geq 5$.

To show equivalence between the instances $(G,k)$ and $(G-v,k)$, we either
find an obstruction ${\mathbb{O}}^{\prime}$ in $(G-v)-X$ or we show that $v$
is a part of _small_ obstruction in $G-X$. We argue for the following two
cases depending on the nature of $v$ in $V({\mathbb{O}})$. We use
$\mathsf{prev}(v)$ and $\mathsf{next}(v)$ to denote the adjacent vertices of
$v$ in $V({\mathbb{O}})$ (here the selection is arbitrary). Let $\mathsf{g}$
denote the centre of this Monad ${\mathbb{O}}$.

Case A

Here we consider the case when vertex $v$ is not the centre of the Monad
${\mathbb{O}}:=C^{*}_{\ell}$, i.e., $v\neq\mathsf{g}$. We argue for all the
following eight cases depending on whether the vertices
$\mathsf{prev}(v),\mathsf{next}(v)$, and $\mathsf{g}$ of ${\mathbb{O}}$ belong
to $T$ or not. Notice that $v$ was deleted because it was an irrelevant
(unmarked) vertex. From the redundant solution property (lemma 7), we know
that ${\mathbb{O}}$ has at least five vertices from $T$ and $v$ is adjacent to
at most two of them while non-adjacent to the rest.

  1. 1.

$\boldsymbol{\mathsf{prev}(v)\in T,~{}\mathsf{next}(v)\in T,~{}\mathsf{g}\in
T}$. Let $u$ be a vertex in ${\mathbb{O}}\cap T$ such that $(u,v)\notin E(G)$.
Note that such a vertex $u$ always exists because of the redundant solution
property. During Procedure $\mathtt{Mark\mathchar 45\relax 1}$, we have added
a set $S:=\mathtt{Mark}_{i}[A,B]$ of at least $2(k+1)$ vertices from
${\mathcal{Q}_{i}}$ where $A=\\{\mathsf{prev}(v),\mathsf{next}(v)\\}$ and
$B=\\{u,\mathsf{g}\\}$. Otherwise, we would have added $v$ to
$T({\mathcal{Q}_{i}})$. So each vertex in $S$ is non-adjacent to both $u$ and
$\mathsf{g}$ and adjacent to both $\mathsf{prev}(v)$ and $\mathsf{next}(v)$.
Since $|S|>k$, there exists a vertex in $S$ which is not in $X$. Let
$v^{\prime}$ be such a vertex (arbitrarily chosen) from $S\setminus X$. Assume
that $u_{1}$ and $u_{2}$ are the two closest vertices of $u$ along the
clockwise and anti-clockwise directions, respectively in $V({\mathbb{O}})$,
which are also adjacent to $v^{\prime}$. Notice that there is an induced path
$P$ between $u_{1}$ and $u_{2}$ passing through $u$ such that $V(P)\subseteq
V({\mathbb{O}})$ and $N(v^{\prime})\cap V(P-u_{1}-u_{2})=\emptyset$. Clearly,
$v\notin P$. Let $C$ be the cycle induced by the vertices
$V(P)\cup\\{v^{\prime}\\}$. Since $v^{\prime}\notin X$ and $P\cap
X=\emptyset$, $C\cup\\{\mathsf{g}\\}$ forms an obstruction that is contained
in $(G-v)-X$. And this contradicts the fact that $X$ is a solution to $G-v$
for PHCAVD.

  2. 2.

$\boldsymbol{\mathsf{prev}(v)\in T,~{}\mathsf{next}(v)\in
T,~{}\mathsf{g}\notin T}$. Let $u$ be a vertex in ${\mathbb{O}}\cap T$ such
that $(u,v)\notin E(G)$. Recall that during Procedure $\mathtt{Mark\mathchar
45\relax 1}$, we have added a set $S:=\mathtt{Mark}_{i}[A,B]$ of at least
$2(k+1)$ vertices from ${\mathcal{Q}_{i}}$ where
$A=\\{\mathsf{prev}(v),\mathsf{next}(v)\\}$ and $B=\\{u\\}$. Otherwise, we
would have added $v$ to $T({\mathcal{Q}_{i}})$. But each vertex in $S$ is
adjacent to both $\mathsf{prev}(v)$ and $\mathsf{next}(v)$. Since $|S|>k$,
there exists a vertex in $S$ which is not in $X$. Let $v^{\prime}$ be such a
vertex (arbitrarily chosen) from $S\setminus X$. If
$(v^{\prime},\mathsf{g})\notin E(G)$, using similar arguments as in case A.1.
we can find an induced subgraph ${\mathbb{O}}^{\prime}$ in $G$ which is an
obstruction in $(G-v)-X$, a contradiction. Else, $(v^{\prime},\mathsf{g})\in
E(G)$. In this case, we can a find a $\overline{C_{3}^{*}}$, in $(G-v)-X$
induced by the vertices
$\\{v^{\prime},\mathsf{prev}(v),\mathsf{next}(v),\mathsf{g}\\}$, which is an
obstruction in $(G-v)-X$, again a contradiction.

  3. 3.

$\boldsymbol{\mathsf{prev}(v)\in T,~{}\mathsf{next}(v)\notin
T,~{}\mathsf{g}\in T}$. Let $u$ be a vertex in ${\mathbb{O}}\cap T$ such that
$(u,v)\notin E(G)$. Note that such a vertex $u$ always exists because of the
redundant solution property. Recall that during Procedure
$\mathtt{Mark\mathchar 45\relax 1}$, we have added a set
$S:=\mathtt{Mark}_{i}[A,B]$ of at least $2(k+1)$ vertices from
${\mathcal{Q}_{i}}$ where $A=\\{\mathsf{prev}(v)\\}$ and
$B=\\{u,\mathsf{g}\\}$. Otherwise, we would have added $v$ to
$T({\mathcal{Q}_{i}})$. In $S$, we must have added the left most $(k+1)$
vertices, say $S_{1}$ and the right most $(k+1)$ vertices, say $S_{2}$ in
${\mathcal{Q}_{i}}$. Since $|S_{1}|>k$ and $|S_{2}|>k$, there exists some
vertices in each of $S_{1}$ and $S_{2}$ which are not in $X$. Let
$v^{\prime}_{1}$ and $v^{\prime}_{2}$ be a pair of such vertices (arbitrarily
chosen) from $S_{1}\setminus X$ and $S_{2}\setminus X$, respectively. Since
$v,v^{\prime}_{1},v^{\prime}_{2}\in{\mathcal{Q}_{i}}$ and
$(v,\mathsf{next}(v))\in E(G)$ , either $v^{\prime}_{1}$ or $v^{\prime}_{2}$
must be adjacent to $\mathsf{next}(v)$. Without loss of generality, we assume
that $(v^{\prime}_{1},\mathsf{next}(v))\in E(G)$. Since
$\\{\mathsf{prev}(v),\mathsf{next}(v)\\}\subseteq N(v^{\prime}_{1})$ and
$v^{\prime}_{1}$ is non-adjacent to both $u$ and $\mathsf{g}$, so there must
exist two distinct vertices $u_{1}$ and $u_{2}$ in ${\mathbb{O}}$ such that
$\\{u_{1},u_{2}\\}\subseteq N(v^{\prime}_{1})$ with an induced path $P$
between them passing through $u$ where $V(P)\subseteq V({\mathbb{O}})$ and
$N(v^{\prime}_{1})\cap V(P-u_{1}-u_{2})=\emptyset$. Clearly, $v\notin V(P)$,
as $(v,v^{\prime}_{1})\in E(G)$. Let $C$ be the cycle induced by the vertices
$V(P)\cup\\{v^{\prime}_{1}\\}$. Now $P\cap X=\emptyset$ and
$v^{\prime}_{1}\notin X$ together imply that
${\mathbb{O}}^{\prime}:=C\cup\\{\mathsf{g}\\}$ is an obstruction in $(G-v)-X$,
a contradiction.

  4. 4.

$\boldsymbol{\mathsf{prev}(v)\notin T,~{}\mathsf{next}(v)\in
T,~{}\mathsf{g}\in T}$. Since the selection of $\mathsf{prev}(v)$ and
$\mathsf{next}(v)$ is arbitrary, so arguments for this case are similar to
that of case A.3.

  5. 5.

$\boldsymbol{\mathsf{prev}(v)\in T,~{}\mathsf{next}(v)\notin
T,~{}\mathsf{g}\notin T}$. Let $u$ be a vertex in ${\mathbb{O}}\cap T$ such
that $(u,v)\notin E(G)$. Note that such a vertex $u$ always exists because of
the redundant solution property. Recall that during Procedure
$\mathtt{Mark\mathchar 45\relax 1}$, we have added a set
$S:=\mathtt{Mark}_{i}[A,B]$ of at least $2(k+1)$ vertices from
${\mathcal{Q}_{i}}$ where $A=\\{\mathsf{prev}(v)\\}$ and $B=\\{u\\}$.
Otherwise, we would have added $v$ to $T({\mathcal{Q}_{i}})$. In $S$, we must
have added the left most $(k+1)$ vertices, say $S_{1}$ and the right most
$(k+1)$ vertices, say $S_{2}$ in ${\mathcal{Q}_{i}}$. Since $|S_{1}|>k$ and
$|S_{2}|>k$, there exist some vertices in each of $S_{1}$ and $S_{2}$ which
are not in $X$. Let $v^{\prime}_{1}$ and $v^{\prime}_{2}$ be a pair of such
vertices (arbitrarily chosen) from $S_{1}\setminus X$ and $S_{2}\setminus X$,
respectively. As $v,v^{\prime}_{1},v^{\prime}_{2}\in{\mathcal{Q}_{i}}$ and
$(v,\mathsf{next}(v))\in E(G)$ , either $v^{\prime}_{1}$ or $v^{\prime}_{2}$
must be adjacent to $\mathsf{next}(v)$. Without loss of generality, we assume
that $(v^{\prime}_{1},\mathsf{next}(v))\in E(G)$. If
$(v^{\prime},\mathsf{g})\notin E(G)$ using arguments similar to that in case
A.3. , we can find an induced subgraph ${\mathbb{O}}^{\prime}$ in $G$ which is
an obstruction in $(G-v)-X$, a contradiction. Else,
$(v^{\prime},\mathsf{g})\in E(G)$. In this case, we can a find a
$\overline{C_{3}^{*}}$, in $(G-v)-X$ induced by the vertices
$\\{v^{\prime},\mathsf{prev}(v),\mathsf{next}(v),\mathsf{g}\\}$, which is an
obstruction in $(G-v)-X$, again a contradiction.

  6. 6.

$\boldsymbol{\mathsf{prev}(v)\notin T,~{}\mathsf{next}(v)\in
T,~{}\mathsf{g}\notin T}$. Since selection of $\mathsf{prev}(v)$ and
$\mathsf{next}(v)$ is arbitrary, so arguments for this case is similar to that
of case A.5.

  7. 7.

$\boldsymbol{\mathsf{prev}(v)\notin T,~{}\mathsf{next}(v)\notin
T,~{}\mathsf{g}\in T}$. Let $u$ be a vertex in ${\mathbb{O}}\cap T$ such that
$(u,v)\notin E(G)$. Note that such a vertex $u$ always exists because of the
redundant solution property. Recall that during Procedure
$\mathtt{Mark\mathchar 45\relax 1}$, we have added a set
$S:=\mathtt{Mark}_{i}[A,B]$ of at least $2(k+1)$ vertices from
${\mathcal{Q}_{i}}$ where $A=\emptyset$ and $B=\\{u,\mathsf{g}\\}$. Otherwise,
we would have added $v$ as well to $T({\mathcal{Q}_{i}})$. If there exists a
vertex $v^{\prime}\in S\setminus X$ such that
$(v^{\prime},\mathsf{prev}(v))\notin E(G)$ and
$(v^{\prime},\mathsf{next}(v))\notin E(G)$, then we get an induced subgraph
$\overline{C_{3}^{*}}$, in $G-X$ induced by the vertices
$\\{v,v^{\prime},\mathsf{prev}(v),\mathsf{next}(v)\\}$, which is a _small_
obstruction in $G-X$. This is a contradiction to the fact that there is no
_small_ obstruction containing $v$ in $G-X$. If there exists a vertex
$v^{\prime}\in S\setminus X$ such that $(v^{\prime},\mathsf{prev}(v))\in E(G)$
and $(v^{\prime},\mathsf{next}(v))\in E(G)$, then using the same procedure as
in case A.1. , we can find an induced subgraph ${\mathbb{O}}^{\prime}$ in $G$
which is an obstruction in $(G-v)-X$, a contradiction. Else, each vertex in
$S$ is adjacent to exactly one of $\mathsf{prev}(v)$ and $\mathsf{next}(v)$.
During the procedure Mark-1, in $S$ we must have added the left most $(k+1)$
vertices, say $S_{1}$ and the right most $(k+1)$ vertices, say $S_{2}$ in
${\mathcal{Q}_{i}}$. Since $|S_{1}|>k$ and $|S_{2}|>k$, there exist some
vertices in each of $S_{1}$ and $S_{2}$ which are not in $X$. Let
$v^{\prime}_{1}$ and $v^{\prime}_{2}$ be a pair of such vertices (arbitrarily
chosen) from $S_{1}\setminus X$ and $S_{2}\setminus X$, respectively. Without
loss of generality, we assume that $(v^{\prime}_{1},\mathsf{prev}(v))\in E(G)$
and $(v^{\prime}_{2},\mathsf{next}(v))\in E(G)$. Clearly,
$(v^{\prime}_{2},\mathsf{prev}(v))\notin E(G)$ and
$(v^{\prime}_{1},\mathsf{next}(v))\notin E(G)$. Since $u$ is non-adjacent to
both $v^{\prime}_{1}$ and $v^{\prime}_{2}$, there exists a pair of vertices
$u_{1}$ and $u_{2}$ in ${\mathbb{O}}$ such that $(u_{1},v^{\prime}_{1})\in
E(G)$, $(u_{2},v^{\prime}_{2})\in E(G)$ with an induced path
$P\subseteq{\mathbb{O}}$ between $u_{1}$ and $u_{2}$ passing through $u$ where
$N(\\{v^{\prime}_{1},v^{\prime}_{2}\\})\cap V(P-u_{1}-u_{2})=\emptyset$.
Clearly, $v\notin P$, as $(v,v^{\prime}_{1}),(v,v^{\prime}_{2})\in E(G)$. Let
$C$ be the cycle induced by the vertices
$V(P)\cup\\{v^{\prime}_{1},v^{\prime}_{2}\\}$. Now $P\cap X=\emptyset$,
$v^{\prime}_{1},v^{\prime}_{2}\notin X$,
$N(\mathsf{g})\cap\\{v^{\prime}_{1},v^{\prime}_{2}\\}=\emptyset$ together
imply that ${\mathbb{O}}^{\prime}:=C\cup\\{\mathsf{g}\\}$ is an obstruction in
$(G-v)-X$, a contradiction.

  8. 8.

$\boldsymbol{\mathsf{prev}(v)\notin T,~{}\mathsf{next}(v)\notin
T,~{}\mathsf{g}\notin T}$. Let $u$ be a vertex in ${\mathbb{O}}\cap T$ such
that $(u,v)\notin E(G)$. Note that such a vertex $u$ always exists because of
the redundant solution property. But during Procedure $\mathtt{Mark\mathchar
45\relax 1}$, we have added a set $S:=\mathtt{Mark}_{i}[A,B]$ of at least
$2(k+1)$ vertices from ${\mathcal{Q}_{i}}$ where $A=\emptyset$ and
$B=\\{u\\}$. Otherwise, $v$ would have been added to $T({\mathcal{Q}_{i}})$.

If there exists a vertex $v^{\prime}\in S\setminus X$ such that $v^{\prime}$
is non-adjacent to both $\mathsf{prev}(v)$ and $\mathsf{next}(v)$, then we can
a find a $\overline{C_{3}^{*}}$ in $G-X$ induced by the vertices
$\\{v,v^{\prime},\mathsf{prev}(v),\mathsf{next}(v)\\}$, which is a _small_
obstruction containing $v$ in $G-X$, a contradiction.

If there exists a vertex $v^{\prime}\in S\setminus X$ such that
$(v^{\prime},\mathsf{g})\in E(G)$ and $v^{\prime}$ is adjacent to both
$\mathsf{prev}(v)$ and $\mathsf{next}(v)$, then we can a find a
$\overline{C_{3}^{*}}$ induced by the vertices
$\\{v^{\prime},\mathsf{prev}(v),\mathsf{next}(v),\mathsf{g}\\}$, which is an
obstruction in $(G-v)-X$, a contradiction.

If there exists a vertex $v^{\prime}\in S\setminus X$ such that
$(v^{\prime},\mathsf{g})\in E(G)$ and $v^{\prime}$ is adjacent to exactly one
of $\mathsf{prev}(v)$ and $\mathsf{next}(v)$, then we argue as follows.
Without loss of generality, we assume that $(v^{\prime},\mathsf{prev}(v))\in
E(G)$. Suppose $v^{*}$ is the adjacent vertex of $\mathsf{prev}(v)$ other than
$v$ in the obstruction. When $(v^{\prime},v^{*})\notin E(G)$, we can a find a
$\overline{S_{3}}$, in $G-X$ induced by the vertices
$\\{v,v^{\prime},\mathsf{prev}(v),v^{*},\mathsf{g},\mathsf{next}(v)\\}$, which
is a _small_ obstruction containing $v$, a contradiction. Else, when
$(v^{\prime},v^{*})\in E(G)$, we can a find a $\overline{C_{3}^{*}}$, in $G-X$
induced by the vertices $\\{v^{\prime},v,v^{*},\mathsf{g}\\}$, which is a
_small_ obstruction containing $v$ in $G-X$, a contradiction.

If there exists a vertex $v^{\prime}\in S\setminus X$ such that
$(v^{\prime},\mathsf{g})\notin E(G)$ and $v^{\prime}$ is adjacent to both
$\mathsf{prev}(v)$ and $\mathsf{next}(v)$, then using the same arguments as in
case A.1. , we can find an induced subgraph ${\mathbb{O}}^{\prime}$ in $G$
which is an obstruction in $(G-v)-X$, a contradiction.

Else, each vertex in $S$ that is non-adjacent to $\mathsf{g}$, must be
adjacent to exactly one of $\mathsf{prev}(v)$ and $\mathsf{next}(v)$. During
the procedure Mark-1, in $S$, we would have added the left most $(k+1)$
vertices, say $S_{1}$ and the right most $(k+1)$ vertices, say $S_{2}$ from
${\mathcal{Q}_{i}}$. Since $|S_{1}|>k$ and $|S_{2}|>k$, there exist some
vertices in each of $S_{1}$ and $S_{2}$, that are not in $X$. Let
$v^{\prime}_{1}$ and $v^{\prime}_{2}$ be a pair of such vertices (arbitrarily
chosen) from $S_{1}\setminus X$ and $S_{2}\setminus X$, respectively. Without
loss of generality, let $(v^{\prime}_{1},\mathsf{prev}(v))\in E(G)$ and
$(v^{\prime}_{2},\mathsf{next}(v))\in E(G)$. Since $u$ is non-adjacent to both
$v^{\prime}_{1}$ and $v^{\prime}_{2}$, there exists a pair of vertices $u_{1}$
and $u_{2}$ in ${\mathbb{O}}$ such that $(u_{1},v^{\prime}_{1})\in E(G)$,
$(u_{2},v^{\prime}_{2})\in E(G)$ with an induced path $P$ in the obstruction
${\mathbb{O}}$ between $u_{1}$ and $u_{2}$ passing through $u$ where
$N(\\{v^{\prime}_{1},v^{\prime}_{2}\\})\cap V(P-u_{1}-u_{2})=\emptyset$.
Clearly, $v\notin P$, as $(v,v^{\prime}_{1}),(v,v^{\prime}_{2})\in E(G)$. Let
$C$ be the cycle induced by the vertices
$V(P)\cup\\{v^{\prime}_{1},v^{\prime}_{2}\\}$. Since $P\cap X=\emptyset$,
$v^{\prime}_{1},v^{\prime}_{2}\notin X$,
$N(\mathsf{g})\cap\\{v^{\prime}_{1},v^{\prime}_{2}\\}=\emptyset$,
${\mathbb{O}}^{\prime}:=C\cup\\{\mathsf{g}\\}$ is an obstruction in $(G-v)-X$,
a contradiction.

Case B

Here we consider the case when $v$ is the centre in the Monad
${\mathbb{O}}:=C^{*}_{\ell}$, i.e., $v=\mathsf{g}$. So there exists a cycle
$H$ in ${\mathbb{O}}$ such that $\mathsf{g}$ is not adjacent to any vertex of
$V(H)$. We have deleted the vertex $v$ since it was an irrelevant (unmarked)
vertex. Let $u$ be a vertex in ${\mathbb{O}}\cap T$. Clearly, $(u,v)\notin
E(G)$. Let ${\mathcal{Q}_{i}}$ be a clique in $\mathcal{Q}$ containing $v$.
During Procedure $\mathtt{Mark\mathchar 45\relax 1}$, we have added a set
$S:=\mathtt{Mark}_{i}[A,B]$ of at least $2(k+1)$ vertices from
${\mathcal{Q}_{i}}$ where $A=\emptyset$ and $B=\\{u\\}$. Otherwise, we would
have added $v$ to $T({\mathcal{Q}_{i}})$. Since $|S|>k$, there exists some
vertex in $S$ which is not in $X$. Let $v^{\prime}$ be such a vertex
(arbitrarily chosen) from $S\setminus X$.

  * •

If the vertex $v^{\prime}$ has no neighbour in $H$, then
${\mathbb{O}}^{\prime}:=H\cup\\{v^{\prime}\\}$ is an obstruction in $(G-v)-X$,
a contradiction.

  * •

If the vertex $v^{\prime}$ has exactly one neighbour, say $u^{\prime}$ in $H$,
then we can a find a $\overline{C_{3}^{*}}$, in $(G-v)-X$, induced by the
vertices
$\\{u^{\prime},\mathsf{prev}(u^{\prime}),\mathsf{next}(u^{\prime}),v^{\prime}\\}$,
which is an obstruction in $(G-v)-X$, a contradiction.

  * •

If the vertex $v^{\prime}$ has exactly two neighbours, say $u^{\prime}$ and
$u^{\prime\prime}$ in $H$, then we argue as following. When
$(u^{\prime},u^{\prime\prime})\notin E(G)$, we can find a
$\overline{C_{3}^{*}}$, in $G-X$ induced by the vertices
$\\{v^{\prime},u^{\prime},u^{\prime\prime},\mathsf{g}\\}$, a contradiction.
When $(u^{\prime},u^{\prime\prime})\in E(G)$, then we can find a
$\overline{S_{3}}$, in $G-X$ induced by the vertices
$\\{v^{\prime},u^{\prime},u^{\prime\prime},\mathsf{prev}(u^{\prime}),\mathsf{next}(u^{\prime\prime}),\mathsf{g}\\}$.
For both these sub-cases, we are able to find _small_ obstructions in $G-X$
containing $v$, which is a contradiction.

  * •

Else the vertex $v^{\prime}$ has at least three neighbours say $u_{1},u_{2}$
and $u_{3}$ in $H$ where $(u_{1},u_{3})\notin E(G)$ (note that such
$u_{1},u_{3}$ always exist as $H$ is large). Then we can find a
$\overline{C_{3}^{*}}$, in $G-X$ induced by the vertices
$\\{v^{\prime},u_{1},u_{3},\mathsf{g}\\}$, which is a _small_ obstruction in
$G-X$ containing $v$, a contradiction.

This completes the proof. ∎

Procedure $\mathtt{Mark\mathchar 45\relax 1}$. Let ${\mathcal{Q}_{i}}$ be a
clique. For a pair of disjoint subsets $A,B\subseteq T$, where $|A|\leq 2$ and
$|B|\leq 2$, let $\mathtt{Mark}_{i}[A,B]$ be the set defined by
$\\{v\in{\mathcal{Q}_{i}}~{}|~{}A\subseteq N(v),~{}B\cap N(v)=\emptyset\\}$.
We initialize $T({\mathcal{Q}_{i}})=\emptyset$, and do as follows: • If
$|\mathtt{Mark}_{i}[A,B]|\leq 2(k+1)$, we add all vertices from the set
$\mathtt{Mark}_{i}[A,B]$ to $T({\mathcal{Q}_{i}})$. • Else, we add the left
most $(k+1)$ vertices (clockwise order of vertices according to their
corresponding arc representation) and the right most $(k+1)$ vertices
(anticlockwise order) in $\mathtt{Mark}_{i}[A,B]$ to $T({\mathcal{Q}_{i}})$.

With the help of reduction rule 2, after deleting all unmarked vertices from
each ${\mathcal{Q}_{i}}\in\mathcal{Q}$, size of each clique
${\mathcal{Q}_{i}}$ is reduced to $k^{\mathcal{O}(1)}$. Therefore, we have the
following result. Notice that $\mathcal{Q}$ (with the reduced cliques) is also
a _nice clique partition_ of $G^{\prime}-T$ in the reduced instance
$(G^{\prime},k)$.

###### Lemma 10

Given an instance $(G,k)$ of PHCAVD and a nice modulator $T\subseteq V(G)$ of
size $k^{\mathcal{O}(1)}$, in polynomial time, we can construct an equivalent
instance $(G^{\prime},k)$ such that $T\subseteq V(G^{\prime})$ and there
exists a nice clique partition $\mathcal{Q}$ of $G^{\prime}-T$ such that the
size of each clique in $\mathcal{Q}$ is bounded by $k^{\mathcal{O}(1)}$.

##  6 Bounding the Size of each Connected Component

From lemma 10, we can assume that the size of every clique in the _nice clique
partition_ ${\mathbb{Q}}=(Q_{1},\ldots)$ of $G-T$ for a given instance $(G,k)$
is bounded by $k^{\mathcal{O}(1)}$. In this section, we will bound the size of
each connected component in $G-T$. For this purpose, it is sufficient to bound
the number of cliques $Q_{i}$’s from ${\mathbb{Q}}$ appearing in each
connected component.

Let $\mathcal{C}$ be such a connected component. Without loss of generality,
we assume that $\mathcal{C}=\bigcup_{i}(Q_{i})$ i.e. in the _nice clique
partition_ ${\mathbb{Q}}$, in the connected component $\mathcal{C}$, the
cliques appear in clockwise direction starting from $Q_{1}$ as
$Q_{1},Q_{2},\ldots$ etc. We denote $(Q_{1},Q_{2},\ldots)$ from $\mathcal{C}$
by ${\mathbb{Q}_{\mathcal{C}}}$.

###### Reduction Rule 3

Let $v$ be a vertex in $T$. If $v$ is contained in at least $k+1$ distinct
claws $(v,a_{i},b_{i},c_{i})$ intersecting exactly at $\\{v\\}$, where
$a_{i},b_{i},c_{i}\in V(G)\setminus T$ then delete $v$ from $G$, and reduce
$k$ by $1$. The resultant instance is $(G-v,k-1)$.

The correctness of the above reduction rule is easy to see as every solution
to $(G,k)$ of PHCAVD must contain the vertex $v$. From here onward we assume
that the reduction rule 3 is no longer applicable.

###### Reduction Rule 4

Let $v$ be a vertex in $T$. If $v$ has neighbors in more than $6(k+1)$
different $Q_{i}$’s ($a_{i}$’s being the corresponding neighbors), then remove
$v$ from $G$ and reduce $k$ by $1$. The resultant instance is $(G-v,k-1)$.

###### Lemma 11

Reduction Rule 4 is safe.

###### Proof

By the pigeonhole principle, there are at least $3(k+1)$ non-consecutive
cliques that have neighbors of $v$. Let these non-consecutive cliques be
denoted by $(Q_{1}^{\prime},Q_{2}^{\prime},\ldots)$. Now we can construct a
set of $k+1$ mutually distinct claws formed by $\\{v,a_{i},a_{i+1},a_{i+2}\\}$
intersecting exactly and only at $\\{v\\}$ where each $a_{j}\in
Q_{j}^{\prime}$. But this implies that any solution to $(G,k)$ of PHCAVD must
contain the vertex $v$. ∎

From now on, we assume that the reduction rules 3 and 4 are no longer
applicable i.e. every vertex $v\in T$ has neighbors in at most $6(k+1)$
different $Q_{i}$’ from ${\mathbb{Q}_{\mathcal{C}}}$. And we have the
following result.

###### Lemma 12

Let $\cal C$ be a connected component in $G-T$. Then there are at most
$6(k+1)|T|$ many distinct cliques $Q_{i}$’s from ${\mathbb{Q}_{\mathcal{C}}}$
such that $N(T)\cap Q_{i}\neq\emptyset$.

If ${\mathbb{Q}_{\mathcal{C}}}$ has more than $300|T|k(k+1)$ cliques, then by
the pigeonhole principle and lemma 12, there are at least $50k$ consecutive
cliques that do not contain any vertex from $N(T)$. Let
$Q_{1},Q_{2},\ldots,Q_{50k}$ be the set of $50k$ such consecutive cliques in
${\mathbb{Q}_{\mathcal{C}}}$ which are disjoint from $N(T)$. Let
$\mathcal{D}_{L}=\\{Q_{i}\mid i\in[15k,20k]\\}$ ,
$\mathcal{D}_{R}=\\{Q_{i}\mid i\in[30k,35k]\\}$, $F=\\{Q_{i}\mid
i\in[20k+1,30k-1]\\}$ and $Z=\mathcal{D}_{L}\cup\mathcal{D}_{R}\cup F$.
Observe that, for a vertex $v\in Z$ and a vertex $u\in T$,
$\text{dist}_{G}(u,v)\geq 15k$. And hence there can not be any _small_
obstruction containing vertices from $Z$ (2) which we will use to our
advantage in many proofs throughout the current section. Let $\tau$ be the
size of minimum $(Q_{20k}-Q_{30k})$ cut in ${\mathbb{Q}_{\mathcal{C}}}$.

###### Reduction Rule 5

Let $F$ be as defined above. Delete all the vertices of $F$ from $G$.
Introduce a new clique $S$ of size $\tau$. Also, add edges such that
$G[V(Q_{20k})\cup S]$ and $G[V(Q_{30k})\cup S]$ are complete graphs. The
cliques appear in the order $Q_{20k},S,Q_{30k}$.

Figure 3: Description of reduction rule 5.

Let $G^{\prime}$ be the reduced graph after application of the reduction rule
5. For an illustration, see fig. 3. Notice that $G^{\prime}-T$ is a proper
Helly circular-arc graph by construction.

###### Observation 2

There are no _small_ obstructions containing any vertices from
$\mathcal{D}_{L}\cup F\cup\mathcal{D}_{R}$ in $G$. Similarly, there are no
_small_ obstructions containing vertices of $\mathcal{D}_{L}\cup
S\cup\mathcal{D}_{R}$ in $G^{\prime}$.

###### Proof

Let ${\mathbb{O}}$ be a _small_ obstruction in $G$ such that
$V({\mathbb{O}})\cap(\mathcal{D}_{L}\cup F\cup\mathcal{D}_{R})\neq\emptyset$.
Since for any vertex $v\in\mathcal{D}_{L}\cup F\cup\mathcal{D}_{R}$ and a
vertex $u\in T$, $\text{dist}_{G}(u,v)\geq 15k$ and $|{\mathbb{O}}|\leq 12$,
hence $V({\mathbb{O}})\cap T=\emptyset$. But this is a contradiction, since
$G-T$ has no obstructions. So there are no _small_ obstructions containing any
vertices from $\mathcal{D}_{L}\cup F\cup\mathcal{D}_{R}$.

Let ${\mathbb{O}}^{\prime}$ be a _small_ obstruction in $G^{\prime}$ such that
$V({\mathbb{O}}^{\prime})\cap(\mathcal{D}_{L}\cup
S\cup\mathcal{D}_{R})\neq\emptyset$, Since for any vertex
$v\in\mathcal{D}_{L}\cup S\cup\mathcal{D}_{R}$ and a vertex $u\in T$,
$\text{dist}_{G^{\prime}}(u,v)\geq 15k$ and $|{\mathbb{O}}^{\prime}|\leq 12$,
hence $V({\mathbb{O}}^{\prime})\cap T=\emptyset$. But this is a contradiction,
since $G^{\prime}-T$ has no obstructions. So there are no _small_ obstructions
containing any vertices from $\mathcal{D}_{L}\cup S\cup\mathcal{D}_{R}$.∎

###### Observation 3

Any M-Hole $H$ of a Monad with a centre $v$ in $G$ which contains a vertex
from $\mathcal{D}_{L}\cup F\cup\mathcal{D}_{R}$, intersects all cliques in
$\mathcal{D}_{L}\cup F\cup\mathcal{D}_{R}$. And such an $H$ has size at least
$20k$.

###### Proof

Without loss of generality suppose $H$ intersects $Q_{i}$ but does not
intersect some $Q_{i+1}\in Z$. Then the clique $Q_{i^{\prime}}$ where
$i^{\prime}=i-1$ contains at least two vertices from $H$. This is only
possible when $H$ has size at most four (since it is a Monad). But then $H$
along with any vertex from $Q_{i-3}$ or $Q_{i+2}$ will form a _small_
obstruction completely contained in $G-T$, which is not possible. Hence $H$
intersects all cliques in $\mathcal{D}_{L}\cup F\cup\mathcal{D}_{R}$.∎

###### Observation 4

Any M-Hole $H$ of a Monad with a centre $v$ in $G^{\prime}$ which contains a
vertex from $\mathcal{D}_{L}\cup S\cup\mathcal{D}_{R}$, intersects all cliques
in $\mathcal{D}_{L}\cup S\cup\mathcal{D}_{R}$. And such an $H$ has size at
least $20k$.

###### Proof

Proof is similar to the proof for 3.∎

###### Lemma 13

Reduction Rule 5 is safe.

###### Proof

We show that $(G,k)$ is a Yes-instance of PHCAVD if and only if
$(G^{\prime},k)$ is a Yes-instance of PHCAVD.

$(\Rightarrow)$ Suppose $(G,k)$ is a Yes-instance and let $X$ be a minimum
size solution. Recall that ${\cal D}_{L}$ and ${\cal D}_{R}$ contain $(5k+1)$
cliques each and $\tau$ is the size of minimum $(Q_{20k}-Q_{30k})$ cut. We
note that this cut may include the vertices from $Q_{20k}$ and $Q_{30k}$. Let
$W$ be the set of vertices from all the cliques in $Q_{20k+1}\cup\ldots\cup
Q_{30k-1}$.

###### Claim

Either $X\cap W=\emptyset$ or $|X\cap W|=\tau$.

###### Proof

Suppose that $X\cap W\neq\emptyset$ and $|X\cap W|<\tau$. Let $v\in X\cap W$.
As $X$ is also a minimal solution, for every vertex $u\in X$, there exists an
obstruction that does not contain any other vertex from $X$. This implies that
there exists a Monad containing $v$ and not containing any vertex from
$X\setminus\\{v\\}$. We first show that $v$ can not be centre of such a Monad.
If it is a centre of Monad $H\cup\\{v\\}$, then from 4, $H\cap Z=\emptyset$.
But in $Z$ we have $k+1$ many cliques and each vertex of them can create an
obstruction (Monad) with $H$ as an M-Hole. Hence $X\cap H$ can not be empty,
which is a contradiction to the fact that $X$ was a minimal solution. So the
obstruction for $v$ must contain $v$ as one of its M-Hole vertices i.e. $v\in
V(H)$. Let the centre of this obstruction be $z$. Notice that $X\cap
H=\\{v\\}$. In the M-Hole $H$, let $v_{1}$ and $v_{2}$ be two vertices from
$Q_{20k}$ and $Q_{30k}$ respectively with no other vertex from $Q_{20k}\cup
Q_{30k}$ in between. Between $v_{1}$ and $v_{2}$, we have $\tau$ many vertex
disjoint (induced) paths, say $\cal P$ in $W$. Since $|X\cap W|<\tau$, it does
not intersect at least one of the paths from $\cal P$. But then replacing the
segment of $H$ between $v_{1}$ and $v_{2}$ with the non-intersected path, we
get a new M-Hole $H^{\prime}$ where $X\cap H^{\prime}=\emptyset$. Adding $z$
as centre, we get an obstruction $H^{\prime}\cup{z}$ which is contained in
$G-X$, a contradiction. Hence $|X\cap W|\geq\tau$. If $|X\cap W|>\tau$, we
construct a new set $X^{\prime}=(X\setminus W)\cup X^{\prime\prime}$, where
$X^{\prime\prime}$ is a $\tau$ sized min-cut between $Q_{20k}$ and $Q_{30k}$,
We claim that $G-X^{\prime}$ is also a proper Helly circular-arc graph. If
not, then there is an obstruction in $G-X^{\prime}$. But such an obstruction
must necessarily contain a vertex from $X\cap W$. Any obstruction containing a
vertex $v\in X\cap W$ is a _large_ obstruction. If this obstruction contains
$v$ as centre, then by arguments similar to the ones made just above, we can
say that $X\setminus W$ also intersects this obstruction, and hence so does
$X^{\prime}$. On the other hand, if the obstruction contains $v$ as a vertex
in its M-Hole, then such an obstruction is hit by the min-cut between
$Q_{20k}$ and $Q_{30k}$ in $X^{\prime}$. But $X^{\prime}$ is a strictly
smaller solution than $X$, which is a contradiction. Hence the claim is
proved.

Using the above claim we consider the following cases: Recall that $X$ is a
solution to the Yes-instance $(G,k)$.

Case 1: $X\cap W=\emptyset$
Here we claim that $X$ is also a solution to $(G^{\prime},k)$. Suppose it is
not true. Then there is an obstruction ${\mathbb{O}}$ in $G^{\prime}-X$. Now
$V({\mathbb{O}})\cap S\neq\emptyset$, otherwise we will have the same
obstruction in $G-X$. Hence this obstruction must be a _large_ obstruction
(from arguments similar to the ones made in 3). Let $v\in({\mathbb{O}}\cap
S)$. If $v$ is a centre in ${\mathbb{O}}$, then $H$ ($H$ is the M-Hole of
${\mathbb{O}}$) is contained in $G-(Z\cup X)$. But any vertex from any clique
between $Q_{24k}$ and $Q_{26k}$ with $H$ will form an obstruction in $G-X$.
Notice that all these (at least) $2k$ vertices, each form an obstruction with
$H$. Hence $X$ must intersect $H$, which is a contradiction to the fact that
$H\cup\\{v\\}$ does not contain any vertex from $X$. For the other case, when
$v$ is part of the M-Hole in ${\mathbb{O}}$, let $v_{1}$ and $v_{2}$ be two
vertices of $H$ from $Q_{20k}$ and $Q_{30k}$ respectively with no other vertex
from $Q_{20k}\cup Q_{30k}$ in between. Since $X$ does not intersect any vertex
from $W$, replacing the segment of $H\cap S$ with a path between $v_{1}$ and
$v_{2}$, we get a new M-Hole $H^{\prime}$, where $X\cap H^{\prime}=\emptyset$.
Adding $z$ as a centre we get an obstruction $H^{\prime}\cup{z}$ which is
contained in $G-X$, a contradiction.

Case 2: $|X\cap W|=\tau$
Here we claim that $X^{\prime}=(X\setminus W)\cup S$ is also a solution to
$(G^{\prime},k)$. Suppose it is not true. Then there is an obstruction
${\mathbb{O}}$ in $G^{\prime}-X^{\prime}$. But then $V({\mathbb{O}})\cap
W\neq\emptyset$. And this obstruction must be a _large_ obstruction (from
arguments similar to the ones made in 3. Let $v\in({\mathbb{O}}\cap W)$. The
vertex $v$ must be a centre in ${\mathbb{O}}$, since $S$ (and hence
$X^{\prime}$) intersects all paths between $Q_{20k}$ and $Q_{30k}$. But then
$H$ ($H$ is the M-Hole of ${\mathbb{O}}$) is contained in $G-(Z\cup X)$. And
there are at least $k+1$ vertices in $Z$ each of which an obstruction with $H$
and at least one of them, say $u$ is not contained in $X$. Hence $u$ along
with $H$ forms a Monad that is contained in $G-X$, a contradiction. Hence
$X^{\prime}$ is also a solution to $(G^{\prime},k)$. This completes the proof
in the forward direction.

$(\Leftarrow)$ Suppose $(G^{\prime},k)$ is a Yes-instance of PHCAVD where $Y$
is a minimum size solution. Let $Z^{\prime}=\mathcal{D}_{L}\cup
S\cup\mathcal{D}_{R}$.

###### Claim

Either $Y\cap S=\emptyset$ or $|Y\cap S|=\tau$.

###### Proof

Suppose that $Y\cap S\neq\emptyset$ and $|Y\cap S|<\tau$. Let $v\in Y\cap S$.
As $Y$ is a minimal solution, for every vertex $u\in Y$, there exists an
obstruction that does not contain any vertex from $Y\setminus\\{u\\}$. This
implies that there exists a Monad containing $v$ and not containing any vertex
in $Y\setminus\\{v\\}$. We first show that $v$ can not be a centre of such an
obstruction. If it is a centre of an obstruction induced by $H\cup\\{v\\}$,
then by 2 $H\cap Z^{\prime}=\emptyset$. But then in $Z^{\prime}$ we have $k+1$
many distinct cliques and each vertex from these cliques can form obstruction
with $H$ as a centre. Hence $Y\cap H$ can not be empty, which is a
contradiction to the fact that $Y$ was a minimal solution. So the obstruction
for $v$ must contain $v$ as one of its M-Hole vertices i.e. $v\in H$. Let the
centre of this obstruction be $z$. Notice that $Y\cap H=\\{v\\}$. In the
M-Hole $H$, let $v_{1}$ and $v_{2}$ be two vertices from $Q_{20k}$ and
$Q_{30k}$ respectively with no other vertex from $Q_{20k}\cup Q_{30k}$ in
between. Between $v_{1}$ and $v_{2}$ we have $\tau$ many vertex disjoint
(induced) paths ($\cal P$) (each path consists of exactly one vertex from
$S$). $Y$ does not intersect at least one of these paths from $\cal P$. But
then replacing the segment of $H$ between $v_{1}$ and $v_{2}$ with the non-
intersected path from $\cal P$, we get a new M-Hole $H^{\prime}$ where $Y\cap
H^{\prime}=\emptyset$. Adding $z$ as the centre, we get an obstruction
$H^{\prime}\cup{z}$ which is contained in $G^{\prime}-Y$, a contradiction.
Hence $Y\cap S=\tau$. Hence the claim is proved.

Using the above claim we consider the following cases: Recall that $Y$ is a
minimum size solution to the Yes-instance $(G^{\prime},k)$.

Case 1: $Y\cap S=\emptyset$
Here we claim that $Y$ is also a solution to $(G,k)$. Suppose it is not true.
Then there is an obstruction ${\mathbb{O}}$ in $G-Y$. ${\mathbb{O}}\cap
W\neq\emptyset$, otherwise we will have the same obstruction in
$G^{\prime}-Y$. Hence this obstruction must be a _large_ obstruction (from
arguments similar to the ones made in 4). Let $v\in({\mathbb{O}}\cap W)$. If
$v$ is a centre in ${\mathbb{O}}$, then $H$ ($H$ is the M-Hole of
${\mathbb{O}}$) is contained in $G-(Z^{\prime}\cup Y)$. But there are at least
$k+1$ vertices from $Z^{\prime}$ who along with $H$ form obstructions in
$G^{\prime}-Y$. Hence $Y$ must intersect $H$, which contradicts the fact that
$H\cup\\{v\\}$ is an obstruction in $G-Y$ . For the other case when $v$ is
part of the M-Hole in ${\mathbb{O}}$, let $v_{1}$ and $v_{2}$ be two vertices
from $Q_{20k}$ and $Q_{30k}$ respectively with no other vertex from
$Q_{20k}\cup Q_{30k}$ in between in $H$. Since $Y$ does not contain any vertex
from $S$, by replacing the segment of $H$ between $v_{1}$ and $v_{2}$ with any
vertex of $S$, we get a new M-Hole $H^{\prime}$ where $Y\cap
H^{\prime}=\emptyset$. Adding $z$ as the centre we get an obstruction
$H^{\prime}\cup{z}$ which is contained in $G^{\prime}-Y$, which is a
contradiction.

Case 2: $|Y\cap S|=\tau$
Here we claim that $Y^{\prime}=(Y\setminus S)\cup Y^{\prime\prime}$, where
$Y^{\prime\prime}$ is a $\tau$ sized min-cut between $Q_{20k}$ and $Q_{30k}$,
is a solution to $(G,k)$. Suppose it is not true. Then there is an obstruction
${\mathbb{O}}$ in $G-Y^{\prime}$. But ${\mathbb{O}}\cap W\neq\emptyset$ and
${\mathbb{O}}$ must be a _large_ obstruction (from arguments similar to the
ones made in 4). Let $v\in({\mathbb{O}}\cap W)$. Since there is no path from
$Q_{20k}$ to $Q_{30k}$ in $G-Y^{\prime}$, any obstruction must contain $v$ as
its centre only. But then $H$ ($H$ is the M-Hole of ${\mathbb{O}}$) is
contained in $G-(Z\cup Y^{\prime})$ and hence also in
$G^{\prime}-(Z^{\prime}\cup Y)$. And there are $k+1$ many vertices in
$Z^{\prime}$ who can form obstructions with the M-Hole $H$. At least one of
them is not contained in $Y$. This vertex along with $H$ forms an obstruction
that is contained in $G^{\prime}-Y$, a contradiction. Hence $Y$ is also a
solution to $(G,k)$. This completes the proof in the reverse direction.

This concludes the proof for the lemma.∎

With reduction rule 5, we obtain the following result.

###### Lemma 14

Given an instance $(G,k)$ of PHCAVD and a nice modulator $T\subseteq V(G)$ of
size $k^{\mathcal{O}(1)}$, in polynomial time, we can construct an equivalent
instance $(G^{\prime},k)$ such that, $T\subseteq V(G^{\prime})$ is a nice
modulator for $G^{\prime}$ and for each connected component $\mathcal{C}$ of
$G^{\prime}-T$, the number of cliques in ${\mathbb{Q}_{\mathcal{C}}}$ is at
most $300\cdot|T|\cdot k(k+1)=\mathcal{O}(k^{2}\cdot{|{T}|})$.

##  7 Bounding the Number of Connected Components

Until now we have assumed that $G-T$ is connected. Further, in section 6, we
showed that the size of any connected component is upper bounded by
$k^{\mathcal{O}(1)}$. In this section, we show that the number of connected
components in $G-T$ can be upper bounded by $k^{\mathcal{O}(1)}$. This
together with the fact that $|T|\leq k^{\mathcal{O}(1)}$, results in a
polynomial kernel for PHCAVD.

Here we bound the number of connected components with an argument similar to
the one using which we bounded the neighborhood of the modulator. We make use
of the claw obstruction to get the desired bound. Notice that if any vertex
$v$ in $T$ has neighbors in three different components in $G-T$, then we get a
claw.

###### Reduction Rule 6

Let $v$ be a vertex in $T$ such that $v$ has neighbors in at least $3(k+1)$
different components in $G-T$ then delete $v$ from $G$, and reduce $k$ by $1$.
The resultant instance is $(G-v,k-1)$.

The correctness of the above reduction rule is easy to see as every solution
to $(G,k)$ of PHCAVD must contain $v$. From now onwards we assume that
reduction rule 6 is not applicable. And this leads to the following lemma.

###### Lemma 15

$T$ can have neighbors in at most $3(k+1)|T|$ many different components.

Now we bound the number of connected components that have no neighbor in $T$.
Towards that, we classify all such connected components into two classes:
interval connected components (which admit an interval representation) and
non-interval connected components. Here non-interval connected components
cover the entire circle whereas others partially cover the underlying circle.

###### Claim 1

The number of non-interval connected components in $G-T$ is at most one.

###### Proof

For contradiction suppose there are at least two non-interval connected
components $C_{1},C_{2}$ in $G-T$. Notice that in any proper Helly circular-
arc representation $\sigma$ of $G-T$, the circular-arcs corresponding to all
the vertices in $C_{1}$ together cover the entire circle in the
representation. But then there is no other connected component in $G-T$ that
can admit arc representation $\sigma$. Hence $C_{2}$ can not have any
circular-arc representation in $\sigma$, a contradiction.∎

###### Reduction Rule 7

If there are more than $(k+1)$ interval connected components in $G-T$ that
have no neighbor in $T$, delete all but $(k+1)$ components.

###### Lemma 16

Reduction Rule 7 is safe.

###### Proof

Let $(G^{\prime},k)$ be the reduced instance. We show that $(G,k)$ is a Yes-
instance of PHCAVD if and only if $(G^{\prime},k)$ is a Yes-instance. The
forward direction is trivial as $G^{\prime}$ is an induced subgraph of $G$. In
the backward direction, let $(G^{\prime},k)$ be a Yes-instance. Assume that
$X$ is a solution for PHCAVD on $(G^{\prime},k)$ and $\sigma$ is a proper
Helly circular-arc representation of $G^{\prime}-X$. As there are $(k+1)$
interval connected components in $G-T$ there always exists a component $C$ in
$G-T$ which has no intersection with $X$ and hence all the vertices in $C$
belong to $G^{\prime}-X$. Now we can always shrink all the arcs corresponding
to $C$ in $\sigma$ to half of their length. In the freed-up space, we can
accommodate the arcs corresponding to the deleted interval connected
components. Hence $(G,k)$ is a Yes-instance.∎

From now onwards we assume that reduction rules 6 and 7 are not applicable.
Now these two reduction rules and lemma 15 implies the following result:

###### Lemma 17

Given an instance $(G,k)$ and a nice modulator $T\subseteq V(G)$ of size
$\mathcal{O}(k^{12})$, in polynomial-time, we can construct an equivalent
instance $(G^{\prime},k^{\prime})$ such that the number of connected component
in $G^{\prime}-T$ is $\mathcal{O}(k\cdot|T|^{2})$.

##  8 Kernel size analysis

Now we are ready to prove the main result of our paper, that is, theorem 1.1.
Before proceeding with the proof, let us state all the bounds that contributes
to the kernel size.

Size of _nice modulator_ $T$: $\mathcal{O}(k^{12})$ (from section 4). Number
of connected components in $G-T$: $\mathcal{O}(k\cdot{{|{T}|}}^{2})$ (by lemma
17). Number of cliques in any connected component in $G-T$:
$\mathcal{O}(k^{2}\cdot|T|)$ (by lemma 14). Size of any clique
${\mathcal{Q}_{i}}$ in $G-T$: $2(k+1){|{T}|}^{4}$ (by remark 1).

######  Proof (Proof of theorem 1.1)

From lemma 2 and lemma 7, in polynomial-time, we can obtain a _nice modulator_
$T\subseteq V(G)$ of size $\mathcal{O}(k^{12})$ or conclude that $(G,k)$ is a
No-instance. Note that, $G-T$ is a proper Helly circular-arc graph. Next, we
take a _nice clique partition_ of $G-T$. Now by lemma 17, in polynomial-time
we return a graph $G$ such that $G-T$ has $\mathcal{O}(k\cdot|T|^{2})$
components. By Lemma lemma 14, in polynomial-time, we can reduce the graph $G$
such that any connected component in $G-T$ has at most
$\mathcal{O}(k^{2}\cdot|T|)$ cliques. Next, we bound the size of each clique
in $G-T$ by $2(k+1){|{T}|}^{4}$ from lemma 10. Hence the graph $G-T$ has at
most $\mathcal{O}(k\cdot|T|^{2})\cdot\mathcal{O}(k^{2}\cdot|T|)\cdot
2(k+1){|{T}|}^{4}$, that is, $\mathcal{O}(k^{4}\cdot|T|^{7})$ many vertices.
Recall that $|T|=\mathcal{O}(k^{12})$. Therefore, the size of the obtained
kernel is $\mathcal{O}(k^{4}\cdot|T|^{7})$, that is, $\mathcal{O}(k^{88})$. ∎

##  9 Conclusion

In this paper, we studied PHCAVD from the perspective of kernelization
complexity, and designed a polynomial kernel of size $\mathcal{O}(k^{88})$. We
remark that the size of a kernel can be further optimized with more careful
case analysis. However, getting a kernel of a significantly smaller size might
require an altogether different approach.

## References

  * [1] Akanksha Agrawal, Daniel Lokshtanov, Pranabendu Misra, Saket Saurabh, and Meirav Zehavi.  Feedback Vertex Set Inspired Kernel for Chordal Vertex Deletion.  In (SODA 2017), pages 1383–1398, 2017.
  * [2] Akanksha Agrawal, Pranabendu Misra, Saket Saurabh, and Meirav Zehavi.  Interval vertex deletion admits a polynomial kernel.  In Timothy M. Chan, editor, SODA 2019, San Diego, California, USA, pages 1711–1730. SIAM, 2019.
  * [3] Hans L. Bodlaender, Rodney G. Downey, Michael R. Fellows, and Danny Hermelin.  On problems without polynomial kernels.  Journal of Computer and System Sciences, 75(8):423–434, 2009\.
  * [4] Yixin Cao, Hanchun Yuan, and Jianxin Wang.  Modification Problems Toward Proper (Helly) Circular-Arc Graphs.  In Jérôme Leroux, Sylvain Lombardy, and David Peleg, editors, MFCS 2023, volume 272 of LIPIcs, pages 31:1–31:14. Schloss Dagstuhl, 2023.
  * [5] Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Daniel Lokshtanov, Daniel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh.  Parameterized Algorithms.  Springer-Verlag, 2015.
  * [6] Reinhard Diestel.  Graph Theory, 4th Edition, volume 173 of Graduate texts in mathematics.  Springer, 2012.
  * [7] Rodney G. Downey and Michael R. Fellows.  Parameterized Complexity.  Monographs in Computer Science. Springer, 1999.
  * [8] Rodney G. Downey and Michael R. Fellows.  Fundamentals of Parameterized Complexity.  Texts in Computer Science. Springer, 2013.
  * [9] Guillermo Durán, Luciano N Grippo, and Martín D Safe.  Structural results on circular-arc graphs and circle graphs: a survey and the main open problems.  Discrete Applied Mathematics, 164:427–443, 2014.
  * [10] Jörg Flum and Martin Grohe.  Parameterized Complexity Theory.  Texts in Theoretical Computer Science. An EATCS Series. Springer, 2006\.
  * [11] Fedor V. Fomin, Saket Saurabh, and Yngve Villanger.  A polynomial kernel for proper interval vertex deletion.  SIAM J. Discret. Math., 27(4):1964–1976, 2013.
  * [12] Martin Charles Golumbic.  Algorithmic Graph Theory and Perfect Graphs.  Academic Press, 1980.
  * [13] Haim Kaplan and Yahav Nussbaum.  Certifying algorithms for recognizing proper circular-arc graphs and unit circular-arc graphs.  Discrete Applied Mathematics, 157(15):3216–3230, 2009.
  * [14] Yuping Ke, Yixin Cao, Xiating Ouyang, Wenjun Li, and Jianxin Wang.  Unit interval vertex deletion: Fewer vertices are relevant.  J. Comput. Syst. Sci., 95:109–121, 2018.
  * [15] R. Krithika, Abhishek Sahu, Saket Saurabh, and Meirav Zehavi.  The parameterized complexity of cycle packing: Indifference is not an issue.  Algorithmica, 81(9):3803–3841, 2019.
  * [16] Min Chih Lin, Francisco J. Soulignac, and Jayme Luiz Szwarcfiter.  Normal Helly circular-arc graphs and its subclasses.  Discret. Appl. Math., 161(7-8):1037–1059, 2013.
  * [17] Min Chih Lin and Jayme L Szwarcfiter.  Characterizations and recognition of circular-arc graphs and subclasses: A survey.  Discrete Mathematics, 309(18):5618–5635, 2009.
  * [18] Min Chih Lin and Jayme Luiz Szwarcfiter.  Characterizations and Linear Time Recognition of Helly Circular-Arc Graphs.  In Danny Z. Chen and D. T. Lee, editors, COCOON 2006, volume 4112 of LNCS, pages 73–82. Springer, 2006.
  * [19] Dániel Marx.  Chordal Deletion is Fixed-Parameter Tractable.  Algorithmica, 57(4):747–768, 2010.
  * [20] Ross M McConnell.  Linear-time recognition of circular-arc graphs.  Algorithmica, 37(2):93–147, 2003.
  * [21] Rolf Niedermeier.  Invitation to Fixed-Parameter Algorithms.  Oxford University Press, 2006.