2026-07-21T19:26:10Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:1235 2024-03-06T11:07:37Z ddc:004 open_access

Exact Elimination of Cycles in Graphs Raible, Daniel Fernau, Henning Maximum Acyclic Subgraph Feedback Arc Set Amortized Analysis Exact exponential algorthms 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^n$ for {sc Feedback Vertex Set} on planar directed graphs is broken. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Daniel Raible and Henning Fernau 2007 Is Part Of Dagstuhl Seminar Proceedings, Volume 7281, Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs (2007) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/DagSemProc.07281.6 urn:nbn:de:0030-drops-12353 https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07281.6 eng https://creativecommons.org/licenses/by/4.0/legalcode