Journal of Computer and Communications
Vol.04 No.08(2016), Article ID:67722,9 pages
10.4236/jcc.2016.48003
An Algorithm for the Feedback Vertex Set Problem on a Normal Helly Circular-Arc Graph
Hirotoshi Honma, Yoko Nakajima, Atsushi Sasaki
Department of Creative Engineering, National Institute of Technology, Kushiro College, Kushiro, Japan
Copyright © 2016 by authors and Scientific Research Publishing Inc.
This work is licensed under the Creative Commons Attribution International License (CC BY).
http://creativecommons.org/licenses/by/4.0/
Received 25 April 2016; accepted 24 June 2016; published 27 June 2016
ABSTRACT
The feedback vertex set (FVS) problem is to find the set of vertices of minimum cardinality whose removal renders the graph acyclic. The FVS problem has applications in several areas such as combinatorial circuit design, synchronous systems, computer systems, and very-large-scale integration (VLSI) circuits. The FVS problem is known to be NP-hard for simple graphs, but polynomial-time algorithms have been found for special classes of graphs. The intersection graph of a collection of arcs on a circle is called a circular-arc graph. A normal Helly circular-arc graph is a proper subclass of the set of circular-arc graphs. In this paper, we present an algorithm that takes 
time to solve the FVS problem in a normal Helly circular-arc graph with n vertices and m edges.
Keywords:
Design and Analysis of Algorithms, Feedback Vertex Set, Normal Helly Circular-Arc Graphs, Intersection Graphs
1. Introduction
Let 
be a family of nonempty sets. A simple graph G is the intersection graph of 
if there exists a one-to-one correspondence between the vertices of G and the sets in
, such that two vertices in G are adjacent if and only if their corresponding sets have a nonempty intersection. If 
is a family of intervals on the real line, G is called an interval graph [1] . Furthermore, a graph G is called a circular-arc graph if it is the intersection graph of a collection of arcs on a circle [1] . Circular-arc graphs properly contain a class of interval graphs as a subclass. Circular-arc graphs have applications in areas such as genetics [2] , traffic control [1] , multidimensional scaling [3] , compiler design [4] , ring network modeling [5] . In recent years, circular-arc graphs have been investigated extensively from both theoretical and algorithmic perspectives [6] - [9] .
Let 
be a simple graph, where V is the set of vertices and E is the set of edges of G, with 
and
. Suppose that 
is a nonempty subset of V. The subgraph of G whose vertex set is 
and whose edge set is the set of those edges of G that have both vertices in 
is called the induced subgraph on 
and is denoted by 
[10] . A cycle with no repeated vertices is a simple cycle. In this paper, the term “cycle” denotes “simple cycle”. A feedback vertex set (FVS) consists of a subset 
such that each cycle in G contains at least one vertex in F. In other words, a subset 
is an FVS of G if the subgraph induced by 
is acyclic. The FVS problem is to find an FVS of minimum cardinality (MFVS) in G. The FVS problem has applications in several areas such as deadlock prevention in operating systems [11] , combinatorial circuit design [12] , VLSI circuits [13] , and information security [14] .
The FVS problem is known to be NP-hard for general graphs [15] and bipartite graphs [16] . In general, it is known that more efficient algorithms can be developed by restricting classes of graphs. For instance, interesting polynomial-time solutions for the FVS problem have been found for special classes of graphs, such as interval graphs [17] [18] , permutation graphs [19] , butterfly networks [20] , hypercubes [21] , star graphs [22] , diamond graphs [23] , and rotator graphs [24] . Saha and Pal presented an algorithm that took 
time for the FVS problem in interval graphs using maximal clique decomposition [18] . The algorithm obtains an MFVS in an interval graph by breaking all cycles for each maximal clique. Circular-arc graphs are a natural generalization of interval graphs. However, the algorithm presented by Saha and Pal [18] cannot be directly applied to circular-arc graphs because the number of maximal cliques in interval graphs is at most the number of vertices, whereas circular-arc graphs may have an exponential number of maximal cliques [25] . In this paper, we propose an algorithm that takes 
time for the FVS problem in a normal Helly circular-arc graph.
The remainder of this paper is organized as follows. We state the definitions and notations used throughout this paper in Section 2. Next, we present our algorithm for the FVS problem and analyze its complexity in Section 3. Finally, we summarize our findings in Section 4 and conclude the paper by briefly discussing the scope for future work.
2. Definitions and Notations
In this section, we provide the definitions and relevant notations used throughout the paper. These establish the basis of the algorithm presented in Section 3. We provide the definitions of a circular-arc model and its corresponding graph. Consider a unit circle C and a family 
of n arcs 
along the circumference of C. Each arc 
has two endpoints 
and 
where 
(resp.,
) is the last point encountered when traversing 
counterclockwise (resp., clockwise). Arc numbers 
are assigned to each arc in increasing order of their 
s, i.e., 
if
. The geometric representation described above is called a circular-arc model. A graph 
is called a circular-arc graph if there exists a family of arcs 
such that there is a one-to-one correspondence between vertex 
and 
such that an edge 
if and only if 
intersects with 
in the circular-arc model.
Normal and Helly circular-arc models (NHCM) are precisely those without three or less arcs covering the entire circle [26] . A graph that admits such a model is called a normal Helly circular-arc graph (NHCG). Examples of an NHCM and its corresponding graph are shown in Figure 1. For an NHCM consisting of n arcs, an arc 
with 
and 
is called a back-arc. The set of all back-arcs is called the back-arc set and is denoted by BA. For CM, shown in Figure 1(a), we have a back-arc set 
by
.
A maximal clique is a clique to which no further vertices of a graph can be added such that it remains a clique. For the graph 
of Figure 1, the maximal cliques, the vertices of which are put in ascending order, are
, 
, 
, 
, 
, 
, 
, 
, and
. The cardinality 
of 
for this graph are
, 
, and
.
Let r be the number of maximal cliques of NHCG G. Throughout this paper, we use the term triangle to denote a cycle whose length is three. We define functions 
and 
as follows:
(a) (b)
Figure 1. Normal Helly circular-arc model 
and its corresponding graph
. (a) A normal Helly circular-arc model
; (b) A normal Helly circular-arc graph
.
(1)
(2)
Thus, 
is the total number of triangles including vertex i in G. For the sake of convenience, in the example shown in Figure 1, we denote the 
and 
value sequences of G by 
and
, respectively. For a simple graph
, 
is a feedback triangle-free vertex set (FTS) if 
has no triangle. In the example shown in Figure 1, 
or 
is a minimum cardinality FTS (MFTS) of G.
A chordal graph is a simple graph in which every cycle of length four or greater has a cycle chord. Interval graphs are a subclass of chordal graphs [18] . Hence, an MFTS is obviously an MFVS for interval graphs. On the other hand, NHCGs are a superclass of interval graphs and not a subclass of chordal graphs. They can have some chordless cycles of length greater than three. For example, the graph 
shown in Figure 1 has chordless cycles 
of length eight. If F is an MFTS and not an MFVS of an NHCG
, 
has a chordless cycle of length greater than three. A chordless cycle in 
is called a periphery. For example, in Figure 1, 
is an MFTS of
, and 
consists of a periphery
. Therefore, 
is not an MFVS, although F is an MFTS of
.
3. Algorithm and Its Correctness
In this section, we present an algorithm for solving the FVS problem for an NHCG. We will concisely describe the outline of our algorithm. First, we decompose a given NHCG into maximal cliques. An FTS is obtained by removing 
vertices from each maximal clique
. An MFTS is constructed by minimizing the number of removed vertices. At this point, if the constructed MFTS includes no periphery, it is an MFVS. Otherwise, we can obtain an MFVS by including a vertex for breaking the periphery in the MFTS.
Let 
be an NHCG corresponding to a model M. Algorithm 1 receives as an input the endpoints 
of each 
and back-arc set BA, and outputs an MFVS F of G.
We use the graph 
shown in Figure 1 as an example to illustrate Algorithm 1 step by step (the updated part is underlined).
Begin
(Step 1)
, 
, 
, 
, 
, 
, 
, 
, and
.
,
.
(Step 2)
,
.
1st iteration
(1-1)
, 
,
.
(1-2)
, 
,
.
(1-3)
, 
,
.
.
2nd iteration
(2-1)
, 
,
.
(2-2)
, 
,
.
.
3rd iteration
.
(3-1)
, 
,
.
(3-2)
, 
,
.
.
(Step 3)
has no periphery. Then,
.
End
In Step 1, all maximal cliques can be generated in 
time for an NHCG G with n vertices and m edges [27] . Moreover, we compute 
and 
for
. Step 2 constructs an MFTS by adding 
vertices to F for each maximal clique
. A graph obtained by deleting all but two vertices from each
, 
, has no triangle. In the example 
shown in Figure 1, we first select vertices “1” and “4” and add them to F because 
are the maximum values of all 
values. In the next step, for
, we select vertex “9” and add it to F because 
are maximum values and 
and
.
, which we obtained after executing Step 2 of Algorithm 1, is an MFTS of
. In Step 3, we check whether 
has a periphery or not. We obtain an MFVS 
because 
has no periphery.
Lemma 1. Let G be an NHCG. Following the execution of Step 2 of Algorithm 1, F is an MFTS of G.
Proof: Each triangle contained in G is a subset of any maximal clique 
in G. A graph obtained by deleting all but two vertices from each maximal clique 
has no triangle. Thus, a set F consisting of 
vertices of each 
is an FTS of G. It is obvious that the cardinality of F can be reduced by including vertices that appear in many triangles in G. 
is, by definition, the total number of triangles including vertex i in G. An MFTS can be obtained by selecting 
vertices in descending order of 
for each
.
In Step 2, initially, we set 
and
. Next, we compute 
and set
, i.e., vertex k is contained in the largest number of triangles, and 
is the set of maximal cliques containing k. Therefore, we break all triangles containing k in 
by priority to reduce the cardinality of F. Here, we assume that 
consists of m maximal cliques, i.e.
.
In (1-1) of Step 2, we select all vertices except two minima with 
values in 
and add them to F for
. Then, a subgraph 
has no triangle and F is clearly an MFTS of
. Because all triangles in 
are broken by removing vertices in F, 
values, 
, are updated to 
.
In (1-2) of Step 2, if
, no vertex is added to F. This implies that the elimination of vertices in F obtained in the previous step breaks all triangles of
. If
, we select 
vertices in decreasing order of 
in 
and add them to F. It is obvious that the cardinality of F can be reduced by adding vertices that appear in several triangles in F. Following this step, 
has no triangle and F is an MFTS of
. Moreover, 
values, 
, are updated to 
.
Similarly, in the next step (1-3), if
, we select 
vertices in decreasing order of 
in 
and add them to F. 
has no triangle, and F is an MFTS of
. Using a similar argument, following the execution of the m-th step, 
has no triangle, and F is an MFTS of
.
In the second iteration, we update 
to be 
and calculate
. As in the case of the first iteration, we select all vertices except two minima with 
values in 
and add them to F for each
. Step 2 of Algorithm 1 repeats the processes described above until 
becomes an empty set. The method described above thus constructs an MFTS F of the NHCG G.
Here, we explain how 
is used to find an MFTS in Step 2 of Algorithm 1. In the example shown in Figure 1, both vertex sets 
and 
are MFTSs of
. In general, not all MTFSs of an NHCG are its MFVSs. For example, a set 
is an MFVS of
; however, it is not an MFVS because a subgraph 
has a periphery
. We describe how Step 2 of Algorithm 1 constructs an MFTS F such that 
has no periphery, if possible.
In Step 2, we select 
vertices from 
to break all triangles in 
and add them to F. Consider the case where a maximal clique 
and a periphery have a vertex v in common. Clearly, a periphery is broken by removing a vertex v (“5” in Figure 2(a)). Such vertex v containing 
and a periphery in common must be included in some 
(
,
in Figure 2(a)). This implies that
. Moreover, there is no maximal clique 
containing vertices u (“2”, “3”, “4” in Figure 2(a)) except v in
. This is because it is clear from the corresponding model that if there exists a vertex x adjacent to u 
in
, G must have a triangle
.
Next, we consider the case of a maximal clique 
and a periphery have two vertices 
in common. It is obvious that a periphery is broken by removing either v or w (“2”, “5” in Figure 2(b)). In this case, for v and w, there exist maximal cliques 
(
and 
in Figure 2(b)) containing v and w, respectively. Moreover, we have no maximal clique 
containing vertex u, except v and w (“3”, “4” in Figure 2(b)) in
. This is because it is clear from the corresponding model that if there exists a vertex x adjacent to 
in
, G must have a triangle 
or
. Therefore, in Step 2, we select 
vertices in lexicographical order with respect to 
where 
if 
or
,
. By executing the method described above, Step 2 outputs an MFTS F such that an NHCG 
has neither a triangle nor a periphery, if possible.
Thus far, we have presented an example where an MFTS of an NHCG G is also its MFVS. However, there exist cases where an MFTS of G obtained by executing Step 2 of Algorithm 1 is not an MFVS of G. We describe the procedure to construct an MFTS of NHCG 
shown in Figure 3 by executing Step 3.
(a) (b)
Figure 2. A maximal clique and a periphery sharing vertices. (a) MC shares a vertex with a periphery; (b) MC shares two vertices with a periphery.
(a) (b)
Figure 3. Normal Helly circular-arc model M2 and its corresponding graph G2. (a) A normal Helly circular-arc model M2; (b) A normal Helly circular-arc graph G2.
Begin
(Step 1)
, 
, 
, 
, 
, 
, 
, 
, and
.
,
.
(Step 2)
,
.
1st iteration
(1-1)
, 
,
.
(1-2)
, 
,
.
(1-3)
, 
,
.
.
2nd iteration
(2-1)
, 
,
.
(2-2)
, 
,
.
(2-3)
, 
,
.
.
3rd iteration
(3-1)
, 
,
.
(3-2)
, 
,
.
.
(Step 3)
has a periphery
.
We have 
by
.
End
Following the execution of Step 2 of Algorithm 1, we obtain an MFTS 
of
. Removing all vertices in 
breaks all triangles in
. However, F is not an MFVS of 
because 
has a periphery
. The periphery remains unbroken because it does not contain any of
. In fact, there exists no MFVS of cardinality three in
. Hence, we can obtain an MFVS by adding a vertex for breaking the periphery to F if 
consists of a periphery. In Step 3, we include vertex ‘2’ in F by 
and
. We can obtain an MFVS 
of
.
The following lemmas guarantee the validity of Algorithm 1.
Lemma 2. Let G be a normal Helly circular-arc graph. If F is an MFTS and not an MFVS of G, a periphery in 
must contain one or two back-arcs.
Proof: As mentioned in Section 2, interval graphs are a subclass of NHCGs and have no periphery. An NHCM from which all back-arcs are removed is topologically equivalent to an interval model. Therefore, 
must contain at least one back-arc because it has a periphery.
does not contain three or more back-arcs. If 
has three back-arcs, these three back-arcs cover a point 
on the circumference of a circle C by the definition of a back-arc. This implies that 
contains a triangle. Thus, it contradicts the proposition that F is an MFTS of G.
Thus, if F is an MFTS and not an MFVS of
, 
has a periphery that must contain one or two back-arcs.
Lemma 3. Let G be a normal Helly circular-arc graph. Following the execution of Step 3 of Algorithm 1, F is an MFVS of G.
Proof: By Lemma 2, if 
consists of a periphery after executing Step 2, such a periphery must contain one or two back-arcs.
In the case where 
has a periphery and contains one back-arc
, we can break the periphery by removing 
(Figure 4(a)). Thus, we can obtain an MFVS by adding 
to F.
We consider the cases where 
has a periphery and contains two back-arcs
, 
(
). Because both back-arcs cover point 
by definition of back-arc, these two back-arcs must intersect. There are
(a) (b) (c)
Figure 4. Illustration of Lemma 3. (a)
; (b)
, (c)
.
two possible cases where 
contains two back-arcs. The first satisfies 
(Figure 4(b)), and the second satisfies 
(Figure 4(c)). For the former, the periphery is broken by removing
. For the latter, the periphery is broken by removing
. Therefore, we can break the periphery by removing a back-arc 
such that
.
Therefore, we can construct an MFVS after executing Step 3 of Algorithm 1.
In the following, we analyze the complexity of Algorithm 1. In Step 1, all maximal cliques of G are computed in 
time [27] . Moreover, 
and 
are computed for all
. Its complexity depends on the number of maximal cliques of G, which is at most the number of vertices of G. In Step 2, an MFTS F of G is constructed. This step requires as many iterations as the number of maximal cliques. Thus, this step is executed in 
time. In Step 3, we check whether 
consists of a periphery. If 
consists of a periphery, one vertex of 
is added to F. This step is executed in 
time. Thus, we have the following theorem.
Theorem 1. Algorithm 1 finds an MFVS of a normal Helly circular-arc graph G in 
time.
4. Concluding Remarks
In this paper, we proposed an algorithm that takes 
time to find an MFVS on an NHCG with n vertices and m edges. Our algorithm employs other algorithm to find maximal cliques [27] according to a method that can be understood intuitively. The complexity of our algorithm depends on the number of maximal cliques in an NHCG. Reducing the complexity of the algorithm and extending the results to other graphs are issues to be explored in future research.
Acknowledgements
We thank the Editor and the referee for their comments. This work was partially supported by JSPS KAKENHI Grant Number 25330019.
Cite this paper
Hirotoshi Honma,Yoko Nakajima,Atsushi Sasaki, (2016) An Algorithm for the Feedback Vertex Set Problem on a Normal Helly Circular-Arc Graph. Journal of Computer and Communications,04,23-31. doi: 10.4236/jcc.2016.48003
References
- 1. Golumbic, M.C. (2004) Algorithmic Graph Theory and Perfect Graphs. 2nd Edition, Vol. 57, Elsevier.
- 2. Stahl, F.W. (1967) Circular Genetic Maps. Journal of Cellular Physiology, 70, 1-12.
http://dx.doi.org/10.1002/jcp.1040700403 - 3. Hubert, L. (1974) Some Applications of Graph Theory and Related Non-Metric Techniques to Problems of Approximate Seriation: The Case of Symmetric Proximity Measures. British Journal of Mathematical and Statistical Psychology, 27, 133-153.
http://dx.doi.org/10.1111/j.2044-8317.1974.tb00534.x - 4. Tucker, A. (1975) Coloring a Family of Circular-Arcs. SIAM Journal on Applied Mathematics, 29, 493-502.
http://dx.doi.org/10.1137/0129040 - 5. Stefanakos, S. and Erlebach, T. (2004) Routing in All-Optical Ring Networks Revisited. Proc. 9th IEEE Symposium on Computers and Communication, 1, 288-293.
http://dx.doi.org/10.1109/iscc.2004.1358419 - 6. Lin, M.C., Soulignac, F.J. and Szwarcfiter, J.L. (2010) The Clique Operator on Circular-Arc Graphs. Discrete Applied Mathematics, 158, 1259-1267.
http://dx.doi.org/10.1016/j.dam.2009.01.019 - 7. Bhowmick, D. and Chandran, L.S. (2011) Boxicity of Circular Arc Graphs. Graphs and Combinatorics, 27, 769-783.
http://dx.doi.org/10.1007/s00373-010-1002-1 - 8. Kaplan, H. and Nussbaum, Y. (2011) A Simpler Linear-Time Recognition of Circular-Arc Graphs. Algorithmica, 61, 694-737.
http://dx.doi.org/10.1007/s00453-010-9432-y - 9. Cerioli, M.R. and Korenchendler, A.L. (2009) Clique-Coloring Circular-Arc Graphs. Electronic Notes in Discrete Mathematics, 35, 287-292.
http://dx.doi.org/10.1016/j.endm.2009.11.047 - 10. Jungnickel, D. (2000) Graphs, Networks and Algorithms. Springer.
- 11. Silberschatz, A., Galvin, P.B. and Gagne, G. (2003) Operating Systems Concepts. John Wiley and Sons, New York.
- 12. Johnson, D.B. (1975) Finding All the Elementary Circuits of a Directed Graph. SIAM Journal on Computing, 4, 77-84.
http://dx.doi.org/10.1137/0204007 - 13. Hudli, A.V. and Hudli, R.V. (1994) Finding Small Feedback Vertex Sets for VLSI Circuits. Microprocessors and Microsystems, 18, 393-400.
http://dx.doi.org/10.1016/0141-9331(94)90067-1 - 14. Gusfield, D. (1998) A Graph Theoretic Approach to Statistical Data Security. SIAM Journal on Computing, 17, 552- 571.
http://dx.doi.org/10.1137/0217034 - 15. Garey, M.R. and Johnson, D.S. (1979) Computers and Intractability: A Guide to Theory of NP-Completeness, W. H. Freeman, San Francisco.
- 16. Yannakakis, M. (1981) Node-Deletion Problem on Bipartite Graphs. SIAM Journal on Computing, 10, 310-327.
http://dx.doi.org/10.1137/0210022 - 17. Lu, C.L. and Tang, C.Y. (1997) A Linear-Time Algorithm for the Weighted Feedback Vertex Problem on Interval Graphs. Information Processing Letters, 61, 107-111.
http://dx.doi.org/10.1016/S0020-0190(96)00193-7 - 18. Saha, A. and Pal, M. (2005) An Algorithm to Find a Minimum Feedback Vertex Set of an Interval Graph. Advanced Modeling and Optimization, 7, 99-116.
- 19. Liang, Y.D. (1994) On the Feedback Vertex Set Problem in Permutation Graphs. Information Processing Letters, 52, 123-129.
http://dx.doi.org/10.1016/0020-0190(94)00133-2 - 20. Luccio, F.L. (1998) Almost Exact Minimum Feedback Vertex Set in Meshes and Butterflies. Information Processing Letters, 66, 59-64.
http://dx.doi.org/10.1016/S0020-0190(98)00039-8 - 21. Focardi, R., Luccio, F.L. and Peleg, D. (2000) Feedback Vertex Set in Hypercubes. Information Processing Letters, 76, 1-5.
http://dx.doi.org/10.1016/S0020-0190(00)00127-7 - 22. Wang, F.H., Wang, Y.L. and Chang, J.M. (2004) Feedback Vertex Sets in Star Graphs. Information Processing Letters, 89, 203-208.
http://dx.doi.org/10.1016/j.ipl.2003.11.001 - 23. Carrabs, F., Cerulli, R., Gentili, M. and Parlato, G. (2005) A Linear Time Algorithm for the Minimum Weighted Feed- back Vertex Set on Diamonds. Information Processing Letters, 94, 29-35.
http://dx.doi.org/10.1016/j.ipl.2004.12.008 - 24. Kuo, C.J., Hsu, C.C., Lin, H.R. and Lin, K.K. (2009) An Efficient Algorithm for Minimum Feedback Vertex Sets in Rotator Graphs. Information Processing Letters, 109, 450-453.
http://dx.doi.org/10.1016/j.ipl.2009.01.004 - 25. Tucker, A. (1980) An Efficient Test for Circular-Arc Graphs. SIAM Journal on Computing, 9, 1-24.
http://dx.doi.org/10.1137/0209001 - 26. McKee, T.A. (2003) Restricted Circular-Arc Graphs and Clique Cycles. Discrete mathematics, 263, 221-231.
http://dx.doi.org/10.1016/S0012-365X(02)00578-2 - 27. Pal, M. and Bhattacharjee, G.P. (1995) An Optimal Parallel Algorithm for Computing All Maximal Cliques of an Interval Graph and Its Applications. Journal of The Institution of Engineers (India), 76, 22-33.