Proper Interval Vertex Deletion

Abstract

The NP-complete problem Proper Interval Vertex Deletion is to decide whether an input graph on n vertices and m edges can be turned into a proper interval graph by deleting at most k vertices. Van Bevern et al. (In: Proceedings WG 2010. Lecture notes in computer science, vol. 6410, pp. 232–243, 2010) showed that this problem can be solved in $\mathcal {O}((14k +14)^{k+1} kn^{6})$ time. We improve this result by presenting an $\mathcal {O}(6^{k} kn^{6})$ time algorithm for Proper Interval Vertex Deletion. Our fixed-parameter algorithm is based on a new structural result stating that every connected component of a {claw,net,tent,C ₄,C ₅,C ₆}-free graph is a proper circular arc graph, combined with a simple greedy algorithm that solves Proper Interval Vertex Deletion on {claw,net,tent,C ₄,C ₅,C ₆}-free graphs in $\mathcal {O}(n+m)$ time. Our approach also yields a polynomial-time 6-approximation algorithm for the optimization variant of Proper Interval Vertex Deletion.

1 Introduction

Many NP-hard problems can be solved in polynomial time on restricted graph classes. Classical examples are the polynomial-time algorithms for Graph Coloring, Maximum Clique and Maximum Independent Set on chordal graphs by Gavril [9] and on perfect graphs by Grötschel, Lovász and Schrijver [11], the polynomial-time algorithm for computing the branchwidth of a planar graph by Seymour and Thomas [21], and Courcelle’s Theorem for solving problems expressible in monadic second-order logic on graphs of bounded treewidth [7]. We refer to the book of Golumbic [10] for further references on algorithms for special graph classes.

Often, algorithms for solving problems on specific graph classes can be generalized to also work for graphs that are somehow close to these graph classes. The closeness of a graph G to a graph class can be defined in several ways, leading to different types of graph modification problems. Let us mention three types of graph modification problems here, covering many of the most natural problems in algorithmic graph theory. The -Vertex Deletion problem takes as input a graph G and an integer k, and the task is to decide whether G can be transformed into a graph that belongs to class by deleting at most k vertices from G. The -Edge Deletion problem is defined similarly, but now the question is whether a member of can be obtained by deleting at most k edges from G. The problem of deciding whether a graph in can be obtained by adding at most k edges to G is known as the -Completion problem.

It is hardly surprising that the problems -Vertex Deletion, -Edge Deletion, and -Completion are NP-hard for almost all natural graph classes . For example, Yannakakis [26] showed that -Edge Deletion is NP-complete for many different classes , such as forests, bipartite graphs and outerplanar graphs. Lewis and Yannakakis [16] showed that -Vertex Deletion is NP-complete for any nontrivial and hereditary graph class , where a graph class is called hereditary if every induced subgraph of every graph in the class also belongs to the same graph class. Arguably the most famous NP-complete example of -Completion is the Minimum Fill-In problem, which is the problem of determining the smallest number of edges whose addition makes the input graph chordal [27].

From a parameterized complexity perspective, the situation is much less clear. We are still far from understanding what properties make a graph modification problem fixed-parameter tractable (FPT), which means that there exists an algorithm that solves the problem on n-vertex input graphs in f(k)⋅n ^c time, for some constant c and some function f that depends only on k. Examples of graph classes for which -Vertex Deletion is known to be FPT are edgeless graphs [6], forests [4], chordal graphs [18], planar graphs [19] and proper interval graphs [23]. On the other hand, -Vertex Deletion is known to be W[2]-hard when is the class of wheel-free graphs [17] or the class of perfect graphs [12], rendering it highly unlikely that an FPT algorithm exists for these classes. The -Edge Deletion problem is known to be FPT when is the class of planar graphs [14], forests [5], or chordal graphs [18]. For the -Completion problem, FPT algorithms are known for the case where is the class of chordal graphs [3, 13], interval graphs [24] or proper interval graphs [13].

All the graph classes mentioned above can be characterized by a (not necessarily finite) set of forbidden induced subgraphs. Cai [3] showed that the problems -Vertex Deletion, -Edge Deletion and -Completion are all FPT for any hereditary graph class , as long as can be characterized by a finite number of forbidden induced subgraphs. The result of Cai leaves the parameterized complexity open for all hereditary graph classes that cannot be characterized by a finite number of forbidden induced subgraphs. A typical example, corresponding to the famous Feedback Vertex Set problem, is the class of forests, where all the cycles are forbidden induced subgraphs.

In this paper, a hole is defined as an induced cycle of length at least 4, and thus chordal graphs are exactly the graphs that are hole-free. Despite this simple characterization, it was not until 2006 that Marx [18] proved the Chordal Vertex Deletion problem to be FPT. Wegner [25] (see also Brandstädt et al. [2]) showed that proper interval graphs are exactly the class of graphs that are {claw,net,tent,hole}-free, where the claw, the net, and the tent are three well-known graphs on at most 6 vertices (see Fig. 1). Proper interval graphs are hereditary, since each induced subgraph of a {claw,net,tent,hole}-free graph is also {claw,net,tent,hole}-free. Hence, by combining the aforementioned results of Wegner, Cai, and Marx, it can be shown that Proper Interval Vertex Deletion is FPT. Recently, van Bevern et al. [23] presented an algorithm for Proper Interval Vertex Deletion using the structure of a problem instance that is already {claw,net,tent,C ₄,C ₅,C ₆}-free. Using this approach, they obtained an algorithm with running time $\mathcal {O}((14k +14)^{k+1} kn^{6})$. Furthermore, they showed that the Proper Interval Vertex Deletion problem remains NP-complete when restricted to {claw,net,tent}-free input graphs.

Fig. 1

The (infinite) family of forbidden induced subgraphs of proper interval graphs: the claw, the net, the tent, and all the holes, i.e., all induced cycles of length at least 4

Our Results

We present a simpler and faster algorithm for the Proper Interval Vertex Deletion problem than the one presented by van Bevern et al. [23]. Our algorithm, which runs in time $\mathcal {O}(6^{k} kn^{6})$, is based on a new combinatorial result of independent interest, stating that every connected component of a {claw,net,tent,C ₄,C ₅,C ₆}-free graph is a proper circular arc graph. Using the structure of proper circular arc graphs, we show that Proper Interval Vertex Deletion can be solved on {claw,net,tent,C ₄,C ₅,C ₆}-free graphs in linear time. Our FPT algorithm for Proper Interval Vertex Deletion on general graphs is obtained by combining this linear-time algorithm with a branching algorithm that produces a family of {claw,net,tent,C ₄,C ₅,C ₆}-free problem instances. Like the algorithm by Villanger et al. [24] for Interval Completion, this is a branching algorithm where the leaves of the search tree correspond to polynomial-time solvable problem instances, rather than potential solutions. To complement the study of modifying a graph into a proper interval graph by deleting vertices, we also give a polynomial-time 6-approximation algorithm for the optimization variant of Proper Interval Vertex Deletion.

2 Preliminaries

All graphs considered in this text are simple and undirected. For a graph G=(V,E), we use n to denote the number of vertices and m to denote the number of edges in G. Two vertices u,v∈V are adjacent if {u,v}∈E. The neighborhood of a vertex u in G is denoted by N _G (u), and a vertex v∈N _G (u) if {u,v}∈E. The closed neighborhood of u is the set N _G [u]=N _G (u)∪{u}. Two vertices u,v∈V are twins if N _G [u]=N _G [v]. Let S⊆V. We write G[S] to denote the subgraph of G induced by S, i.e., G[S]:=(S,{{u,v}∈E∣u,v∈S}). The graph G[V∖S] is denoted by G−S, and we write G−v instead of G−{v} for a vertex v∈V.

A path P in G is a subgraph of G whose vertices can be ordered v ₁,v ₂,…,v _r such that {v _i ,v _i+1}∈E for 1≤i<r. A path P is called induced if {v _i ,v _j }∉E whenever i+1<j. If {v ₁,v _r }∈E, then P is a cycle in G, and this cycle is induced if 1 and r are the only values of i and j for which i+1<j and {v _i ,v _j }∈E. A chord of a path (cycle) is an edge of G between two vertices of the path (cycle) that are not consecutive on the path (cycle). The length of a path (cycle) is the number of edges in that path (cycle). A hole is an induced cycle of length at least 4. We use C _r to denote a hole of length r≥4. A graph is hole-free if it does not contain a hole as an induced subgraph. More generally, we say that a graph G is F-free for some graph F if G does not contain an induced subgraph isomorphic to F. For any family $\mathcal{F}$ of graphs, we say that G is ${\mathcal{F}}$ -free if G is F-free for every $F\in {\mathcal{F}}$. If a graph class ${\mathcal{G}}$ is ${\mathcal{F}}$-free, then the graphs in ${\mathcal{F}}$ are called the forbidden induced subgraphs of ${\mathcal{G}}$.

A graph G is an interval graph if it is the intersection graph of intervals on the real line, i.e., if each vertex of G can be assigned an interval on the real line, such that two vertices are adjacent in G if and only if their corresponding intervals intersect. The collection of intervals ${\mathcal{I}}$ is called an interval model of G. A proper interval graph, also known as a unit interval graph or an indifference graph, is an interval graph that has an interval model ${\mathcal{I}}$ where no interval is properly contained in another interval, i.e., where no interval is a subinterval of another interval. Alternatively, a graph is a proper interval graph if and only if it is {claw,net,tent,hole}-free [25]; see Fig. 1 for a depiction of the forbidden induced subgraphs of proper interval graphs.

A graph G is a circular arc graph if it is the intersection graph of arcs on a circle, i.e., if each vertex of G can be assigned an interval (arc) on a circle such that two vertices are adjacent in G if and only if their corresponding intervals intersect. Like for interval graphs, the intervals in ${\mathcal{I}}$ constitute a (circular arc) model of G. A circular arc graph is a proper circular arc graph if it has a model ${\mathcal{I}}$ where no interval of the model is a subinterval of another interval. An example of a proper circular arc graph (the tent) and a corresponding proper circular arc model is given in Fig. 2. A circular arc graph is a unit circular arc graph if it has a circular arc model where all the arcs are of unit length. It is easy to see that every unit circular arc graph is a proper circular arc graph. The reverse, however, is not true: Tucker [22] showed that the tent (see Fig. 2) is not a unit circular arc graph. This is an interesting contrast to the well-known fact that the classes of proper interval graphs and unit interval graphs do coincide [20].

Fig. 2

A proper circular arc graph (the tent) on the left, with a corresponding proper circular arc model on the right. The three vertices of degree 2 in the tent form a so-called asteroidal triple, which implies that the tent is not an interval graph [15]

Let G be a proper circular arc graph and let ${\mathcal{I}}$ be a proper circular arc model of G. For any subset ${\mathcal{X}}\subseteq {\mathcal{I}}$ of intervals, we say that (the union of the intervals in) ${\mathcal{X}}$ covers the circle if every point of the circle in the model ${\mathcal{I}}$ is contained in at least one interval in ${\mathcal{X}}$. Recall that in any proper circular arc model, no interval is a subinterval of another interval. Consequently, we may assume that no single interval in ${\mathcal{I}}$ covers the circle. In fact, it is known that every proper circular arc graph has a proper circular arc model in which no pair of intervals covers the circle [10, 22]. Moreover, we may always assume that no two intervals in a proper circular arc model share an endpoint, i.e., that all 2n endpoints of intervals in ${\mathcal{I}}$ are distinct [22]. Throughout the paper, we will tacitly assume that all proper circular arc models we consider satisfy these properties.

Given a proper circular arc model ${\mathcal{I}}$ of a proper circular arc graph G, we refer to the clockwise direction along the circle as the right direction, whereas the left direction refers to the counter-clockwise direction. Each vertex v of G corresponds to an interval I _v in ${\mathcal{I}}$ whose leftmost point v ^s is called its start point, and whose rightmost point v ^e is called its end point; note that v ^s and v ^e are well-defined due to the assumption that no interval in ${\mathcal{I}}$ covers the circle. For convenience, we will label an interval I _v simply with v in any figure of a circular arc model in this paper.

For two points p ₁ and p ₂ on an interval I _v , we say that p ₁ is left of p ₂, denoted by p ₁<p ₂, if p ₂ is not a point on the subinterval of I _v from v ^s to p ₁. We write p ₁≤p ₂ if either p ₁=p ₂ or p ₁ is to the left of p ₂. An interval I _v is to the left of an interval I _w if v ^s<w ^s<v ^e<w ^e, and in this case we say that I _w is to the right of I _v . Note that, for any two intersecting intervals $I_{v},I_{w}\in {\mathcal{I}}$, either I _v is to the left of I _w or vice versa, since we assume that no two intervals in ${\mathcal{I}}$ cover the circle. For obvious reasons, we cannot define “to the left” and “to the right” if the intervals I _v and I _w do not intersect. For two adjacent vertices v and w in G, we say that v is to the left of w (and w is to the right of v) if the interval I _v is to the left of the interval I _w in ${\mathcal{I}}$. A vertex v is the leftmost neighbor of a vertex w if v is to the left of w, and no other neighbor of w is to the left of v. The rightmost neighbor of a vertex is defined analogously.

Let I _v and I _v be two intersecting intervals in ${\mathcal{I}}$, where I _v is to the left of I _w . We define the union of I _v and I _w to be the interval with start point v ^s and end point w ^e. Let X⊆V be a set such that G[X] is connected. Then there exists a vertex ordering v ₁,v ₂,…,v _|X| of the vertices in X such that G[{v ₁,v ₂,…,v _i }] is connected for 1≤i≤|X|. Let ${\mathcal{X}}=\{I_{v} \mid v\in X\}$ be the set of intervals in ${\mathcal{I}}$ corresponding to the vertices in X. The union of the intervals in ${\mathcal{X}}$ is the interval I _1,|X|, where the interval I _1,i is defined recursively as the union of the interval I _1,i−1 and the interval $I_{v_{i}}$, and where I _1,2 is the union of intervals $I_{v_{1}}$ and $I_{v_{2}}$. Equivalently, the union of the intervals of ${\mathcal{X}}$ is the interval that contains exactly those points of the circle of model ${\mathcal{I}}$ that are contained in at least one interval in ${\mathcal{X}}$.

3 Almost Proper Interval Graphs

Adopting the terminology introduced by van Bevern et al. [23], we define an almost proper interval graph to be a {claw,net,tent,C ₄,C ₅,C ₆}-free graph. The main result of this section is a theorem stating that every connected component of an almost proper interval graph is a proper circular arc graph. Before presenting this main result, we prove some structural properties of proper circular arc graphs and almost proper interval graphs.

Lemma 1

Let G be a proper circular arc graph and let ${\mathcal{I}}$ be a proper circular arc model of G. If G contains an induced cycle of length r≥4, then $|{\mathcal{X}}|\geq \lceil r/2 \rceil$ for any subset ${\mathcal{X}}\subseteq {\mathcal{I}}$ of intervals whose union covers the circle.

Proof

Let us first recall that we may assume that all 2n start and end points of the intervals in ${\mathcal{I}}$ are distinct. Let ϵ be the smallest distance on the circle between any two of these 2n start and end points. We now construct a new proper circular arc model ${\mathcal{I}}'$ from ${\mathcal{I}}$ as follows. First, for each $I_{v}\in {\mathcal{I}}$, we add an identical interval I _v′ to the model; we say that each added interval I _v′ is marked. Then, for each pair of identical intervals I _v and I _v′, we shift the start and end points of the marked interval I _v′ by ϵ/2 to the right. This finishes the construction of ${\mathcal{I}}'$. Note that, by construction, ${\mathcal{I}}'$ is a proper circular arc model, and that all 4n start and end points of the intervals in ${\mathcal{I}}'$ are distinct.

Let G′ be the proper circular arc graph represented by the model ${\mathcal{I}}'$. We say that a vertex v′ in G′ is marked if its corresponding interval I _v′ is marked. Note that, for each vertex v of G, the vertices v and v′ are twins in G′, since the intervals I _v and I _v′ intersect exactly the same set of intervals in ${\mathcal{I}}'$.

Suppose G′ contains an induced cycle C on r≥4 unmarked vertices, and let ${\mathcal{Y}}$ be the set of intervals in the model ${\mathcal{I}}'$ representing the vertices of C. Notice that the union of the intervals in ${\mathcal{Y}}$ covers the circle of the model ${\mathcal{I}}'$, as in any proper circular arc model, only induced cycles of length 3 can be represented by intervals whose union does not cover the circle. Let ${\mathcal{X}}'$ be a minimal subset of marked intervals in ${\mathcal{I}}'$ such that the union of the intervals in ${\mathcal{X}}'$ covers the circle. Due to the minimality of ${\mathcal{X}}'$, the set of vertices represented by the intervals in ${\mathcal{X}}'$ induces a cycle in G′.

Let the intervals of ${\mathcal{Y}}$ be numbered $I_{v_{1}}$ to $I_{v_{r}}$ in such a way that $I_{v_{i-1}}$ is to the left of $I_{v_{i}}$ for 1<i≤r, and $I_{v_{r}}$ is to the left of $I_{v_{1}}$. In a similar way, let the intervals of ${\mathcal{X}}'$ be numbered $I_{u_{1}}$ to $I_{u_{|{\mathcal{X}}'|}}$ in such a way that $I_{u_{1}}$ is to the left of $I_{v_{1}}$, $I_{v_{1}}$ is to the left of $I_{u_{2}}$, $I_{u_{i-1}}$ is to the left of interval $I_{u_{i}}$ for $1 < i \leq |{\mathcal{X}}'|$, and $I_{u_{|{\mathcal{X}}'|}}$ is to the left of $I_{u_{1}}$. Notice that these two orderings exist since ${\mathcal{Y}}$ and ${\mathcal{X}}'$ both cover the circle, and there are no two intervals in ${\mathcal{Y}}\cup {\mathcal{X}}'$ such that one is a subinterval of another.

For any two points x and y, we will say that x is to the left of y, denoted by x<y, if x is to the left of y on the interval that is the union of the intervals in ${\mathcal{X}}'\setminus \{I_{u_{|{\mathcal{X}}'}|}\}$. Note that “to the left” is well-defined here, since the union of the intervals in ${\mathcal{X}}'\setminus \{I_{u_{|{\mathcal{X}}'}|}\}$ does not cover the circle due to the minimality of ${\mathcal{X}}'$. We now distinguish between two cases. □

Case 1: $v_{2}^{s} < u_{1}^{e}$

We first prove that $u_{i}^{e}<v_{2i-1}^{e}$ for 1<i≤r by induction on i. Note that $u_{2}^{e}<v_{3}^{e}$, since the definition of ${\mathcal{I}}'$ implies that $u_{2}^{s}<u_{1}^{e}<v_{1}^{e}<v_{3}^{s}$, and $I_{v_{3}}$ is not a subinterval of $I_{u_{2}}$ (see Fig. 3). Hence the claim holds for i=2. For the induction hypothesis, suppose that $u_{i-1}^{e}<v_{2i-3}^{e}$ for some i≥2. Then $u_{i}^{s}<u_{i-1}^{e}<v_{2i-3}^{e}<v_{2i-1}^{s}$. This, together with the observation that $I_{v_{2i-1}}$ is not a subinterval of $I_{u_{i}}$, implies that $u_{i}^{e}<v_{2i-1}^{e}$.

Fig. 3

Figure for Case 1: $v_{2}^{s} < u_{1}^{e}$. We prove that, in this case, $u_{i}^{e} < v_{2i-1}^{e}$ for 1<i≤r

Since we are considering the case where $v_{2}^{s} < u_{1}^{e}$ and $I_{v_{r}}$ is not a subinterval of $I_{u_{1}}$, we have $v_{r-2}^{e}<u_{1}^{s}$. By the above induction proof, we know that $u_{r-1}^{e}<v_{2r-4}^{e}$, and hence $u_{\lfloor (r-1)/2\rfloor}^{e}<v_{r-2}^{e}$. Consequently, interval $I_{u_{\lfloor (r-1)/2\rfloor}+1}$ is required to cover point $v_{r-2}^{e}$, which implies that $|{\mathcal{X}}'|\geq \lfloor (r-1)/2\rfloor+1=\lceil r/2\rceil$.

Case 2: $u_{1}^{e} < v_{2}^{s}$

Since $u_{1}^{e} < v_{2}^{s}$, we know that $u_{2}^{s} < u_{1}^{e} < v_{2}^{s} < u_{2}^{e} < v_{2}^{e}$, where the last inequality follows from the fact that $I_{v_{2}}$ is not a subinterval of $I_{u_{2}}$ (see Fig. 4). Using similar arguments as in Case 1, we can use induction on i to prove that $u_{i}^{e} < v_{2i-2}^{e}$ for 1<i≤r as follows. We already observed that the base case $u_{2}^{e}<v_{2}^{e}$ holds. Assume that $u_{i-1}^{e} < v_{2i-4}^{e}$ for some i≥2. Then $u_{i}^{s} < u_{i-1}^{e} < v_{2i-4}^{e} < v_{2i-2}^{s}$. Since $I_{v_{2i-2}}$ is not a subinterval of $I_{u_{i}}$, we get $u_{i}^{e} < v_{2i-2}^{e}$.

Fig. 4

Figure for Case 2: $u_{1}^{e} < v_{2}^{s}$. We prove that, in this case, $u_{i}^{e} < v_{2i-2}^{e}$ for 1<i≤r

The assumption $u_{1}^{e} < v_{2}^{s}$ implies that $v_{r-3}^{e} < u_{1}^{s}$, since otherwise $I_{v_{r-1}}$ would be a subinterval of $I_{u_{1}}$. It follows from the above induction proof that $u_{\lfloor(r-1)/2\rfloor}^{e} < v_{r-3}^{e}$, which means that the interval I _{⌊(r−1)/2⌋+1} is required to cover the point $v_{r-3}^{e}$. Just as in Case 1, we conclude that $|{\mathcal{X}}'|\geq \lfloor (r-1)/2\rfloor +1 = \lceil r/2 \rceil$.  □

The following result is due to Brandstädt and Dragan [1].

Proposition 1

([1])

Let C be an induced cycle of length at least 5 in a {claw,net}-free graph G of diameter greater than 3. Then every vertex in V(G)∖V(C) is adjacent exactly to two, three or four consecutive vertices of C.

The following result, which will be used in the proofs of some of the lemmas below, easily follows from Proposition 1. Note that the class of {claw,net,C ₄}-free graphs is a superclass of the class of almost proper interval graphs.

Corollary 1

Let C be an induced cycle of length at least 6 in a {claw,net,C ₄}-free graph G. Then every vertex in V(G)∖V(C) is adjacent exactly to two, three or four consecutive vertices of C.

Proof

Brandstädt and Dragan [1] proved that a {claw,net}-free graph of diameter greater than 3 cannot contain the C ₅, the tent, or the graph $S_{3}^{-}$ as an induced subgraph, where $S_{3}^{-}$ is the graph obtained from the tent by removing one edge between two vertices of degree 4 (such as the edge ab in Fig. 2). Moreover, it follows from the proof of Proposition 1 in [1] that we can replace “in a {claw,net}-free graph G of diameter greater than 3” in Proposition 1 by “in a $\{\mbox {claw},\mbox {net},S_{3}^{-}\}$-free graph G”. Since the graph $S_{3}^{-}$ contains a C ₄ as an induced subgraph, this suffices to prove Corollary 1. □

Recall that an almost proper interval graph is a {claw,net,tent,C ₄,C ₅,C ₆}-free graph. In Theorem 1 below, we prove that every connected almost proper interval graph is a proper circular arc graph. The proof of Theorem 1 is constructive: given a connected almost proper interval graph G, a proper circular arc model of G is constructed in an incremental way as follows. The algorithm starts with an induced subgraph of G that is an induced cycle of length at least 7. (Note that if G does not contain such a cycle, G is a proper interval graph, and hence a proper circular arc graph.) At the start of the k-th iteration, the algorithm considers an induced subgraph G _k−1 of G that is a connected proper circular arc graph that contains an induced cycle of length at least 7. A new vertex v _k of G is added to the graph G _k−1 in such a way that the obtained subgraph G _k of G is connected. The algorithm then constructs a proper circular arc model of G _k from the proper circular arc model of G _k−1, and proceeds to the next iteration. The algorithm continues until a proper circular arc model of G has been constructed.

The crucial step in each iteration of the algorithm is the construction of a proper circular arc model of G _k from the proper circular arc model of G _k−1. In order to prove that we can always do this, we need a few structural lemmas. In the three lemmas below, we consider the case where G _k is a connected almost proper interval graph that has a vertex v:=v _k , such that the graph G _k−1=G _k −v is a proper circular arc graph that contains a cycle C=w ₁,w ₂,…,w _r for some r≥7. Let ${\mathcal{I}}_{k-1}$ be a proper circular arc model of G _k−1.

The first lemma below shows that, due to the presence of the long cycle C in G _k−1, no subset of six or less intervals in ${\mathcal{I}}_{k-1}$ can cover the circle.

Lemma 2

For any subset ${\mathcal{X}}\subseteq {\mathcal{I}}_{k-1}$ of intervals whose union covers the circle of model ${\mathcal{I}}_{k-1}$, we have that $|{\mathcal{X}}|\geq 7$.

Proof

Let ${\mathcal{X}}\subseteq {\mathcal{I}}$ be a set of intervals whose union covers the circle. Since ${\mathcal{X}}$ covers the circle, there is a subset ${\mathcal{X}}'\subseteq {\mathcal{X}}$ such that ${\mathcal{X}}'$ covers the circle and the vertices of G _k−1 corresponding to the intervals in ${\mathcal{X}}'$ induce a cycle in G _k−1. By Lemma 1, any subset of intervals in ${\mathcal{I}}_{k-1}$ that covers the circle must contain at least 4 intervals, so $|{\mathcal{X}}'|\geq 4$. In fact, since G _k−1 is {C ₄,C ₅,C ₆}-free, we know that $|{\mathcal{X}}'|\geq 7$. Since $|{\mathcal{X}}|\geq |{\mathcal{X}}'|$, the lemma follows. □

The following lemma states that there are two consecutive vertices on cycle C such that v is adjacent to both of them, and every other neighbor of v in G _k is adjacent to at least one of them.

Lemma 3

There exist two consecutive vertices w _t ,w _t+1 on cycle C such that $w_{t},w_{t+1} \in N_{G_{k}}(v)$ and $N_{G_{k}}(v) \subseteq N_{G_{k}}(w_{t}) \cup N_{G_{k}}(w_{t+1})$.

Proof

Since G _k is an induced subgraph of an almost proper interval graph, G _k is {claw,net,tent,C ₄,C ₅,C ₆}-free, and in particular {claw,net,C ₄}-free. Hence, by Corollary 1, the neighbors of v in G _k on cycle C are w _i ,w _i+1,…,w _j , where j≤i+3. Let us first argue that every vertex $x \in N_{G_{k}}(v) \setminus \{w_{i},w_{i+1},\allowbreak\ldots,w_{j}\}$ has a neighbor w _q such that i≤q≤j. For contradiction, let us assume that x is a vertex of $N_{G_{k}}(v) \setminus \{w_{i},w_{i+1},\allowbreak\ldots,w_{j}\}$ that does not have such a neighbor. Then j=i+1, since otherwise G _k [{x,u,w _i ,w _j }] would be a claw. If j=i+1 and x is adjacent to neither w _i−1 nor w _i+2, then G _k [{w _i−1,w _i ,w _i+1,w _i+2,u,x}] is a net. On the other hand, if x is adjacent to w _i−1 or w _i+2, then G _k [{x,u,w _i ,w _i−1}] or G _k [{x,u,w _i+1,w _i+2}] is a C ₄, respectively. In each case, we obtain the desired contradiction.

Now let us assume, for contradiction, that there exists no integer t with i≤t<j such that $N_{G_{k}}(v) \subseteq N_{G_{k}}(w_{t}) \cup N_{G_{k}}(w_{t+1})$. By Corollary 1, the neighbors of any $x \in N_{G_{k}}(v) \setminus V(C)$ on cycle C are consecutive on the cycle, and by the argument above, x has at least one neighbor in {w _i ,w _i+1,…,w _j }. Let i′ and j′ be the largest and smallest integers, respectively, such that i≤i′≤j′≤j and $N_{G_{k}}(v) \subseteq \bigcup_{i' \leq \tau \leq j'}N_{G_{k}}(w_{\tau})$. Let $x,y \in N_{G_{k}}(v)$ be vertices such that $N_{G_{k}}(x) \cap \{w_{i'},w_{i'+1},\ldots,w_{j'}\} = \{w_{i'}\}$ and $N_{G_{k}}(y) \cap \{w_{i'},w_{i'+1},\ldots,w_{j'}\} = \{w_{j'}\}$; note that such vertices x and y exist by the definition of i′ and j′. Recall that we assumed that there is no i≤t<j such that $N_{G_{k}}(v) \subseteq N_{G_{k}}(w_{t}) \cup N_{G_{k}}(w_{t+1})$, which means that i′+1<j′. Hence, vertices x and y are not adjacent, since otherwise G _k [{x,w _i′,w _i′+1,…,w _j′,y}] would be a C ₅ or a C ₆. But then we obtain a contradiction, since G _k [{u,x,w _i′+1,y}] is a claw. □

Before presenting the main result of this section, we prove one additional lemma that describes two useful properties of the neighborhood of v in G _k .

Lemma 4

The graph $G_{k}[N_{G_{k}}(v)]$ is connected, and the union of the intervals representing the vertices in $N_{G_{k}}(v)$ does not cover the circle of model ${\mathcal{I}}_{k-1}$.

Proof

By Lemma 3, there exist two consecutive vertices $w_{t},w_{t+1} \in N_{G_{k}}(v)$ on cycle C such that $N_{G_{k}}(v)$ is contained in $N_{G_{k}}(w_{t}) \cup N_{G_{k}}(w_{t+1})$. Since the vertices w _t and w _t+1 are adjacent and $N_{G_{k}}(v) \subseteq N_{G_{k}}(w_{t}) \cup N_{G_{k}}(w_{t+1})$, the graph $G_{k}[N_{G_{k}}(v)]$ is connected.

Consider now the model ${\mathcal{I}}_{k-1}$ of the graph G _k−1. Let z ₁ be the vertex in $N_{G_{k}}(v)$ whose interval ends in the union of $I_{w_{t}}$ and $I_{w_{t+1}}$ and starts furthest to the left, and let z ₂ be the vertex in $N_{G_{k}}(v)$ whose interval starts in the union of $I_{w_{t}}$ and $I_{w_{t+1}}$ and ends furthest to the right; note that it is possible that z ₁=w _t or z ₂=w _t+1, which implies that such vertices z ₁ and z ₂ exist. Since ${\mathcal{I}}_{k-1}$ is a proper circular arc model, we have $w_{t-2}^{s} < z_{1}^{s} \leq w_{t}^{s} < z_{1}^{e}$ and $z_{2}^{s} < w_{t+1}^{e} \leq z_{2}^{e} < w_{t+3}^{e}$ (see Fig. 5 for an illustration).

Fig. 5

Illustration for the proof of Lemma 4

Let I ^∗ be the union of the intervals $I_{z_{1}},I_{w_{t}}, I_{w_{t+1}},I_{z_{2}}$, i.e., I ^∗ is the interval with start point $z_{1}^{s}$ and end point $z_{2}^{e}$. Since I ^∗ is the union of four intervals, we know that I ^∗ does not cover the circle of model ${\mathcal{I}}_{k-1}$ due to Lemma 2. Moreover, by the definition of z ₁ and z ₂ and the fact that every neighbor of v in G _k is adjacent to w _t or w _t+1, we know that I ^∗ contains I _x as a subinterval for each neighbor $x\in N_{G_{k}}(v)$; in fact, I ^∗ is precisely the union of the intervals representing the vertices in $N_{G_{k}}(v)$. This completes the proof of Lemma 4. □

We are now ready to prove the main result of this section.

Theorem 1

Every connected almost proper interval graph is a proper circular arc graph.

Proof

Let G=(V,E) be a connected almost proper interval graph. If G does not contain an induced cycle of length at least 7, i.e., if G is hole-free, then G is a proper interval graph due to the aforementioned result by Wegner [25]. Since every proper interval graph is a proper circular arc graph, we are done in this case.

Suppose G contains an induced cycle C of length r≥7. Let v ₁,v ₂,…,v _r be an ordering of the vertices of C and let v _r+1,v _r+2,…,v _n be an ordering of the vertices in V∖V(C) such that the graph G _k :=G[{v ₁,v ₂,…,v _k }] is connected for 1≤k≤n. We prove, by induction on k, that G _k is a proper circular arc graph for 1≤k≤n.

For the base case, let us observe that the cycle C is a proper circular arc graph. In fact, due to the choice of the ordering v ₁,…,v _r , it is easy to see that the graph G _k is a proper circular arc graph for 1≤k≤r. Moreover, we can easily construct a proper circular arc model ${\mathcal{I}}_{r}$ for the graph G _r . For the induction hypothesis, assume that G _k−1 is a proper circular arc graph for some k≥r+1, and let ${\mathcal{I}}_{k-1}$ be a proper circular arc model of G _k−1. Recall that v _k is the vertex that is added to G _k−1 in order to obtain G _k . We will show that G _k is a proper circular arc graph as follows. We first add an interval $I_{v_{k}}$ to the model ${\mathcal{I}}_{k-1}$ (in the way described below) to obtain a new model ${\mathcal{I}}^{*}$. We then modify ${\mathcal{I}}^{*}$, if necessary, such that it becomes a proper circular arc model of the graph G _k .

Let us first explain how the interval $I_{v_{k}}$ is added to the proper circular arc model ${\mathcal{I}}_{k-1}$ in order to obtain the (not necessarily proper) circular arc model ${\mathcal{I}}^{*}$. By Lemma 3, $N_{G_{k}}(v_{k})$ contains two consecutive vertices w _t ,w _t+1 of cycle C, such that all vertices of $N_{G_{k}}(v_{k})$ are contained in $N_{G_{k}}(w_{t}) \cup N_{G_{k}}(w_{t+1})$. Let z ₁ be the vertex in $N_{G_{k}}(v_{k})$ with the leftmost end point $z_{1}^{e}$ ($z_{1} \in N_{G_{k}}[w_{t}]$), and let z ₂ be the vertex in $N_{G_{k}}(v_{k})$ with the rightmost start point $z_{2}^{s}$ ($z_{2} \in N_{G_{k}}[w_{t+1}]$). Vertices z ₁ and z ₂ are well-defined as a result of Lemma 4. Notice that z ₁≠z ₂, as both w _t and w _t+1 are contained in $N_{G_{k}}(v_{k})$ by definition. The interval $I_{v_{k}}$ is now added to the model ${\mathcal{I}}_{k-1}$, where the positions of the start point $v_{k}^{s}$ and the end point $v_{k}^{e}$ of $I_{v_{k}}$ depend on whether or not z ₁ and z ₂ are adjacent in the following way (see Fig. 6 for an illustration):

• If $\{z_{1},z_{2}\} \not\in E$, then $v_{k}^{s}$ is placed immediately to the left of $z_{1}^{e}$ and $v_{k}^{e}$ is placed immediately to the right of $z_{2}^{s}$, such that there exists no start or end point p ₁ in model ${\mathcal{I}}_{k-1}$ where $v_{k}^{s} < p_{1} < z_{1}^{e}$ and there exists no start or end point p ₂ where $z_{2}^{s} < p_{2} < v_{k}^{e}$.

• If {z ₁,z ₂}∈E, then $v_{k}^{s}$ is placed immediately to the left of $z_{2}^{s}$ and $v_{k}^{e}$ is placed immediately to the right of $z_{1}^{e}$, such that there exists no start or end point p ₁ in model ${\mathcal{I}}_{k-1}$ where $v_{k}^{s} < p_{1} < z_{2}^{s}$ and there exists no start or end point p ₂ where $z_{1}^{e} < p_{2} < v_{k}^{e}$.

Fig. 6

Illustration of the way interval $I_{v_{k}}$ is added to proper circular arc model ${\mathcal{I}}_{k-1}$ in order to obtain model ${\mathcal{I}}^{*}$, in case $\{z_{1},z_{2}\} \not\in E$ (left figure) or {z ₁,z ₂}∈E (right figure)

Let ${\mathcal{I}}^{*}$ be the model we obtain by adding interval $I_{v_{k}}$ to ${\mathcal{I}}_{k-1}$ in the way described above. It is clear that ${\mathcal{I}}^{*}$ is a circular arc model. However, ${\mathcal{I}}^{*}$ is not necessarily a proper circular arc model, as there might be an interval I _x in ${\mathcal{I}}^{*}$ such that I _x is a subinterval of $I_{v_{k}}$, or vice versa. If such a vertex x exists, we call it an obstruction vertex of type 1. Moreover, it is not guaranteed that ${\mathcal{I}}$ is a circular arc model of the graph G _k , as there might be a vertex x such that {x,v _k }∉E(G _k ) and I _x intersects $I_{v_{k}}$. Such a vertex x is called an obstruction vertex of type 2. Note that a vertex x can be both an obstruction vertex of type 1 and an obstruction vertex of type 2 at the same time.

If no obstruction vertex of type 1 or 2 exists, then ${\mathcal{I}}^{*}$ is a proper circular arc model for G _k , and thus G _k is a proper circular arc graph. In that case, we set ${\mathcal{I}}_{k}:={\mathcal{I}}^{*}$, and we proceed to the next subgraph G _k+1 (unless k=n, in which case we are done). If there exists an obstruction vertex of type 1 or 2, then we will show below how the model ${\mathcal{I}}^{*}$ can be modified in such a way that the number of obstruction vertices strictly decreases, eventually leading to a proper circular arc model ${\mathcal{I}}_{k}$ of G _k . It is clear that this suffices to prove Theorem 1.

Suppose there exists an obstruction vertex x of type 1 or 2. As usual, we write I _x to denote the interval in ${\mathcal{I}}^{*}$ that corresponds to x, and x ^s and x ^e to denote the start and end points of I _x , respectively. Let us consider all possible positions of the points x ^s and x ^e in the model ${\mathcal{I}}^{*}$ with respect to the positions of the points $z_{1}^{e}$ and $z_{2}^{s}$. There are 24 permutations of the four points $x^{s},x^{e},z_{1}^{e},z_{2}^{s}$. Since I _x is an interval in the model ${\mathcal{I}}_{k-1}$, we know that x ^s<x ^e. Hence 12 permutations of the four points $x^{s},x^{e},z_{1}^{e},z_{2}^{s}$ remain, each satisfying x ^s<x ^e. Consider the cases where x ^s and x ^e are both to the left of $z_{1}^{s}$ or both to the right of $z_{2}^{e}$. Since in those cases I _x and $I_{v_{k}}$ do not intersect, x is not an obstruction vertex of type 1. Moreover, since we also know that $x \not\in N_{G_{k}}(v_{k})$ by the definition of z ₁ and z ₂, x is not an obstruction vertex of type 2 either. Since we assumed x to be an obstruction vertex, we can therefore safely ignore the permutations where $x^{s} < x^{e} < z_{1}^{e} < z_{2}^{s}$, $x^{s} < x^{e} < z_{2}^{s} < z_{1}^{e}$, $z_{1}^{e} < z_{2}^{s} < x^{s} < x^{e}$, or $z_{2}^{s} < z_{1}^{e} < x^{s} < x^{e}$. The eight remaining permutations are listed and illustrated in Fig. 7.

Fig. 7

Eight possible ways in which the points x ^s and x ^e of an obstruction vertex x can appear in model ${\mathcal{I}}^{*}$ with respect to the points $z_{1}^{e}$ and $z_{2}^{s}$. (In fact, we prove that Cases 4, 6, 7, and 8 do not occur in ${\mathcal{I}}^{*}$)

In the remainder of this proof, we will consider each of these eight cases separately. In fact, for each of the cases, we will consider two subcases, indicated with “a” and “b”, depending on the existence of the edge {x,v _k } in G _k . For example, Case 1a is the case where $x^{s} < z_{1}^{e} < z_{2}^{s} < x^{e}$ and $x \not\in N_{G_{k}}(v_{k})$, whereas Case 1b is the case where $x^{s} < z_{1}^{e} < z_{2}^{s} < x^{e}$ and $x \in N_{G_{k}}(v_{k})$. Note that Case 2 is symmetric to Case 5, and Case 4 is symmetric to Case 7.

We will use two different proof strategies in the case analysis below. For each of the Cases 4, 6, 7, and 8 (and therefore for both of their subcases), as well as for the Cases 1a, 2b, 3a, and 5b, we prove that they cannot occur in ${\mathcal{I}}^{*}$, as this would contradict the assumption that G _k is {claw,net,tent,C ₄,C ₅,C ₆}-free. For the Cases 1b and 3b, we show how we can manipulate model ${\mathcal{I}}^{*}$ in such a way that the number of obstruction vertices strictly decreases. In Case 2a (and by symmetry also in Case 5a), we can either manipulate the model and strictly reduce the number of obstruction vertices, or obtain a contradiction, depending on whether or not x and z ₁ (respectively z ₂) are twins in G _k−1. Note that once we have successfully decreased the number of obstruction vertices to 0, we have obtained a proper circular arc model ${\mathcal{I}}_{k}$ of G _k .

Before we start with the case analysis, let us make some observations. First, due to Lemma 4, the intervals $I_{z_{1}}$ and $I_{z_{2}}$ can only intersect if $z_{2}^{s} < z_{1}^{e}$. Furthermore, due to Lemma 2, we need the union of at least 7 intervals in order to cover the circle of model ${\mathcal{I}}^{*}$. This means that we can interpret a section of a proper circular arc model as a proper interval model if the section contains a subset of at most six intervals that cover the entire section. Since this is the case for each of the cases we discuss below (as is apparent from the corresponding figures), this observation justifies the horizontal drawing of the section of model ${\mathcal{I}}^{*}$ that we consider in each case. Finally, in the analysis below, one should keep in mind that the graph G _k is {claw,net,tent,C ₄,C ₅,C ₆}-free, as it is an induced subgraph of the {claw,net,tent,C ₄,C ₅,C ₆}-free graph G.

Case 1a: $x^{s} < z_{1}^{e} < z_{2}^{s} < x^{e}$, $x \not\in N_{G_{k}}(v_{k})$

Vertices z ₁ and z ₂ are not adjacent, but both of them are adjacent to x and to v _k . Hence G _k [{z ₁,x,z ₂,v _k }] is a C ₄. This contradiction implies that Case 1a cannot occur in ${\mathcal{I}}^{*}$.

Case 1b: $x^{s} < z_{1}^{e} < z_{2}^{s} < x^{e}$, $x \in N_{G_{k}}(v_{k})$

Suppose x has neighbors x ₁ and x ₂ such that $x_{1}^{s} < x^{s} < x_{1}^{e} < z_{1}^{e} < z_{2}^{s} < x_{2}^{s} <x^{e} < x_{2}^{e}$ (see Fig. 8). Then $x_{1},x_{2} \not\in N_{G_{k}}(v_{k})$ by the definition of z ₁ and z ₂. Moreover, the vertices x ₁ and x ₂ are not adjacent, since $x_{1}^{e} < x_{2}^{s}$. But then G[{x ₁,x,x ₂,v _k }] is a claw, yielding a contradiction.

Fig. 8

Illustration for Case 1b

Now suppose that x does not have such neighbors x ₁ and x ₂, which implies that z ₁ is the leftmost neighbor of x or z ₂ is the rightmost. Assume that z ₁ is the leftmost neighbor of x (see Fig. 8); the case where z ₂ is the rightmost neighbor of x can be dealt with analogously. The assumption that z ₁ is the leftmost neighbor of x implies that, for every point p that is a start or end point of an interval in model ${\mathcal{I}}^{*}$ such that $x^{s} < p < v_{k}^{s}$, p is a start point.

Let $Y:=\{y\in V(G_{k}) \mid x^{s}\leq y^{s}<v_{k}^{s}\}$. Note that Y is non-empty, since x∈Y. Since we are considering the case where $x^{s} < z_{1}^{e} < z_{2}^{s} < x^{e}$, x is an obstruction vertex of type 1. We claim that the same holds for every y∈Y∖{x}. Let y∈Y∖{x}. Since y is to the right of x in the proper circular arc model ${\mathcal{I}}_{k-1}$, we must have x ^e<y ^e, and hence $v_{k}^{e}<y^{e}$. This implies that $I_{v_{k}}$ is a subinterval of I _y , so y is an obstruction vertex of type 1 by definition. We also claim that none of the vertices in Y is an obstruction vertex of type 2. For x, this follows from the fact that I _x and $I_{v_{k}}$ intersect in model ${\mathcal{I}}^{*}$, together with the assumption that $x \in N_{G_{k}}(v_{k})$. Let y∈Y∖{x}. Notice that $y \in N_{G_{k}}(v_{k})$, since otherwise G _k [{x,y,z ₁,z ₂}] would be a C ₄ (see also Case 1a). Since I _y and I _x intersect, y is not an obstruction vertex of type 2.

We will now explain how we can modify model ${\mathcal{I}}^{*}$ in such a way that the number of obstruction vertices strictly decreases. We extend interval $I_{v_{k}}$ by moving the point $v_{k}^{s}$ to the immediate left of x ^s, making sure that there is no start or end point p of any interval in ${\mathcal{I}}^{*}$ with $v_{k}^{s}<p<x^{s}$. Note that after extending $I_{v_{k}}$ this way, none of the vertices in Y is an obstruction vertex of type 1 anymore, since we already saw that x ^e<y ^e for every y∈Y, implying that I _y did not become a subinterval of the extended interval $I_{v_{k}}$. Also note that no new obstruction vertices of type 1 or type 2 are created, due to the assumption that no interval in ${\mathcal{I}}^{*}$ has an end point p with $x^{s} < p < v_{k}^{s}$. Since Y is non-empty, the number of obstruction vertices strictly decreased.

Case 2a: $x^{s} < z_{1}^{e} < x^{e} < z_{2}^{s}$, $x \not\in N_{G_{k}}(v_{k})$

Let us first argue why x is not an obstruction vertex of type 1. Recall that the points $v_{k}^{s}$ and $v_{k}^{e}$ were placed in model ${\mathcal{I}}_{k-1}$ immediately to the left of $z_{1}^{e}$ and immediately to the right of $z_{2}^{s}$, respectively. This, together with the assumption $x^{s} < z_{1}^{e} < x^{e} < z_{2}^{s}$, implies that $x^{s}<v_{k}^{s}<z_{1}^{e}<x^{e}<z_{2}^{s}<v_{k}^{e}$ in this case. Hence I _x is not a subinterval of $I_{v_{k}}$ or vice versa, which means that x is not an obstruction vertex of type 1.

On the other hand, x is an obstruction vertex of type 2, as $x \not\in N_{G_{k}}(v_{k})$ and the intervals I _x and $I_{v_{k}}$ intersect in model ${\mathcal{I}}_{k-1}$. We distinguish between two cases, depending on whether or not x is a twin of z ₁ in the graph G _k−1.

First suppose that x and z ₁ are twins in G _k−1, i.e., $N_{G_{k-1}}[x]=N_{G_{k-1}}[z_{1}]$. We swap the intervals assigned to x and z ₁, i.e., we relabel interval I _x as $I_{z_{1}}$ and relabel interval $I_{z_{1}}$ as I _x . Let ${\mathcal{I}}'$ denote the model obtained after the swap. Note that the swap did not change any of the adjacencies in the graph G _k−1, as x and z ₁ are twins. However, it is possible that z ₁ is no longer the leftmost neighbor of v _k in model ${\mathcal{I}}'$, as there might exist a neighbor z′ of v _k that was to the left of x and to the right of z ₁ in model ${\mathcal{I}}_{k-1}$, which means that z′ is to the left of z ₁ in model ${\mathcal{I}}'$. Hence, we redefine z ₁ to be the leftmost neighbor of v _k in model ${\mathcal{I}}'$. Note that the interval representing the new vertex z ₁ is to the right of the interval that was labeled $I_{z_{1}}$ in model ${\mathcal{I}}_{k-1}$, since that interval corresponds to vertex x in model ${\mathcal{I}}'$, and x is not adjacent to v _k by assumption. Recall that, when interval $I_{v_{k}}$ was added to model ${\mathcal{I}}_{k-1}$, the positions of $v_{k}^{s}$ and $v_{k}^{e}$ were chosen with respect to the positions of $z_{1}^{e}$ and $z_{2}^{s}$ in ${\mathcal{I}}_{k-1}$. Hence, as z ₁ was redefined in model ${\mathcal{I}}'$, we also need to redefine the start point of interval $I_{v_{k}}$ accordingly, i.e., we must place the point $v_{k}^{s}$ immediately to the left of the new point $z_{1}^{e}$. For convenience, we again use ${\mathcal{I}}'$ to denote the obtained model.

We claim that the number of obstruction vertices in model ${\mathcal{I}}'$ is strictly smaller than in model ${\mathcal{I}}_{k-1}$. First, we observe that x is no longer an obstruction vertex, as $x^{s} < z_{1}^{s} < x^{e} < v_{k}^{s}< z_{1}^{e}$ implies that I _x does not intersect $I_{v_{k}}$ in model ${\mathcal{I}}'$. It remains to show that the swap did not create any new obstruction vertices. Let us first observe that since x and z ₁ are twins in G _k−1, every vertex y that is to the right of z ₁ and to the left of x in model ${\mathcal{I}}_{k-1}$ is a twin of x and z ₁. This, together with the definition of the new vertex z ₁ as the leftmost neighbor of v _k in model ${\mathcal{I}}'$, implies that the swap did not change any of the adjacencies in G _k , and consequently no new obstruction vertices of type 2 were created. Suppose, for contradiction, that there is a vertex y that was not an obstruction vertex of type 1 in model ${\mathcal{I}}_{k-1}$, but is an obstruction vertex of type 1 in model ${\mathcal{I}}'$. Note that the length of the interval $I_{v_{k}}$ strictly decreased, as the point $v_{k}^{s}$ was moved to the right. Hence, $I_{v_{k}}$ is a subinterval of I _y in model ${\mathcal{I}}'$ (and not the other way around). Since y was not an obstruction vertex of type 1 in model ${\mathcal{I}}_{k-1}$, but is an obstruction vertex in model ${\mathcal{I}}'$, we must have $z_{1}^{s}<y^{s}<x^{s}$ in the proper circular arc model ${\mathcal{I}}_{k-1}$. This contradicts the assumption that x and z ₁ are twins in G _k−1.

Now consider the case where x and z ₁ are not twins in G _k−1. Then there exists a vertex $z_{1}' \in N_{G_{k-1}}[z_{1}] \setminus N_{G_{k-1}}[x]$ or a vertex $x' \in N_{G_{k-1}}[x] \setminus N_{G_{k-1}}[z_{1}]$ (see Fig. 9). Suppose there exists a vertex $z_{1}' \in N_{G_{k-1}}[z_{1}] \setminus N_{G_{k-1}}[x]$. Interval $I_{z_{1}'}$ is to the left of interval $I_{z_{1}}$ in model ${\mathcal{I}}_{k-1}$. Hence, by the definition of z ₁, we have $z_{1}' \not\in N_{G_{k-1}}(v_{k})$. This yields a contradiction, since $G_{k}[\{z_{1}',z_{1},x,v_{k}\}]$ is a claw.

Fig. 9

Illustration for Case 2a

Now suppose that x has a neighbor x′ not adjacent to z ₁, which means that x′ is to the right of x (see Fig. 9). Vertex x′ is not adjacent to v _k , since otherwise G _k [{v _k ,z ₁,x,x′}] would be a C ₄. Recall that G, and by construction also G _k−1, contains the induced cycle C of length at least 7. Since ${\mathcal{I}}_{k-1}$ is a proper circular arc model, the intervals representing the vertices of C cover the circle. Let w ₁ be the leftmost neighbor of z ₁ contained in C, and let w ₂ be the left neighbor of w ₁ on C. As there is no vertex in $N_{G_{k-1}}[z_{1}] \setminus N_{G_{k-1}}[x]$, we get $w_{1} \in N_{G_{k-1}}(x)$. Vertex w ₁ is not adjacent to v _k , as it is to the left of z ₁ and z ₁ is the leftmost neighbor of v _k . Moreover, since $w_{1}^{e}$ is to the left of $v_{k}^{s}$ and the start point of interval I _x′ is to the right of $v_{k}^{s}$, w ₁ is not adjacent to x′. Finally, as w ₂ is to the left of w ₁, vertex w ₂ is not adjacent to any vertex in {z ₁,x,v _k ,x′,z ₂}. Then G _k [{w ₂,w ₁,z ₁,x,x′,v _k }] is a net, yielding a contradiction.

Case 2b: $x^{s} < z_{1}^{e} < x^{e} < z_{2}^{s}$, $x \in N_{G_{k}}(v_{k})$

In this case, since $x \in N_{G_{k}}(v_{k})$ and the intervals I _x and $I_{v_{k}}$ intersect in model ${\mathcal{I}}_{k-1}$, x is not an obstruction vertex of type 2. As we explained at the start of Case 2a, x is also not an obstruction vertex of type 1. We conclude that Case 2b cannot occur in model ${\mathcal{I}}^{*}$.

Case 3a: $x^{s} < z_{2}^{s} < z_{1}^{e} < x^{e}$, $x \not\in N_{G_{k}}(v_{k})$

As the intervals in ${\mathcal{I}}_{k-1}$ representing the vertices of cycle C cover the circle, there exist two vertices w ₁ and w ₂ on C such that w ₁ the leftmost neighbor of z ₁ contained in C and w ₂ is the rightmost neighbor of z ₂ contained in C (see Fig. 10). Vertices w ₁ and w ₂ are not adjacent to v _k , as z ₁ and z ₂ are defined as the leftmost and rightmost neighbors of v _k , respectively. If w ₁ (respectively w ₂) is not adjacent to x, then G _k [{w ₁,z ₁,v _k ,x}] (respectively G _k [{w ₂,z ₂,v _k ,x}]) is a claw. Hence, both w ₁ an w ₂ must be adjacent to x.

Fig. 10

Illustration for Case 3a. Vertices w ₁ and w ₁ are either not adjacent (left figure) or adjacent (right figure) in G _k

Suppose w ₁ and w ₂ are not adjacent (see the left side of Fig. 10). If w ₁ is adjacent to z ₂ or if w ₂ is adjacent to z ₁, then G _k [{w ₁,z ₂,v _k ,w ₂}] or G _k [{w ₁,z ₁,w ₂,v _k }]) is a claw, respectively. This means that w ₁ is not adjacent to z ₂ and w ₂ is not adjacent to z ₁. But then G _k [{w ₁,w ₂,z ₁,z ₂,v _k ,x}] is a tent, yielding a contradiction.

Now suppose w ₁ and w ₂ are adjacent (see the right side of Fig. 10). Let w ₃ be the left neighbor of w ₁ on cycle C, and let w ₄ be the right neighbor of w ₂ on C. Since C is an induced cycle, the vertices w ₃,w ₁,w ₂,w ₄ form an induced path. Both w ₁ and w ₂ are adjacent to z ₁, and neither w ₃ nor w ₄ is adjacent to z ₁ by the definition of w ₁ and w ₂. Since v _k is not adjacent to any of the vertices w ₁,w ₂,w ₃,w ₄, graph G _k [{z ₁,w ₁,w ₂,w ₃,w ₄,v _k }] is a net. This contradiction shows that Case 3a cannot occur in model ${\mathcal{I}}^{*}$.

Case 3b: $x^{s} < z_{2}^{s} < z_{1}^{e} < x^{e}$, $x \in N_{G_{k}}(v_{k})$

Since $x \in N_{G_{k}}(v_{k})$ and intervals I _x and $I_{v_{k}}$ intersect, x is not an obstruction vertex of type 1. However, since $I_{v_{k}}$ is a subinterval of I _x , x is an obstruction vertex of type 2. As we showed in Case 1b, x cannot have two neighbors x ₁ and x ₂ such that $x_{1}^{s} < x^{s} < x_{1}^{e} < v_{k}^{s}$ and $v_{k}^{e} < x_{2}^{s} < x^{e} < x_{2}^{e}$, since then G _k [{x ₁,x,x ₂,v _k }] would be a claw. As a consequence, either no end point of any interval in model ${\mathcal{I}}^{*}$ can be to the right of x ^s and to the left of $v_{k}^{s}$, or no start point of any interval in ${\mathcal{I}}^{*}$ can be to the right of $v_{k}^{e}$ and to the left of x ^e.

Let us assume that no end point appears to the right of x ^s and to the left of $v_{k}^{s}$; the other case can be dealt with analogously. Just like in Case 1b, we define a set $Y:=\{y\in V(G_{k}) \mid x^{s} \leq y^{s} < v_{k}^{s}\}$. Note that Y is non-empty, as x∈Y. We can use the exact same arguments as in Case 1b to show that none of the vertices in Y is an obstruction vertex of type 2, and that every vertex in Y is an obstruction vertex of type 1 due to the fact that, for every y∈Y, $I_{v_{k}}$ is a subinterval of I _y in model ${\mathcal{I}}^{*}$.

We modify model ${\mathcal{I}}^{*}$ in the exact same way as in Case 1b: we move the start point $v_{k}^{s}$ of interval $I_{v_{k}}$ to the immediate left of x ^s, making sure that no start or end point of any interval in ${\mathcal{I}}^{*}$ lies to the right of $v_{k}^{s}$ and to the left of x ^s. As we saw in Case 1b, extending $I_{v_{k}}$ this way does not create any new obstruction vertices. Moreover, as the vertices of Y are no longer obstruction vertices in the new model and the set Y is non-empty, the number of obstruction vertices strictly decreased.

Case 4a: $x^{s} < z_{2}^{s} < x^{e} < z_{1}^{e}$, $x \not\in N_{G_{k}}(v_{k})$

Recall that the intervals representing the vertices of C cover the circle of model ${\mathcal{I}}^{*}$. Let w ₁ and w ₂ be vertices of C such that w ₁ is the leftmost neighbor of x contained in C and w ₂ is the rightmost neighbor of z ₂ contained in C. Furthermore, let w ₃ be the left neighbor of w ₁ in C, and let w ₄ be the right neighbor of w ₂ in C (see Fig. 11).

Fig. 11

Illustration for Case 4a

By the definition of z ₁ and z ₂, vertex v _k is not adjacent to any of the vertices w ₁,w ₂,w ₃,w ₄. Vertex w ₂ is adjacent to x, since otherwise G _k [{w ₂,z ₂,v _k ,x}] is a claw. Vertex w ₃ is adjacent to w ₁, but not to any vertex in the set {x,v _k ,z ₁,z ₂,w ₂,w ₄}, as w ₁ the leftmost neighbor of x and w ₃ is to the left of w ₁. By symmetrical arguments, w ₄ is adjacent to w ₂, but not to any vertex in {x,v _k ,z ₁,z ₂,w ₁,w ₄}. Vertices w ₃ and w ₄ are not adjacent, since then the six intervals $I_{w_{3}}$, $I_{w_{1}}$, $I_{z_{1}}$, $I_{z_{2}}$, $I_{w_{2}}$, and $I_{w_{4}}$ would cover the circle of the proper circular arc model ${\mathcal{I}}_{k-1}$, contradicting Lemma 2.

Since the graph G _k [{v _k ,z ₂,x,w ₂,w ₄,w ₁}] is not a net, at least one of the edges {w ₁,w ₂},{w ₁,z ₂} is present in G _k ; all other potential edges have already been excluded. Suppose {w ₁,w ₂}∉E, which means that {w ₁,z ₂}∈E. In this case, G[{w ₁,z ₂,w ₂,v _k }] is a claw, yielding a contradiction. Hence we must have {w ₁,w ₂}∈E. Moreover, we must have {w ₁,z ₂}∈E, since otherwise G _k [{w ₁,w ₂,w ₄,z ₂}] would be a claw. Now we obtain a contradiction, as G[{v _k ,z ₂,w ₃,w ₁,w ₄,w ₂}] is a net. We conclude that Case 4a cannot occur in model ${\mathcal{I}}^{*}$.

Case 4b: $x^{s} < z_{2}^{s} < x^{e} < z_{1}^{e}$, $x \in N_{G_{k}}(v_{k})$

Recall that z ₁ is defined to be the leftmost neighbor of v _k in model ${\mathcal{I}}^{*}$. Since x is adjacent to v _k and x is to the left of z ₁, we immediately obtain a contradiction, implying that Case 4b cannot occur.

Case 5: $z_{1}^{e} < x^{s} < z_{2}^{s} < x^{e}$

This case is symmetric to Case 2.

Case 6a: $z_{1}^{e} < x^{s} < x^{e} < z_{2}^{s}$, $x \not\in N_{G_{k}}(v_{k})$

In this case, the vertices z ₁ and z ₂ are not adjacent to each other, and neither z ₁ nor z ₂ is adjacent to x. By Lemma 3, there exist two consecutive vertices w _t ,w _t+1 on cycle C such that $w_{t},w_{t+1} \in N_{G_{k}}(v_{k})$ and $N_{G_{k}}(v_{k}) \subseteq N_{G_{k}}(w_{t}) \cup N_{G_{k}}(w_{t+1})$. Note that, apart from interval $I_{v_{k}}$, there is no interval in model ${\mathcal{I}}^{*}$ whose start point is to the left of $z_{1}^{e}$ and whose end point is to the right of $z_{2}^{s}$, since otherwise I _x would be a subinterval of such an interval in ${\mathcal{I}}_{k-1}$, contradicting the assumption that ${\mathcal{I}}_{k-1}$ is a proper circular arc model. In particular, this means that there is an induced path z ₁,w _i ,w _i+1,z ₂ in $N_{G_{k}}(v_{k})$ such that w _i ,w _i+1 are vertices of C; it is possible that z ₁=w _t or z ₂=w _t+1. Interval I _x is not a subinterval of $I_{w_{i}}$ or $I_{w_{i+1}}$ in the proper circular arc model ${\mathcal{I}}_{k-1}$, so x is adjacent to both w _i and w _i+1. Now we have a contradiction, since G _k [{z ₁,w _i ,w _i+1,z ₂,x,v _k }] is a tent. Hence Case 6a does not occur in model ${\mathcal{I}}^{*}$.

Case 6b: $z_{1}^{e} < x^{s} < x^{e} < z_{2}^{s}$, $x \in N_{G_{k}}(v_{k})$

Just like in Case 6a, z ₁ and z ₂ are not adjacent to each other or to vertex x. Since we now consider the case where $x \in N_{G_{k}}(v_{k})$, the graph G _k [{z ₁,x,z ₂,v _k }] is a claw. This contradiction implies that Case 6b cannot occur.

Case 7: $z_{2}^{s} < x^{s} < z_{1}^{e} < x^{e}$

This case is symmetric to Case 4.

Case 8: $z_{2}^{s} < x^{s} < x^{e} < z_{1}^{e}$

This case cannot occur, since I _x is a subinterval of both $I_{z_{1}}$ and $I_{z_{2}}$, contradicting the assumption that ${\mathcal{I}}_{k-1}$ is a proper circular arc model of G _k−1.

For each of the eight cases above, we either proved that they cannot occur in model ${\mathcal{I}}^{*}$, or we showed how model ${\mathcal{I}}^{*}$ can be manipulated in such a way that the number of obstruction vertices strictly decreases. Since we obtain a proper circular arc model ${\mathcal{I}}_{k}$ of G _k once we have successfully decreased the number of obstruction vertices to 0, this completes the proof of Theorem 1.  □

4 Algorithmic Implications

In this section, we present an $\mathcal {O}(6^{k} kn^{6})$ time algorithm for Proper Interval Vertex Deletion. Our FPT algorithm is based on the structural characterization of almost proper interval graphs given in Theorem 1, together with a linear-time algorithm for solving Proper Interval Vertex Deletion on almost proper interval graphs. We also present a 6-approximation algorithm for the optimization variant of Proper Interval Vertex Deletion on general graphs.

Recall that Wegner [25] showed that the class of proper interval graphs is exactly the class of {claw,net,tent,hole}-free graphs, and that an almost proper interval graph is defined to be a {claw,net,tent,C ₄,C ₅,C ₆}-free graph. Hence, a graph G is a proper interval graph if and only if G is an almost proper interval graph that is hole-free. Solving the Proper Interval Vertex Deletion problem on almost proper interval graphs therefore boils down to finding a smallest subset of vertices in an almost proper interval graph whose deletion destroys all the holes in the graph. This motivates the following definition.

Let G=(V,E) be a connected almost proper interval graph. A hole cut of G is a vertex set X⊆V such that G−X is a proper interval graph. A hole cut X of G is minimal if X is empty or if, for every proper subset X′⊂X, the graph G−X′ contains a hole. A hole cut of G is minimum if G does not have a hole cut whose size is strictly smaller than the size of X.

Due to Theorem 1, graph G is a proper circular arc graph. Let ${\mathcal{I}}$ be a proper circular arc model of G. For any vertex v∈V, let R _v denote the set of neighbors of v that are to the right of v, i.e., R _v :={w∈V∣w ^s<v ^e<w ^e}. Clearly, for every vertex v∈V, the set R _v is a hole cut; after all, in the proper circular arc model ${\mathcal{I}}'$ of the graph G−R _v , vertex v does not have any neighbor that is to the right of v. This implies that we can “cut” the circle in model ${\mathcal{I}}'$ to the immediate right of point v ^e in order to obtain a proper interval model of G−R _v . The following lemma shows that every minimal hole cut of G is exactly the set R _v for some v∈V.

Lemma 5

Let G be a connected almost proper interval graph, and let ${\mathcal{I}}$ be a proper circular arc model of G. For every minimal hole cut X of G, there exists a vertex v in G such that X=R _v .

Proof

First suppose G is a proper interval graph. Then the unique minimal hole cut of G is the empty set. Moreover, since G is connected, there is a unique vertex v∈V(G) such that R _v is empty. Hence, X=R _v in this case.

Now suppose G is not a proper interval graph. Let X be a minimal hole cut of G. Suppose, for contradiction, that $R_{v} \not\subseteq X$ for each vertex v∈V(G). Then every vertex in V(G)∖X has a neighbor to the right, where “to the right” is defined with respect to the proper circular arc model ${\mathcal{I}}$ of G. As a consequence, there exists a set of intervals in ${\mathcal{I}}$ representing vertices in V(G)∖X such that the union of these covers the circle. Let ${\mathcal{Y}}$ be an inclusion-minimal such set. Since G is a connected almost proper interval graph that is not a proper interval graph, G contains a hole C of length at least 7. Moreover, since G is a proper circular arc graph by Theorem 1, we know by Lemma 1 that for every subset ${\mathcal{X}}\subseteq {\mathcal{I}}$ of intervals that cover the circle of model ${\mathcal{I}}$, we have $|{\mathcal{X}}|\geq 4$. This implies that $|{\mathcal{Y}}|\geq 4$, which means that the set Y of corresponding vertices in G induces a hole in G. Since Y∩X=∅, the vertices in Y also induce a hole in G−X, contradicting the fact that X is a hole cut of G. □

Lemma 5 implies that a connected almost proper interval graph contains at most n minimal hole cuts. The next lemma shows how we can exploit this fact in order to solve Proper Interval Vertex Deletion in linear time on connected almost proper interval graphs.

Lemma 6

The Proper Interval Vertex Deletion problem can be solved in $\mathcal {O}(n+m)$ time on almost proper interval graphs.

Proof

Let (G,k) be an instance of Proper Interval Vertex Deletion, where G is an almost proper interval graph. Let us first assume that G is connected; at the end of this proof, we consider the case where G is not connected. Note that (G,k) is a yes-instance if and only if G has a hole cut of size at most k. Hence, in order to prove Lemma 6 for connected almost proper interval graphs, it suffices to show that we can find a minimum hole cut of G in $\mathcal {O}(n+m)$ time.

We first check if G is a proper interval graph. It is well-known that this can be done in $\mathcal {O}(n+m)$ time, for example using the recognition algorithm for proper interval graphs by Deng et al. [8]. If G is a proper interval graph, then the empty set is the unique minimum hole cut of G.

Suppose G is not a proper interval graph. By Lemma 5, for every minimal hole cut X of G, there exists a vertex v∈V(G) such that X=R _v . Since a minimum hole cut is also minimal, we only need to show how we can find, in linear time, a set R _v in G of smallest size. In order to find such a set, we use a FIFO queue Q, where vertices of G will be added to the back of the queue and removed from the front of the queue. We will make two “round trips” along the circle of model ${\mathcal{I}}$, starting at point x ^e for an arbitrary vertex x of G, and traversing the circle in the clockwise direction, i.e., from left to right.

The first round trip is used to add and remove vertices to and from Q in such a way that at the moment x ^e has been reached for the second time, Q contains exactly the vertices of R _x . This can be done as follows. After adding x to the queue, we start traversing the circle from left to right, starting at point x ^e. As soon as a point y ^s is reached, vertex y is added to the back of the queue, and vertex y is removed from the front of queue as soon as point y ^e is reached. Note that the fact that ${\mathcal{I}}$ is a proper circular arc model guarantees that vertex y is at the front of the queue at the moment y ^e is reached. Let us consider which vertices are in the queue at the moment x ^e has been reached for the second time, i.e., at the moment x has been removed from the queue for the first time. For every vertex z∈V(G)∖R _x , we encountered both z ^s and z ^e, which means that z is not in Q. On the other hand, for every z∈R _x , we only encountered point z ^s, and not z ^e. This means that Q contains exactly the vertices of R _x after x ^e has been reached for the second time.

In the second round trip, we again add a vertex y to the queue when y ^s is reached, and remove y from the queue when as soon as point y ^e is reached. Every time a point y ^e is reached, Q contains exactly those vertices whose intervals contain the point y ^e, i.e., Q contains exactly the vertices of the set R _y . Hence, by keeping track of the size of Q during the second round trip, and returning the elements of Q at the moment it has smallest size, we can find a set R _v such that |R _v |≤|R _w | for every w∈V(G). As we argued before, such a set R _v is a minimum hole cut of G due to Lemma 5.

It remains to argue how to proceed when the input graph G is not connected. Let G ₁,…,G _r be the connected components of G, and let n _i and m _i denote the number of vertices and edges in G _i , respectively, for 1≤i≤r. For each connected component G _i , we can use the above procedure to find, in $\mathcal {O}(n_{i}+m_{i})$ time, a minimum hole cut of G _i . Let x _i be the size of a minimum hole cut in G _i , for 1≤i≤r, and let $x:=\sum_{i=1}^{r} x_{i}$. Since $\sum_{i=1}^{r} n_{i}=n$ and $\sum_{i=1}^{r} m_{i}=m$, the value of x can be computed in $\mathcal {O}(n+m)$ time. It is obvious that G has a hole cut of size at most k if and only if x≤k. □

We are now ready to provide an efficient FPT algorithm for the Proper Interval Vertex Deletion problem on general graphs.

Theorem 2

The Proper Interval Vertex Deletion problem can be solved in $\mathcal {O}(6^{k} kn^{6})$ time.

Proof

Let (G,k) be an instance of Proper Interval Vertex Deletion, and let us refer to the integer k as the budget of the instance. Any set X⊆V(G) with |X|≤k such that G−X is a proper interval graph is called a solution for (G,k). Recall that the forbidden induced subgraphs of proper interval graphs are the claw, the net, the tent, and all the holes [25] (see also Fig. 1). In order to transform G into a proper interval graph, we need to delete vertices from G such that the obtained graph does not contain any of the aforementioned forbidden induced subgraphs.

The first phase of the algorithm is a bounded search tree procedure that transforms the instance (G,k) into $\mathcal {O}(6^{k})$ sub-instances, such that the graph in each sub-instance is an almost proper interval graph, and the budget is at least 0. This is done as follows. Starting with the instance (G,k), the algorithm checks whether G contains a subset of vertices U such that U induces a claw, a net, a tent, a C ₄, a C ₅, or a C ₆ in G. Since each of these graphs has at most six vertices, this check can trivially be performed in $\mathcal {O}(n^{6})$ time. If no such set U is found, then G is an almost proper interval graph, and the algorithm proceeds to the next phase. If such a set U is found, the algorithm branches on the at most six possible ways of deleting a single vertex u from U, creating at most six sub-instances (G′,k′), where G′:=G−u for some vertex u∈U, and k′:=k−1. Since any solution for (G,k) must contain at least one vertex of each forbidden induced subgraph in G, we have that (G,k) is a yes-instance if and only if at least one of the sub-instances (G′,k′) is a yes-instance of Proper Interval Vertex Deletion.

As long as there is a sub-instance in which the graph is not an almost proper interval graph and the budget is at least 1, another round of branching is performed; every sub-instance in which the graph is already an almost proper interval graph is left untouched. Each time the algorithm branches, the budget is decreased by exactly 1. Since the initial budget was k, the first phase is completed after at most k rounds of branching. The above procedure naturally defines a search tree, where each of the leaves corresponds to a sub-instance. At the end of the first phase, the algorithm discards every sub-instance in which the graph is not {claw,net,tent,C ₄,C ₅,C ₆}-free and the budget is 0. If all sub-instances are discarded, then G contains more than k vertex-disjoint forbidden induced subgraphs, which means that (G,k) is a no-instance. Otherwise, the algorithm proceeds to the second phase, which is described below. Since the algorithm branches at most k times, the total number of sub-instances that is created in the first phase of the algorithm is $\mathcal {O}(6^{k})$. The total time used in this phase is $\mathcal {O}(6^{k} kn^{6})$.

In the second phase, the algorithm considers each sub-instance (G″,k″) where G″ is an almost proper interval graph and k″≥0. Since G″ is an almost proper interval graph, we can use the algorithm of Lemma 6 to decide in $\mathcal {O}(n+m)$ time whether (G″,k″) is a yes-instance. As argued before, it is clear that (G,k) is a yes-instance if and only if at least one of the sub-instances (G″,k″) is a yes-instance. This completes the proof of Theorem 2. □

For the remainder of this subsection, we consider Proper Interval Vertex Deletion to be an optimization problem rather than a decision problem. In other words, we define Proper Interval Vertex Deletion to be the problem that takes as input a graph G, and the task is to find a vertex subset X⊆V(G) of minimum size such that G−X is a proper interval graph. We now show how the FPT algorithm of Theorem 2 can be turned into a 6-approximation algorithm for Proper Interval Vertex Deletion.

Theorem 3

There is a 6-approximation algorithm for the Proper Interval Vertex Deletion problem running in time $\mathcal {O}(n^{7})$.

Proof

Let G=(V,E) be a graph. We describe an $\mathcal {O}(n^{7})$ time procedure that finds a set X⊆V such that G−X is a proper interval graph, and such that |X|≤6|Y| for any set Y⊆V such that G−Y is a proper interval graph. Initially, the set X is empty. As long as there exists a vertex set U⊆V such that G[U] is a claw, a net, a tent, a C ₄, a C ₅, or a C ₆, we delete all the vertices of U from G, and add all the vertices of U to X. If no such vertex set U exists, then the remaining graph G′ is an almost proper interval graph by definition. Using the algorithm of Lemma 5, we can find a minimum hole cut X′ of G′ in $\mathcal {O}(n+m)$ time. Finally, we add all the vertices of X′ to X. The approximation factor 6 follows from the observation that each set U≠X′ whose vertices are added to X contains at most 6 vertices, and that any hole cut Y of G must contain at least one vertex from each such set U.

It remains to analyze the running time. Since each of the sets U that is found in the first phase of the algorithm contains at most 6 vertices, each such set U can be found in $\mathcal {O}(n^{6})$ time. As the algorithm finds $\mathcal {O}(n)$ sets U in total, the first phase of the algorithm takes $\mathcal {O}(n^{7})$ time. The second phase of the algorithm, i.e., finding the hole cut X′ of the almost proper interval graph G′, takes $\mathcal {O}(n+m)$ time. This yields an overall running time of $\mathcal {O}(n^{7})$. □

5 Conclusion

We proved that every {claw,net,tent,C ₄,C ₅,C ₆}-free graph is the disjoint union of proper circular arc graphs. Using this structural result, we obtained an $\mathcal {O}(6^{k} kn^{6})$ time algorithm for Proper Interval Vertex Deletion, as well as a polynomial-time 6-approximation algorithm for the optimization variant of the problem.

Van Bevern et al. [23] proved that the Proper Interval Vertex Deletion problem is NP-hard on graphs that are {claw,net,tent}-free. We showed that the problem can be solved in linear time on almost proper interval graphs, i.e., on graphs that are {claw,net,tent,C ₄,C ₅,C ₆}-free. It would be interesting to know if the problem remains NP-hard when restricted to {claw,net,tent,C ₄}-free graphs, or if it becomes polynomial-time solvable on this graph class.

To conclude this paper, we mention two related open problems. Is the problem of deciding whether at most k vertices can be deleted from a given graph in order to get an interval graph or a proper circular arc graph fixed-parameter tractable when parameterized by k? Settling the parameterized complexity of this problem for interval graphs seems to be the more interesting of the two.