# Modification Problems
toward Proper (Helly) Circular-arc Graphs

Yixin Cao School of Computer Science and Engineering, Central South
University, Changsha, China.Department of Computing, Hong Kong Polytechnic
University, Hong Kong, China<EMAIL_ADDRESS>Jianxin
Wang11footnotemark: 1 Hanchun Yuan11footnotemark: 1

###### Abstract

We present a $9^{k}\cdot n^{O(1)}$-time algorithm for the proper circular-arc
vertex deletion problem, resolving an open problem of van ’t Hof and Villanger
[Algorithmica 2013] and Crespelle et al. [arXiv:2001.06867]. Our structural
study also implies parameterized algorithms for modification problems toward
proper Helly circular-arc graphs.

##  1 Introduction

A graph is a _circular-arc graph_ if its 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 another,
then the graph is a _proper circular-arc graph_. See Figure 1 for two examples
of proper circular-arc graphs. Proper circular-arc graphs “form an important
subclass of the class of all claw-free graphs,” and their study has been an
important step towards finding “a structural characterization of all claw-free
graphs” [7]. The structures and recognition of proper circular-arc graphs have
been well studied and well understood [19, 9].

$u_{1}$$v_{1}$$u_{2}$$v_{2}$$u_{3}$$v_{3}$

$v_{1}$$v_{2}$$v_{3}$$u_{1}$$u_{2}$$u_{3}$

(a) $S_{3}$

$v_{5}$$v_{1}$$v_{2}$$v_{3}$$v_{4}$

$v_{1}$$v_{2}$$v_{3}$$v_{4}$$v_{5}$

(b) $W_{4}$

Figure 1: Two proper circular-arc graphs and their arc representations.

Another and earlier motivation of studying (proper) circular-arc graphs is
from their relation with (proper) interval graphs, i.e., intersection graphs
of intervals on the real line. It is easy to see that each (proper) interval
graph is a (proper) circular-arc graph, and the connection of these classes
has been used in both structural and algorithmic studies of these classes.
Indeed, the first linear-time recognition algorithm for proper circular-arc
graphs is based on a general observation of both proper circular-arc graphs
and proper interval graphs [9]. Neither graph in Figure 1 is a proper interval
graph, but removing any vertex from Figure 1(a), or any vertex but $v_{5}$
from Figure 1(b) leaves a proper interval graph.

Let $\mathcal{G}$ be a graph class. Given a graph $G$ and an integer $k$, the
$\mathcal{G}$ vertex deletion problem asks whether we can remove $k$ vertices
from $G$ to make a graph in $\mathcal{G}$. These problems have been
intensively studied in the framework of parameterized computation. Suppose
that the input graph has $n$ vertices and $m$ edges. We say that a graph
problem is fixed-parameter tractable (FPT) if there is an algorithm solving it
in time $f(k)\cdot n^{O(1)}$, where $f$ is a computable function depending
only on $k$ [10]. For example, it is well known that the proper interval
vertex deletion problem is FPT[20, 3]. In the algorithm of van ’t Hof and
Villanger [20], the kinship between proper circular arc graphs and proper
interval graphs plays a crucial role. They show that it suffices to destroy
all the small forbidden induced subgraphs, and then the graph is already a
proper circular-arc graph, on which the proper interval vertex deletion
problem can be solved in linear time. They asked whether the proper circular
arc vertex deletion problem is FPT as well, and this open problem was recently
raised again by Crespelle et al. [8]. We answer this question affirmatively.

######  Theorem 1.1.

The proper circular-arc vertex deletion problem can be solved in time
$9^{k}\cdot n^{O(1)}$.

A major difference between the class of proper interval graphs and the class
of proper circular-arc graphs is that the later class is not closed under
disjoint union. This can be easily observed from their representations: while
we can always put intervals for two different components side by side, no such
accommodation is possible for two set of arcs if one set of them covers the
whole circle. As a matter of fact, if a proper circular-arc graph is not
connected, it has to be a proper interval graph. (The same remark applies to
the relation between circular-arc graphs and interval graphs.)

If a proper circular-arc graph contains a hole of length at least five, then
its property is quite similar to a proper interval graph. What is difficult is
when a few arcs cover the whole circle in an arc representation. For such a
graph, it is more convenient to study its complement. Indeed, when
characterizing proper circular-arc graphs, Tucker [19] actually listed the
forbidden induced subgraphs of the complement class. He also observed that if
the complement $\overline{G}$ of a proper circular-arc graph $G$ is not
connected, then $\overline{G}$ is bipartite. _Permutation graphs_ are the
intersection graphs of line segments between two parallel lines, and
_bipartite permutation graphs_ are those permutation graphs that are
bipartite. Bipartite permutation graphs are also known as proper interval
bigraphs and unit interval bigraphs [16]. It is well known that a co-bipartite
graph $H$ is a proper circular-arc graph if and only if $\overline{H}$ is
bipartite permutation graph.

Let $(G,k)$ be an instance to the proper circular-arc vertex deletion problem,
and let $V_{-}$ be a solution. If $G-V_{-}$ is not connected, then it is a
proper interval graph; if ${G-V_{-}}$ is not co-connected, then it is the
complement of a bipartite permutation graph. We can call the algorithm of Cao
[3] and the algorithm of Bożyk et al. [1] to check whether such a set $V_{-}$
exists, and we are done if it does. In the rest we may assume that $G-V_{-}$
is neither a proper interval graph nor the complement of a bipartite graph,
hence both connected and co-connected. For this purpose we may assume that $G$
itself is both connected and co-connected; otherwise, there is a unique
component $C$ of $G$ or $\overline{G}$ such that $V(G)\setminus V(C)\subseteq
V_{-}$. Either the instance is trivially FPT, when $n=O(k)$, or it suffices to
consider the largest component of $G$ or $\overline{G}$.

The algorithm proceeds as follows. We can destroy all forbidden induced
subgraphs of order at most seven by branching. Now $G$ is free of small
forbidden induced subgraphs and is both connected and co-connected. Our key
observation is that if ${G}$ is not already a proper circular-arc graph, then
$\overline{G}$ must be bipartite. Note that any induced subgraph of a
bipartite graph is bipartite, but we have assumed that $G-V_{-}$ is not the
complement of a bipartite graph. Therefore, we are ready to directly return
“yes” or “no.”

Since the parameterized algorithm branches on a small set of vertices that
intersects every solution, we can easily turn it into an approximation
algorithm for the maximum proper circular-arc induced subgraph problem.

######  Theorem 1.2.

There is a polynomial-time approximation algorithm of approximation ratio $9$
for the minimization version of the proper circular-arc vertex deletion
problem.

Proper circular-arc graphs also arise naturally when we consider the clique
graph (the intersection graph of maximal cliques of a host graph) of a
circular-arc graph. The complicated structures of circular-arc graphs are
mainly due to the lack of the so-called _Helly_ property: every set of
pairwise intersecting arcs has a common intersection. For example, neither
representation in Figure 1 is Helly: the set $\\{v_{1},v_{2},v_{3}\\}$ in (a)
and the set $\\{v_{3},v_{4},v_{5}\\}$ in (b) violate the Helly property. A
graph is a _Helly circular-arc graph_ if it admits an arc representation that
is Helly. Since every interval representation is Helly, all interval graphs
are Helly circular-arc graphs. It is well known that the clique graph of an
interval graph, with at most $n$ maximal cliques, is a proper interval graph
[15]. The same upper bound holds for the number of maximal cliques in a Helly
circular-arc graph, and the clique graph of a Helly circular-arc graph is
always a proper circular-arc graph [11]. Let us remark parenthetically that a
circular-arc graph may have an exponential number of maximal cliques, e.g.,
the complement of the union of $p$ disjoint edges, which has $2p$ vertices,
each of degree $2p-2$.

A graph is a proper Helly circular-arc graph if and only if its clique matrix
has the circular-ones property for both rows and columns [18].

The class of proper Helly circular-arc graphs is sandwiched between proper
circular-arc graphs and proper interval graphs. This observation has been
crucial for our algorithms for modification problems toward proper interval
graphs [3]. A graph is a _proper Helly circular-arc graph_ if it has an arc
representation that is both proper and Helly. A word of caution is worth on
the definition of proper Helly circular-arc graphs. One graph might admit two
arc representations, one being proper and the other Helly, but no arc
representation that is both proper and Helly. For example, both
representations in Figure 1 are proper but neither is Helly, and it is not
difficult to make Helly arc representations for $S_{3}$ and $W_{4}$, but, as
the reader may easily verify, neither of them admits an arc representation
that is both proper and Helly. Therefore, the class of proper Helly circular-
arc graphs does not contain all those graphs being both proper circular-arc
graphs and Helly circular-arc graphs, but a proper subclass of it. Indeed, a
proper circular-arc graph is a proper Helly circular-arc graph if and only if
it is $\\{S_{3},W_{4}\\}$-free [17].

We then consider modification problems toward proper Helly circular-arc
graphs. For this class we consider also the edge deletion and completion
problems (a proof of their NP-completeness was provided in the appendix).
Again, we start by destroying all small forbidden induced subgraphs, up to six
vertices. We show that a connected graph free of such induced subgraphs is
already a proper Helly circular-arc graph. For the vertex deletion problem,
either we remove all but one component, or we remove vertices to get a proper
interval graph. The edge deletion problem is even simpler: if the graph is not
connected, we cannot make it connected by deleting edges. Thus, depending on
whether the graph is connected, either we are already done, or we are solving
the proper interval edge deletion problem. This idea can even solve the
general deletion problem that allows $k_{1}$ vertex deletions and $k_{2}$ edge
deletions. The situation is quite different for the completion problem. We are
happy if we can add at most $k$ edges to make the input graph a proper
interval graph. Otherwise, we have to make a connected proper Helly circular-
arc graph. After we have dealt with all the small forbidden induced subgraphs,
the only nontrivial case is when there is a large component, which contains a
long hole $H$, and several small components. We need to “attach” these small
components to vertices on $H$. Since these operations are local, we can find a
solution by dynamic programming. Thus, all the three problems are FPT, and
they can be done in linear FPT time. Again, the parameterized algorithm for
the vertex deletion problem can be easily turned into an approximation
algorithm.

######  Theorem 1.3.

For modification problems toward proper Helly circular-arc graphs, there are

  * •

an $O(6^{k}\cdot(m+n))$-time algorithm for the vertex deletion problem;

  * •

an $O(8^{k}\cdot(m+n))$-time algorithm for the edge deletion problem;

  * •

an $O(14^{k_{1}+k_{2}}\cdot(m+n))$-time algorithm for the deletion problem;
and

  * •

a $k^{O(k)}\cdot(m+n)$-time algorithm for the completion problem.

Moreover, there is an $O(nm+n^{2})$-time approximation algorithm of
approximation ratio $6$ for the minimization version of the proper Helly
circular-arc vertex deletion problem.

Somewhat surprisingly, modification problems toward circular-arc graphs and
its subclasses have not received sufficient attention. We hope our work will
inspire more study in this direction. Apart from the two classes in the
present paper, the next interesting class is the class of normal Helly
circular-arc graphs, a super class of proper Helly circular-arc graphs. They
have played crucial roles in solving modification problems to interval graphs
[6, 2]. Also related and probably simpler are the modification problems toward
unit (Helly) circular-arc graphs. It is well known that a graph is a proper
interval graph if and only if it is a unit interval graph. However, there are
proper (Helly) circular-arc graphs that are not unit (Helly) circular-arc
graphs, e.g., the graph obtained from an even hole of length at least eight by
adding edges to connect consecutive even-numbered vertices. We refer
interested readers to Lin et al. [18] and Cao [3] for the hierarchy of
subclasses of circular-arc graphs.

##  2 Preliminaries

All graphs discussed in this paper are undirected and simple. The vertex set
and edge set of a graph $G$ is denoted by, respectively, $V(G)$ and $E(G)$.
Let $n=|V(G)|$ and $m=|E(G)|$. A _walk_ in a graph $G$ is a sequence of
vertices and edges in the form of $v_{0}$, $v_{0}v_{1}$, $v_{1}$,
$v_{1}v_{2}$, $\ldots$, $v_{\ell}$. Since the edges are determined by the
vertices, such a walk can be denoted by $v_{0}v_{1}\ldots v_{\ell}$
unambiguously. We say that this walk connects $v_{0}$ and $v_{\ell}$, which
are the _ends_ of this walk, and refer to it as a $v_{0}$–$v_{\ell}$ walk. The
_length_ of a walk is the number of occurrences of edges it contains, and
$\ell$ in the previous example. A walk is _closed_ if $\ell>1$ and
$v_{0}=v_{\ell}$. A walk is a _path_ if all its vertices are distinct. A
closed walk of length $\ell$ is a _cycle_ if it visits precisely $\ell$
vertices; i.e., no repeated vertices except the two ends. A _hole_ is an
induced cycle of length at least four. A walk, path, cycle, or hole is _odd_
(resp., _even_) if its length is odd (resp., even). 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 no or all vertices on the
cycle, then we end with a $C_{\ell}^{*}$ or $W_{\ell}$, respectively.

The complement graph $\overline{G}$ of a graph $G$ is defined on the same
vertex set $V(G)$, where a pair of vertices $u$ and $v$ is adjacent in
$\overline{G}$ if and only if $uv\not\in E(G)$; e.g., $\overline{C_{5}^{*}}$
is ${W_{5}}$. The graph $\overline{C_{3}^{*}}$ is also called a _claw_. A
graph $G$ is _connected_ if every pair of vertices is connected by a path, and
_co-connected_ if $\overline{G}$ is connected.

A _circular-arc graph_ is the intersection graph of a set of arcs on a circle.
The set of arcs is called an _arc representation_ of this graph. In this
paper, all arcs are closed. An arc representation is _proper_ if no arc in it
properly contains another arc. A graph is a _proper circular-arc graph_ if it
has a proper arc presentation. In case that there is a point of the cycle
avoided by all the arcs in an arc representation, we can cut the circle and
straighten all the arcs into line segments. Such a graph is an _interval
graph_ , i.e., the intersection graph of a set of closed intervals on the real
line, and the set of intervals is an _interval representation_ of this graph.
Proper interval graphs are defined analogously. Clearly, any (proper) interval
representation can be viewed as a (proper) arc representation leaving some
point uncovered, and hence all (proper) interval graphs are always (proper)
circular-arc graphs.

(a) $S_{3}$ (tent)

(b) $\overline{S_{3}}$ (net)

(c) $F_{1}$ (long claw)

(d) $F_{2}$

(e) $F_{3}$

(f) $F_{4}$

Figure 2: Some small forbidden induced graphs.

Let $F$ be a fixed graph. We say that a graph $G$ is _$F$ -free_ if $G$ does
not contain $F$ as an induced subgraph. For a set $\mathcal{F}$ of graphs, a
graph $G$ is _$\mathcal{F}$ -free_ if $G$ is $F$-free for every
$F\in\mathcal{F}$. If every $F\in\mathcal{F}$ is minimal, i.e., not containing
any $F^{\prime}\in\mathcal{F}$ as a proper induced subgraph, then
$\mathcal{F}$ are the (minimal) _forbidden induced subgraphs_ of this class.
See Figure 2 for some of the forbidden induced subgraphs considered in the
present paper. We use $S_{3}^{*}$ to denote the graph obtained by adding an
isolated vertex to $S_{3}$.

######  Theorem 2.1 ([19]).

A graph is a proper circular-arc graph if and only if it is free of
$S_{3}^{*}$, $C_{\ell}^{*}$ with $\ell\geq 4$, as well as the complement of
$S_{3}$, $F_{1}$, $F_{2}$, $F_{3}$, $F_{4}$, ${C_{2\ell+2}}$, and
${C_{2\ell-1}^{*}}$ with $\ell\geq 2$.

Neither the class of circular-arc graphs nor the class of proper circular-arc
graphs is closed under taking disjoint unions. Indeed, if a (proper) circular-
arc graph $G$ is not a (proper) interval graph, then in any representation of
$G$, the union of the arcs covers the whole circle. Such a graph is
necessarily connected.

######  Proposition 2.2 (Folklore).

If a proper circular-arc graph $G$ is not connected, then $G$ is a proper
interval graph.

Proper circular-arc graphs have three infinite families of forbidden induced
subgraphs, namely, $\\{C_{\ell}^{*}\mid\ell\geq 4\\}$,
$\\{\overline{C_{2\ell+2}}\mid\ell\geq 2\\}$, and
$\\{\overline{C_{2\ell-1}^{*}}\mid\ell\geq 2\\}$. The first of them can be
ignored for connected graphs.

######  Lemma 2.3.

Let $G$ be a connected graph. If $G$ does not contain the complement of
$C_{3}^{*}$ or $S_{3}$, then $G$ is $\\{C_{\ell}^{*}\mid\ell\geq 5\\}$-free.

###### Proof.

Suppose for contradiction that there exist an induced cycle $C$ and a vertex
$v$ in $G$ with $|C|\geq 5$ and $V(C)\cap N(v)=\emptyset$. Since $G$ is
connected, we can find a shortest path from $v$ to $C$. Let the last three
vertices on this path be $x$, $y$, and $z$; note that $z$ is on $C$ and $x$ is
nonadjacent to any vertex on $C$. We may number the vertices on $C$ such that
$C=v_{1}v_{2}\cdots v_{|C|}$ and $z=v_{2}$. If $y$ is adjacent to only $v_{2}$
on $C$, then $\\{v_{1},v_{2},v_{3},y\\}$ induces a claw. If $y$ is also
adjacent to both $v_{1}$ and $v_{3}$, then $\\{v_{1},v_{3},x,y\\}$ induces a
claw, and it is similar if $y$ is adjacent to any three consecutive vertices
on $C$. Otherwise, $y$ is adjacent to precisely one of $v_{1}$ and $v_{3}$.
Without loss of generality, assume that $y$ is adjacent to $v_{3}$ but not
$v_{1}$. Note that $y$ is not adjacent to $v_{4}$ either, and then
$\\{v_{1},v_{2},v_{3},v_{4},x,y\\}$ induces a copy of the complement of
$S_{3}$. ∎

An arc representation is Helly if every set of pairwise intersecting arcs has
a common intersection. A circular-arc graph is _proper Helly_ if it has an arc
representation that is both proper and Helly.

######  Theorem 2.4 ([18]).

A proper circular-arc graph is a proper Helly circular-arc graph if and only
if it contains no $W_{4}$ or $S_{3}$.

Note that $S_{3}^{*}$ contains $S_{3}$, while all the complements of $F_{1}$,
$F_{2}$, $F_{3}$, $F_{4}$, and $\\{{C_{2\ell}},{C_{2\ell-1}^{*}}\mid\ell\geq
4\\}$ contain $W_{4}$. The following corollaries follow from Theorem 2.4,
together with Theorem 2.1 and Lemma 2.3, respectively.

######  Corollary 2.5 ([18]).

A graph is a proper Helly circular-arc graph if and only if it contains no
$\overline{C^{*}_{3}}$, $S_{3},\overline{S_{3}}$, $W_{4}$, $W_{5}$,
$\overline{C_{6}}$, or $C_{\ell}^{*}$ for $\ell\geq 4$.

######  Corollary 2.6.

Let $G$ be a connected graph. If $G$ does not contain $\overline{C_{3}^{*}}$,
$C_{4}^{*}$, $S_{3},\overline{S_{3}}$, $W_{4}$, $W_{5}$, or
$\overline{C_{6}}$, then $G$ is a proper Helly circular-arc graph.

Recall that proper interval graphs are precisely
$\\{\overline{C_{3}^{*}},S_{3},\overline{S_{3}},C_{\ell}\mid\ell\geq
4\\}$-free graphs.

######  Corollary 2.7.

Let $G$ be a proper Helly circular-arc graph. Then $G$ is a proper interval
graph if and only if $G$ does not contain any holes.

The following can be viewed as a constructive version of Corollary 2.6.

######  Proposition 2.8.

Let $G$ be a connected graph. In $O(m+n)$ time we can either detect an induced
subgraph in
$\\{\overline{C_{3}^{*}},C_{4}^{*},S_{3},\overline{S_{3}},W_{4},W_{5},\overline{C_{6}}\\}$,
or build a proper and Helly arc representation for $G$.

###### Proof.

We start by calling the certifying recognition algorithm for proper Helly
circular-arc graphs [4]. If a proper and Helly arc representation is found,
then we return it. In the rest, the algorithm returns a forbidden induced
subgraph. If the forbidden induced subgraph is one of
$\overline{C_{3}^{*}},C_{4}^{*},S_{3},\overline{S_{3}},W_{4},W_{5}$, and
$\overline{C_{6}}$, then we return its vertex set. Otherwise, the outcome must
be a $C_{\ell}^{*}$, where $\ell\geq 5$, and let $H=v_{1}\cdots v_{\ell}$ be
the hole and $v$ the isolated vertex. We can use breadth-first search to find
a shortest path from $v$ to $H$. Let $x$ and $y$ be the last two vertices on
this path that are not on $H$; note that $y$ is adjacent to $H$ while $x$ is
not. If $y$ has only one neighbor $v_{i}$ on $H$, then we return
$\\{v_{i},y,v_{i-1},v_{i+1}\\}$ as a claw. If $y$ has exactly two consecutive
neighbors on $H$, say, $v_{i}$ and $v_{i+1}$, then we return
$\\{x,y,v_{i-1},v_{i},v_{i+1},v_{i+2}\\}$ as an $\overline{S_{3}}$. In the
rest, $y$ is adjacent to two vertices $v_{i}$ and $v_{j}$ on $H$ with
$|i-j|>1$, then we return $\\{y,x,v_{i},v_{j}\\}$ as a claw. ∎

A graph is a _permutation graph_ if its vertices can be assigned to line
segments between two parallel lines such that there is an edge between two
vertices if and only if their corresponding segments intersect. The class of
permutation graphs has a large number of forbidden induced subgraphs [12].
Fortunately, most of them contain an odd cycle, and thus the structures of
forbidden induced subgraphs of bipartite permutation graphs are far simpler.

######  Theorem 2.9 ([12]).

A graph is a bipartite permutation graph if and only if it is free of $F_{1}$,
$F_{2}$, $F_{3}$, ${C_{2\ell+2}}$, and ${C_{2\ell-1}}$ with $\ell\geq 2$.

The following statement correlates proper circular-arc graphs and bipartite
permutation graphs.

######  Theorem 2.10 (Folklore).

The following are equivalent on a graph $G$:

  1. i)

$G$ is a proper circular-arc graph and $\overline{G}$ is bipartite; and

  2. ii)

$\overline{G}$ is a bipartite permutation graph.

###### Proof.

i) $\rightarrow$ ii). By Theorem 2.1, $\overline{G}$ is free of $F_{1}$,
$F_{2}$, $F_{3}$, and ${C_{2\ell+2}},\ell\geq 2$. On the other hand, since
$\overline{G}$ is bipartite, it does not contain any odd cycle, Thus, the
claim then follows from Theorem 2.9.

ii) $\rightarrow$ i). By Theorem 2.9, $\overline{G}$ is free of $F_{1}$,
$F_{2}$, $F_{3}$, ${C_{2\ell+2}}$, and ${C_{2\ell-1}}$ with $\ell\geq 2$.
Moreover, $\overline{G}$ cannot contain $S_{3}$, $\overline{S_{3}^{*}}$,
$F_{4}$, or $\overline{C_{\ell}^{*}}$ with $\ell\geq 4$ because each of them
contains a triangle; $\overline{G}$ is free of ${C_{2\ell-1}^{*}}$ with
$\ell\geq 2$ because ${C_{2\ell-1}^{*}}$ contains an odd cycle. ∎

The following is complement to Proposition 2.2 in a sense. Note that (proper)
circular-arc graphs that are co-bipartite have played crucial roles in
understanding these graph classes [19].

######  Proposition 2.11.

Let $G$ be a proper circular-arc graph. If $\overline{G}$ is not connected,
then $\overline{G}$ is a bipartite permutation graph.

###### Proof.

Since ${G}$ is a proper circular-arc graph, $\overline{G}$ does not contain
$C_{2\ell-1}^{*}$ or $C_{2\ell+2}$ with $\ell\geq 2$. If $\overline{G}$ is not
connected and contain any odd cycle, then this cycle and any vertex from
another component form a $C_{2\ell-1}^{*}$. Therefore, $\overline{G}$ is
bipartite, and the statement follows from Theorem 2.10. ∎

##  3 Deletions to proper Helly circular-arc graphs

We first study the proper Helly circular-arc vertex deletion problem. We may
assume without loss of generality that the input graph cannot be made a proper
interval graph by removing $k$ vertices. Therefore, the resulting graph after
removing any $k$-solution is connected by Proposition 2.2. An FPT algorithm is
immediate from Corollary 2.6: after destroying all the copies of
$\overline{C_{3}^{*}}$, $C_{4}^{*}$, $S_{3},\overline{S_{3}}$, $W_{4}$,
$W_{5}$, and $\overline{C_{6}}$ in $G$ by standard branching, we return all
vertices except those in a maximum-order component. A similar (and simpler)
approach works for the proper Helly circular-arc edge deletion problem. The
focus of the following proof is thus on efficient implementations.

######  Theorem 3.1.

The proper Helly circular-arc vertex deletion problem and the proper Helly
circular-arc edge deletion problem can be solved in time $O(6^{k}\cdot(m+n))$
and $O(10^{k}\cdot(m+n))$, respectively.

###### Proof.

Let ($G,k$) be an instance of proper Helly circular-arc vertex deletion. Our
algorithm proceeds as follows. We start by calling the algorithm of Cao [3] to
check whether there is a set $V_{-}$ of at most $k$ vertices such that
$G-V_{-}$ is a proper interval graph. If the set is found, then we return
“yes.” In the rest, we look for a solution $V_{-}$ such that $G-V_{-}$ is not
a proper interval graph. By Proposition 2.2, (note that a proper Helly
circular-arc graph is a proper circular-arc graph,) $G-V_{-}$ is connected.

For the general case, the algorithm solves the problem by making recursive
calls to itself; we return “no” directly for a recursive call in which $k<0$.
For each component $C$ of $G$, we call the algorithm of Proposition 2.8. If an
induced subgraph $G[F]$ is found, then the algorithm calls itself $|F|$ times,
each with a new instance $(G-v,k-1)$ for some $v\in F$. Since we need to
delete at least one vertex from $F$, the original instance $(G,k)$ is a yes-
instance if and only if at least one of the instances $(G-v,k-1)$ is a yes-
instance. Now that $G$ is free of $\overline{C_{3}^{*}}$, $C_{4}^{*}$,
$S_{3},\overline{S_{3}}$, $W_{4}$, $W_{5}$, and $\overline{C_{6}}$, every
component of $G$ is a proper Helly circular-arc subgraph (Corollary 2.6). We
find a component $C$ of $G$ that has the maximum order. We return “yes” if
$|V(C)|\geq n-k$, when $V(G)\setminus V(C)$ is a solution, or “no” otherwise.
Since each of
$\overline{C_{3}^{*}},C_{4}^{*},S_{3},\overline{S_{3}},W_{4},W_{5}$, and
$\overline{C_{6}}$ has at most $6$ vertices, at most $6$ recursive calls are
made, all with parameter value $k-1$. By Proposition 2.8, each recursive call
can be made in $O(m+n)$ time. Therefore, the total running time is
$O(6^{k}\cdot(m+n))$.

The algorithm for the edge deletion problem is even simpler. Again, we start
by calling the algorithm for proper interval edge deletion problem [3], which
takes time $O(4^{k}\cdot(m+n))$. We proceed only when the answer is “no.” In
the recursive calls for the general case, we always return “no” whenever $k$
is negative or $G$ becomes disconnected; note that a disconnected graph cannot
be made connected by edge deletions. We call the algorithm of Proposition 2.8,
and return “yes” if $G$ is already a proper Helly circular-arc graph.
Otherwise, an induced subgraph $F$ is found. The algorithm calls itself
$|E(F)|$ times, each with a new instance $(G-uv,k-1)$ for some edge $uv$ in
$G[F]$. By Proposition 2.8, each recursive call can be made in $O(m+n)$ time.
Therefore, the total running time is $O(10^{k}\cdot(m+n))$, where $10$ is the
number of edges in a $W_{5}$. ∎

It is straightforward to adapt an approximation algorithm for the proper Helly
circular-arc vertex deletion problem from the parameterized algorithm in
Theorem 3.1.

######  Theorem 3.2.

There is an $O(nm+n^{2})$-time approximation algorithm of approximation ratio
$6$ for the minimization version of the proper Helly circular-arc vertex
deletion problem.

###### Proof.

Let $G$ be the input graph. We start by creating an empty set $X$. We call the
algorithm in Proposition 2.8 with $G-X$. If the algorithm returns a vertex
set, then add all of them to $X$. We continue this process until each
component of $G-X$ is a proper Helly circular-arc graph. We call the
$6$-approximation algorithm of Cao [3] to find a set $Y$ such that $(G-X)-Y$
is a proper interval graph. We then take $V_{-}$ to be the smaller of $X\cup
Y$ and $V(G)\setminus V(C)$, where $C$ is a component of the maximum order of
$G-X$, with ties broken arbitrarily. Note that we always have $X\subseteq
V_{-}$.

To analyze the approximation ratio, let $V^{*}_{-}$ be an optimal solution of
$G$. Since each vertex set returned by Proposition 2.8 induces a subgraph in
$\\{\overline{C_{3}^{*}},C_{4}^{*},S_{3},\overline{S_{3}},W_{4},W_{5},\overline{C_{6}}\\}$,
the set $V^{*}_{-}$ contains at least one vertex from it according to
Corollary 2.5. Thus,

$|X|\leq 6|V^{*}_{-}\cap X|.$

Since $G-X$ is an induced subgraph of $G-(V^{*}_{-}\cap X)$, we have

$\mathrm{opt}(G-X)\leq\mathrm{opt}(G-(V^{*}_{-}\cap X))\leq|V^{*}_{-}\setminus
X|.$

Further, let $Y^{*}$ be an optimal solution of $G-X$. If $(G-X)-Y^{*}$ is a
proper interval graph, then

$|V_{-}\setminus X|\leq|Y|\leq 6|Y^{*}|=6\,\mathrm{opt}(G-X);$

otherwise,

$|V_{-}\setminus X|=n-|V(C)|-|X|=\mathrm{opt}(G-X).$

In summary,

$|V_{-}|=|X|+|V_{-}\setminus X|\leq 6|V^{*}_{-}\cap
X|+6\,\mathrm{opt}(G-X)\leq 6|V^{*}_{-}\cap X|+6|V^{*}_{-}\setminus
X|=6|V^{*}_{-}|,$

and the approximation ratio is $6$.

We now analyze the running time. Since each of
$\overline{C_{3}^{*}},C_{4}^{*},S_{3},\overline{S_{3}},W_{4},W_{5}$, and
$\overline{C_{6}}$ has at least $4$ vertices, at most $n/4$ such subgraphs can
be detected and deleted in the first phase. By Proposition 2.8, each of them
takes $O(m+n)$ time, hence $O(nm+n^{2})$ in total. The approximation algorithm
of Cao [3] takes another $O(nm+n^{2})$ time. The total running time is thus
$O(nm+n^{2})$. ∎

From Theorem 3.1 we can easily derive an FPT algorithm for the combined
deletion problem toward proper Helly circular-arc graphs, which allows $k_{1}$
vertex deletions and $k_{2}$ edge deletions.

######  Theorem 3.3.

There is an $O(16^{k_{1}+k_{2}}\cdot(m+n))$-time parameterized algorithm for
the proper Helly circular-arc deletion problem.

###### Proof.

This algorithm is very similar to the one used in Theorem 3.1. We may assume
that the graph is
$\\{\overline{C_{3}^{*}},C_{4}^{*},S_{3},\overline{S_{3}},W_{4},W_{5},\overline{C_{6}}\\}$-free;
otherwise, we break small forbidden induced subgraphs (on at most six
vertices) by branching on deleting one of its vertices or edges. If the graph
is already a proper Helly circular-arc graph, we are done. If it can be made a
proper interval graph by deleting $k_{1}$ vertices and at most $k_{2}$ edges,
then we return “yes” in time $O(4^{k_{1}+k_{2}}\cdot(m+n))$ [3]. Otherwise, we
have to make a proper Helly circular-arc graph that is not a proper interval
graph. We return yes if a largest component has at least $n-k_{1}$ vertices,
and no otherwise. The running time is from the branching step, where we need
to consider $6$ vertices or $10$ edges. ∎

It remains to fill in the gap between the constants in Theorems 3.1 and 3.3
and those announced in Theorems 1.3, with an idea is similar to [3,
Proposition 4.4 and Theorem 4.5]. Of the seven small forbidden induced
subgraphs, only $S_{3}$, $W_{5}$, and $\overline{C_{6}}$ has more than eight
edges. For an $S_{3}$, either we delete one edge between two degree-four
vertices, or we have to delete both edges incident to a degree-2 vertex. For a
$W_{5}$ we only need to consider the five edges incident to the center vertex:
deleting edge(s) from the $C_{5}$ leaves a claw. For a $\overline{C_{6}}$,
either we delete one edge that is not in any triangle, or we have to delete at
least four edges from the two triangles. Thus, the edge deletion problem and
the general deletion problem can be solved in time $O(8^{k}\cdot(m+n))$ and
$O(14^{k_{1}+k_{2}}\cdot(m+n))$, respectively.

##  4 Proper Helly circular-arc completion

Compared to the deletion problems, the completion problem toward proper Helly
circular-arc graphs is significantly more difficult. For all the deletion
problems, we can always assume that the graph is connected, and then by
Corollary 2.6, we are only concerned with small forbidden induced subgraph.
Since adding edges may make a graph connected, we cannot assume connectedness
for the completion problem.

Every hole in a proper Helly circular-arc graph is clearly dominating, and we
can be more specific on the intersection between a hole and the neighborhood
of any vertex.

######  Proposition 4.1.

Let $H$ be a hole in a proper Helly circular-arc graph. Every vertex in this
graph has at least two neighbors on $H$.

###### Proof.

In any arc representation for the graph, the arcs for vertices on $H$ cover
the whole circle. Thus, every vertex $x$ has a neighbor on $H$. Moreover, if
$x$ has a single neighbor on $H$, then there is a claw, contradicting
Corollary 2.5. ∎

It is well known that the maximal cliques of an interval graph can be arranged
as a path. Gavril [13] showed that the maximal cliques of a Helly circular-arc
graph can be arranged as a circle. This implies that a Helly circular-arc
graph has a linear number of maximal cliques.

######  Theorem 4.2 ([13]).

A graph $G$ is a Helly circular-arc graph if and only if its maximal cliques
can be arranged as a circle so that for every vertex $v$ in $G$, the maximal
cliques containing $v$ are consecutive.

We use a _clique circle_ to denote the circular arrangement of maximal cliques
specified in Theorem 4.2, and a _clique path_ is defined analogously. Note
that a clique path can always be viewed as a clique circle, while if two
consecutive cliques of a clique circle are disjoint, then it can be viewed as
a clique path. We put the maximal cliques of a clique circle in clockwise
order, and for each vertex $v$ that is not universal, let ${\mathtt{lp}(v)}$
and ${\mathtt{rp}(v)}$ denote indices of the most anticlockwise, and
respectively, the most clockwise clique containing $v$. We set the arc for the
vertex $v$ to be $[{\mathtt{lp}(v)},{\mathtt{rp}(v)}]$.

######  Proposition 4.3.

Let $\\{K_{1},\ldots,K_{\ell}\\}$ be a clique circle for a graph $G$. The set
of arcs $\\{[{\mathtt{lp}(v)},{\mathtt{rp}(v)}]\mid v\in V(G)\\}$ is an arc
representation for $G$.

###### Proof.

Since all the endpoints of the arcs are integral, two arcs intersect, if and
only if there is an integer in their intersection. Note that an integer $i$ is
contained in the arcs for vertices $u$ and $v$ if and only if both $u$ and $v$
are contained in $K_{i}$, hence $uv\in E(G)$. ∎

In passing we remark that a connected proper Helly circular-arc graph has a
unique clique cycle, up to full reversal [9, 5].

Proper interval graphs are precisely claw-free interval graphs, which can be
restated as a graph is a proper interval graph if and only if it is claw-free
and has a clique path. One may thus expect that a graph is a proper Helly
circular-arc graph if and only if it is claw-free and has a clique circle. As
we have mentioned, however, $S_{3}$ is a Helly circular-arc graph and hence
has a clique circle, but it is not a proper Helly circular-arc graph even
though it is claw-free. The following statement can be directly observed from
forbidden induced subgraphs of the class of proper Helly circular-arc graphs
and of the class of normal Helly circular-arc graphs; see also Lin et al. [18,
Theorem 9].111An arc representation is known to be normal and Helly if no set
of three or fewer arcs covers the circle [13, 4].

######  Lemma 4.4 ([18]).

A graph is a proper Helly circular-arc graph if and only if it is claw-free
and it has an arc representation in which no set of three or fewer arcs covers
the circle.

If a proper Helly circular-arc graph $G$ is not an interval graph, then it has
a hole. The structure of every local part of $G$ is very like a proper
interval graph. With the removal of two maximal cliques with no edge in
between from $G$, the hole is separated into two sub-paths. Since every
remaining vertex is adjacent to one of the two sub-paths, the remaining graph
has precisely two components.

######  Lemma 4.5.

Let $G$ be a proper Helly circular-arc graph that is not an interval graph.
Let $A_{1}$ and $A_{2}$ be two maximal cliques of $G$ with no edge between
them, and let $B_{1}$ and $B_{2}$ be the vertex sets of the two components of
$G-(A_{1}\cup A_{2})$. Let $G_{1}$ be any proper interval graph on $B_{1}\cup
A_{1}\cup A_{2}$ in which $A_{1}$ and $A_{2}$ are the end cliques, and
$N_{G_{1}}(A_{i})\cap B_{1}=N_{G}(A_{i})\cap B_{1}$ for $i=1,2$. Replacing
$G[B_{1}\cup A_{1}\cup A_{2}]$ by $G_{1}$ gives another proper Helly circular-
arc graph.

###### Proof.

Let $G^{\prime}$ denote the resulting graph (after replacing $G[B_{1}\cup
A_{1}\cup A_{2}]$ by $G_{1}$ in $G$). We may number the maximal cliques of $G$
in a way that $K_{1}=A_{1}$ and $K_{p}=A_{2}$ while
$B_{1}\subseteq\bigcup_{i=1}^{p}K_{i}$. Let
$K_{1},K^{\prime}_{2},\ldots,K^{\prime}_{q},K_{p}$ be a clique path for
$G_{1}$.

We first argue that $G^{\prime}$ is claw-free. Suppose for contradiction that
$G^{\prime}[\\{v,x,y,z\\}]$ is a claw, with $v$ being the center. Since both
$G$ and $G_{1}$ are claw-free, the claw must intersect both $B_{1}$ and
$B_{2}$. Thus, $v$ must be in $K_{1}$ or $K_{p}$. Without loss of generality,
assume $v\in K_{p}$, while $x\in B_{1}$ and $z\in B_{2}$. Note that the vertex
$z$ has the same neighborhood in $G$ and in $G^{\prime}$. Since
$G[\\{v,x,y,z\\}]$ is not a claw, we have $xy\in E(G)\setminus E(G^{\prime})$.
By the assumption $N_{G_{1}}(K_{p})\cap B_{1}=N_{G}(K_{p})\cap B_{1}$, we must
have $y\in B_{1}$. But then $G_{1}[\\{v,x,y,z^{\prime}\\}]$, where
$z^{\prime}$ is any vertex in $K_{p}\setminus K^{\prime}_{q}$, is a claw, a
contradiction to that $G_{1}$ is a proper interval graph.

We then argue that

$K_{1},K^{\prime}_{2},\ldots,K^{\prime}_{q},K_{p},K_{p+1},\ldots$

gives a clique circle for $G^{\prime}$. Since no vertex in $B_{1}$ or $B_{2}$
is adjacent to all vertices in $K_{1}$ or in $K_{p}$ in $G^{\prime}$, both
$K_{1}$ and $K_{p}$ are maximal cliques of $G^{\prime}$. Since there is no
edge between vertices in $B_{1}$ and $B_{2}$, both $K^{\prime}_{i},2\leq i\leq
q$ and $K_{j},j>p$ are maximal cliques of $G^{\prime}$. A vertex $v\not\in
K_{1}\cup K_{p}$ is in either $B_{1}$ or $B_{2}$, and it is contained in
either $K^{\prime}_{i},2\leq i\leq q$ or $K_{j},j>p$. Since
$K_{1},K_{2},\ldots,K_{p},\ldots$ is a clique circle of $G$ and
$K_{1},K^{\prime}_{2},\ldots,K^{\prime}_{q},K_{p}$ is a clique path for
$G_{1}$, those containing $v$ are consecutive. Now suppose without loss of
generality $v\in K_{p}$. Maximal cliques containing $v$ are
$\ldots,K^{\prime}_{q},K_{p},K_{p+1},\ldots$. Therefore, for any vertex $v$,
the maximal cliques of $G^{\prime}$ containing $v$ are consecutive.

We can use Proposition 4.3 to derive an arc representation for $G^{\prime}$.
For any set of arcs to cover the whole circle in the representation, we need
one arc from $B_{1}$, $B_{2}$, $A_{1}$, and $A_{2}$, hence at least four arcs.
Thus, $G^{\prime}$ is a proper Helly circular-arc graph by Lemma 4.4. ∎

For the completion problem, we may again assume that the input graph $G$ is
free of $\overline{C_{3}^{*}}$, $C_{4}^{*}$,
$S_{3},\overline{S_{3}},W_{4},W_{5}$, and $\overline{C_{6}}$. We are done if
$G$ is already a proper Helly circular-arc graph. In particular, this is the
case when $G$ is a proper interval graph or when $G$ is connected (Corollary
2.6). Thus, we may assume that $G$ is not connected and it is not a proper
interval graph. There must be a hole in $G$ (Corollary 2.7), and we add either
a chord of this hole, or an edge between this hole and every vertex in other
components. If there is a hole of length of no more than $16k+16$, then there
are only $O(k^{2})$ such choices, and we can branch on adding one of them. In
the rest every hole is longer than $16k+16$. Let $H$ be such a hole, and let
$G_{0}$ be the component of $G$ that contains $H$; note that $G_{0}$ is a
proper Helly circular-arc graph. After adding $k$ or fewer edges, there must
be a hole of length greater than $k$ in the subgraph induced by $V(H)$. Thus,
for every vertex $x$ in $V(G)\setminus V(G_{0})$, an edge must be added
between $x$ and $H$. We can return “no” if $|V(G_{0})|<n-{k}$. Other
components have fewer than $k$ vertices while any hole is longer than
$16k+16$, and thus they are already proper interval subgraphs.

We say that a vertex $x$ is _touched_ by a solution $E_{+}$ if $x$ is an
endpoint of an edge in $E_{+}$, and a set $X$ of vertices is _touched_ if at
least one vertex in $X$ is touched. All vertices in $V(G)\setminus V(G_{0})$
are touched, and we are more concerned with touched vertices in $G_{0}$.

######  Proposition 4.6.

Let $E_{+}$ be a solution to $G$. If a maximal clique $K$ of $G$ is untouched
by $E_{+}$, then $K$ is a maximal clique of $G+E_{+}$.

###### Proof.

It is clear that $K$ remains a clique in $G+E_{+}$. Suppose that $K$ is not
maximal, then it is a proper subset of a maximal clique $K^{\prime}$ of
$G+E_{+}$. We can find a vertex $x\in K^{\prime}\setminus K$. But then there
must be $y\in K$ such that $xy\in E_{+}$, contradicting that $y$ is untouched.
∎

We may fix a clique circle $\mathcal{K}$ of $G_{0}$, and assume that $H$ and
$\mathcal{K}$ are numbered such that no neighbor of $v_{1}$ or $v_{|H|}$ is
touched, and $\\{v_{1},v_{|H|}\\}\subseteq K_{1}$, which is untouched. Note
that $G_{0}$ has at least $|H|$ maximal cliques, and few of them are touched
by a $k$-solution $E_{+}$. By Lemma 4.5 and Proposition 4.6, these untouched
maximal cliques serve “isolators” of the modifications.

We can guess another untouched maximal clique $K_{p}$ of $G_{0}$ that is
disjoint from and nonadjacent to $K_{1}$. Then $H$ is broken into two paths in
$G-(K_{1}\cup K_{p})$. Recall that every vertex in $V(G)\setminus V(G_{0})$
needs to be connected to a vertex on $H$. When the graph $G+E_{+}$ is not a
proper interval graph, every small component is connected to one and only one
of the two sub-paths of $H$ (otherwise the resulting graph remains connected
after all vertices in $K_{1}\cup K_{p}$ removed, contradicting Proposition
4.6). We can guess in $2^{k}$ time to which side each small component is
attached. Then we need to add edges to make two proper interval graphs.
However, we cannot call the proper interval completion problem to solve this
task. For example, the subgraph induced by $\bigcup_{i=1}^{p}K_{i}$ together
with the small components is already a proper interval graph. The trouble is
how to make them connected while keeping $K_{1}$ and $K_{p}$ the ends of the
final clique path. The same holds for the other part of the problem.

For each $i$ with $1<i<|H|$, let the maximal cliques containing $v_{i}$ be
$K_{\mathrm{from}(i)}$, $\ldots$, $K_{\mathrm{to}(i)}$; i.e.,
$\mathrm{from}(i)$ and $\mathrm{to}(i)$ are the smallest and, respectively,
the largest indices. We define $K_{\mathrm{to}(1)}$ and
$K_{\mathrm{from}(|H|)}$ analogously. Let $r$ denote the number of small
components, denoted as $C_{1},\ldots,C_{r}$. For each pair $p,q$ of indices
with $1<p<q<|H|$, and each subset $S$ of $[1..r]$, we check whether it is
possible to add at most $k$ edges to make
$G[\bigcup_{i=\mathtt{to}(p)}^{\mathtt{from}(q)}K_{i}\cup\bigcup_{j\in
S}C_{j}]$ a proper interval graph, under the condition that
$K_{\mathtt{to}(p)}$ and $K_{\mathtt{from}(q)}$ are the end cliques and remain
untouched. Let $\beta(S,p,q)$ denote the minimum cost if it is at most $k$, or
$\infty$. We define $\beta(S,p,q)$ to be $\infty$ when $K_{\mathtt{to}(p)}$
and $K_{\mathtt{from}(q)}$ are not disjoint. Then $\beta([1..r],1,|H|)$ is the
value we need, which can be calculated as follows.

######  Proposition 4.7.

The value of $\beta([1..r],1,|H|)$ can be computed in $k^{O(k)}(n+m)$ time.

###### Proof.

First, for $a$ and $b$ with $a<b\leq b+8k$ and $S\subseteq[1..r]$, we
calculate $\beta(S,a,b)$ as follows. From each component $C_{j}$ with $j\in
S$, we take a vertex $x$, guess a vertex $v_{i}$ with $a<i<b$, and add the
edge $xv_{i}$. After that, the subgraph induced by
$\bigcup_{i=\mathtt{to}(a)}^{\mathtt{from}(b)}K_{i}\cup\bigcup_{j\in S}C_{j}$
is connected. It will remain connected after adding edges. We then branch on
adding edges to destroy induced subgraphs in
$\\{\overline{C_{3}^{*}},S_{3},\overline{S_{3}}\\}$ and holes in the subgraph
induced by
$\bigcup_{i=\mathtt{to}(a)}^{\mathtt{from}(b)}K_{i}\cup\bigcup_{j\in S}C_{j}$,
without adding any edges incident to $K_{\mathtt{to}(a)}$ or
$K_{\mathtt{from}(b)}$.

Since $G_{0}$ is a proper Helly circular-arc graph, a vertex is adjacent to at
most four vertices on $H$ (there is a claw otherwise). Therefore, at most $8k$
vertices on $H$ have touched neighbors. If $v_{b-1}$ has a touched neighbor,
then for some $i$ with $2\leq i\leq 8k+2$, the vertex $v_{b-i}$ has no touched
neighbor. For $b-a>8k$, by Lemma 4.5, we have

$\beta(S,a,b)=\min_{\begin{subarray}{c}1\leq i\leq 8k+1\\\ S^{\prime}\subseteq
S\end{subarray}}\left(\beta(S\setminus
S^{\prime},a,b-i)+\beta(S^{\prime},b-i,b)\right).$ (1)

We can then use dynamic programming to calculate $\beta([1..r],1,|H|)$ with
(1). ∎

We are now ready to summarize the algorithm in Figure 3.

1. if there exists an induced subgraph $X$ in $\\{\overline{C_{3}^{*}},C_{4}^{*},S_{3},\overline{S_{3}},W_{4},W_{5},\overline{C_{6}}\\}$ then branch on adding missing edges of $X$; \\ returns “no” if $k$ becomes negative. 2. if $G$ is a proper Helly circular-arc graph then return “yes”; 3. find a hole $H$ of $G$ and let $G_{0}$ be the component of $G$ that contains $H$; 4. if $|H|\leq 16k+16$ then branch on adding chords of $H$ or edges between $H$ and other components; 5. if $|V(G_{0})|<n-{k\over 2}$ then return “no”; 6. if $\beta([1..r],1,|H|)\leq k$ then return “yes”; else return “no.” Figure 3: The outline of the algorithm for the proper Helly circular-arc completion problem.

######  Lemma 4.8.

The proper Helly circular-arc completion problem can be solved in time
$k^{O(k)}(n+m)$.

###### Proof.

If $G$ contains an induced subgraph in
$\\{\overline{C_{3}^{*}},C_{4}^{*},S_{3},\overline{S_{3}},W_{4},W_{5},\overline{C_{6}}\\}$,
then any solution must contain at least one missing edge in this subgraph.
After step 1, $G$ is
$\\{\overline{C_{3}^{*}},C_{4}^{*},S_{3},\overline{S_{3}},W_{4},W_{5},\overline{C_{6}}\\}$-free,
and it is already a proper Helly circular-arc graph if it is connected
(Corollary 2.6). Since every component of $G$ is a proper circular-arc graph,
but $G$ is not a proper interval graph, there must be a hole in $G$ (Corollary
2.7). Step 4 is obviously correct: a solution contains a chord of $H$ or an
edge between $H$ and other components of $G$. Now that $H$ is longer than
$16k+16$, there must be a hole after adding at most $k$ edges. Every vertex in
$V(G)\setminus V(G_{0})$ must be made adjacent to this hole. The correctness
of step 5 follows from Proposition 4.1, and the correctness of step 6 follows
from the definition of $\beta$.

We now analyze the running time of the algorithm. The algorithm makes at most
$O(6^{k})$ recursive calls in step 1, all with parameter value $k-1$. We can
check whether $G$ is a proper Helly circular-arc graph in linear time [4].
When it is not, we can find a hole in linear time. At most $k^{O(k)}$
recursive calls are made in step 4, all with parameter value $k-1$. In step 6,
we use Proposition 4.7 to calculate $\beta([1..r],1,|H|)$, for which we need
to guess a numbering of $H$ and $\mathcal{K}$. At most $8k$ vertices on $H$
have touched neighbors. Thus, by trying $16k$ vertices on $H$, we can find one
pair of adjacent vertices as $v_{1}$ and $v_{|H|}$. The total time is thus
$k^{O(k)}(n+m)$. ∎

A natural question is on the complexity of the proper Helly circular-arc
completion problem on
$\\{\overline{C_{3}^{*}},C_{4}^{*},S_{3},\overline{S_{3}},W_{4},W_{5},\overline{C_{6}}\\}$-free
graphs. A related and (maybe) simpler question is when all but one of the
components of the input graph are proper interval graphs, while the other is a
proper Helly circular-arc graph. Let us remark that a polynomial-time
algorithm for this later problem implies a polynomial-time algorithm for the
proper interval completion problem on proper Helly circular-arc graphs.

However, it is not obvious how to solve the proper Helly circular-arc editing
problem, which allows $k_{1}$ vertex deletions, $k_{2}$ edge deletions, and
$k_{3}$ edge additions. We do not have the optimal substructures as we have
seen in the completion problem: we may need to cut some vertices off $G_{0}$
by deleting edges, and attach them to other parts of $G_{0}$; see Figure 4 for
an example. Let us mention that the idea does solve the modification problem
to proper Helly circular-arc graphs that allows both vertex deletions and edge
additions.

$3$$3$$3$$3$$99$$2$$4$$99$$3$$3$$3$$3$$10$$10$$10$$10$$10$$10$$10$$1$ Figure
4: The input graph $G$ comprises two components. Each node denotes a set of
true twins with the designated number of vertices, and a line between two
nodes indicates all the edges between the two sets of vertices. We can make
$G$ a proper Helly circular-arc graph by deleting $6$ edges and adding $426$
edges (i.e., $k_{1}=0$, $k_{2}=6$, and $k_{3}=426$). We need to remove all the
six edges incident to the shadowed vertex and add edges between it and the six
vertices (in two sets of sizes $2$ and $4$ respectively) at the top.

######  Conjecture.

The proper Helly circular-arc editing problem is fixed-parameter tractable.

##  5 Proper circular-arc vertex deletion

Since we will use properties of both the graph $G$ and its complement, we beg
the reader’s attentiveness in reading this section. There are algorithms for
the vertex deletion problem toward both proper interval graphs and bipartite
permutation graphs. We are henceforth focused on graphs that are both
connected and co-connected. As usual, we can get rid of small forbidden
induced subgraphs easily.

######  Definition.

We say that a graph is _reduced_ if it is both connected and co-connected, and
it contains no $C_{3}^{*}$, $C_{5}^{*}$, $\overline{C_{4}^{*}}$, $C_{6}$,
$S_{3}$, $\overline{S_{3}^{*}}$, $F_{1}$, $F_{2}$, $F_{3}$, or $F_{4}$.

Similar to Proposition 2.8, one can make an algorithm for finding one of the
subgraphs list above when the input graph is not reduced. We omit details
since it does not improve our main algorithm. The next lemma is complement and
similar to Lemma 2.3.

######  Lemma 5.1.

A reduced graph is $\\{C_{\ell}^{*}\mid\ell\geq 7\\}$-free.

###### Proof.

Let $R$ be a reduced graph. Suppose for contradiction that there exist a hole
$H$ of length at least seven and a vertex that is nonadjacent to any vertex on
$H$. Since ${R}$ is connected, we can find a vertex $x$ adjacent to $H$, and
another vertex $y$ that is adjacent to $x$ but not to $R$. Let
$H=v_{1}v_{2}\cdots v_{|H|}$. We argue first that $x$ cannot be adjacent to
two consecutive vertices on $H$. Suppose for contradiction that $x$ is
adjacent both $v_{1}$ and $v_{2}$. Then $v_{1},v_{2}$, and $x$ form a
triangle. Since $R$ is free of $C^{*}_{3}$, it follows that $x$ is adjacent to
both $v_{4}$ and $v_{5}$. But then $v_{1},v_{2},v_{4},v_{5}$, and $x$ induce a
$\overline{C_{4}^{*}}$.

Assume without loss of generality that $x$ is adjacent to $v_{3}$. Note that
$x$ is adjacent to neither $v_{2}$ nor $v_{4}$. If $x$ is adjacent to $v_{5}$
as well, then $x$ is nonadjacent to $v_{6}$, and
$\\{v_{2},\ldots,v_{6},x,y\\}$ induces an $F_{2}$. By symmetry, $x$ cannot be
adjacent to $v_{1}$ either. But then $\\{v_{1},\ldots,v_{5},x,y\\}$ induces an
$F_{1}$. ∎

By definition, a reduced graph is $C_{3}^{*}$\- and $C_{5}^{*}$-free.

######  Corollary 5.2.

A reduced graph is $\\{C_{2\ell+1}^{*}\mid\ell\geq 1\\}$-free.

By Theorem 2.1, the definition of reduced graphs, and Lemma 2.3, a reduced
graph is the complement of a proper circular-arc graph if and only if it does
not contain any even hole of length at least eight. We will therefore be
focused on long even holes. The following statement characterizes reduced
graphs that contain long even holes.

######  Lemma 5.3.

If a reduced graph contains an even hole of length at least eight, then it is
bipartite.

###### Proof.

Let $v_{1}v_{2}\cdots v_{\ell}$ be an even hole with $\ell\geq 8$ of a reduced
graph $R$, and denote it by $B$. We prove the lemma with a sequence of claims.

Our first claim is that no vertex on $B$ participates in any triangle. If
there is a triangle involving two vertices from $B$, say, $uv_{1}v_{2}$, then
either it forms a $C_{3}^{*}$ with $v_{4}$ or $V_{5}$, when $u$ is not
adjacent to one of $v_{4}$ and $v_{5}$, or $\\{u,v_{1},v_{2},v_{4},v_{5}\\}$
induces a $\overline{C_{4}^{*}}$. Since neither is possible, we can conclude
that there is no triangle involving two vertices of $B$. Now suppose that
there is a triangle involving a single vertex from $B$, say, $uwv_{1}$ with
$u,w\in V(R)\setminus V(B)$. Since $R$ is $C_{3}^{*}$-free, for $i=3,4$, there
is at least one edge between $v_{i}$ and $u,w$. By the argument above, neither
$u$ nor $w$ can be adjacent to both $v_{3}$ and $v_{4}$. Thus,
$\\{u,w,v_{3},v_{4}\\}$ induces a $C_{4}$, and so does the set
$\\{u,w,v_{6},v_{7}\\}$. But then $\\{u,w,v_{1},v_{3},v_{4},v_{6},v_{7}\\}$
induces an $F_{4}$, a contradiction to that $R$ is reduced.

The second claim is that if some odd hole of $R$ intersects $B$, then there
exists an odd hole of $R$ whose intersection with $B$ is a nonempty sub-path
of $B$. Let $C$ have the minimum number of vertices out of $B$ among all the
odd holes that intersect $B$ (i.e., $|V(C)\setminus V(B)|$ is minimized). We
take a nontrivial sub-path $P_{C}$ of $C$ such that only the two ends of this
path are on $B$. Without loss of generality, assume the ends of $P_{C}$ are
$v_{1}$ and $v_{p}$. Let $P_{B}$ be the sub-path $v_{1}v_{2}\cdots v_{p}$ of
$B$. If $P_{B}$ and $P_{C}$ have different parities (one even and the other
odd), then they together form an odd induced cycle. By the first claim, this
induced cycle must be an odd hole, and we are done. Otherwise, we replace
$P_{C}$ by $P_{B}$ in $C$ to produce another odd closed walk. Therefore, we
always end with an odd closed walk that avoids at least one vertex in
$V(C)\setminus V(B)$ and whose vertices are all from $V(B)\cup V(C)$. From
this odd closed walk we can find an odd induced cycle $C^{\prime}$. Since
$V(C^{\prime})\subseteq V(C)\cup V(B)$ and $C^{\prime}\neq C$, the cycle
$C^{\prime}$ must intersect $B$. On the other hand, since $B$ is an even hole,
$C^{\prime}$ intersects $C$ as well. Since $P_{C}$ is a nontrivial path, it
has at least one inner vertex, which is not on $C^{\prime}$. It follows that
$|V(C^{\prime})\setminus V(B)|<|V(C)\setminus V(B)|$, contradicting the
selection of $C$.

The third claim is that if $V(C)\cap V(B)$ is consecutive for an odd induced
cycle $C$, then $|V(C)\cap V(B)|\leq 4$. Assume without loss of generality
that the intersection of $B$ and $C$ is the sub-path $v_{1}v_{2}\cdots v_{c}$.
We consider the odd cycle formed by the other $v_{1}$–$v_{c}$ path on $B$ and
the other $v_{1}$–$v_{c}$ path on $C$, which consists of vertices $V(B)\cup
V(C)\setminus\\{v_{2},v_{3},\ldots,v_{c-1}\\}$. From this odd cycle we can
retrieve an odd induced cycle $C^{\prime}$. If $c>4$, then $v_{3}$ is not
adjacent to any vertex on $C^{\prime}$. But then $C^{\prime}$ and $v_{3}$ form
a $C_{|C^{\prime}|}^{*}$, contradicting Corollary 5.2.

The fourth claim is that no odd induced cycle can intersect $B$. Suppose for
contradiction that there are such odd induced cycles. We take an odd induced
cycle $C$ such that (1) $V(B)\cap V(C)$ induces a path; (2) $|V(B)\cap V(C)|$
is maximized among all cycles satisfying (1); and (3) $C$ is the shortest
among all cycles satisfying both (1) and (2). The existence of such a cycle is
ensured by the second claim. Let $q=|C|$ and $c=|V(B)\cap V(C)|$. Assume
without loss of generality that the intersection of $B$ and $C$ is the sub-
path $v_{1}v_{2}\cdots v_{c}$, and we may number the vertices on $C$ as
$u_{1},u_{2},\ldots,u_{q}$ such that $u_{i}=v_{i}$ for $i=1,\ldots,c$. We
consider the cycle $A$ formed by the two $v_{1}$–$v_{c}$ paths
$v_{c}v_{c+1}\cdots v_{\ell}v_{1}$ and $u_{c}u_{c+1}\cdots u_{q}u_{1}$. The
length of $A$, which visits $V(B)\cup
V(C)\setminus\\{v_{2},v_{3},\ldots,v_{c-1}\\}$, is $\ell+q-2(c-1)$, hence odd.
We use chords $v_{i}u_{j}$ of $A$ to decompose $A$ into a sequence of induced
cycles as follows. We start with $i=c+2$ and $j$ being the smallest index such
that $v_{c+2}u_{j}\in E(G)$. The first cycle is
$v_{c+2}v_{c+1}u_{c}u_{c+1}\cdots u_{j}$. See Figure 5(a) for an illustration.

  1. Case 1,

the first cycle $v_{c+2}v_{c+1}u_{c}u_{c+1}\cdots u_{j}$ is odd; let it be
$C^{\prime}$. Note that ${j}$ has the same parity as $c$.

First, suppose that $C^{\prime}$ is induced. The cycle $C^{\prime}$ has three
common vertices with $B$. Thus, $c\geq 3$ by the second condition in the
selection of $C$. Note that $v_{1}$ is not on $C^{\prime}$. Since $v_{2}$ has
a neighbor on $C^{\prime}$ (Corollary 5.2), the neighbor has to be $v_{3}$.
Thus, $c=3$. Since $\ell\geq 8$, the only possible neighbor of $v_{1}$ on
$C^{\prime}$ is $u_{q}$. Thus, $j=q$. If $q=5$, then $v_{6}$ must be adjacent
to $u_{4}$, (the vertex $v_{6}$ is adjacent to some vertex on $C$, while
$u_{5}$ cannot form a triangle with $v_{5}$ and $v_{6}$,) and the odd hole
$u_{4}v_{3}v_{4}v_{5}v_{6}$ forms a $C_{5}^{*}$ with $v_{1}$. Now that $q>5$,
the set $\\{v_{1},v_{2},v_{3},v_{4},v_{5},u_{4},u_{5}\\}$ induces a long claw.

In the rest, $C^{\prime}$ is not induced. By the definition of $j$, there is
no chord of $C^{\prime}$ incident to $v_{c+2}$. In other words, all the chords
of $C^{\prime}$ are incident to $v_{c+1}$. They partition $C^{\prime}$ into
induced cycles, which are all strictly shorter than $C$. Since $C^{\prime}$ is
odd, at least one of these induced cycles is odd; let it be
$C^{\prime\prime}$. The intersection of $C^{\prime\prime}$ and $B$ is one of
$\\{v_{c+1}\\}$, $\\{v_{c+1},v_{c}\\}$, and $\\{v_{c+1},v_{c+2}\\}$, hence
consecutive. By the selection of $C$, we must have $|V(B)\cap
V(C^{\prime\prime})|<|V(B)\cap V(C)|=c$. But then $v_{c-2}$ or $v_{c-1}$ (when
$c\geq 3$) or $v_{c-1}$ (when $c=2$) has no neighbor on $C^{\prime\prime}$,
contradicting Corollary 5.2.

Now that the first cycle is even, we continue as follows. We find the next
neighbor of $v_{i}$ in $u_{j+1},\ldots,u_{q}$, if one exists. Otherwise, we
find the edge between $v_{i+1},\ldots,v_{\ell}$ and $u_{j},\ldots,u_{q}$. We
check the induced cycle formed by the two chords and the two sub-paths on $B$
and $C$. We stop if it is odd. Otherwise we update $i$ and $j$, and continue
the search until we reach $v_{\ell}$.

  1. Case 2,

the cycle $v_{i}\cdots v_{i^{\prime}}u_{j^{\prime}}u_{j^{\prime}-1}\cdots
u_{j}$ is odd, where $v_{i}u_{j}$ and $v_{i^{\prime}}u_{j^{\prime}}$ are the
previous chord and new chord, respectively. Let the cycle be denoted as
$C^{\prime}$. Note that neither $v_{1}$ nor $v_{c}$ is on $C^{\prime}$. If
$c\geq 3$, then $v_{2}$ has no neighbor on $C^{\prime}$ (because both $B$ and
$C$ are induced), contradicting Corollary 5.2. By the second condition in the
selection of $C$, we have $|V(C^{\prime})\cap V(B)|\leq|V(C)\cap V(B)|=c\leq
2$. Thus, $i^{\prime}\leq i+1$. By Corollary 5.2, the vertex $v_{c}$ has at
least one neighbor on $C^{\prime}$.

     * •

Subcase 2.1, $c=2$. See Figure 5(b). Note that $v_{2}$ has three neighbors on
$B$ and $C$, of which neither $v_{1}$ nor $v_{3}$ can be on $C^{\prime}$. (In
particular, $v_{3}$ is on the first cycle, which contains $v_{c}$, i.e.,
$v_{2}$.) Thus, $j=c+1=3$, which further implies $i=4$. Note that $u_{q}$
cannot be adjacent to $v_{4}$: if $u_{q}v_{4}\in E(R)$, then
$u_{q}v_{3}\not\in E(R)$ because of the first claim, and then
$u_{q}v_{1}v_{2}v_{3}v_{4}$ is an induced $C_{5}$, contradicting the second
condition in the selection of $C$. Again, $v_{1}$ has a neighbor on
$C^{\prime}$ by Corollary 5.2, and it has to be $u_{q}$. It follows that
$i^{\prime}=5$, and then by the selection of the cycle, there is no edge
between $v_{4},v_{5}$ and any vertex in $\\{u_{4},u_{5},\ldots,u_{q-1}\\}$. We
argue that $v_{3}$ is not adjacent to $u_{4}$ by contradiction. If $q=5$, then
the cycle $v_{1}v_{2}v_{3}u_{4}u_{5}$ intersects $B$ with three vertices; it
cannot be induced by the selection of $C$, but then there is a triangle
intersecting $B$, contradicting the first claim. If $q\geq 7$, then
$\\{v_{1},v_{2},v_{3},v_{4},v_{5},u_{4},u_{5}\\}$ induces an $F_{1}$.
Therefore, $v_{3}u_{4}\not\in E(R)$ and the set
$\\{v_{1},v_{2},v_{3},v_{4},v_{5},u_{3},u_{4}\\}$ induces an $F_{2}$.

     * •

Subcase 2.2, $c=1$. See Figure 5(c). Then $|V(C^{\prime})\cap V(B)|=|V(C)\cap
V(B)|=1$. By the third condition in the selection of $C$, we have
$|C^{\prime}|=|C|=q$. Thus, $j=c+1=2$ and $j^{\prime}=q$ and $i=c+2=3$. None
of $v_{2}$, $v_{4}$, and $v_{\ell}$ can be adjacent to $u_{2}$ by the first
claim. We now argue that $u_{3}$ cannot be adjacent to $v_{2}$, $v_{4}$, or
$v_{\ell}$. Suppose that $u_{3}v_{2}\in E(R)$. Then
$v_{1}v_{2}u_{3}u_{4}\cdots u_{q}$ is an odd cycle, from which we can find an
induced odd cycle. But this contradicts the selection of $C$: either it shares
two vertices with $B$, or it is shorter than $C$. It is likewise when
$u_{3}v_{4}\in E(R)$ or $u_{3}v_{\ell}\in E(R)$: in particular, we consider
the odd cycles $v_{3}v_{4}u_{3}u_{4}\cdots u_{q}$, and respectively,
$v_{1}v_{\ell}u_{3}u_{4}\cdots u_{q}$. The set
$\\{v_{\ell},v_{1},v_{2},v_{3},v_{4},u_{2},u_{3}\\}$ induces an $F_{2}$.

If neither of the previous two cases is true, then the last cycle must be odd.
All the small cycles use edges from $A$ and the chords of $A$. Moreover, each
edge on $A$ appears in precisely one of the cycles, and if a chord is used,
then it appears in precisely two of the cycles. Therefore, the sum of the
lengths of all these cycles has the same parity as $A$, hence odd.

  1. Case 3,

the last cycle $C^{\prime}$, which contains $v_{1}$, is odd. Since $R$ is
$C_{\ell}^{*}$-free (By Lemma 5.1 and note that $\ell>7$), the vertex
$u_{q-1}$ is adjacent to some $v_{i}$ with $c<i\leq\ell$. The vertex $u_{q}$
may or may not have other neighbors (other than $v_{1}$) on $B$. Thus,
$C^{\prime}$ is either $v_{1}u_{q}v_{i}v_{i+1}\cdots v_{\ell}$ or
$v_{1}u_{q}u_{q-1}v_{i}v_{i+1}\cdots v_{\ell}$. By the selection of $C$, we
have $|V(C^{\prime})\cap V(B)|=\ell-i+2\leq c$. In particular, $c\leq 3$, then
$i\geq\ell-1$. Therefore, $v_{3}$ is not adjacent to any vertex on
$C^{\prime}$, contradicting Corollary 5.2.

Thus, no vertex on $B$ is contained in any odd induced cycle.

Finally, we show that $R$ does not contain any odd cycle at all. Let $C$ be an
odd induced cycle that is disjoint from $B$. First assume $C=x_{1}x_{2}x_{3}$.
Since $R$ is $C_{3}^{*}$-free, every vertex on $B$ is adjacent to at least one
vertex on $C$. Without loss of generality that $x_{1}$ has the largest number
of neighbors on $B$, and let their indices be $i_{1}$, $i_{2}$, $\ldots$,
$i_{p}$, sorted increasingly. Note that all of them have the same parity by
the fourth claim. Since $R$ is $C_{6}$-free, $i_{j+1}-i_{j}$ is either two or
at least six for all $j=1,\ldots,p-1$. Since $p\geq\ell/3$, there must be
three consecutive ones with differences two; assume without loss of
generality, that they are $v_{1}$, $v_{3}$, and $v_{5}$. If $\ell=8$, then
$x_{1}v_{5}v_{6}\cdots v_{8}v_{1}$ has length six, and hence $x_{1}$ must be
adjacent to $v_{7}$ as well; otherwise, $x_{1}$ has another neighbor on $B$
because $p\geq\ell/3\geq 4$. This neighbor forms an $F_{3}$ with
$\\{x_{1},v_{1},v_{2},\ldots,v_{5}\\}$. Now that $|C|\geq 5$; let it be
$x_{1}x_{2}\cdots x_{|C|}$. We take $v_{i}\in N(x_{1})\cap V(B)$ and $v_{j}\in
N(x_{3})\cap V(B)$. The sub-path $v_{i}v_{i+1}\cdots v_{j}$ forms an odd cycle
with either $x_{1}x_{2}x_{3}$ or $x_{3}x_{4}\cdots x_{|C|}x_{1}$. From this
odd cycle we can retrieve an induced odd cycle, which has to intersect both
$B$ and $C$. This contradicts the fourth claim, and concludes the proof of
this lemma. ∎

$v_{c+1}$$v_{c+2}$$v_{c+3}$$v_{c+4}$$v_{c+5}$$v_{c+6}$$B$$C$$v_{c}/u_{c}$$v_{1}/u_{1}$$v_{\ell}$$v_{2}/u_{2}$
(a)

$v_{3}$$v_{4}$$v_{5}$$v_{2}$$v_{1}$$u_{3}$$u_{4}$ (b)

$v_{2}$$v_{3}$$v_{4}$$v_{1}$$v_{\ell}$$u_{2}$$u_{3}$$u_{q}$ (c)

Figure 5: Illustration for the proof of Lemma 5.3.

The following is immediate from Theorem 2.1, Lemma 2.3, and Lemma 5.3.

######  Corollary 5.4.

If a reduced graph $R$ is not bipartite, then $R$ is the complement of a
proper circular-arc graph.

We are now ready to present the algorithm for the proper circular-arc vertex
deletion problem. Let $(G,k)$ be an instance to the problem, and we may assume
without loss of generality that $G$ does not contain any small forbidden
induced subgraphs on at most seven vertices. If there is a set $V_{-}$ of $k$
vertices such that $G-V_{-}$ is a proper interval graph or
$\overline{G}-V_{-}$ is a bipartite permutation graph, then we are done.
Hence, we will look for a solution $V_{-}$ such that $G-V_{-}$ is both
connected and co-connected (Propositions 2.2 and 2.11).

For this purpose we may assume that $G$ itself is connected and co-connected:
if $G$ is not connected, we can work on the components of $G$ one by one, and
it is similar for $\overline{G}$. Thus, $\overline{G}$ is a reduced graph. If
$\overline{G}$ is not bipartite, then $G$ is already a proper circular-arc
graph (Corollary 5.4). Otherwise, $\overline{G}$ is bipartite, of which any
induced subgraph of it is bipartite. In other words, if there exists a
solution $V_{-}$, then $\overline{G}-V_{-}$ is a bipartite permutation graph,
and this has been handled already.

1. if $(G,k)$ is a yes-instance of proper interval vertex deletion then return “yes”; 2. if $(\overline{G},k)$ is a yes-instance of bipartite permutation vertex deletion then return “yes”; \\ We’re looking for a solution $V_{-}$ with both $G-V_{-}$ and $\overline{G}-V_{-}$ connected. 3. branch on deleting vertices of small forbidden induced subgraphs; 4. guess a component $C$ of $G$; 5. $k\leftarrow k-|V(G)\setminus V(C)|$; 6. if $\overline{C}$ is bipartite then return “no”; 7. $C^{\prime}\leftarrow$ a maximum non-bipartite component of $\overline{C}$; 8. if $|V(C)\setminus V(C^{\prime})|\leq k$ then return “yes”; else return “no.” Figure 6: The outline of the algorithm for proper circular-arc vertex deletion.

Again, it is quite straightforward to turn this algorithm into an
approximation algorithm, and the proof is similar to that of Theorem 3.2.

######  Theorem 5.5.

There is a $9^{k}\cdot n^{O(1)}$-time parameterized algorithm for the proper
circular-arc vertex deletion problem, and a polynomial-time approximation
algorithm of approximation ratio $9$ for the minimization version of the
proper circular-arc vertex deletion problem.

###### Proof.

We use the parameterized algorithm described in Figure 6. The correctness of
steps 1 and 2 follows from that all proper interval graphs and all the
complements of bipartitie permutation graphs are proper circular-arc graphs.
Step 3 is correct because a solution of $G$ needs to contain a vertex from
every forbidden induced subgraph of $G$. Since we have passed step 1, there
does not exist a solution $V_{-}$ such that $G-V_{-}$ is a proper interval
graph. Thus, the resulting graph is connected by Proposition 2.2, and all its
vertices are from a single component $C$ of $G$. This justifies steps 4 and 5.
On the other hand, since we have passed step 2, there does not exist a
solution $V_{-}$ such that $\overline{G}-V_{-}$ is a bipartite permutation
graph. If $\overline{C}$ is bipartite, then any induced subgraph of
$\overline{C}$ is bipartite. Thus, the correctness of step 6 follows from
Theorem 2.10. For the same reason, it suffices to consider each non-bipartite
component of $\overline{C}$ (Proposition 2.11). Note that each component of
$\overline{C}$ is a reduced graph. If it is non-bipartite, then its complement
is already a proper circular-arc graph (Corollary 5.4). Thus, it suffices to
take the non-bipartite component of $\overline{C}$ of the maximum order, and
remove all the others. This justifies steps 7 and 8.

We now analyze the running time of the algorithm. The first two steps take
time $O(6^{k}\cdot(m+n))$ [3] and $9^{k}\cdot n^{O(1)}$ [1], respectively. At
most $7$ recursive calls are made in step 3, all with parameter value $k-1$.
Thus, it takes $7^{k}\cdot n^{O(1)}$ time. There are at most $n$ components in
$G$, and the rest (steps 5–8) can be done in $O(m+n)$ time. Thus, the
algorithm can be done in $9^{k}\cdot n^{O(1)}$ time.

We now modify the parameterized algorithm to produce an approximation
algorithm. We check every set of at most seven vertices of $G$. If it induces
a forbidden induced subgraph, then we remove all its vertices from $G$ and add
them to the solution. We continue this process until no such a set can be
found, and let $G^{\prime}$ be the resulting graph. We construct three
solutions, and return the smallest of them, with ties broken arbitrarily. The
first is by applying the $6$-approximation algorithm for proper interval
vertex deletion [3] to $G^{\prime}$, and the second is by applying the
$9$-approximation algorithm for bipartite permutation vertex deletion [1] to
$\overline{G^{\prime}}$. Let them be denoted by $V_{-}^{1}$ and $V_{-}^{2}$,
respectively. For each component, we take the largest non-bipartite component
of its complement. We put all the other vertices into a set. We take the
smallest of these sets as the third solution $V_{-}^{3}$. We return the
smallest of the three solutions.

Let $V^{*}_{-}$ be an optimal solution to $G$. Clearly, $|V(G)\setminus
V(G^{\prime})|\leq 7|V^{*}_{-}\setminus V(G^{\prime})|$. If
$G^{\prime}-V^{*}_{-}$ is a proper interval graph, then $|V_{-}^{1}\cap
V(G^{\prime})|\leq 6\mathrm{opt}(G^{\prime})\leq 6|V^{*}_{-}\cap
V(G^{\prime})|$; likewise, if $\overline{G}-S$ is a bipartite permutation
graph, then $|V_{-}^{2}\cap V(G^{\prime})|\leq 9|V^{*}_{-}\cap
V(G^{\prime})|$. If neither is true, then $|V_{-}^{3}\cap
V(G^{\prime})|=\mathrm{opt}(G^{\prime})\leq|V^{*}_{-}\cap V(G^{\prime})|$.
Therefore, the size of the solution returned by the algorithm is never greater
than $9|V^{*}_{-}|$. ∎

## Appendix: Hardness of edge modifications to proper (Helly) circular-arc
graphs

We note that the NP-completeness of the edge modification problems toward
proper (Helly) circular-arc graphs follows from Proposition 2.2.

######  Lemma A.6.

Both the proper Helly circular-arc edge deletion problem and the proper Helly
circular-arc completion problem are NP-complete.

###### Proof.

Both problems are clearly in NP, and we now show their NP-hardness. Let $G$ be
a graph, and let $G^{\prime}$ be the graph obtained from $G$ by adding
$|V(G)|^{2}$ isolated vertices. Since $G^{\prime}$ is not connected, we cannot
make it connected by deleting edges. By Proposition 2.2, $(G,k)$ is a yes-
instance of the proper interval edge deletion problem if and only if
$(G^{\prime},k)$ is a yes-instance of the proper Helly circular-arc edge
deletion problem. We now consider the completion problem. On the one hand, to
make $G^{\prime}$ connected we need to add at least $|V(G)|^{2}$ edges. On the
other hand, we can always make $G^{\prime}$ a proper interval graph by adding
all possible edges to make each component a clique. Thus, $(G,k)$ is a yes-
instance of the proper interval completion problem if and only if
$(G^{\prime},k)$ is a yes-instance of the proper Helly circular-arc completion
problem. The statement then follows from NP-hardness of the corresponding
problems toward proper interval graphs [21, 14]. ∎

Let us remark that the reductions used in the proof of Lemma A.6 also apply to
edge modification problems toward proper circular-arc graphs.

## References

  * [1] Łukasz Bożyk, Jan Derbisz, Tomasz Krawczyk, Jana Novotná, and Karolina Okrasa.  Vertex deletion into bipartite permutation graphs.  In Yixin Cao and Marcin Pilipczuk, editors, 15th International Symposium on Parameterized and Exact Computation, IPEC 2020, December 14-18, 2020, Hong Kong, China, volume 180 of LIPIcs, pages 5:1–5:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.  doi:10.4230/LIPIcs.IPEC.2020.5.
  * [2] Yixin Cao.  Linear recognition of almost interval graphs.  In Robert Krauthgamer, editor, Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1096–1115. SIAM, 2016\.  doi:10.1137/1.9781611974331.ch77.
  * [3] Yixin Cao.  Unit interval editing is fixed-parameter tractable.  Information and Computation, 253:109–126, 2017.  doi:10.1016/j.ic.2017.01.008.
  * [4] Yixin Cao, Luciano N. Grippo, and Martín D. Safe.  Forbidden induced subgraphs of normal Helly circular-arc graphs: Characterization and detection.  Discrete Applied Mathematics, 216:67–83, 2017.  doi:10.1016/j.dam.2015.08.023.
  * [5] Yixin Cao and Yuping Ke.  Recognizing subclasses of circular-arc graphs.  manuscript, 2022.
  * [6] Yixin Cao and Dániel Marx.  Interval deletion is fixed-parameter tractable.  ACM Transactions on Algorithms, 11(3):21:1–21:35, 2015.  doi:10.1145/2629595.
  * [7] Maria Chudnovsky and Paul D. Seymour.  Claw-free graphs. III. Circular interval graphs.  Journal of Combinatorial Theory, Series B, 98(4):812–834, 2008\.  doi:10.1016/j.jctb.2008.03.001.
  * [8] Christophe Crespelle, Pål Grønås Drange, Fedor V. Fomin, and Petr A. Golovach.  A survey of parameterized algorithms and the complexity of edge modification.  arXiv:2001.06867, 2020.
  * [9] Xiaotie Deng, Pavol Hell, and Jing Huang.  Linear-time representation algorithms for proper circular-arc graphs and proper interval graphs.  SIAM Journal on Computing, 25(2):390–403, 1996.  doi:10.1137/S0097539792269095.
  * [10] Rodney G. Downey and Michael R. Fellows.  Fundamentals of Parameterized Complexity.  Undergraduate texts in computer science. Springer, 2013.  doi:10.1007/978-1-4471-5559-1.
  * [11] Guillermo Durán and Min Chih Lin.  Clique graphs of Helly circular arc graphs.  Ars Combinatoria, 60, 2001.
  * [12] Tibor Gallai.  Transitiv orientierbare graphen.  Acta Mathematica Academiae Scientiarum Hungaricae, 18:25–66, 1967\.  Translated by Frédéric Maffray and Myriam Preissmann as in Perfect Graphs, Jorge L. Ramírez-Alfonsín and Bruce A. Reed, Eds., Wiley, 2001, pp.25-66.  doi:10.1007/BF02020961.
  * [13] Fănică Gavril.  Algorithms on circular-arc graphs.  Networks, 4:357–369, 1974.  doi:10.1002/net.3230040407.
  * [14] Paul W. Goldberg, Martin C. Golumbic, Haim Kaplan, and Ron Shamir.  Four strikes against physical mapping of DNA.  Journal of Computational Biology, 2(1):139–152, 1995.  doi:10.1089/cmb.1995.2.139.
  * [15] Bruce Hedman.  Clique graphs of time graphs.  Journal of Combinatorial Theory, Series B, 37(3):270–278, 1984\.  doi:10.1016/0095-8956(84)90059-5.
  * [16] Pavol Hell and Jing Huang.  Interval bigraphs and circular arc graphs.  Journal of Graph Theory, 46(4):313–327, 2004.  doi:10.1002/jgt.20006.
  * [17] Min Chih Lin, Francisco J. Soulignac, and Jayme L. Szwarcfiter.  Proper Helly circular-arc graphs.  In Andreas Brandstädt, Dieter Kratsch, and Haiko Müller, editors, Graph Theoretic Concepts in Computer Science - WG 2007, volume 4769 of LNCS, pages 248–257. Springer, 2007.  doi:10.1007/978-3-540-74839-7_24.
  * [18] Min Chih Lin, Francisco J. Soulignac, and Jayme L. Szwarcfiter.  Normal Helly circular-arc graphs and its subclasses.  Discrete Applied Mathematics, 161(7-8):1037–1059, 2013.  doi:10.1016/j.dam.2012.11.005.
  * [19] Alan C. Tucker.  Structure theorems for some circular-arc graphs.  Discrete Mathematics, 7(1-2):167–195, 1974.  doi:10.1016/S0012-365X(74)80027-0.
  * [20] Pim van ’t Hof and Yngve Villanger.  Proper interval vertex deletion.  Algorithmica, 65(4):845–867, 2013.  doi:10.1007/s00453-012-9661-3.
  * [21] Mihalis Yannakakis.  Computing the minimum fill-in is NP-complete.  SIAM Journal on Algebraic and Discrete Methods, 2(1):77–79, 1981\.  doi:10.1137/0602010.