TUHH Open Research (TORE)https://tore.tuhh.deTORE captures, stores, indexes, preserves, and distributes digital research material.Fri, 02 Jun 2023 03:00:18 GMT2023-06-02T03:00:18Z5041- Hitting long directed cycles is fixed-parameter tractablehttp://hdl.handle.net/11420/5756Title: Hitting long directed cycles is fixed-parameter tractable
Authors: Göke, Alexander; Marx, Dániel; Mnich, Matthias
Abstract: In the Directed Long Cycle Hitting Set problem we are given a directed graph G, and the task is to find a set S of at most k vertices/arcs such that G − S has no cycle of length longer than `. We show that the problem can be solved in time 2O(`6+`k3 log k+k5 log k log `) · nO(1), that is, it is fixed-parameter tractable (FPT) parameterized by k and `. This algorithm can be seen as a far-reaching generalization of the fixed-parameter tractability of Mixed Graph Feedback Vertex Set [Bonsma and Lokshtanov WADS 2011], which is already a common generalization of the fixed-parameter tractability of (undirected) Feedback Vertex Set and the Directed Feedback Vertex Set problems, two classic results in parameterized algorithms. The algorithm requires significant insights into the structure of graphs without directed cycles of length longer than and can be seen as an exact version of the approximation algorithm following from the Erdős-Pósa property for long cycles in directed graphs proved by Kreutzer and Kawarabayashi [STOC 2015]. © Alexander Göke, Dániel Marx, and Matthias Mnich; licensed under Creative Commons License CC-BY 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020).
Wed, 01 Jan 2020 00:00:00 GMThttp://hdl.handle.net/11420/57562020-01-01T00:00:00Z
- Parameterized Algorithms for generalizations of directed feedback vertex sethttp://hdl.handle.net/11420/4604Title: Parameterized Algorithms for generalizations of directed feedback vertex set
Authors: Göke, Alexander; Marx, Dániel; Mnich, Matthias
Abstract: The Directed Feedback Vertex Set (DFVS) problem takes as input a directed graph G and seeks a smallest vertex set S that hits all cycles in G. This is one of Karp’s 21 -complete problems. Resolving the parameterized complexity status of DFVS was a long-standing open problem until Chen et al. in 2008 showed its fixed-parameter tractability via a -time algorithm, where. Here we show fixed-parameter tractability of two generalizations of DFVS: Find a smallest vertex set S such that every strong component of has size at most s: we give an algorithm solving this problem in time. Find a smallest vertex set S such that every non-trivial strong component of is 1-out-regular: we give an algorithm solving this problem in time. We also solve the corresponding arc versions of these problems by fixed-parameter algorithms.
Tue, 01 Jan 2019 00:00:00 GMThttp://hdl.handle.net/11420/46042019-01-01T00:00:00Z
- Parameterized algorithms for generalizations of directed feedback vertex set http://hdl.handle.net/11420/13461Title: Parameterized algorithms for generalizations of directed feedback vertex set
Authors: Göke, Alexander; Marx, Dániel; Mnich, Matthias
Tue, 01 Nov 2022 00:00:00 GMThttp://hdl.handle.net/11420/134612022-11-01T00:00:00Z
- Domination and cut problems on chordal graphs with bounded leafagehttp://hdl.handle.net/11420/14451Title: Domination and cut problems on chordal graphs with bounded leafage
Authors: Galby, Esther; Marx, Dániel; Schepper, Philipp; Sharma, Roohani; Tale, Prafullkumar
Abstract: The leafage of a chordal graph G is the minimum integer ℓ such that G can be realized as an intersection graph of subtrees of a tree with ℓ leaves. We consider structural parameterization by the leafage of classical domination and cut problems on chordal graphs. Fomin, Golovach, and Raymond [ESA 2018, Algorithmica 2020] proved, among other things, that Dominating Set on chordal graphs admits an algorithm running in time 2O(ℓ2) · nO(1). We present a conceptually much simpler algorithm that runs in time 2O(ℓ)·nO(1). We extend our approach to obtain similar results for Connected Dominating Set and Steiner Tree. We then consider the two classical cut problems MultiCut with Undeletable Terminals and Multiway Cut with Undeletable Terminals. We prove that the former is W[1]-hard when parameterized by the leafage and complement this result by presenting a simple nO(ℓ)-time algorithm. To our surprise, we find that Multiway Cut with Undeletable Terminals on chordal graphs can be solved, in contrast, in nO(1)-time.
Thu, 01 Sep 2022 00:00:00 GMThttp://hdl.handle.net/11420/144512022-09-01T00:00:00Z