Polynomial-time Algorithms for the Subset Feedback Vertex
Set Problem on Interval Graphs and Permutation Graphs
Charis Papadopoulos∗

Spyridon Tzimas†

arXiv:1701.04634v2 [cs.DS] 1 Feb 2017

Abstract
Given a vertex-weighted graph G = (V, E) and a set S ⊆ V , a subset feedback vertex
set X is a set of the vertices of G such that the graph induced by V \ X has no cycle
containing a vertex of S. The Subset Feedback Vertex Set problem takes as input
G and S and asks for the subset feedback vertex set of minimum total weight. In contrast
to the classical Feedback Vertex Set problem which is obtained from the Subset
Feedback Vertex Set problem for S = V , restricted to graph classes the Subset
Feedback Vertex Set problem is known to be NP-complete on split graphs and,
consequently, on chordal graphs. However as Feedback Vertex Set is polynomially
solvable for AT-free graphs, no such result is known for the Subset Feedback Vertex
Set problem on any subclass of AT-free graphs. Here we give the first polynomial-time
algorithms for the problem on two unrelated subclasses of AT-free graphs: interval graphs
and permutation graphs. As a byproduct we show that there exists a polynomial-time
algorithm for circular-arc graphs by suitably applying our algorithm for interval graphs.
Moreover towards the unknown complexity of the problem for AT-free graphs, we give
a polynomial-time algorithm for co-bipartite graphs. Thus we contribute to the first
positive results of the Subset Feedback Vertex Set problem when restricted to
graph classes for which Feedback Vertex Set is solved in polynomial time.

1

Introduction

For a given set S of vertices of a graph G, a subset feedback vertex set X is a set of vertices
such that every cycle of G[V \ X] does not contain a vertex from S. The Subset Feedback
Vertex Set problem takes as input a graph G = (V, E) and a set S ⊆ V and asks for
the subset feedback vertex set of minimum cardinality. In the weighted version every vertex
of G has a weight and the objective is to compute a subset feedback vertex set with the
minimum total weight. The Subset Feedback Vertex Set problem is a generalization
of the classical Feedback Vertex Set problem in which the goal is to remove a set of
vertices X such that G[V \ X] has no cycles. Thus by setting S = V the problem coincides
with the NP-complete Feedback Vertex Set problem [16]. Both problems find important
applications in several aspects that arise in optimization theory, constraint satisfaction, and
bayesian inference [12, 2, 1, 13]. Interestingly the Subset Feedback Vertex Set problem
for |S| = 1 also coincides with the NP-complete Multiway Cut problem [15] in which the
task is to disconnect a predescribed set of vertices [17, 8].
Subset Feedback Vertex Set was first introduced by Even et al. who obtained a constant factor approximation algorithm for its weighted version [12]. The unweighted version
in which all vertex weights are equal has been proved to be fixed parameter tractable [11].
Moreover the fastest algorithm for the weighted version in general graphs runs in O∗ (1.86n )
∗
†

Department of Mathematics, University of Ioannina, Greece. E-mail: charis@cs.uoi.gr
Department of Mathematics, University of Ioannina, Greece. E-mail: roytzimas@hotmail.com

1

AT-free ?

permutation

P
weighted

interval

P
weighted

⊂
P
weighted

chordal

NP-complete
unweighted

⊃

P
weighted

⊃

⊃

co-bipartite

⊃

⊂

circular-arc

split

NP-complete
unweighted

Figure 1: The computational complexity of the Subset Feedback Vertex Set problem
restricted to the considered graph classes. All polynomial-time results (P) are obtained in
this work, whereas the NP-completeness result of split graphs, and, consequently, of chordal
graphs, is due to [15].
time1 by enumerating its minimal solutions [15], whereas for the unweighted version the
fastest algorithm runs in O∗ (1.75n ) time [14]. As the unweighted version of the problem is
shown to be NP-complete even when restricted to split graphs [15], there is a considerable
effort to reduce the running time on chordal graphs, a proper superclass of split graphs, and
more general on other classes of graphs. Golovach et al. considered the weighted version and
gave an algorithm that runs in O∗ (1.67n ) time for chordal graphs [18]. Reducing the existing
running time even on chordal graphs has been proved to be quite challenging and only for
the unweighted version of the problem a faster algorithm was given that runs in O∗ (1.61n )
time [9]. In fact the O∗ (1.61n )-algorithm given in [9] runs for every graph class which is
closed under vertex deletions and edge contractions, and on which the weighted Feedback
Vertex Set problem can be solved in polynomial time. Thus there is an algorithm that
runs in O∗ (1.61n ) time for the unweighted version of the Subset Feedback Vertex Set
problem when restricted to AT-free graphs [9], a graph class that properly contains permutation graphs and interval graphs. Here we show that for the classes of permutation graphs
and interval graphs we design a much faster algorithm even for the weighted version of the
problem.
As a generalization of the classical Feedback Vertex Set problem, let us briefly give
an overview of the complexity of Feedback Vertex Set on graph classes related to permutation graphs and interval graphs. Concerning the complexity of Feedback Vertex
Set on restricted graphs classes it is known to be NP-complete on bipartite graphs [28] and
planar graphs [16], whereas it becomes polynomial-time solvable on the classes of chordal
graphs [10, 27], circular-arc graphs [27], interval graphs [24], permutation graphs [4, 5, 3, 22],
cocomparability graphs [23], and, more generally, AT-free graphs [21]. Despite the positive
and negative results of the Feedback Vertex Set problem, very few similar results are
known concerning the complexity of the Subset Feedback Vertex Set problem. Clearly
for graph classes for which the Feedback Vertex Set problem is NP-complete, so does
the Subset Feedback Vertex Set problem. However as the Subset Feedback Vertex
Set problem is more general that Feedback Vertex Set problem, it is natural to study its
complexity for graph classes for which Feedback Vertex Set is polynomial-time solvable.
In fact restricted to graph classes there is only a negative result for the Subset Feedback
Vertex Set problem regarding the NP-completeness of split graphs [15]. Such a result,
however, implies that there is an interesting algorithmic difference between the two problems, as the Feedback Vertex Set problem is known to be polynomial-time computable
for chordal graphs [10, 27], and, thus, also for split graphs.
Here we initiate the study of Subset Feedback Vertex Set restricted on graph classes
from the positive perspective. We consider its weighted version and give the first positive
1

The O∗ notation is used to suppress polynomial factors.

2

results on permutation graphs and interval graphs, both being proper subclasses of AT-free
graphs. As already explained, we are interested towards subclasses of AT-free graphs since
for chordal graphs the problem is already NP-complete [15]. Permutation graphs and interval
graphs are unrelated to split graphs and are both characterized by a linear structure with
respect to a given vertex ordering [6, 19, 27]. For both classes of graphs we design polynomialtime algorithms based on dynamic programming of subproblems defined by passing the
vertices of the graph according to their natural linear ordering. One of our key ingredients is
that during the pass of the dynamic programming we augment the considered vertex set and
we allow the solutions to be chosen only from a specific subset of the vertices rather than the
whole vertex set. Although for interval graphs such a strategy leads to a simple algorithm,
the case of permutation graphs requires further descriptions of the considered subsolutions
by augmenting the considered part of the graph with a small number of additional vertices.
As a side result we show that the problem has a polynomial time solution on a larger class of
interval graphs, namely to that of circular-arc graphs, by suitably applying our algorithm for
interval graphs. Moreover towards the unknown complexity of the problem for the class of
AT-free graphs, we consider the class of co-bipartite graphs (complements of bipartite graphs)
and settle the corresponding complexity status. More precisely we show that the number
of minimal solutions of a co-bipartite graph is polynomial which implies a polynomial-time
algorithm of the Subset Feedback Vertex Set problem for the class of co-bipartite
graphs. Our overall results are summarized in Figure 1. Therefore, we contribute to provide
the first positive results of the Subset Feedback Vertex Set problem on subclasses of
AT-free graphs.

2

Preliminaries

All graphs in this text are undirected and simple. A graph is denoted by G = (V, E) with
vertex set V and edge set E. We use the convention that n = |V | and m = |E|. For a vertex
subset S ⊆ V , the subgraph of G induced by S is G[S] = (S, {{u, v} ∈ E | u, v ∈ S}). The
neighborhood of a vertex
S x of G is N (x) = {v | xv ∈ E} and the degree of x is |N (x)|. If
S ⊆ V , then N (S) = x∈S N (x) \ S. A clique is a set of pairwise adjacent vertices, while an
independent set is a set of pairwise non-adjacent vertices.
A path is a sequence of distinct vertices P = hv1 v2 · · · vk i where each pair of consecutive
vertices vi vi+1 forms an edge of G. If additional v1 vk is an edge then we obtain a cycle. In
this paper, we distinguish between paths (or cycles) and induced paths (or induced cycles).
By an induced path (or cycle) of G we mean a chordless path (or cycle). A graph is connected
if there is a path between any pair of vertices. A connected component of G is a maximal
connected subgraph of G. A forest is a graph that contains no cycles and a tree is a forest
that is connected.
A weighted graph G = (V, E) is a graph, where each vertex v ∈ V is assigned a weight
that is a real number. We denote by w(v) the weight of each vertex v ∈ V . For a vertex set
A ⊂ V the weight of A is the sum of the weights of all vertices in A.
The Subset Feedback Vertex Set (SFVS) problem is defined as follows: given a weighted
graph G and a vertex set S ⊆ V , find a vertexPset X ⊂ V , such that all cycles containing
vertices of S, also contains a vertex of X and v∈X w(v) is minimized. In the unweighted
version of the problem all weights are equal. A vertex set X is defined as minimal subset
feedback vertex set if no proper subset of X is a subset feedback vertex set for G and S. The
classical Feedback Vertex Set (FVS) problem is a special case of the subset feedback
vertex set problem with S = V . Note that a minimum weight subset feedback vertex set is
dependent on the weights of the vertices, whereas a minimal subset feedback vertex set is

3

only dependent on the vertices and not their weights. Clearly, both in the weighted and the
unweighted versions, a minimum subset feedback vertex set must be minimal.
An induced cycle of G is called S-cycle if a vertex of S is contained in the cycle. We
define an S-forest of G to be a vertex set Y ⊆ V such that no cycle in G[Y ] is an S-cycle.
An S-forest Y is maximal if no proper superset of Y is an S-forest. Observe that X is a
minimal subset feedback vertex set if and only if Y = V \ X is a maximal S-forest. Thus,
the problem of computing a minimum weighted subset feedback vertex set is equivalent to
the problem of computing a maximum weighted S-forest. Let us denote by FS the class of
S-forests. In such terms, given the graph G and the subset S of V , we are interested in
finding a maxw {Y ⊆ V | G[Y ] ∈ FS }, where maxw selects a vertex set having the maximum
sum of its weights.

3

Computing SFVS on interval graphs and circular-arc graphs

Here we present a polynomial-time algorithm for the SFVS problem on interval graphs.
A graph is an interval graph if there is a bijection between its vertices and a family of
closed intervals of the real line such that two vertices are adjacent if and only if the two
corresponding intervals overlap. Such a bijection is called an interval representation of the
graph, denoted by I. Notice that every induced subgraph of an interval graph is an interval
graph. Hereafter we assume that the input graph is connected; otherwise, we apply the
described algorithm in each connected component and take the overall solution as the union
of the sub-solutions.
As already mentioned, instead of finding a subset feedback vertex set X of minimum
weight of (G, S) we concentrate on the equivalent problem of finding a maximum weighted
S-forest Y of (G, S). We first define the necessary vertex sets. Let G be a weighted interval
graph and let I be its interval representation. The left and right endpoints of an interval i,
1 ≤ i ≤ n, are denoted by `(i) and r(i), respectively. Each interval i is labeled from 1 to n
according to their ascending r(i). For technical reasons of our algorithm, we add an interval
with label 0 that does not belong to S, has negative weight, and augment I to I + by setting
`(0) = −1 and r(0) = 0. Notice that interval 0 is non-adjacent to any vertex of G. Clearly if
Y is a maximum weighted S-forest for G[I + ] then Y \ {0} is a maximum weighted S-forest
for G[I]. Moreover it is known that any induced cycle of an interval graph is an induced
triangle [24, 27].
We consider the two relations on V that are defined by the endpoints of the intervals as
follows:
i ≤` j ⇐⇒ `(i) ≤ `(j)
i ≤r j ⇐⇒ r(i) ≤ r(j)
Since all endpoints of the collection’s intervals are distinct, it is not difficult to show that ≤`
and ≤r are total orders on V . We write `- min to denote the interval having the minimum
left-endpoint among its operands with respect to ≤` ; and we write r- max to denote the
interval having the maximum right-endpoint among its operands with respect to ≤r . We
define two different types of predecessors of an interval i with respect to ≤r , which correspond
to the subproblems that our dynamic programming algorithm wants to solve. Let i ∈ V \{0}.
Then
• <i =def r- max{h ∈ V : h <r i} and
• i =def r- max{h ∈ V : h <r i and {h, i} ∈
/ E}.

Moreover for a vertex i ∈ V we let Vi =def {h ∈ V : h ≤r i}. Observe that for two vertices
i, x ∈ V with r(i) < r(x), x ∈ V \ Vi . An example of interval graph with the given notation
of Vi is given in Figure 2.
4

e
b
a

c

f
g

d

Ve
V<e
Ve
Vf
V<f
Vf

= {a, b, c, d, e}
= {a, b, c, d}
=∅
= {a, b, c, d, e, f }
= {a, b, c, d, e}
= {a, b, c}

Figure 2: An interval graph given by its interval representation and the corresponding sets
of Ve and Vf . Observe that <f = e whereas f = c. Also notice that the intervals that are
properly contained within the gray area form the set Ve .
Observation 3.1. Let i ∈ V \ {0} and let j ∈ V \ Vi such that {i, j} ∈ E. Then,
(1) Vi = V<i ∪ {i} and
(2) V<i = Vj ∪ {h ∈ V<i : {h, j} ∈ E}.
Proof. The first statement follows by the definitions of Vi and <i. For the second statement
observe that V<i can be partitioned into the non-neighbors of j in V<i and the neighbors
of j in V<i . The first set corresponds to Vj whereas the second set is exactly the set
{h ∈ V<i : {h, j} ∈ E}.
Now we define the sets that our dynamic programming algorithm uses in order to compute
the S-forest-inducing vertex set of G that has maximum weight.
Definition 3.2 (A-sets). Let i ∈ V . Then,
Ai =def max{X ⊆ Vi : G[X] ∈ FS }.
w

Definition 3.3 (B-sets). Let i ∈ V and let x ∈ V \ Vi . Then,
Bix =def max{X ⊆ Vi : G[X ∪ {x}] ∈ FS }.
w

Definition 3.4 (C-sets). Let i ∈ V and let x, y ∈ V \ (Vi ∪ S) such that x <` y and
{x, y} ∈ E. Then,
Cix,y =def max{X ⊆ Vi : G[X ∪ {x, y}] ∈ FS }.
w

Since V0 = {0} and w(0) ≤ 0, A0 = ∅ and, since Vn = V , An = maxw {X ⊆ V : G[X] ∈
FS }. The following lemmas state how to recursively compute all A-sets, B-sets and C-sets
besides A0 .

i ∪ {i} .
Lemma 3.5. Let i ∈ V \ {0}. Then Ai = maxw A<i , B<i
Proof. By Observation 3.1 (1), Vi = V<i ∪{i}. There are two cases to consider for i ∈ V \{0}:
either i ∈
/ Ai or i ∈ Ai . In the former we have Ai = A<i , whereas in the latter i cannot
i by definition, which implies that A = B i ∪ {i}.
induce an S-cycle in B<i
i
<i
For a set of vertices L ⊆ V , the leftmost vertex is the vertex of L having the minimum
left endpoint. That is, the leftmost vertex of L is the vertex x0 such that x0 = `- min{L}.
Lemma 3.6. Let i ∈ V and let x ∈ V \ Vi . Moreover, let x0 be the leftmost vertex of {i, x}
and let y 0 be the vertex of {i, x} \ {x0 }.
(1) If {i, x} ∈
/ E, then Bix = Ai .
5


n
o
 maxw B x , B x0 0 ∪ {i} , if i ∈ S or x ∈ S
n <i y
o
(2) If {i, x} ∈ E, then Bix =
 maxw B x , C x0 ,y0 ∪ {i} , if i, x ∈
/ S.
<i
<i
Proof. Assume first that {i, x} ∈
/ E. Then r(i) < `(x), so that x has no neighbour in
G[Vi ∪ {x}]. Thus no subset of Vi ∪ {x} containing x induces an S-cycle of G. By Definitions
3.2 and 3.3, it follows that Bix = Ai .
Next assume that {i, x} ∈ E. If i ∈
/ Bix then according to Observation 3.1 (1) it follows
x
x
that Bi = B<i . So let us assume in what follows that i ∈ Bix . Observe that Bix \ {i} ⊆ V<i ,
by Observation 3.1 (1). We distinguish two cases according to whether i or x belong to S.
• Let i ∈ S or x ∈ S. Assume there is a vertex h ∈ Bix \ {i} such that {h, y 0 } ∈ E. Then
we know that `(y 0 ) < r(h) and by definition we have `(x0 ) < `(y 0 ) and r(h) < r(x0 ).
This particularly means that h is adjacent to x0 . This however leads to a contradiction
since hh, x0 , y 0 i is an induced S-triangle of G. Thus for any vertex h ∈ Bix \ {i} we
know that {h, y 0 } ∈
/ E. By Observation 3.1 (2) notice that Bix \ {i} ⊆ Vy0 . Also
observe that the neighbourhood of y 0 in G[Vy0 ∪ {x0 , y 0 }] is {x0 }. Thus no subset of
x0 ∪ {i}.
Vy0 ∪ {x0 , y 0 } that contains y 0 induces an S-cycle of G. Therefore Bix = By
0
0

0

x ,y
• Let i, x ∈
/ S. By the fact Vi = V<i ∪ {i} and since x0 <` y 0 we get Bix = C<i
∪ {i}.

Therefore in all cases we reach the desired equations.
Lemma 3.7. Let i ∈ V and let x, y ∈ V \(Vi ∪S) such that x <` y and {x, y} ∈ E. Moreover,
let x0 be the leftmost vertex of {i, x, y} and let y 0 be the vertex of {i, x, y} \ {x0 }.
1. If {i, y} ∈
/ E, then Cix,y = Bix .
( x,y
C<i n
o, if i ∈ S
x,y
2. If {i, y} ∈ E, then Ci =
x,y
x0 ,y 0
maxw C<i , C<i ∪ {i} , if i ∈
/ S.
Proof. Assume first that {i, y} ∈
/ E. Then r(i), `(x) < `(y) < r(x), so that the neighbourhood of y in G[Vi ∪ {x, y}] is {x}. Thus no subset of Vi ∪ {x, y} that contains y induces an
S-cycle of G. By Definitions 3.3 and 3.4, it follows that Cix,y = Bix .
Assume next that {i, y} ∈ E. Then `(x) < `(y) < r(i) < r(x), r(y), so that hi, x, yi is an
x,y
induced triangle of G. If i ∈
/ Cix,y then by Observation 3.1 (1) we have Cix,y = C<i
. Suppose
that i ∈ Cix,y . If i ∈ S then hi, x, yi is an induced S-triangle of G, contradicting the fact that
i ∈ Cix,y . By definition observe that x, y ∈ Cix,y which means that also x ∈
/ S and y ∈
/ S.
Hence i ∈ Cix,y implies that S ∩ {i, x, y} = ∅. We will show that under the assumptions
x0 ,y 0
{i, y} ∈ E and i ∈ Cix,y , we have Cix,y = C<i
∪ {i}. Notice that Cix,y \ {i} ⊆ V<i which
x0 ,y 0
means that every solution of Cix,y is a solution of C<i
∪ {i}.
x0 ,y 0
To complete the proof we show that every solution of C<i
∪ {i} is indeed a solution of
Cix,y . Let z 0 be the vertex of {i, x, y} \ {x0 , y 0 }. Observe that by the leftmost ordering
we have `(x0 ) < `(y 0 ) < `(z 0 ). We consider the graph G<i induced by the vertices of
V<i ∪ {x0 , y 0 , z 0 }. Assume for contradiction that an S-triangle of G<i is not an S-triangle in
0 0
0 0
Cix ,y . Every S-triangle that contains x0 or y 0 of G<i remains an S-triangle in Cix ,y . Thus
z 0 must be contained in such an S-triangle of G<i . Let hv1 , v2 , z 0 i be an induced S-triangle
of G<i , where v1 , v2 ∈ V<i . Since x0 , y 0 , z 0 ∈
/ S, without loss of generality, assume that
v1 ∈ S. The S-triangle of G<i implies that `(z 0 ) < r(v1 ). By the fact that v1 ∈∈ V<i we
have r(v1 ) < r(x0 ), r(y 0 ), r(z 0 ). Since `(x0 ) < `(y 0 ) < `(z 0 ) the previous inequalities imply
0 0
that {v1 , x0 }, {v1 , y 0 } ∈ E. Thus hv1 , x0 , y 0 i is an induced S-triangle in Cix ,y , leading to a
x0 ,y 0
contradiction. Therefore Cix,y = C<i
∪ {i} as desired.
6

Now we are equipped with our necessary tools to obtain the main result of this section,
namely a polynomial-time algorithm for SFVS on interval graphs.
Theorem 3.8. Subset Feedback Vertex Set can be solved in O(n3 ) time on interval
graphs.
Proof. We briefly describe such an algorithm based on Lemmas 3.5, 3.6, and 3.7. In a
preprocessing step we compute < i and  i for each interval i ∈ V \ {0}. We scan all
intervals from 0 to n in an ascending order with respect to <` . For every interval i that
we visit, we compute first Ai according to Lemma 3.5 and then compute Bix and Cix,y for
every x, y such that `(i) < `(x) < `(y) according to Lemmas 3.6 and 3.7, respectively. At
the end we output An as already explained. The correctness of the algorithm follows from
Lemmas 3.5–3.7.
Regarding the running time, notice that computing < i and  i can be done in O(n)
time since the intervals are sorted with respect to their end-points. The computation of a
single A-set, B-set or C-set takes constant time. Therefore the overall running time of the
algorithm is O(n3 ).
We will show that the previous algorithm can be polynomially applied for a superclass
of interval graphs, namely to that of circular-arc graphs. A graph is called circular-arc if it
is the intersection graph of arcs of a circle. Every vertex is represented by an arc, such that
two vertices are adjacent if and only if the corresponding arcs intersect. The family of arcs
corresponding to the vertices of the graph constitute a circular-arc model.
Theorem 3.9. Subset Feedback Vertex Set can be solved in O(n4 ) time on circular-arc
graphs.
Proof. Let G be the input circular-arc graph and let S ⊆ V . If G is an interval graph then
we run the algorithm given in Theorem 3.8. Otherwise in any circular-arc model the whole
circle is covered by arcs. Let the set of n arcs of the circle have arc end-points 1, . . . , 2n. We
denote by Ai the set of arcs containing point i. By the circular-arc model notice that for
each i the graph G − Ai is an interval graph. Moreover notice that the subgraph induced by
Ai is a clique and, thus, an interval graph.
Our algorithm proceeds in two phases. First it chooses all 2n points and for each removes
all arcs containing it. Then we run the interval graph algorithm on the remaining graph
without the arcs of the point. More formally, for each point i let Xi be a maximum S-forest
of G − Ai . Observe that Xi can be computed by the interval algorithm. At the end we
choose the maximum weighted set among all Xi for each point i. This constitutes the first
phase of our algorithm.
Concerning its correctness, recall that the whole circle is covered by arcs. Let C be the
family of minimal set of arcs that cover the whole circle. For any set C ∈ C observe that
G[C] is a cycle. Assume first that there is an S-cycle CS ∈ C. Then we must remove for
some point of the circle all arcs containing it. Thus if there is an S-cycle CS ∈ C then there
is a point i such that the set Xi is a maximum S-forest.
In what follows we assume that there is no S-cycle in C. Consider an S-cycle CS0 in G.
We show next that CS0 ⊆ Ai , for some point i. Suppose for contradiction that the S-cycle
CS0 * Ai . Choose an appropriate Ai such that si ∈ Ai ∩ S. Then there is a neighbour x of
si that belongs to CS0 such that x ∈
/ Ai . Let y be the other neighbour of si in the S-cycle
CS0 . If x and y are adjacent then {x, y, si } induce an S-triangle and there is a point i0 such
that {x, y, si } ⊆ Ai0 . Otherwise, there is a path between x and y because of the S-cycle CS0 .
Such a path is contained in the graph G − Ai so that there is a cycle CS ∈ C, leading to a
contradiction. Therefore such an S-cycle is completely contained in some Ai .

7

Aj
sj

sj+1

yj

yj+1

Figure 3: A circular-arc graph given by its circular-arc model considered in the proof of
Theorem 3.9.
At the second phase we remove any vertex that is non-adjacent to an S-vertex. Let NS
be the vertices that are non-adjacent to any S-vertex. In any solution X of the graph G−NS
we can safely add the vertices of NS . This is because no vertex of NS participates in any
S-cycle CS0 of G, since CS0 ⊆ Ai for some point i.
If the graph G − NS is an interval graph then we run the interval algorithm given in
Theorem 3.8. Otherwise, we will show that there is an edge e in G − NS such that
(i) no S-cycle of G − NS passes through e and
(ii) the graph obtained from G − NS by removing e is an interval graph.
Since G − NS is a circular-arc graph but not an interval graph, C is non-empty. Let
hy1 , y2 , . . . , yk i be a chordless cycle of C with k ≥ 4. For every two adjacent vertices yj , yj+1
of the cycle there is a point j such that yj , yj+1 ∈ Aj , yj ∈
/ Aj+1 , and yj+1 ∈
/ Aj−1 . Figure 3
shows the corresponding situation. Then observe that Aj ∩ S = ∅, since for any vertex
x ∈ Aj ∩ S we have an S-cycle hy1 , . . . , yj , x, yj+1 , . . . , yk i in C. Let sj and sj+1 be the first
counterclockwise and clockwise arcs, respectively, that belong to S starting at point j. It is
clear that yj is adjacent to sj and yj+1 is adjacent to sj+1 . If yj is also adjacent to sj+1 then
hy1 , . . . , yj , sj+1 , yj+1 , . . . , yk i is an S-cycle in C. Thus yj is adjacent to sj and non-adjacent
to sj+1 whereas yj+1 is adjacent to sj+1 and non-adjacent to sj .
Next we show that Aj = {yj , yj+1 }. Let x ∈ Aj \ {yj , yj+1 }. Since every vertex of
G − NS is adjacent to at least one vertex of S, x is adjacent to sj or sj+1 . If x is adjacent
to sj then there is an S-cycle hy1 , . . . , yj , sj , x, yj+1 , . . . , yk i in C. The symmetric S-cycle
occurs whenever x is adjacent to sj+1 . Thus in all cases we reach a contradiction so that
Aj = {yj , yj+1 }. This shows that if we remove the edge e0 = {yj , yj+1 } from G − NS
then we get an interval graph by the circular-arc model of G − NS . Moreover no S-cycle
passes through the edge e0 = {yj , yj+1 } as then we would have an S-cycle in C. Hence by
Theorem 3.8 we run the algorithm on the graph obtained from G − NS by removing the edge
e0 and compute a solution X 0 . Therefore X 0 ∪ NS ∪ e0 is a solution of the original graph G.
Regarding the running time the most time consuming is the first phase of our algorithm
in which we need to run for every point the interval algorithm. Observe that there are at
most 2n points and for each we need to run the O(n3 ) interval algorithm. Therefore the
total running time of our algorithm is O(n4 ).

4

Computing SFVS on permutation graphs

Let π = π(1), . . . , π(n) be a permutation over {1, . . . , n}, that is a bijection between {1, . . . , n}
and {1, . . . , n}. The position of an integer i in π is denoted by π −1 (i). Given a permutation
π, the inversion graph of π, denoted by G(π), has vertex set {1, . . . , n} and two vertices i, j
are adjacent if (i − j)(π(i) − π(j)) < 0. A graph is a permutation graph if it is isomorphic to
the inversion graph of a permutation [6, 19]. For our purposes, we assume that a permutation
8

graph is given as a permutation π and equal to the defined inversion graph. Permutation
graphs also have an interesting geometric intersection model: they are the intersection graphs
of segments between two horizontal parallel lines, that is, there is a one-to-one mapping from
the segments onto the vertices of a graph such that there is an edge between two vertices of
the graph if and only if their corresponding segments intersect. We refer to the two horizontal lines as top and bottom lines. This representation is called a permutation diagram and a
graph is a permutation graph if and only if it has a permutation diagram. It is important
to note that every induced subgraph of a permutation graph is a permutation graph. Every
permutation graph with permutation π has a permutation diagram in which the endpoints
of the line segments on the bottom line appear in the same order as they appear in π.
We assume that we are given a connected permutation graph G = (V, E) such that
G = G(π) along with a vertex set S ⊆ V and a weight function w : V → R+ as input. We
add an isolated vertex in G and augment π to π 0 as follows: π 0 = {0} ∪ π with π 0 (0) = 0.
Further we assign a negative value for 0’s weight and assume that 0 ∈
/ S. It is important
to note that any induced cycle of a permutation graph is either an induced triangle or an
induced square [4, 3, 5, 22, 27].
We consider the two relations on V defined as follows: i ≤t j if and only if i ≤ j and
i ≤b j if and only if π −1 (i) ≤ π −1 (j) for all i, j ∈ V ∪ {0}. It is not difficult to see that both
≤t and ≤b are total orders on V ; they are exactly the orders in which the integers appear
on the top and bottom line, respectively, in the permutation diagram. Moreover we write
i <t j or i <b j if and only if i 6= j and i ≤t j or i ≤b j, respectively. We extend ≤t and
≤b to support sets of vertices as follows. For two sets of vertices L and R we write L ≤t R
(resp., L ≤b R) if for any two vertices u ∈ L and v ∈ R, u ≤t v (resp., u ≤b v).
Let G =def G(π) be a permutation graph. Two vertices i, j ∈ {0, 1, . . . , n} with i ≤t j are
called crossing pair, denoted by ij, if j ≤b i. We denote by X the set of crossing pairs in G.
Observe that a crossing pair ij with i 6= j corresponds to an edge of G. In order to distinguish
the edges of G with the crossing pairs of the form ii we let I = {ii | i ∈ {1, . . . , n}}, so that
X \ I contains exactly the edges of G.
Given two crossing pairs gh, ij ∈ X we define two partial orderings:
gh ≤` ij ⇐⇒ g ≤t i and h ≤b j
gh ≤r ij ⇐⇒ g ≤b i and h ≤t j.
As in the case for interval graphs, we write `- min to denote the crossing pair with the
minimum top and bottom integers with respect to ≤` ; and we write r- max to denote the
crossing pair with the maximum top and bottom integers with respect to ≤r .
Our dynamic programming algorithm iterates on ordered crossing vertex pairs. We next
define the predecessors of a crossing pair with respect to ≤r , which correspond to the subproblems that our dynamic programming algorithm wants to solve. Let ij ∈ X \ {00} be a
crossing pair. We define the set of vertices that induce the part of the subproblem that we
consider at each crossing pair as follows: Vij =def {h ∈ V : hh ≤r ij}. Let x be a vertex such
that i <b x or j <t x. By definition notice that x does not belong in Vij . The predecessors
of the crossing pair ij are defined as follows:
• 0ij =def r- max{gh ∈ X : gh ≤r ij and h 6= j},
• 6ij =def r- max{gh ∈ X : gh ≤r ij and g 6= i},
• <ij =def r- max{gh ∈ X : gh <r ij,
• ij =def r- max{gh ∈ X : gh <r ij and {g, i}, {g, j}, {h, i}, {h, j} ∈
/ E}, and
• <ijxx =def r- max{gh ∈ X : gh <r ij and {g, x}, {h, x} ∈
/ E}.
9

a

b

c

d

e

f

g

h

b

h

f

c

a

g

d

e

0dg = df
6dg = gg
<dg = af
dg = ac
<dghh = bb

Vdg
V0dg
V6dg
V<dg
Vdg

= {a, b, c, d, f, g}
= {a, b, c, d, f }
= {a, b, c, f, g}
= {a, b, c, f }
= {a, b, c}

Figure 4: A permutation graph given by its permutation diagram and the set Vdg of the
crossing pair dg together with the corresponding predecessors of dg. Observe that the line
segments that are properly contained within the gray area form the set Vdg .
Although it seems somehow awkward to use one the symbols {0, 6, <, , <} for the
defined predecessors, we stress that such predecessors are required only to describe the
necessary subset Vgh of Vij . Moreover it is not difficult to see that each of the symbol
gravitates towards a particular meaning with respect to the top and bottom orderings as
well as the non-adjacency relationship. An example of a permutation graph that illustrates
the defined predecessors is given in Figure 4.
With the above defined predecessors of ij, we show how the set Vij can be partitioned
into smaller sets of vertices with respect to a suitable predecessor.
Observation 4.1. Let ij ∈ X and let x ∈ V \ Vij . Then,
(1) Vij = V0ij ∪ {j} = V6ij ∪ {i} = V<ij ∪ {i, j},
(2) V<ij = Vjj ∪ {h ∈ V<ij : {h, j} ∈ E} = Vii ∪ {h ∈ V<ij : {h, i} ∈ E},
(3) Vii = Vij ∪ {h ∈ Vii : {h, j} ∈ E},
(4) Vjj = Vij ∪ {h ∈ Vjj : {h, i} ∈ E}, and
(5) V<ij = V<ijxx ∪ {h ∈ V<ij : {h, x} ∈ E}.
Proof. Let ij1 be the predecessor 0ij. By the r- max choice of j1 , there is no vertex j 0 such
that j1 <t j 0 <t j. Thus Vij1 ∪ {j} is the set Vij . The rest of the equalities in the first
statement follow in a similar way.
Let i1 j1 be the predecessor jj. Then both i1 and j1 are non-adjacent to j and have
the maximum values such that i1 <b j and j1 <t j, respectively. This particularly means
that i1 <t j1 <t j and j1 <b i1 <b j. Thus any vertex i0 ∈ Vij \ {i, j} with j1 <t i0 <t j
or i1 <b i0 <b j must be adjacent to j which implies that V<ij \ Vjj contains exactly the
neighbours of j in V<ij . These arguments imply the second, third, and fourth statements.
For the last statement, notice that V<ij can be partitioned into the neighbours and the
non-neighbours of x. By definition V<ijxx contains the non-neighbours of x so that every
vertex of V<ij \ V<ijxx is adjacent to x.
It is clear that for any edge {i, j} ∈ E either i <t j and j <b i hold, or j <t i and i <b j
hold. If further ij ∈ X \ I, is a crossing pair then we know that i <t j and j <b i.
Next we define the sets that our dynamic programming algorithm computes in order to
compute the induced S-forest vertex set of G that has maximum weight. Our main idea
relies on the similar sets that we used for the dynamic programming of interval graphs. That
is, we need to describe appropriate sets that define the solutions to be chosen only from a
specific part of the considered subproblem. Although for interval graphs we showed that
adding two vertices into such sets is enough, for permutation graphs we need to consider at
most two newly crossing pairs which corresponds to consider at most four newly vertices.

10

Moreover as a crossing pair may belong to I we are enforced to describe such a situation
into two different sets for each subproblem.
Definition 4.2 (A-sets). Let ij ∈ X . Then,
Aij =def max{X ⊆ Vij : G[X] ∈ FS }.
w

Definition 4.3 (B-sets). Let ij ∈ X and let x ∈ V \ Vij . Then,
xx
Bij
=def max{X ⊆ Vij : G[X ∪ {x}] ∈ FS }.
w

Definition 4.4 (B-sets). Let ij ∈ X and xy ∈ X \ I such that j <t y, i <b x, and x, y ∈
/ S.
Then,
xy
Bij
=def max{X ⊆ Vij : G[X ∪ {x, y}] ∈ FS }.
w

Definition 4.5 (C-sets). Let ij ∈ X , xy ∈ X \ I, and z ∈ V \ (Vij \ {x, y}) such that
xy <` zz, at least one of x, y is adjacent to z, j <t y, i <b x, and x, y, z ∈
/ S. Then,
xy,zz
Cij
=def max{X ⊆ Vij : G[X ∪ {x, y, z}] ∈ FS }.
w

Definition 4.6 (C-sets). Let ij ∈ X and xy, zw ∈ X \I such that xy <` zw, {x, w}, {y, z} ∈
E, j <t {y, w}, i <b {x, z}, and x, y, z, w ∈
/ S. Then,
xy,zw
Cij
=def max{X ⊆ Vij : G[X ∪ {x, y, z, w}] ∈ FS }.
w

Observe that, since V00 = {0} and w(0) ≤ 0, A00 = ∅ and, since Vπ(n)n = V , Aπ(n)n =
maxw {X ⊆ V : G[X] ∈ FS }. The following lemmas state how to recursively compute all
A-sets, B-sets, and C-sets other than A00 . Because every crossing pair ij might be of the
form ii we first consider the sets Aii , Biixx , Biixy , Ciixy,zz , and Ciixy,zw .
Lemma 4.7. Let i ∈ V \ {0}. Then Aii = A<ii ∪ {i}.
Proof. By Observation 4.1 (1) we have A<ii ∪ {i} ∈ Aii . Also notice that the neighbourhood
of i in G[Vii ] is ∅. Thus no subset of Vii that contains i induces an S-cycle in G, so that
i ∈ Aii . Therefore Aii = A<ii ∪ {i}.
Lemma 4.8. Let i ∈ V and let x ∈ V \ Vii .
1. If {i, x} ∈
/ E then Biixx = Aii .
xx ∪ {i}.
2. If {i, x} ∈ E then Biixx = B<ii

Proof. Assume first that {i, x} ∈
/ E. Since x ∈ V \ Vii we know that i <t x or i <b x.
Moreover as {i, x} ∈
/ E we have i <t x and i <b x. Then x has no neighbour in G[Vii ∪ {x}].
Thus no subset of Vii ∪{x} that contains x induces an S-cycle in G. Hence Biixx = Aii follows.
Next assume that {i, x} ∈ E. Then the neighbourhood of i in G[Vii ∪ {x}] is {x}. This
means that no subset of Vii ∪ {x} that contains i induces an S-cycle in G, so that i ∈ Biixx .
xx ∪ {i}.
By Observation 4.1 (1) it follows that Biixx = B<ii
Lemma 4.9. Let i ∈ V and let xy ∈ X \ I such that i <t y, i <b x, and x, y ∈
/ S.
1. If {i, y} ∈
/ E then Biixy = Biixx .
2. If {i, x} ∈
/ E then Biixy = Biiyy .
11

(
3. If {i, x}, {i, y} ∈ E then Biixy =

xy
B<ii
, if i ∈ S
xy
B<ii ∪ {i}, if i ∈
/ S.

Proof. By i <t y, i <b x, and the fact that xy is a crossing pair, we have {x, i} <t y and
{y, i} <b x. Assume first that i is non-adjacent to at least one of x and y. Let {i, y} ∈
/ E.
Then {i, x} <t y and i <b y <b x, so that the neighbourhood of y in G[Vii ∪ {x, y}] is
{x}. Thus no subset of Vii ∪ {x, y} that contains y induces an S-cycle of G which implies
that Biixy = Biixx . Completely symmetric arguments apply if {i, x} ∈
/ E showing the second
statement.
Next assume that {i, x}, {i, y} ∈ E. Then x <t i <t y and y <b i <b x, so that the
neighbourhood of i in G[X ∪ {x, y}] is {x, y}. We distinguish two cases according to whether
i belongs to S. Suppose that i ∈ S. Then hi, x, yi is an induced S-triangle of G, so that
xy
i∈
/ Biixy . Thus by Observation 4.1 (1), Biixy = B<ii
holds if i ∈ S.
Suppose next that i ∈
/ S. We will show that no subset of Vii ∪ {x, y} that contains i
induces an S-cycle of G. Recall that i is non-adjacent to any vertex of Vii and the only
induced cycles of a permutation graph is either a triangle or a square. Assume that hv1 , v2 , ii
is an induced S-triangle of G where v1 , v2 ∈ V<ii ∪ {x, y}. Then {v1 , v2 } = {x, y} leading
to a contradiction, because i, x, y ∈
/ S. So let us assume that hv1 , v2 , v3 , ii is an induced
S-square of G where v1 , v2 , v3 ∈ V<ii ∪ {x, y}. By the fact that i only adjacent to x and y
in G[Vii ∪ {x, y}] we have that v1 , v3 correspond to the vertices x and y. This however leads
to a contradiction since {x, y} ∈ E and {v1 , v3 } ∈
/ E by the induced S-square. Therefore
no subset of Vii ∪ {x, y} that contains i induces an S-cycle of G, so that i ∈ Biixy . By
xy
Observation 4.1 (1) Biixy = B<ii
∪ {i} holds and this completes the proof.
Lemma 4.10. Let i ∈ V , xy ∈ X \ I, and let z ∈ V \ (Vii \ {x, y}) such that xy <` zz, at
least one of x, y is adjacent to z, i <t y, i <b x, and x, y, z ∈
/ S.
1. If {i, z} ∈
/ E then Ciixy,zz = Biixy .
(
xy,zz
C<ii
,
if i ∈ S
xy,zz
2. If {i, z} ∈ E then Cii
=
xy,zz
C<ii ∪ {i}, if i ∈
/ S.

Proof. Since z ∈ V \ (Vii \ {x, y}), we have i <t z or i <b z. Assume first that {i, z} ∈
/ E.
Observe that this means that i <t z and i <b z. Then z is non-adjacent to any vertex of Vii
so that the neighborhood of z in G[Vii ∪ {x, y, z}] is a subset of {x, y}. Since x, y, z ∈
/ S, no
xy,zz
xy
subset of Vii ∪ {x, y, z} that contains z induces an S-cycle in G. Thus Cii
= Bii .
Assume next that {i, z} ∈ E. This means that either i <t z and z <b i hold, or z <t i
and i <b z hold. Since i <t y and i <b x, we get either i <t {y, z} and z <b i <b x, or
z <t i <t y and i <b {x, z}. Moreover since xy is a crossing pair and xy <` zz, exactly one
of following holds:
• {i, x} <t {y, z} and y <b z <b i <b x;
• x <t z <t i <t y and {i, y} <b {x, z}.

This means that y, z ∈ N (i) and x is adjacent to z, or x, z ∈ N (i) and y is adjacent to z.
We distinguish two cases depending on whether i belongs to S.
• Let i ∈ S. We will show that i ∈
/ Ciixy,zz . If both x and y are adjacent to i then
hi, x, yi is an induced S-triangle in G. Thus either y, z ∈ N (i) and x is adjacent to
z, or x, z ∈ N (i) and y is adjacent to z. Assume the former, that is, y, z ∈ N (i),
x∈
/ N (i), and x is adjacent to z. If {y, z} ∈ E then hi, y, zi is an induced S-triangle
and if {y, z} ∈
/ E then hi, y, x, zi is an induced S-square. Similarly if x, z ∈ N (i),
y∈
/ N (i), and y is adjacent to z we obtain an induced S-cycle in G. Therefore in all
xy,zz
cases i ∈
/ Ciixy,zz and by Observation 4.1 (1) we get Ciixy,zz = C<ii
.
12

• Let i ∈
/ S. We will show that i ∈ Ciixy,zz . Assume for contradiction that there is an
induced S-triangle hv1 , v2 , ii or S-square hv1 , v2 , v3 , ii in G where v1 , v2 , v3 ∈ V<ii ∪
{x, y, z}. Notice that N (i) ∩ V<ii = ∅ so that {v1 , v2 } ⊂ {x, y, z} or {v1 , v3 } ⊂ {x, y, z},
respectively. In the former case we reach a contradiction because i, x, y, z ∈
/ S. In the
latter case for the same reason notice that v2 ∈ S which implies that v2 ∈ V<ii . If
{v1 , v3 } = {x, y} then we reach a contradiction to the S-square hv1 , v2 , v3 , ii because
{x, y} ∈ E. Thus {v1 , v3 } = {y, z} or {v1 , v3 } = {x, z}. Without loss of generality
assume that {v1 , v3 } = {y, z}. Then {y, z} ∈
/ E, for otherwise we reach again a
contradiction to the given S-square. Observe that {y, z} ∈
/ E implies that {x, z} ∈ E
by the hypothesis for z. This however shows that hy, v2 , xi or hy, v2 , z, xi induce an
S-triangle or an S-square of G without i depending on whether x is adjacent to v2 ,
so that v2 ∈
/ Ciixy,zz . Therefore in all cases we reach a contradiction which means that
xy,zz
xy,zz
i ∈ Cii
and by Observation 4.1 (1), Ciixy,zz = C<ii
∪ {i} holds.
In each case we have showed the described equations and this completes the proof.
Lemma 4.11. Let i ∈ V and let xy, zw ∈ X \ I such that xy <` zw, {x, w}, {y, z} ∈ E,
i <t {y, w}, i <b {x, z}, and x, y, z, w ∈
/ S.
1. If {i, w} ∈
/ E then Ciixy,zw = Ciixy,zz .

2. If {i, z} ∈
/ E then Ciixy,zw = Ciixy,ww .
(
3. If {i, z}, {i, w} ∈ E then

Ciixy,zw

=

xy,zw
C<ii
,
if i ∈ S
xy,zw
C<ii ∪ {i}, if i ∈
/ S.

Proof. Observe that x, y, z, w ∈ V \Vii because i <t {y, w} and i <b {x, z}. Assume first that
{i, w} ∈
/ E. Since i <t w and i <b w, w has no neighbour in Vii . Thus the neighbourhood of
w in G[Vii ∪{x, y, z, w}] is a subset of {x, y, z}. We will show that w ∈
/ Ciixy,zw . Assume that a
subset of Vii ∪ {x, y, z, w} that contains w induces an S-cycle in G. If hv1 , v2 , wi is an induced
S-triangle of G then {v1 , v2 } ⊂ {x, y, z} which leads to a contradiction, because x, y, z, w ∈
/ S.
Suppose that hv1 , v2 , v3 , wi is an induced S-square of G. Then {v1 , v3 } ⊂ {x, y, z} and, since
x, y, z, w ∈
/ S we know that v2 ∈ S and v2 ∈ Vii .
• Assume that {v1 , v3 } = {x, y} or {v1 , v3 } = {y, z}. Then we reach a contradiction to
the induced S-square, because {x, y}, {y, z} ∈ E.
• Assume that {v1 , v3 } = {x, z}. If {x, z} ∈ E then hv1 , v2 , v3 , wi does not induce an Ssquare. If {x, z} ∈
/ E then hx, v2 , yi or hx, v2 , z, yi induce an S-triangle or an S-square
in G which reach to a contradiction to v2 ∈
/ Ciixy,zz .
Therefore, if a subset of Vii ∪ {x, y, z, w} that contains w induces an S-cycle of G, then its
non-empty intersection with Vii is not a subset of Ciixy,zz which implies that Ciixy,zw = Ciixy,zz .
The case for {i, z} ∈
/ E is completely symmetric showing the second statement.
Let {i, z}, {i, w} ∈ E. Then either i <t {z, w} and {z, w} <b i, or {z, w} <t i and
i <b {z, w}. Since xy <` zw, i <t {y, w}, and i <b {x, z}, the following hold:
• x <t z <t i <t {y, w} and
• y <b w <b i <b {x, z}.
Thus the neighborhood of i in G[Vii ∪ {x, y, z, w}] is {x, y, z, w}. Assume that i ∈ S. Then
hi, x, yi is an S-triangle of G which implies i ∈
/ Ciixy,zw . By Observation 4.1 (1) we get
xy,zw
xy,zw
Cii
= C<ii . Let us assume that i ∈
/ S. We will show that if a subset of Vii ∪ {x, y, z, w}
that contains i induces an S-cycle of G, then its non-empty intersection with V<ii is not a
subset of Ciixy,zw .
13

• Let v1 , v2 ∈ V<ii ∪ {x, y, z, w} such that hv1 , v2 , ii is an induced S-triangle of G. Then
{v1 , v2 } ⊂ {x, y, z, w}, a contradiction, because i, x, y, z, w ∈
/ S.
• Let v1 , v2 , v3 ∈ V<ii ∪ {x, y, z, w} such that hv1 , v2 , v3 , ii is an induced S-square of G.
Then {v1 , v3 } ⊂ {x, y, z, w} and, since i, x, y, z, w ∈
/ S, v2 ∈ S. Thus v2 ∈ V<ii . Because
v1 , v3 are non-adjacent, we have {v1 , v3 } = {x, z} or {v1 , v3 } = {y, w}. In both cases
we reach a contradiction since hx, v2 , z, yi or hy, v2 , w, zi induce S-squares in G.

Thus if i ∈
/ S then i ∈ Ciixy,zw . Therefore by Observation 4.1 (1) we obtain Ciixy,zw =
xy,zw
C<ii ∪ {i}.

Based on Lemmas 4.7–4.11, for each crossing pair of the form ii we can describe its
subsolution by using appropriate formulations of the A-, B-, or C-sets. In the forthcoming
xx , B xy , C xy,zz , and C xy,zw
lemmas we give the recursive formulations for the sets Aij , Bij
ij
ij
ij
whenever ij ∈ X \ I which particularly means that i and j are distinct vertices in G.
Lemma 4.12. Let ij ∈ X \ I. Then,

n
o
 maxw A0ij , A6ij , B ii ∪ {i, j}, B jj ∪ {i, j} , if i ∈ S or j ∈ S
jj
n
o ii
Aij =
 maxw A0ij , A6ij , B ij ∪ {i, j} ,
if i, j ∈
/ S.
<ij
Proof. Let j ∈
/ Aij . Then by Observation 4.1 (1) it follows that Aij = A0ij . Similarly if
i∈
/ Aij then Aij = A6ij . For the rest of the proof we assume that i, j ∈ Aij . Notice that
by Observation 4.1 (1) we have Aij \ {i, j} ⊆ V<ij . We distinguish two cases according to
whether i or j belong to S.
ij
• Assume that i, j ∈
/ S. Then Aij = B<ij
∪ {i, j} holds which completes the second
description in the formula.

• Assume that i ∈ S or j ∈ S. Let h ∈ Aij \ {i, j} such that {h, i}, {h, j} ∈ E. Then
hh, i, ji is an induced S-triangle in G, resulting a contradiction to i, j ∈ Aij . Thus for
every h ∈ Aij \ {i, j} we know that {h, i} ∈
/ E or {h, j} ∈
/ E. Let g, h ∈ Aij \ {i, j} such
that {g, j}, {h, i} ∈ E and {g, i}, {h, j} ∈
/ E. Observe that {g, h} <b i and {g, h} <t j.
Since ij is a crossing pair we know that i <t j and j <b i. If i <t g or j <b h then g
is adjacent to i or h is adjacent to j, leading to a contradiction. Thu g <t i <t h and
h <b j <b g hold which imply that {g, h} ∈ E. Hence hg, h, i, ji is an induced S-square
in G, a contradiction. This means that all vertices of Aij \ {i, j} are non-adjacent to i
or j or both. Then by Observation 4.1 (2) it follows that either Aij \ {i, j} ⊆ Vjj or
Aij \ {i, j} ⊆ Vii .
Suppose that the former holds, that is Aij \ {i, j} ⊆ Vjj . The neighborhood of j
in G[Vjj ∪ {i, j}] is {i}. Thus no subset of Vjj ∪ {i, j} that contains j induces an
ii
S-cycle in G. This means that Aij = Bjj
∪ {i, j} as described in the first description
in the given formula. If Aij \ {i, j} ⊆ Vii then completely symmetric we have Aij =
jj
Bii
∪ {i, j}.

Therefore the corresponding formulas given in the statement follow.
xx and B xy . Given a set of
With the next two lemmas we describe recursively the sets Bij
ij
vertices L ⊆ V we define the following crossing pair. The leftmost crossing pair of L is the
crossing pair x0 y 0 ∈ X \ I with x0 , y 0 ∈ L such that for any z 0 w0 ∈ X \ I with z 0 , w0 ∈ L,
x0 y 0 ≤` z 0 w0 holds.

Lemma 4.13. Let ij ∈ X \ I and let x ∈ V \ Vij . Moreover let x0 y 0 be the leftmost crossing
pair of {i, j, x} and let z 0 be the vertex of {i, j, x} \ {x0 , y 0 }.
14

xx = A .
1. If {i, x}, {j, x} ∈
/ E then Bij
ij

2. If {i, x} ∈ E and {j, x} ∈
/ E then

n
o
jj
xx , B xx , B ii

max
B
∪
{i,
j},
B
∪
{i,
j}
, if i ∈ S or j ∈ S

w
ix


n 0ij 6ij jj
o
xx
xx , B xx , B ij
Bij
=
maxw B0ij
if i, j ∈
/ S and x ∈ S
6ij
<ijxx ∪ {i, j} ,

n
o

0
0
0
0

 maxw B xx , B xx , C x y ,z z ∪ {i, j} ,
if i, j, x ∈
/ S.
0ij
6ij
<ij
3. If {i, x} ∈
/ E and {j, x} ∈ E then

n
o
jj
xx , B xx , B ii

max
B
∪
{i,
j},
B
∪
{i,
j}
, if i ∈ S or j ∈ S

w
ii


n 0ij 6ij xj
o
xx
xx , B xx , B ij
Bij
=
maxw B0ij
if i, j ∈
/ S and x ∈ S
6ij
<ijxx ∪ {i, j} ,

n
o

0
0
0
0

 maxw B xx , B xx , C x y ,z z ∪ {i, j} ,
if i, j, x ∈
/ S.
0ij
6ij
<ij
4. If {i, x}, {j, x} ∈ E then

n
o
 maxw B xx , B xx ,
if i ∈ S or j ∈ S or x ∈ S
0ij
6ij
xx
n
o
Bij
=
0 y 0 ,z 0 z 0
x
 maxw B xx , B xx , C
∪ {i, j} , if i, j, x ∈
/ S.
0ij
6ij
<ij
Proof. Let us assume first that {i, x}, {j, x} ∈
/ E. Since i <t j, j <b i, and x ∈ V \ Vij ,
we know that i <t j <t x and j <b i <b x. Thus the neighborhood of x in G[Vij ∪ {x}] is
∅. Hence no subset of Vij ∪ {x} that contains x induces an S-cycle of G and it follows that
xx = A as described in the first statement.
Bij
ij
xx . By Observation 4.1 (1) we get
Assume next that {i, x} ∈ E or {j, x} ∈ E. Let j ∈
/ Bij
xx
xx
xx
xx
xx
xx . Notice
Bij = B0ij . Similarly, if i ∈
/ Bij then Bij = B6ij . So suppose next that i, j ∈ Bij
xx \ {i, j} ⊆ V
that Bij
<ij by Observation 4.1 (1). We distinguish the following cases.
• Assume that {i, x} ∈ E and {j, x} ∈
/ E. Since x ∈
/ Vij , j <t x or i <b x. If i <b x
then x <t i as {i, x} ∈ E but then x <t j and j <b i <b x so that {j, x} ∈ E, leading
to a contradiction. Thus j <t x holds. Since {i, x} ∈ E and {j, x} ∈
/ E, we have
j <b < x <b i and i <t < j <t x. We further reduce to the situations depending on
whether i, j, x belong to S.
xx \ {i, j} such that {h, i}, {h, j} ∈ E. Then hh, i, ji
– Let i ∈ S or j ∈ S. Let h ∈ Bij
is an induced S-triangle in G, a contradiction. So {h, i} ∈
/ E or {h, j} ∈
/ E for
xx \ {i, j}. Let g, h ∈ B xx \ {i, j} such that {g, j}, {h, i} ∈ E. Since
every h ∈ Bij
ij
{g, h} <b i and {g, h} <t j by the choice of g, h ∈ Bij , it follows that g <t i <t h
and h <b j <b g. Thus {g, h} ∈ E. This however results in an induced S-square
xx \ {i, j} either {h, i} ∈
hg, h, i, ji in G. This means that for every h ∈ Bij
/ E or
xx
{h, j} ∈
/ E. By Observation 4.1 (2) it follows that either Bij \ {i, j} ⊆ Vjj or
xx \ {i, j} ⊆ V
Bij
ii .
In the former case notice that both j and x in G[Vjj ∪ {i, j, x}] are adjacent only
to i. Thus no subset of Vjj ∪ {i, j, x} that contains j or x induces an S-cycle of
xx = B ii
G so that Bij
jj ∪ {i, j} as described.
xx \ {i, j} ⊆ V
xx
In the latter case we have Bij
ii . Let h ∈ Bij \ {i, j}. We show that
{h, x} ∈
/ E. Assume for contradiction that {h, x} ∈ E. This means that either
h <t x and x <b h, or x <t h and h <b x. Observe that h <t j and h <b i. Since
j <b < x <b i and i <t < j <t x, we get the following:

15

∗ h <t i <t j <t x and
∗ j <b x <b h <b i.

Thus {h, j} ∈ E. This however shows that hh, j, i, xi is an induced S-square in G,
xx \ {i, j}. Then by
leading to a contradiction. Thus {h, x} ∈
/ E for every h ∈ Bij
xx
Observation 4.1 (3) it follows that Bij \ {i, j} ⊆ Vix . This means that i and x
are only adjacent to j in G[Vix ∪{i, j, x}]. Hence no subset of Vix ∪{i, j, x} that
xx = B jj ∪ {i, j} as described.
contains i or x induces an S-cycle in G, so that Bij
ix

xx \ {i, j}. We show that {h, x} ∈
– Let i, j ∈
/ S and x ∈ S. Let h ∈ Bij
/ E. Assume
for contradiction that {h, x} ∈ E. Then either h <t x and x <b h hold, or x <t h
and h <b x hold. Since {i, x} ∈ E, {j, x} ∈
/ E, and ij is a crossing pair, we have

∗ {h, i} <t j <t x and
∗ j <b x <b h <b i

implying that {h, j} ∈ E. If {h, i} ∈ E then hh, i, ji is an induced S-triangle
whereas if {h, i} ∈
/ E then hh, j, i, xi is an induced S-square. Thus we reach a
xx =
contradiction so that {h, x} ∈
/ E. Then by Observation 4.1 (5) we get Bij
ij
B<ijxx
∪ {i, j}, as described.
0 0

0 0

x y ,z z
xx \ {i, j} ⊆ V
xx
– Let i, j, x ∈
/ S. By the fact Bij
∪ {i, j}.
<ij , we have Bij = B<ij

• Assume that {i, x} ∈
/ E and {j, x} ∈ E. This case is symmetric to the one above, so
that the following hold:
jj
xx = B ii
xx
– If i ∈ S or j ∈ S then either Bij
xj ∪ {i, j} or Bij = Bii ∪ {i, j}.

xx = B ij
– If x ∈ S then Bij
<ijxx ∪ {i, j}.
0 0

0 0

xx = B x y ,z z .
– If i, j, x ∈
/ S then Bij
<ij

• Assume that both {i, x}, {j, x} ∈ E. Then no vertex of {i, x, y} can belong to S
xx \ {i, j} ⊆ V
xx
as hi, j, xi is an induced triangle in G. Since Bij
<ij , we get Bij =
0 0

0 0

x y ,z z
B<ij
∪ {i, j}.

Therefore every case results in the described statement of the formulas as required.
Let ij, xy ∈ X \ I such that j <t y and i <b x. It is not difficult to see that if we remove
any crossing pair uv from {i, j, x, y} then the remaining set contains exactly two vertices
that are adjacent.
Lemma 4.14. Let ij, xy ∈ X \ I such that j <t y, i <b x and x, y ∈
/ S. Moreover let x0 y 0 be
the leftmost crossing pair of {i, j, x, y} and let z 0 w0 be the crossing pair of {i, j, x, y} \ {x0 , y 0 }.
xy
xx .
1. If {i, y} ∈
/ E then Bij
= Bij
xy
yy
2. If {j, x} ∈
/ E then Bij
= Bij
.

3. If {i, y}, {j, x} ∈ E then

n
o
 maxw B xy , B xy ,
if i ∈ S or j ∈ S
xy
n 0ij 6ij
o
Bij
=
0
0
0
0
 maxw B xy , B xy , C x y ,z w ∪ {i, j} , if i, j ∈
/ S.
0ij
6ij
<ij
Proof. Assume that {i, y} ∈
/ E. Then i <b y since i <t x <t y. Thus
• i <t j, {j, x} <t y, and
16

• j <b i <b y <b x,
so that the neighborhood of y in G[Vij ∪ {x, y}] is {x}. Thus no subset of Vij ∪ {x, y} that
xy
xx as described. If {j, x} ∈
contains y induces an S-cycle in G. Therefore Bij
= Bij
/ E then i
xy
yy
is non-adjacent to x and similar to the previous case we obtain Bij
= Bij
.
Assume that {i, y}, {j, x} ∈ E. We distinguish cases depending on whether i or j belong
xy
xy
to the solution. Assume first that at least one of i or j does not belong to Bij
. Let j ∈
/ Bij
.
xy
xy
xy
By Observation 4.1 (1) we have Bij = B0ij . If i ∈
/ Bij then in a similar fashion we get
xy
xy
Bij
= B6ij
.
xy
xy
Next assume that i, j ∈ Bij
. Notice that by Observation 4.1 (1), we have Bij
\ {i, j} ⊆
V<ij . Let us show that both i and j do not belong to S. If {i, x} ∈ E or {j, y} ∈ E then
hi, x, yi or hj, x, yi induce a triangle in G, since {i, y}, {j, x} ∈ E. Otherwise, {i, x}, {j, y} ∈
/
E, so that hi, j, x, yi is an induced square in G. Thus in any case there is an S-cycle in G
xy
whenever i ∈ S or j ∈ S which lead to a contradiction to the fact i, j ∈ Bij
. Hence i, j ∈
/ S.
0 0

0

0

xy
xy
x y ,z w
Since Bij
\ {i, j} ⊆ V<ij , it follows Bij
= C<ij
∪ {i, j} as required.

With the following two lemmas we consider the last two cases that correspond to the sets
xy,zz
xy,zw
Cij
and Cij
, respectively.
Lemma 4.15. Let ij, xy ∈ X \ I and let z ∈ V \ Vij such that xy <` zz, at least one of x, y
is adjacent to z, j <t y, i <b x, and x, y, z ∈
/ S. Moreover let x0 y 0 be the leftmost crossing
pair of {i, j, x, y, z} and let z 0 w0 be the leftmost crossing pair of {i, j, x, y, z} \ {x0 , y 0 }.
xy,zz
xy
1. If {i, z}, {j, z} ∈
/ E then Cij
= Bij
.

2. If {i, z} ∈ E or {j, z} ∈ E then

n
o
 maxw C xy,zz , C xy,zz ,
if i ∈ S or j ∈ S
6ij
xy,zz
n 0ij
o
Cij
=
0
0
0
0
 maxw C xy,zz , C xy,zz , C x y ,z w ∪ {i, j} , if i, j ∈
/ S.
0ij
6ij
<ij
Proof. Assume first that {i, z}, {j, z} ∈
/ E. Then i <t j, {j, x} <t {y, z}, {i, y} <b {x, z},
and j <b i. This means that the neighborhood of z in G[Vij ∪ {x, y, z}] is a subset of {x, y}.
We will show that no subset of Vij ∪ {x, y, z} that contains z induces an S-cycle of G.
• Let hv1 , v2 , zi be an induced S-triangle such that v1 , v2 ∈ Vij ∪ {x, y}. Then {v1 , v2 } =
{x, y} which leads to a contradiction, because x, y, z ∈
/ S.
• Let hv1 , v2 , v3 , zi be an induced S-square such that v1 , v2 , v3 ∈ Vij ∪ {x, y}. Then
{v1 , v3 } = {x, y} which leads to a contradiction, because {x, y} ∈ E.
xy,zz
Thus no subset of Vij ∪ {x, y, z} that contains z induces an S-cycle of G. Therefore Cij
=
xy
Bij holds.
Assume that {i, z} ∈ E or {j, z} ∈ E. We distinguish cases depending on whether i
xy,zz
xy,zz
xy,zz
or j belong to Cij
. If j ∈
/ Cij
or i ∈
/ Cij
then by Observation 4.1 (1) we get
xy,zz
xy,zz
xy,zz
xy,zz
xy,zz
Cij
= C0ij
or Cij
= C6ij
, respectively. The remaining case is i, j ∈ Cij
. Here
we will show the described formula given in the second statement. By Observation 4.1 (3),
xy,zz
notice that Cij
\ {i, j} ⊆ V<ij .

Case 1: Assume that i ∈ S or j ∈ S. We will show that there is an S-cycle that contains i or
xy,zz
j leading to a contradiction to the assumption i, j ∈ Cij
. Let us assume that {i, z} ∈ E;
the case for {j, z} ∈ E is completely symmetric. Thus i <t z and z <b i hold or z <t i and
i <b z hold. Moreover we know that x <t z and y <b z because xy <` zz. Since ij, xy are
crossing pairs and i <t j <t y, i <b x, exactly one of the following holds:
17

• x <t z <t < i <t y and {i, y} <b {x, z};
• {i, x} <t {y, z} and y <b z <b i <b x.
If the former inequalities hold then it is not difficult to see that {i, x}, {y, z} ∈ E. And if
the latter inequalities hold then {i, y}, {x, z} ∈ E. Suppose that {i, x}, {y, z} ∈ E.
• If {i, y} ∈ E then hi, x, yi is an induced S-triangle.
• If {x, z} ∈ E then hi, x, zi is an induced S-triangle.
• If {i, y}, {x, z} ∈
/ E then hi, x, y, zi is an induced S-square.
Next suppose that {i, y}, {x, z} ∈ E.
• If {i, x} ∈ E then hi, x, yi is an induced S-triangle.
• If {y, z} ∈ E then hi, y, zi is an induced S-triangle.
• If {i, x}, {y, z} ∈
/ E then hi, y, x, zi is an induced S-square.
xy,zz
xy,zz
xy,zz
Therefore if i ∈ S or j ∈ S then i, j ∈
/ Cij
so that Cij
can be expressed as C0ij
or
xy,zz
C6ij
, as already explained previously.

Case 2: Assume that i, j ∈
/ S. Let a0 be the vertex of {i, j, x, y, z} \ {x0 , y 0 , z 0 , w0 }. Observe
0
that a ∈
/ S since S ∩ {i, j, x, y, z} = ∅. We will show that if a subset of V<ij ∪ {x0 , y 0 , z 0 , w0 , a0 }
that contains a0 induces an S-cycle of G, then its non-empty intersection with V<ij is not a
x0 y 0 ,z 0 w0
subset of C<ij
. Assume for contradiction that a subset of vertices of an induced S-cycle
0 0

0

0

x y ,z w
that contains a0 belongs to C<ij
. Since the only induced cycles in a permutation graph
are triangles or squares we assume that a0 is contained in an S-triangle or an S-square.

• Let hv1 , v2 , a0 i be an induced S-triangle such that v1 , v2 ∈ V<ij ∪ {x0 , y 0 , z 0 , w0 }. Since
x0 , y 0 , z 0 , w 0 ∈
/ S, without loss of generality, assume that v1 ∈ S which implies that
v1 ∈ V<ij . This means that v1 <t j ≤t y 0 and v1 <b i ≤b x0 . By the choices of x0 y 0 ,
z 0 w0 , and a0 we know that x0 <t z 0 <t a0 and y 0 <b w0 <b a0 . Since {v1 , a0 } ∈ E, a0 <t v1
and v1 <b a0 hold or v1 <t a0 and a0 <b v1 hold. Thus exactly one of the following
holds:
– x0 <t z 0 <t < a0 <t v1 <t y 0 and {v1 , y 0 } <b {x0 , z 0 , a0 };

– {v1 , x0 } <t {y 0 , w0 , a0 } and y 0 <b w0 <b < a0 <b v1 <b x0 .

If the former inequalities hold then it is not difficult to see that {v1 , x0 }, {v1 , z 0 } ∈
E. And if the latter inequalities hold then {v1 , y 0 }, {v1 , w0 } ∈ E. Suppose that
{v1 , x0 }, {v1 , z 0 } ∈ E.
– If {v1 , y 0 } ∈ E then hv1 , x0 , y 0 i is an induced S-triangle.
– If {x0 , z 0 } ∈ E then hv1 , x0 , z 0 i is an induced S-triangle.

– If {v1 , y 0 }, {x0 , z 0 } ∈
/ E then hv1 , x0 , y 0 , z 0 i is induced an S-square.

Next suppose that {v1 , y 0 }, {v1 , w0 } ∈ E.
– If {v1 , x0 } ∈ E then hv1 , x0 , y 0 i is an induced S-triangle.

– If {y 0 , w0 } ∈ E then hv1 , y 0 , w0 i is an induced S-triangle.

– If {v1 , x0 }, {y 0 , w0 } ∈
/ E then hv1 , y 0 , x0 , w0 i is induced an S-square.
18

0 0

0

0

x y ,z w
Therefore in all cases we obtain that v1 ∈
/ C<ij
.

• Let hv1 , v2 , v3 , a0 i be an induced S-square such that v1 , v2 , v3 ∈ V<ij ∪ {x0 , y 0 , z 0 , w0 }.
If v1 ∈ S or v3 ∈ S then by the previous argument the S-vertex is not an element of
x0 y 0 ,z 0 w0
C<ij
. So assume that v2 ∈ S. Since x0 , y 0 , z 0 , w0 ∈
/ S, we have v2 ∈ V<ij , so that
v2 <t j ≤t y 0 and v2 <b i ≤b x0 . By the choices of x0 y 0 and a0 we know that x0 <t a0
and y 0 <b a0 . Moreover the induced S-square imply that either {v2 , a0 } <t {v1 , v3 }
and {v1 , v3 } <b {v2 , a0 } hold or {v1 , v3 } <t {v2 , a0 } and {v2 , a0 } <b {v1 , v3 } hold. Thus
exactly one of the following holds:
– {v2 , x0 } <t a0 <t {v1 , v3 } and {v1 , v3 } <b v2 <b {x0 , a0 };
– {v1 , v3 } <t v2 <t {y 0 , a0 } and {v2 , y 0 } <b a0 <b {v1 , v3 }.

The first inequalities imply that {v1 , x0 }, {v3 , x0 } ∈ E whereas the second inequalities
imply that {v1 , y 0 }, {v3 , y 0 } ∈ E. Suppose that {v1 , x0 }, {v3 , x0 } ∈ E.
– If {v2 , x0 } ∈ E then hv1 , v2 , x0 i is an induced S-triangle.

– If {v2 , x0 } ∈
/ E then hv1 , v2 , v3 , x0 i is an induced S-square.

Similarly if {v1 , y 0 }, {v3 , y 0 } ∈ E then we obtain an S-triangle hv1 , v2 , x0 i or an S-square
x0 y 0 ,z 0 w0
hv1 , v2 , v3 , x0 i. Thus {v1 , v2 , v3 } ∩ V<ij is not a subset of C<ij
.
Therefore if a subset of V<ij ∪ {x0 , y 0 , z 0 , w0 , a0 } that contains a0 induces an S-cycle then its
x0 y 0 ,z 0 w0
non-empty intersection with V<ij is not a subset of C<ij
. This particularly implies that
0 0

0

0

xy,zz
x y ,z w
Cij
= C<ij
∪ {i, j} as described in the second statement.
xy,zw
The next lemma shows how to recursively compute Cij
. Note that in each case we
xy,zw
describe Cij
as a predefined smaller set of a subsolution that is either in the same form
or has already been described in one of the previous lemmas.

Lemma 4.16. Let ij, xy, zw ∈ X \I such that xy <` zw, {x, w}, {y, z} ∈ E, j <t {y, w}, i <b
{x, z}, and x, y, z, w ∈
/ S. Moreover let x0 y 0 be the leftmost crossing pair of {i, j, x, y, z, w}
and let z 0 w0 be the leftmost crossing pair of {i, j, x, y, z, w} \ {x0 , y 0 }.
xy,zw
xy,zz
1. If {i, w} ∈
/ E then Cij
= Cij
.
xy,zw
xy,ww
2. If {j, z} ∈
/ E then Cij
= Cij
.

3. If {i, w}, {j, z} ∈ E then

n
o
 maxw C xy,zw , C xy,zw ,
if i ∈ S or j ∈ S
0ij
6ij
xy,zw
n
o
Cij
=
0 y 0 ,z 0 w 0
xy,zw
xy,zw
x
 maxw C
∪ {i, j} , if i, j ∈
/ S.
0ij , C6ij , C<ij
Proof. Assume first that {i, w} ∈
/ E. Then i <t w and i <b w hold, since i <t j <t w. Thus
the following hold, as ij, xy, zw are crossing pairs:
• i <t j <t {y, w}, x <t {y, z}, z <t w,
• j <b i <b w <b z, and {i, y} <b {x, w}.
Then the neighborhood of w in G[Vij ∪ {x, y, z, w}] is a subset of {x, y, z}. We will show
that if a subset of Vij ∪ {x, y, z, w} that contains w induces an S-cycle then its non-empty
xy,zz
intersection with Vij is not a subset of Cij
. Since an S-cycle in G is only an S-triangle or
an S-square, we distinguish the following two cases:
19

• Let hv1 , v2 , wi be an induced S-triangle such that v1 , v2 ∈ Vij ∪{x, y, z}. Then {v1 , v2 } ⊂
{x, y, z} since N (w) ⊆ {x, y, z}, which leads to a contradiction, because x, y, z, w ∈
/ S.
• Let hv1 , v2 , v3 , wi be an induced S-square such that v1 , v2 , v3 ∈ Vij ∪ {x, y, z}. Then
{v1 , v3 } ⊂ {x, y, z}. Since x, y, z, w ∈
/ S, we have v2 ∈ S so that v2 ∈ Vij .
– Assume that {v1 , v3 } = {x, y} or {y, z}. Then we reach a contradiction because
{x, y}, {y, z} ∈ E.
– Assume that {v1 , v3 } = {x, z}. Then it is clear that {x, z} ∈
/ E. This however
xy,zz
shows that hx, v2 , z, yi is an induced S-square, so that v2 ∈
/ Cij
.

Therefore, if a subset of Vij ∪ {x, y, z, w} that contains w induces an S-cycle then its nonxy,zz
xy,zw
xy,zz
empty intersection with Vij is not a subset of Cij
. Thus Cij
= Cij
holds.
If we assume that {j, z} ∈
/ E then similar arguments with the previous case for {i, w} ∈
/E
xy,zw
xy,ww
show that Cij
= Cij
.
xy,zw
Our remaining case is {i, w}, {j, z} ∈ E. If j ∈
/ Cij
then by Observation 4.1 (1) we get
xy,zw
xy,zw
xy,zw
xy,zw
xy,zw
Cij
= C0ij . Similarly if i ∈
/ Cij
then Cij
= C6ij
. So let us assume that both
xy,zw
xy,zw
i, j belong to the solution Cij
, that is i, j ∈ Cij
. Notice that by Observation 4.1 (1)
xy,zw
we know that Cij
\ {i, j} ⊆ V<ij . We distinguish two cases depending on whether i, j
belong to S. If i ∈ S or j ∈ S then the following induced S-cycles show that we reach a
xy,zw
contradiction to i, j ∈ Cij
:
• If {i, z} ∈ E then hi, j, zi is an induced S-triangle.
• If {j, w} ∈ E then hi, j, wi is an induced S-triangle.
• If {i, z}, {j, w} ∈
/ E, then hi, j, z, wi is an induced S-square.
xy,zw
xy,zw
Thus if i ∈ S or j ∈ S then we know that j ∈
/ Cij
or i ∈
/ Cij
which shows the first
xy,zw
description of Cij
in the third statement.
xy,zw
Let i, j ∈
/ S and recall that i, j ∈ Cij
and {i, w}, {j, z} ∈ E. Observe that the set
{i, j, x, y, z, w} \ {x0 , y 0 , z 0 , w0 } contains two adjacent vertices. Let a0 b0 be the crossing pair
of {i, j, x, y, z, w} \ {x0 , y 0 , z 0 , w0 } so that a0 <t b0 and b0 <b a0 . We will show that if a subset
of V<ij ∪ {x0 , y 0 , z 0 , w0 , a0 , b0 } that contains a0 or b0 induces an S-cycle then its non-empty
x0 y 0 ,z 0 w0
intersection with V<ij is not a subset of C<ij
. Such an S-cycle is either an S-triangle or
an S-square.

• Let hv1 , v2 , b0 i be an induced S-triangle such that v1 , v2 ∈ V<ij ∪ {x0 , y 0 , z 0 , w0 , a0 }. Since
x0 , y 0 , z 0 , w0 , a0 , b0 ∈
/ S, without loss of generality, assume that v1 ∈ S so that v1 ∈ V<ij .
x0 y 0 ,z 0 w0
Then v1 <t j <t {y, w} and v1 <b i <b {x, z}. Our goal is to show that v1 ∈
/ C<ij
.
Since {v1 , b0 } ∈ E and x0 <t a0 <t b0 , we get v1 <t b0 and b0 <b v1 . Also notice that
x0 y 0 <` z 0 w0 <` a0 b0 so that y 0 <b w0 <b b0 . Thus the following hold:
– {v1 , x0 } <t {y 0 , w0 , b0 } and
– y 0 <b w0 <b b0 <b {v1 , x0 }.

This shows that {v1 , y 0 }, {v1 , w0 } ∈ E. With these facts we obtain the following S-cycles
x0 y 0 ,z 0 w0
so that v1 ∈
/ C<ij
:
– If {v1 , x0 } ∈ E then hv1 , x0 , y 0 i is an induced S-triangle.

– If {y 0 , w0 } ∈ E then hv1 , y 0 , w0 i is an induced S-triangle.

– If {v1 , x0 }, {y 0 , w0 } ∈
/ E then hv1 , y 0 , x0 , w0 i is an induced S-square.

20

• Let hv1 , v2 , v3 , b0 i be an S-square such that v1 , v2 , v3 ∈ V<ij ∪ {x0 , y 0 , z 0 , w0 , a0 }. If v1 ∈ S
or v3 ∈ S then similar to the previous argument we can show that the S-vertex does
x0 y 0 ,z 0 w0
not belong to C<ij
. Assume that v2 ∈ S. Since x0 , y 0 , z 0 , w0 , a0 , b0 ∈
/ S, v2 ∈ V<ij .
Thus v2 <t j <t {y, w} and v2 <b i <b {x, z} which mean that v2 <t {y 0 , w0 , b0 } and
v2 <b {x0 , z 0 , a0 }. Moreover x0 y 0 <` z 0 w0 <` a0 b0 imply x0 <t z 0 <t a0 and y 0 <b w0 <b b0 .
By the given S-square we have {v1 , v3 } <t {v2 , b0 } and {v2 , b0 } <b {v1 , v3 }. Since
{v2 , b0 } ∈
/ E, we also have v2 <t b0 and v2 <b b0 . Then the following hold:
– {v1 , v3 } <t v2 <t {y 0 , b0 } and
– {v2 , y 0 } <b b0 <b {v1 , v3 }.

0 0

0

0

x y ,z w
Thus {v1 , y 0 }, {v3 , y 0 } ∈ E. Now the following S-cycles show that v2 ∈
/ C<ij
.

– If {v2 , y 0 } ∈ E then hv1 , v2 , y 0 i is an induced S-triangle.

– If {v2 , y 0 } ∈
/ E then hv1 , v2 , v3 , y 0 i is an induced S-square.
• Following the same lines as above we can show that if a subset of V<ij ∪{x0 , y 0 , z 0 , w0 , a0 , b0 }
that contains a0 induces an S-cycle of G then its non-empty intersection with V<ij is
x0 y 0 ,z 0 w0
not a subset of C<ij
.
Therefore, if a subset of V<ij ∪ {x0 , y 0 , z 0 , w0 , a0 , b0 } that contains a0 or b0 induces an S-cycle
x0 y 0 ,z 0 w0
then its non-empty intersection with V<ij is not a subset of C<ij
. By this fact it follows
0 0

0

0

xy,zw
x y ,z w
that Cij
= C<ij
∪ {i, j} as described in the third statement.

It is important to notice that all described formulations are given recursively based on
Lemmas 4.7–4.16. Now we are in position to state our claimed polynomial-time algorithm
for the SFVS problem on permutation graphs.
Theorem 4.17. Subset Feedback Vertex Set can be solved in O(m3 ) time on permutation graphs.
Proof. Let us describe such an algorithm. Given the permutation diagram, that is the
ordering <t and <b on V , we first compute all crossing pairs ij of X . Observe that the number
of such pairs is n+m. For each crossing pair ij we compute its predecessors {0, 6, <, , <}
according to the corresponding definition. Note that such a simple application requires O(n2 )
time for every crossing pair ij, giving a total running time of O(n2 m). Next we scan all
crossing pairs of X according to their ascending order with respect to <r . For every crossing
pair ij we compute Aij according to Lemmas 4.7 and 4.12. That is, for every crossing pair xy
xy
of V \ Vij in descending order with respect to <` we compute Bij
according to Lemmas 4.8,
xy
4.9, 4.13, and 4.14. By the recursive formulations of Bij , for every crossing pair zw of V \Vxy
xy,zw
in descending order with respect to <` we compute Cij
according to Lemmas 4.10, 4.11,
3
4.15, and 4.16. In total all such computations require O(m ) time. At the end the set Aπ(n)n
is the maximum weighted S-forest for G so that V \ Aπ(n)n is exactly the subset feedback
vertex set of G.

5

Concluding remarks

In accordance to Theorem 3.9 that uses the algorithm for interval graphs, we believe that our
algorithm for permutation graphs can be suitably applied for the class of circular permutation
graphs (the class of circular permutation graphs generalizes permutation graphs analogous
to that of circular-arc graphs with respect to interval graphs [6, 19]). From the complexity

21

point of view, since FVS is polynomial-time solvable on the class of AT-free graphs [21], a
natural problem is to settle the complexity of SFVS on AT-free graphs. Interestingly most
problems that are hard on AT-free graphs are already hard on co-bipartite graphs (see for
e.g., [25]). Co-bipartite graphs are the complements of bipartite graphs and are unrelated
to permutation graphs or interval graphs. Here we show that SFVS admits a simple and
efficient (polynomial-time) solution on co-bipartite graphs and therefore excluding such an
approach through a hardness result on co-bipartite graphs.
Theorem 5.1. The number of maximal S-forests of a co-bipartite graph is at most 22n4 and
these can be enumerated in time O(n4 ).
Proof. Let G = (V, E) be a co-bipartite graph and let (A, B) be a partition of V such that
such that G[A] and G[B] are cliques. We further partition V as (AS , AR , BS , BR ) where
AS = A ∩ S, AR = A \ S, BS = B ∩ S and BR = B \ S. For a vertex v of G and a
set U ∈ {AS , BS , AR , BR } we denote by NU (v) the neighbours of v in the set U , that is,
NU (v) =def N (v) ∩ U . Moreover the symmetric difference of two sets L and R is the set
(L \ R) ∪ (R \ L) and is denoted by L M R. Let (X, Y, Z, W ) be the partition of the vertex
set of a maximal S-forest of G such that X ⊆ AS , Y ⊆ AR , Z ⊆ BS and W ⊆ BR . It is clear
that |X| ≤ 2 and |Z| ≤ 2. Thus it is sufficient to consider the following cases with respect
to X and Z:
• Let X = ∅ and Z = ∅. Then the maximal S-forest contains no vertex of S, so we can
safely include all vertices of V \ S. Thus the following set is a maximal S-forest of G:
1. (∅, AR , ∅, BR ).

• Let X = {aS } and Z = ∅. Observe that |Y | ≤ 1, since G[X ∪ Y ] is a clique. If Y = ∅
then including at least two neighbours of aS that are contained in BR leads to an Scycle. Thus we can safely include all non-neighbours of aS and exactly one neighbour
of aS contained in BR in the maximal S-forest. If Y = {aR } then including a neighbour
of aS and a neighbour of aR (may well be the same) that are contained in BR leads
to an S-cycle. If we do not include a neighbour of aS then we can safely include all
other vertices of BR . However if we include a neighbour of aS that is non-adjacent to
aR then we can safely include all other vertices that are non-adjacent to both. Thus
the following sets induce the corresponding maximal S-forests of G:
2. ({aS }, ∅, ∅, BR ), where NBR (aS ) = ∅;

3. ({aS }, ∅, ∅, {bR } ∪ (BR \ N (aS ))), where bR ∈ NBR (aS );
4. ({aS }, {aR }, ∅, BR \ N (aS ));

5. ({aS }, {aR }, ∅, {bR } ∪ (BR \ N ({aS , aR }))), where bR ∈ NBR (aS ) \ NBR (aR ).

• Let X = ∅ and Z = {bS }. Completely symmetric arguments with the previous case
imply that the following sets induce the corresponding maximal S-forests of G:
6. (∅, AR , {bS }, ∅), where NAR (bS ) = ∅;

7. (∅, {aR } ∪ (AR \ N (bS )) , {bS }, ∅), where aR ∈ NAR (bS );

8. (∅, AR \ N (bS ), {bS }, {bR });

9. (∅, {aR } ∪ (AR \ N ({bS , bR })) , {bS }, {bR }), where aR ∈ NAR (bS ) \ NAR (bR ).

• Let X = {aS } and Z = {bS }. Then both |Y | ≤ 1 and |W | ≤ 1. Thus the following sets
induce the maximal S-forest of G:
10. ({aS }, ∅, {bS }, ∅), where {aS , bS } ∈ E and V \ S ⊆ N (aS ) ∩ N (bS );

11. ({aS }, {aR }, {bS }, ∅), where G[{aS , aR , bS }] is acyclic and BR ⊆ N (aS ) ∪ N (aR );
12. ({aS }, ∅, {bS }, {bR }), where G[{aS , bS , bR }] is acyclic and AR ⊆ N (bS ) ∪ N (bR );
22

13. ({aS }, {aR }, {bS }, {bR }), where G[{aS , aR , bS , bR }] is acyclic.

• Let X = {aS , a0S } and Z = ∅. Then |Y | = 0, since G[X ∪ Y ] is a clique. Adding a
vertex of BR that is adjacent to both aS and a0S leads to an S-cycle. If we add a vertex
of BR that is adjacent to either aS or a0S then adding another such vertex leads to an
S-cycle. Thus we can safely include all other vertices that are non-adjacent to either
aS or a0S .
14. ({aS , a0S }, ∅, ∅, BR \ (N (aS ) ∩ N (a0S ))), where NBR (aS ) M NBR (a0S ) = ∅;

15. ({aS , a0S }, ∅, ∅, {bR } ∪ (BR \ N ({aS , a0S }))), where bR ∈ NBR (aS ) M NBR (a0S ).

• Let X = ∅ and Z = {bS , b0S }. Completely symmetric arguments with the previous case
imply that the following sets induce the corresponding maximal S-forest of G:
16. (∅, AR \ (N (bS ) ∩ N (b0S )), {bS , b0S }, ∅), where NAR (bS ) M NAR (b0S ) = ∅;

17. (∅, {aR } ∪ (AR \ (N (bS ) ∪ N (b0S ))) , {bS , b0S }, ∅), where aR ∈ NAR (bS ) M NAR (b0S ).

• Let X = {aS , a0S } and Z = {bS }. Then |Y | = 0 and |W | ≤ 1. Thus the following sets
induce the maximal S-forest of G:
18. ({aS , a0S }, ∅, {bS }, ∅), where G[{aS , a0S , bS }] is acyclic;

19. ({aS , a0S }, ∅, {bS }, {bR }), where G[{aS , a0S , bS , bR }] is acyclic.

• Let X = {aS } and Z = {bS , b0S }. Then similarly to the previous case we obtain the
following:
20. ({aS }, ∅, {bS , b0S }, ∅), where G[{aS , bS , b0S }] is acyclic.

21. ({aS }, {aR }, {bS , b0S }, ∅), where G[{aS , bS , b0S , a}] is acyclic.

• Let X = {aS , a0S } and Z = {bS , b0S }. Then |Y | = 0 and |W | = 0 so that the following
set induces such a maximal S-forest:
22. ({aS , a0S }, ∅, {bS , b0S }, ∅), where G[{aS , a0S , bS , b0S }] is acyclic.

Because |X|, |Y |, |Z|, |W | ≤ n, each described maximal S-forest gives at most n4 maximal Sforests. Therefore in total there are at most 22n4 maximal S-forests that correspond to each
particular case. Taking into account that any maximal S-forest has at most n vertices, these
arguments can be applied to obtain an enumeration algorithm that runs in time O(n4 ).
We strongly believe that such an approach towards AT-free graphs should deal first with
the complexity of the unweighted version of the SFVS. Concerning graph classes related to
bounded graph parameters, we would like to note that FVS is polynomial-time solvable on
bounded clique-width graphs [7]. The computational complexity for SFVS on such graphs,
or even on bounded linear clique-width graphs, has not been resolved yet and stimulates an
intriguing open question.
Another interesting open question is concerned with problems related to terminal-sets
such as the Multiway Cut problem in which we want to disconnect a given set of terminals
by removing vertices of minimum total weight. As already mentioned in the Introduction,
the Multiway Cut problem reduces to the Subset Feedback Vertex Set problem by
adding a vertex s with S = {s} that is adjacent to all terminals and whose weight is larger
than the sum of the weights of all vertices in the original graph [15]. Notice that through
such an approach in order to solve even the unweighted Multiway Cut problem one needs
to solve the weighted Subset Feedback Vertex Set problem. This actually implies that
Multiway Cut is polynomial-time solvable in permutation graphs and interval graphs by
using our algorithms for the SFVS problem. However polynomial-time algorithms for the
Multiway Cut problem were already known for permutation and interval graphs by a
more general terminal-set problem [20, 26]. Nevertheless it is still interesting to consider

23

the computational complexity of the unweighted Multiway Cut problem on subclasses of
AT-free graphs such as co-comparability graphs.

References
[1] R. Bar-Yehuda, D. Geiger, J. Naor, and R. M. Roth. Approximation algorithms for the
feedback vertex set problem with applications to constraint satisfaction and bayesian
inference. SIAM Journal on Computing, 27(4):942–959, 1998.
[2] A. Becker and D. Geiger. Optimization of pearl’s method of conditioning and greedy-like
approximation algorithms for the vertex feedback set problem. Artificial Intelligence,
83(1):167 – 188, 1996.
[3] A. Brandstädt. On improved time bounds for permutation graph problems. In Proceedings of WG 1992, pages 1–10, 1985.
[4] A. Brandstädt and D. Kratsch. On the restriction of some NP-complete graph problems
to permutation graphs. In Proceedings of FCT 1985, pages 53–62, 1985.
[5] A. Brandstädt and D. Kratsch. On domination problems for permutation and other
graphs. Theoretical Computer Science, 54(2):181 – 198, 1987.
[6] A. Brandstädt, V. B. Le, and J. Spinrad. Graph Classes: A Survey. Society for Industrial
and Applied Mathematics, 1999.
[7] B.-M. Bui-Xuan, O. Suchý, J. A. Telle, and M. Vatshelle. Feedback vertex set on graphs
of low clique-width. Eur. Journal of Combinatorics, 34(3):666–679, 2013.
[8] G. Calinescu. Multiway cut. In Encyclopedia of Algorithms. Springer, 2008.
[9] R. H. Chitnis, F. V. Fomin, D. Lokshtanov, P. Misra, M. S. Ramanujan, and S. Saurabh.
Faster exact algorithms for some terminal set problems. In Proceedings of IPEC 2013,
pages 150–162, 2013.
[10] D. G. Corneil and J. Fonlupt. The complexity of generalized clique covering. Discrete
Applied Mathematics, 22(2):109 – 118, 1988.
[11] M. Cygan, M. Pilipczuk, M. Pilipczuk, and J. O. Wojtaszczyk. Subset feedback vertex
set is fixed-parameter tractable. SIAM J. Discrete Math., 27(1):290–309, 2013.
[12] G. Even, J. Naor, and L. Zosin. An 8-approximation algorithm for the subset feedback
vertex set problem. SIAM J. Comput., 30(4):1231–1252, 2000.
[13] P. Festa, P. M. Pardalos, and M. G. C. Resende. Feedback set problems. In Encyclopedia
of Optimization, pages 1005–1016. Springer, 2009.
[14] F. V. Fomin, S. Gaspers, D. Lokshtanov, and S. Saurabh. Exact algorithms via monotone local search. In Proceedings of STOC 2016, pages 764–775, 2016.
[15] F. V. Fomin, P. Heggernes, D. Kratsch, C. Papadopoulos, and Y. Villanger. Enumerating
minimal subset feedback vertex sets. Algorithmica, 69(1):216–231, 2014.
[16] M. R. Garey and D. S. Johnson. Computers and Intractability. W. H. Freeman and Co.,
1978.

24

[17] N. Garg, V. V. Vazirani, and M. Yannakakis. Multiway cuts in node weighted graphs.
J. Algorithms, 50(1):49–61, 2004.
[18] P. A. Golovach, P. Heggernes, D. Kratsch, and R. Saei. Subset feedback vertex sets in
chordal graphs. J. Discrete Algorithms, 26:7–15, 2014.
[19] M. C. Golumbic. Algorithmic Graph Theory and Perfect Graphs. Annals of Discrete
Mathematics 57, Elsevier, 2004.
[20] J. Guo, F. Huffner, E. Kenar, R. Niedermeier, and J. Uhlmann. Complexity and exact
algorithms for vertex multicut in interval and bounded treewidth graphs. European
Journal of Operational Research, 186:542–553, 2008.
[21] D. Kratsch, H. Müller, and I. Todinca. Feedback vertex set on AT-free graphs. Discrete
Applied Mathematics, 156(10):1936–1947, 2008.
[22] Y. D. Liang. On the feedback vertex set problem in permutation graphs. Information
Processing Letters, 52(3):123 – 129, 1994.
[23] Y. D. Liang and M.-S. Chang. Minimum feedback vertex sets in cocomparability graphs
and convex bipartite graphs. Acta Informatica, 34(5):337–346, 1997.
[24] C. L. Lu and C. Y. Tang. A linear-time algorithm for the weighted feedback vertex
problem on interval graphs. Information Processing Letters, 61(2):107–111, 1997.
[25] C. Maw-Shang. Weighted domination of cocomparability graphs. Discrete Applied
Mathematics, 80(2):135 – 148, 1997.
[26] C. Papadopoulos. Restricted vertex multicut on permutation graphs. Discrete Applied
Mathematics, 160(12):1791–1797, 2012.
[27] J. P. Spinrad. Efficient Graph Representations. American Mathematical Society, Fields
Institute Monograph Series 19, 2003.
[28] M. Yannakakis. Node-deletion problems on bipartite graphs.
10(2):310–327, 1981.

25

SIAM J. Comput.,

