Exact Elimination of Cycles in Graphs

2007/01/01 by Daniel Raible, Henning Fernau, Raible, Daniel +1
Computer Science · #Advanced Graph Theory Research #Computational Geometry and Mesh Generation #Graph Theory and Algorithms

paper · doi:10.4230/dagsemproc.07281.6

Abstract

One of the standard basic steps in drawing hierarchical graphs is to invert some arcs of the given graph to make the graph acyclic. We discuss exact and parameterized algorithms for this problem. In particular we examine a graph class called (1,n)-graphs, which contains cubic graphs. For both exact and parameterized algorithms we use a non-standard measure approach for the analysis. The analysis of the parameterized algorithm is of special interest, as it is not an amortized analysis modelled by 'finite states' but rather a 'top-down' amortized analysis. For (1,n)-graphs we achieve a running time of Oh^*(1.1871^m) and Oh^*(1.212^k), for cubic graphs Oh^*(1.1798^m) and Oh^*(1.201^k), respectively. As a by-product the trivial bound of 2ⁿ for sc Feedback Vertex Set on planar directed graphs is broken.

Citations

• Methods for Visual Understanding of Hierarchical System Structures

Related

• A Naive Algorithm for Feedback Vertex Set
• Deletion to Scattered Graph Classes I -- case of finite number of graph classes
• Tight Bounds for Feedback Vertex Set Parameterized by Clique-width
• Incremental Cycle Detection, Topological Ordering, and Strong Component\n Maintenance
• Modification Problems toward Proper (Helly) Circular-arc Graphs