An Algorithm for Minimum Feedback Vertex Set Problem on a Trapezoid Graph

Hirotoshi HONMA  Yutaro KITAMURA  Shigeru MASUYAMA  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E94-A   No.6   pp.1381-1385
Publication Date: 2011/06/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E94.A.1381
Print ISSN: 0916-8508
Type of Manuscript: Special Section LETTER (Special Section on Discrete Mathematics and Its Applications)
design and analysis of algorithms,  feedback vertex set,  trapezoid graphs,  NP-hard,  

Full Text: PDF>>
Buy this Article

In an undirected graph, the feedback vertex set (FVS for short) problem is to find a set of vertices of minimum cardinality whose removal makes the graph acyclic. The FVS has applications to several areas such that combinatorial circuit design, synchronous systems, computer systems, VLSI circuits and so on. The FVS problem is known to be NP-hard on general graphs but interesting polynomial solutions have been found for some special classes of graphs. In this paper, we present an O(n2.68 + γn) time algorithm for solving the FVS problem on trapezoid graphs, where γ is the total number of factors included in all maximal cliques.