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.

DOI: 10.4236/jcc.2016.48003                

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 polynomi-al-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

Received 25 April 2016; accepted 24 June 2016; published 27 June 2016

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 M₂; (b) A normal Helly circular-arc graph G₂.

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.

Conflicts of Interest

The authors declare no conflicts of interest.

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.