TUHH Open Research (TORE)https://tore.tuhh.deTORE captures, stores, indexes, preserves, and distributes digital research material.Wed, 31 May 2023 23:42:47 GMT2023-05-31T23:42:47Z5081Parameterized complexity of induced graph matching on claw-free graphshttp://hdl.handle.net/11420/4568Title: Parameterized complexity of induced graph matching on claw-free graphs
Authors: Hermelin, Danny; Mnich, Matthias; Leeuwen, Erik Jan van
Abstract: The Induced Graph Matching problem asks to find \(k\) disjoint induced subgraphs isomorphic to a given graph \(H\) in a given graph \(G\) such that there are no edges between vertices of different subgraphs. This problem generalizes the classical Independent Set and Induced Matching problems, among several other problems. We show that Induced Graph Matching is fixed-parameter tractable in \(k\) on claw-free graphs when \(H\) is a fixed connected graph, and even admits a polynomial kernel when \(H\) is a complete graph. Both results rely on a new, strong, and generic algorithmic structure theorem for claw-free graphs. Complementing the above positive results, we prove \(\mathsf {W}[1]\)-hardness of Induced Graph Matching on graphs excluding \(K_{1,4}\) as an induced subgraph, for any fixed complete graph \(H\). In particular, we show that Independent Set is \(\mathsf {W}[1]\)-hard on \(K_{1,4}\)-free graphs. Finally, we consider the complexity of Induced Graph Matching on a large subclass of claw-free graphs, namely on proper circular-arc graphs. We show that the problem is either polynomial-time solvable or \(\mathsf {NP}\)-complete, depending on the connectivity of \(H\) and the structure of \(G\).
Sun, 30 Mar 2014 00:00:00 GMThttp://hdl.handle.net/11420/45682014-03-30T00:00:00ZDomination when the stars are outhttp://hdl.handle.net/11420/4632Title: Domination when the stars are out
Authors: Hermelin, Danny; Mnich, Matthias; Leeuwen, Erik Jan van; Woeginger, Gerhard
Tue, 01 Jan 2019 00:00:00 GMThttp://hdl.handle.net/11420/46322019-01-01T00:00:00ZParameterized complexity dichotomy for Steiner multicuthttp://hdl.handle.net/11420/4628Title: Parameterized complexity dichotomy for Steiner multicut
Authors: Bringmann, Karl; Hermelin, Danny; Mnich, Matthias; Leeuwen, Erik Jan van
Thu, 01 Jan 2015 00:00:00 GMThttp://hdl.handle.net/11420/46282015-01-01T00:00:00ZPolynomial kernels for deletion to classes of acyclic digraphshttp://hdl.handle.net/11420/4574Title: Polynomial kernels for deletion to classes of acyclic digraphs
Authors: Mnich, Matthias; Leeuwen, Erik Jan van
Abstract: We consider the problem to find a set X of vertices (or arcs) with |X| <= k in a given digraph G such that D = G-X is an acyclic digraph. In its generality, this is DIRECTED FEEDBACK VERTEX SET or DIRECTED FEEDBACK ARC SET respectively. The existence of a polynomial kernel for these problems is a notorious open problem in the field of kernelization, and little progress has been made. In this paper, we consider both deletion problems with an additional restriction on D, namely that D must be an out-forest, an out-tree, or a (directed) pumpkin. Our main results show that for each of these three restrictions the vertex deletion problem remains NP-hard, but we can obtain a kernel with k^{O(1)} vertices on general digraphs G. We also show that, in contrast to the vertex deletion problem, the arc deletion problem with each of the above restrictions can be solved in polynomial time.
Fri, 01 Jan 2016 00:00:00 GMThttp://hdl.handle.net/11420/45742016-01-01T00:00:00ZParameterized complexity of induced H-matching on claw-free graphshttp://hdl.handle.net/11420/4584Title: Parameterized complexity of induced H-matching on claw-free graphs
Authors: Hermelin, Danny; Mnich, Matthias; Leeuwen, Erik Jan van
Abstract: The Induced H -Matching problem asks to find k disjoint, induced subgraphs isomorphic to H in a given graph G such that there are no edges between vertices of different subgraphs. This problem generalizes amongst others the classical Independent Set and Induced Matching problems. We show that Induced H -Matching is fixed-parameter tractable in k on claw-free graphs when H is a fixed connected graph of constant size, and even admits a polynomial kernel when H is a clique. Both results rely on a new, strong algorithmic structure theorem for claw-free graphs. To show the fixed-parameter tractability of the problem, we additionally apply the color-coding technique in a nontrivial way. Complementing the above two positive results, we prove the W[1]-hardness of Induced H -Matching for graphs excluding K 1,4 as an induced subgraph. In particular, we show that Independent Set is W[1]-hard on K 1,4-free graphs.
Sun, 01 Jan 2012 00:00:00 GMThttp://hdl.handle.net/11420/45842012-01-01T00:00:00ZParameterized complexity dichotomy for Steiner Multicuthttp://hdl.handle.net/11420/4612Title: Parameterized complexity dichotomy for Steiner Multicut
Authors: Bringmann, Karl; Hermelin, Danny; Mnich, Matthias; Leeuwen, Erik Jan van
Abstract: We consider the Steiner Multicut problem, which asks, given an undirected graph G, a collection T={T1,...,Tt}, Ti V(G), of terminal sets of size at most p, and an integer k, whether there is a set S of at most k edges or nodes such that of each set Ti at least one pair of terminals is in different connected components of G-S. We provide a dichotomy of the parameterized complexity of Steiner Multicut. For any combination of k, t, p, and the treewidth tw(G) as constant, parameter, or unbounded, and for all versions of the problem (edge deletion and node deletion with and without deletable terminals), we prove either that the problem is fixed-parameter tractable, W[1]-hard, or (para-)NP-complete. Our characterization includes a dichotomy for Steiner Multicut on trees as well as a polynomial time versus NP-hardness dichotomy (by restricting k,t,p,tw(G) to constant or unbounded).
Thu, 01 Sep 2016 00:00:00 GMThttp://hdl.handle.net/11420/46122016-09-01T00:00:00ZPolynomial kernels for deletion to classes of acyclic digraphshttp://hdl.handle.net/11420/4695Title: Polynomial kernels for deletion to classes of acyclic digraphs
Authors: Mnich, Matthias; Leeuwen, Erik Jan van
Abstract: We consider the problem to find a set X of vertices (or arcs) with |X|≤k in a given digraph G such that D=G−X is an acyclic digraph. In its generality, this is DIRECTED FEEDBACK VERTEX SET (or DIRECTED FEEDBACK ARC SET); the existence of a polynomial kernel for these problems is a notorious open problem in the field of kernelization, and little progress has been made. In this paper, we consider the vertex deletion problem with an additional restriction on D, namely that D must be an out-forest, an out-tree, or a (directed) pumpkin. Our main results show that for each of the above three restrictions we can obtain a kernel with kO(1) vertices on general digraphs. We also show that the arc deletion problem with the first two restrictions (out-forest and out-tree) can be solved in polynomial time; this contrasts the status of the vertex deletion problem of these restrictions, which is NP-hard even for acyclic digraphs. The arc and vertex deletion problem with the third restriction (pumpkin), however, can be solved in polynomial time for acyclic digraphs, but becomes NP-hard for general digraphs. We believe that the idea of restricting D could yield new insights towards resolving the status of DIRECTED FEEDBACK VERTEX SET.
Tue, 07 Mar 2017 00:00:00 GMThttp://hdl.handle.net/11420/46952017-03-07T00:00:00ZDomination when the stars are outhttp://hdl.handle.net/11420/4556Title: Domination when the stars are out
Authors: Hermelin, Danny; Mnich, Matthias; Leeuwen, Erik Jan van; Woeginger, Gerhard
Sat, 01 Jan 2011 00:00:00 GMThttp://hdl.handle.net/11420/45562011-01-01T00:00:00Z