TUHH Open Research (TORE)https://tore.tuhh.deTORE captures, stores, indexes, preserves, and distributes digital research material.Thu, 02 Feb 2023 07:20:06 GMT2023-02-02T07:20:06Z50921- On routing disjoint paths in bounded treewidth graphshttp://hdl.handle.net/11420/4545Title: On routing disjoint paths in bounded treewidth graphs
Authors: Ene, Alina; Mnich, Matthias; Pilipczuk, Marcin; Risteski, Andrej
Fri, 01 Jan 2016 00:00:00 GMThttp://hdl.handle.net/11420/45452016-01-01T00:00:00Z
- New approximation algorithms for (1,2)-TSPhttp://hdl.handle.net/11420/4571Title: New approximation algorithms for (1,2)-TSP
Authors: Adamaszek, Anna; Mnich, Matthias; Paluch, Katarzyna
Abstract: We give faster and simpler approximation algorithms for the (1,2)-TSP problem, a well-studied variant of the traveling salesperson problem where all distances between cities are either 1 or 2. Our main results are two approximation algorithms for (1,2)-TSP, one with approximation factor 8/7 and run time O(n^3) and the other having an approximation guarantee of 7/6 and run time O(n^{2.5}). The 8/7-approximation matches the best known approximation factor for (1,2)-TSP, due to Berman and Karpinski (SODA 2006), but considerably improves the previous best run time of O(n^9). Thus, ours is the first improvement for the (1,2)-TSP problem in more than 10 years. The algorithm is based on combining three copies of a minimum-cost cycle cover of the input graph together with a relaxed version of a minimum weight matching, which allows using "half-edges". The resulting multigraph is then edge-colored with four colors so that each color class yields a collection of vertex-disjoint paths. The paths from one color class can then be extended to an 8/7-approximate traveling salesperson tour. Our algorithm, and in particular its analysis, is simpler than the previously best 8/7-approximation. The 7/6-approximation algorithm is similar and even simpler, and has the advantage of not using Hartvigsen's complicated algorithm for computing a minimum-cost triangle-free cycle cover.
Mon, 01 Jan 2018 00:00:00 GMThttp://hdl.handle.net/11420/45712018-01-01T00:00:00Z
- New algorithms for maximum disjoint paths based on tree-likenesshttp://hdl.handle.net/11420/4601Title: New algorithms for maximum disjoint paths based on tree-likeness
Authors: Fleszar, Krzysztof; Mnich, Matthias; Spoerhase, Joachim
Abstract: We study the classical NP-hard problems of finding maximum-size subsets from given sets of k terminal pairs that can be routed via edge-disjoint paths (MAXEDP) or node-disjoint paths (MAXNDP) in a given graph. The approximability of MAXEDP/NDP is currently not well understood; the best known lower bound is Ω(log 1/2-ϵn), assuming NP ⊈ ZPTIME(npoy gn). This constitutes a significant gap to the best known approximation upper bound of O(√n) due to Chekuri et al. (2006) and closing this gap is currently one of the big open problems in approximation algorithms. In their seminal paper, Raghavan and Thompson (Combinatorica, 1987) introduce the technique of randomized rounding for LPs; their technique gives an O(1)-approximation when edges (or nodes) may be used by O (log n/log log n) paths. In this paper, we strengthen the above fundamental results. We provide new bounds formulated in terms of the feedback vertex set number r of a graph, which measures its vertex deletion distance to a forest. In particular, we obtain the following. • For MAXEDP, we give an O(√r · log1.5 kr)-approximation algorithm. As r ≤ n, up to logarithmic factors, our result strengthens the best known ratio O(√n) due to Chekuri et al. • Further, we show how to route Ω(OPT) pairs with congestion O(log kr/log log kr), strengthening the bound obtained by the classic approach of Raghavan and Thompson. • For MAXNDP, we give an algorithm that gives the optimal answer in time (k + r)O(r) · n. This is a substantial improvement on the run time of 2k r O(r) · n, which can be obtained via an algorithm by Scheffler. We complement these positive results by proving that MAXEDP is NP-hard even for r = 1, and MAXNDP is W[1]-hard for parameter r. This shows that neither problem is fixed-parameter tractable in r unless FPT = W[1] and that our approximability results are relevant even for very small constant values of r. © Krzysztof Fleszar, Matthias Mnich, and Joachim Spoerhase.
Mon, 01 Aug 2016 00:00:00 GMThttp://hdl.handle.net/11420/46012016-08-01T00:00:00Z
- Linear-time recognition of map graphs with outerplanar witnesshttp://hdl.handle.net/11420/7612Title: Linear-time recognition of map graphs with outerplanar witness
Authors: Mnich, Matthias; Rutter, Ignaz; Schmidt, Jens M.
Abstract: Map graphs generalize planar graphs and were introduced by Chen, Grigni and Papadimitriou [STOC 1998, J.ACM 2002]. They showed that the problem of recognizing map graphs is in NP by proving the existence of a planar witness graph W. Shortly after, Thorup [FOCS 1998] published a polynomial-time recognition algorithm for map graphs. However, the run time of this algorithm is estimated to be Ω(n120) for n-vertex graphs, and a full description of its details remains unpublished. We give a new and purely combinatorial algorithm that decides whether a graph G is a map graph having an outerplanar witness W. This is a step towards a first combinatorial recognition algorithm for general map graphs. The algorithm runs in time and space O(n + m). In contrast to Thorup's approach, it computes the witness graph W in the affirmative case.
Wed, 22 Jun 2016 00:00:00 GMThttp://hdl.handle.net/11420/76122016-06-22T00:00:00Z
- Beyond Max-Cut: λ-extendible properties parameterized above the Poljak-Turzík boundhttp://hdl.handle.net/11420/4555Title: Beyond Max-Cut: λ-extendible properties parameterized above the Poljak-Turzík bound
Authors: Mnich, Matthias; Philip, Geevarghese; Saurabh, Saket; Suchý, Ondřej
Sun, 01 Jan 2012 00:00:00 GMThttp://hdl.handle.net/11420/45552012-01-01T00:00:00Z
- Max-Cut parameterized above the Edwards-Erdős boundhttp://hdl.handle.net/11420/4054Title: Max-Cut parameterized above the Edwards-Erdős bound
Authors: Crowston, Robert; Jones, Mark; Mnich, Matthias
Abstract: We study the boundary of tractability for the Max-Cut problem in graphs. Our main result shows that Max-Cut parameterized above the Edwards-Erdős bound is fixed-parameter tractable: we give an algorithm that for any connected graph with n vertices and m edges finds a cut of size (m/2) + (n-1/4) + k in time 2 O(k) ⋅n 4 , or decides that no such cut exists. This answers a long-standing open question from parameterized complexity that has been posed a number of times over the past 15 years. Our algorithm has asymptotically optimal running time, under the Exponential Time Hypothesis, and is strengthened by a polynomial-time computable kernel of polynomial size.
Sun, 12 Jul 2015 00:00:00 GMThttp://hdl.handle.net/11420/40542015-07-12T00:00:00Z
- 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
- Dense Steiner problems: approximation algorithms and inapproximabilityhttp://hdl.handle.net/11420/5996Title: Dense Steiner problems: approximation algorithms and inapproximability
Authors: Karpinski, Marek; Lewandowski, Mateusz; Meesum, Syed Mohammad; Mnich, Matthias
Abstract: The Steiner Tree problem is a classical problem in combinatorial optimization: the goal is to connect a set T of terminals in a graph G by a tree of minimum size. Karpinski and Zelikovsky (1996) studied the δ-dense version of Steiner Tree, where each terminal has at least δ |V(G)∖ T| neighbours outside T, for a fixed δ > 0. They gave a PTAS for this problem. We study a generalization of pairwise δ-dense Steiner Forest, which asks for a minimum-size forest in G in which the nodes in each terminal set T₁,…,Tk are connected, and every terminal in Tᵢ has at least δ |Tⱼ| neighbours in Tⱼ, and at least δ|S| nodes in S = V(G)∖ (T₁∪…∪ Tk), for each i, j in {1,…, k} with i≠ j. Our first result is a polynomial-time approximation scheme for all δ > 1/2. Then, we show a ((13/12)+ε)-approximation algorithm for δ = 1/2 and any ε > 0. We also consider the δ-dense Group Steiner Tree problem as defined by Hauptmann and show that the problem is APX-hard.
Wed, 01 Jan 2020 00:00:00 GMThttp://hdl.handle.net/11420/59962020-01-01T00:00:00Z
- Parameterized 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:00Z
- A time- and space-optimal algorithm for the many-visits TSPhttp://hdl.handle.net/11420/4450Title: A time- and space-optimal algorithm for the many-visits TSP
Authors: Berger, André; Kozma, László; Mnich, Matthias; Vincze, Roland
Abstract: The many-visits traveling salesperson problem (MV-TSP) asks for an optimal tour of n cities that visits each city c a prescribed number k_c of times. Travel costs may be asymmetric, and visiting a city twice in a row may incur a non-zero cost. The MV-TSP problem finds applications in scheduling, geometric approximation, and Hamiltonicity of certain graph families.
The fastest known algorithm for MV-TSP is due to Cosmadakis and Papadimitriou (SICOMP, 1984). It runs in time n^{O(n)} + O(n^3 \log \sum_c k_c ) and requires n^{O(n)} space. The interesting feature of the Cosmadakis-Papadimitriou algorithm is its \emph{logarithmic} dependence on the total length \sum_c k_c of the tour, allowing the algorithm to handle instances with very long tours, beyond what is tractable in the standard TSP setting. However, its superexponential dependence on the number of cities in both its time and space complexity renders the algorithm impractical for all but the narrowest range of this parameter.
In this paper we significantly improve on the Cosmadakis-Papadimitriou algorithm, giving an MV-TSP algorithm that runs in
time 2^{O(n)}, i.e.\ single-exponential in the number of cities, with polynomial space. The space requirement of our algorithm is (essentially) the size of the output, and assuming the Exponential-time Hypothesis (ETH), the time requirement is optimal. Our algorithm is deterministic, and arguably both simpler and easier to analyse than the original approach of Cosmadakis and Papadimitriou. It involves an optimization over directed spanning trees and a recursive, centroid-based decomposition of trees.
Tue, 01 Jan 2019 00:00:00 GMThttp://hdl.handle.net/11420/44502019-01-01T00:00:00Z
- Domination 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:00Z
- The complexity ecology of parameters: An illustration using bounded max leaf numberhttp://hdl.handle.net/11420/4557Title: The complexity ecology of parameters: An illustration using bounded max leaf number
Authors: Fellows, Michael; Lokshtanov, Daniel; Misra, Neeldhara; Mnich, Matthias; Rosamond, Frances; Saurabh, Saket
Abstract: In the framework of parameterized complexity, exploring how one parameter affects the complexity of a different parameterized (or unparameterized problem) is of general interest. A well-developed example is the investigation of how the parameter treewidth influences the complexity of (other) graph problems. The reason why such investigations are of general interest is that real-world input distributions for computational problems often inherit structure from the natural computational processes that produce the problem instances (not necessarily in obvious, or well-understood ways). The max leaf number ml(G) of a connected graph G is the maximum number of leaves in a spanning tree for G. Exploring questions analogous to the well-studied case of treewidth, we can ask: how hard is it to solve 3-Coloring, Hamilton Path, Minimum Dominating Set, Minimum Bandwidth or many other problems, for graphs of bounded max leaf number? What optimization problems are W[1]-hard under this parameterization? We do two things:
(1) We describe much improved FPT algorithms for a large number of graph problems, for input graphs G for which ml(G)≤k, based on the polynomial-time extremal structure theory canonically associated to this parameter. We consider improved algorithms both from the point of view of kernelization bounds, and in terms of improved fixed-parameter tractable (FPT) runtimes O *(f(k)).
(2) The way that we obtain these concrete algorithmic results is general and systematic. We describe the approach, and raise programmatic questions.
Fri, 09 Jan 2009 00:00:00 GMThttp://hdl.handle.net/11420/45572009-01-09T00:00:00Z
- Parameterized 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:00Z
- Planar $k$-path in subexponential time and polynomial spacehttp://hdl.handle.net/11420/4553Title: Planar $k$-path in subexponential time and polynomial space
Authors: Lokshtanov, Daniel; Mnich, Matthias; Saurabh, Saket
Sat, 01 Jan 2011 00:00:00 GMThttp://hdl.handle.net/11420/45532011-01-01T00:00:00Z
- Combinatorial n-fold integer programming and applicationshttp://hdl.handle.net/11420/4607Title: Combinatorial n-fold integer programming and applications
Authors: Knop, Dušan; Koutecký, Martin; Mnich, Matthias
Abstract: Many fundamental NP-hard problems can be formulated as integer linear programs (ILPs). A famous algorithm by Lenstra allows to solve ILPs in time that is exponential only in the dimension of the program. That algorithm therefore became a ubiquitous tool in the design of fixed-parameter algorithms for NP-hard problems, where one wishes to isolate the hardness of a problem by some parameter. However, it was discovered that in many cases using Lenstra's algorithm has two drawbacks: First, the run time of the resulting algorithms is often doublyexponential in the parameter, and second, an ILP formulation in small dimension can not easily express problems which involve many different costs. Inspired by the work of Hemmecke, Onn and Romanchuk [Math. Prog. 2013], we develop a single-exponential algorithm for so-called combinatorial n-fold integer programs, which are remarkably similar to prior ILP formulations for various problems, but unlike them, also allow variable dimension. We then apply our algorithm to a few representative problems like Closest String, Swap Bribery, Weighted Set Multicover, and obtain exponential speedups in the dependence on the respective parameters, the input size, or both. Unlike Lenstra's algorithm, which is essentially a bounded search tree algorithm, our result uses the technique of augmenting steps. At its heart is a deep result stating that in combinatorial n-fold IPs an existence of an augmenting step implies an existence of a "local" augmenting step, which can be found using dynamic programming. Our results provide an important insight into many problems by showing that they exhibit this phenomenon, and highlights the importance of augmentation techniques.
Fri, 01 Sep 2017 00:00:00 GMThttp://hdl.handle.net/11420/46072017-09-01T00:00:00Z
- Dynamic parameterized problems and algorithmshttp://hdl.handle.net/11420/4608Title: Dynamic parameterized problems and algorithms
Authors: Alman, Josh; Mnich, Matthias; Vassilevska Williams, Virginia
Abstract: Fixed-parameter algorithms and kernelization are two powerful methods to solve NP-hard problems. Yet, so far those algorithms have been largely restricted to static inputs. In this paper we provide fixed-parameter algorithms and kernelizations for fundamental NP-hard problems with dynamic inputs. We consider a variety of parameterized graph and hitting set problems which are known to have f(k)n¹⁺ᵒ⁽¹⁾ time algorithms on inputs of size n, and we consider the question of whether there is a data structure that supports small updates (such as edge/vertex/set/element insertions and deletions) with an update time of g(k)nᵒ⁽¹⁾; such an update time would be essentially optimal. Update and query times independent of n are particularly desirable. Among many other results, we show that Feedback Vertex Set and k-Path admit dynamic algorithms with f(k)ᴼ⁽¹⁾n update and query times for some function f depending on the solution size k only. We complement our positive results by several conditional and unconditional lower bounds. For example, we show that unlike their undirected counterparts, Directed Feedback Vertex Set and Directed k-Path do not admit dynamic algorithms with nᵒ⁽¹⁾ update and query times even for constant solution sizes k≤ 3, assuming popular hardness hypotheses. We also show that unconditionally, in the cell probe model, Directed Feedback Vertex Set cannot be solved with update time that is purely a function of k.
Sat, 01 Jul 2017 00:00:00 GMThttp://hdl.handle.net/11420/46082017-07-01T00:00:00Z
- New deterministic algorithms for solving parity gameshttp://hdl.handle.net/11420/6271Title: New deterministic algorithms for solving parity games
Authors: Mnich, Matthias; Röglin, Heiko; Rösner, Clemens
Tue, 17 Jul 2018 00:00:00 GMThttp://hdl.handle.net/11420/62712018-07-17T00:00:00Z
- Linear-time recognition of map graphs with outerplanar witnesshttp://hdl.handle.net/11420/4533Title: Linear-time recognition of map graphs with outerplanar witness
Authors: Mnich, Matthias; Rutter, Ignaz; Schmidt, Jens M.
Abstract: Map graphs generalize planar graphs and were introduced by Chen et al. (STOC 1998, J. ACM, 2002). They showed that the problem of recognizing map graphs is in by proving the existence of a planar witness graph . Shortly after, Thorup (FOCS 1998) published a polynomial-time recognition algorithm for map graphs. However, the run time of this algorithm is estimated to be for
-vertex graphs, and a full description of its details remains unpublished.
We give a new and purely combinatorial algorithm that decides whether a graph
is a map graph having an outerplanar witness . This is a step towards a first combinatorial recognition algorithm for general map graphs. The algorithm runs in time and space . In contrast to Thorup’s approach, it computes the witness graph in the affirmative case.
Tue, 01 May 2018 00:00:00 GMThttp://hdl.handle.net/11420/45332018-05-01T00:00:00Z
- Scheduling and fixed-parameter tractabilityhttp://hdl.handle.net/11420/4055Title: Scheduling and fixed-parameter tractability
Authors: Mnich, Matthias; Wiese, Andreas
Abstract: Fixed-parameter tractability analysis and scheduling are two core domains of combinatorial optimization which led to deep understanding of many important algorithmic questions. However, even though fixed-parameter algorithms are appealing for many reasons, no such algorithms are known for many fundamental scheduling problems. In this paper we present the first fixed-parameter algorithms for classical scheduling problems such as makespan minimization, scheduling with job-dependent cost functions—one important example being weighted flow time—and scheduling with rejection. To this end, we identify crucial parameters that determine the problems’ complexity. In particular, we manage to cope with the problem complexity stemming from numeric input values, such as job processing times, which is usually a core bottleneck in the design of fixed-parameter algorithms. We complement our algorithms with(Formula presented.) (Formula presented.)-hardness results showing that for smaller sets of parameters the respective problems do not allow fixed-parameter algorithms. In particular, our positive and negative results for scheduling with rejection explore a research direction proposed by Dániel Marx.
Mon, 01 Dec 2014 00:00:00 GMThttp://hdl.handle.net/11420/40552014-12-01T00:00:00Z
- Treewidth computation and kernelization in the parallel external memory modelhttp://hdl.handle.net/11420/4567Title: Treewidth computation and kernelization in the parallel external memory model
Authors: Jacob, Riko; Lieber, Tobias; Mnich, Matthias
Abstract: We present a randomized algorithm which computes, for any fixed k, a tree decomposition of width at most k of any input graph. We analyze it in the parallel external memory (PEM) model that measures efficiency by counting the number of cache misses on a multi-CPU private cache shared memory machine. Our algorithm has sorting complexity, which we prove to be optimal for a large parameter range.
We use this algorithm as part of a PEM-efficient kernelization algorithm. Kernelization is a technique for preprocessing instances of size n of NP-hard problems with a structural parameter κ by compressing them efficiently to a kernel, an equivalent instance of size at most g(κ). An optimal solution to the original instance can then be recovered efficiently from an optimal solution to the kernel. Our main results here is an adaption of the linear-time randomized protrusion replacement algorithm by Fomin et al. (FOCS 2012). In particular, we obtain efficient randomized parallel algorithms to compute linear kernels in the PEM model for all separable contraction-bidimensional problems with finite integer index (FII) on apex minor-free graphs, and for all treewidth-bounding graph problems with FII on topological minor-free graphs.
Wed, 01 Jan 2014 00:00:00 GMThttp://hdl.handle.net/11420/45672014-01-01T00:00:00Z
- Polynomial kernels for weighted problemshttp://hdl.handle.net/11420/4560Title: Polynomial kernels for weighted problems
Authors: Etscheid, Michael; Kratsch, Stefan; Mnich, Matthias; Röglin, Heiko
Sun, 01 Jan 2017 00:00:00 GMThttp://hdl.handle.net/11420/45602017-01-01T00:00:00Z
- Feedback vertex sets in tournamentshttp://hdl.handle.net/11420/4566Title: Feedback vertex sets in tournaments
Authors: Gaspers, Serge; Mnich, Matthias
Abstract: We study combinatorial and algorithmic questions around minimal feedback vertex sets (FVS) in tournament graphs. On the combinatorial side, we derive upper and lower bounds on the maximum number of minimal FVSs in an n‐vertex tournament. We prove that every tournament on n vertices has at most 1.6740n minimal FVSs, and that there is an infinite family of tournaments, all having at least 1.5448n minimal FVSs. This improves and extends the bounds of Moon (1971). On the algorithmic side, we design the first polynomial space algorithm that enumerates the minimal FVSs of a tournament with polynomial delay. The combination of our results yields the fastest known algorithm for finding a minimum‐sized FVS in a tournament.
Tue, 26 Jun 2012 00:00:00 GMThttp://hdl.handle.net/11420/45662012-06-26T00:00:00Z
- New algorithms for maximum disjoint paths based on tree-likenesshttp://hdl.handle.net/11420/4561Title: New algorithms for maximum disjoint paths based on tree-likeness
Authors: Fleszar, Krzysztof; Mnich, Matthias; Spoerhase, Joachim
Mon, 01 Jan 2018 00:00:00 GMThttp://hdl.handle.net/11420/45612018-01-01T00:00:00Z
- Ranking and drawing in subexponential timehttp://hdl.handle.net/11420/4552Title: Ranking and drawing in subexponential time
Authors: Fernau, Henning; Fomin, Fedor V.; Lokshtanov, Daniel; Mnich, Matthias; Philip, Geevarghese; Saurabh, Saket
Abstract: In this paper we obtain parameterized subexponential-time algorithms for p -Kemeny Aggregation (p-KAGG) — a problem in social choice theory — and for p -One-Sided Crossing Minimization (p-OSCM) – a problem in graph drawing (see the introduction for definitions). These algorithms run in time O∗(2O(k√logk)), where k is the parameter, and significantly improve the previous best algorithms with running times O∗(1.403 k ) and O∗(1.4656 k ), respectively. We also study natural “above-guarantee” versions of these problems and show them to be fixed parameter tractable. In fact, we show that the above-guarantee versions of these problems are equivalent to a weighted variant of p -Directed Feedback Arc Set. Our results for the above-guarantee version of p-KAGG reveal an interesting contrast. We show that when the number of “votes” in the input to p-KAGG is odd the above guarantee version can still be solved in time O∗(2O(k√logk)), while if it is even then the problem cannot have a subexponential time algorithm unless the exponential time hypothesis fails (equivalently, unless FPT=M[1]).
Sat, 01 Jan 2011 00:00:00 GMThttp://hdl.handle.net/11420/45522011-01-01T00:00:00Z
- Kernel and fast algorithm for dense triplet inconsistencyhttp://hdl.handle.net/11420/4541Title: Kernel and fast algorithm for dense triplet inconsistency
Authors: Guillemot, Sylvain; Mnich, Matthias
Abstract: Westudytheparameterizedcomplexityofinferringsupertreesfromsetsofrootedtriplets,an important problem in phylogenetics. For a setLof labels and a dense setTof tripletsdistinctly leaf-labeled by 3-subsets ofL, we seek a tree distinctly leaf-labeled byLandcontainingallbutatmostktripletsfromTashomeomorphicsubtree.Ourresultsarethefirst polynomial kernel for this problem, withO(k2)labels, and a subexponential fixed-parameteralgorithmrunningintimeO(|L|4)+2O(k1/3logk).
Wed, 02 Jan 2013 00:00:00 GMThttp://hdl.handle.net/11420/45412013-01-02T00:00:00Z
- Interval scheduling and colorful independent setshttp://hdl.handle.net/11420/4536Title: Interval scheduling and colorful independent sets
Authors: van Bevern, René; Mnich, Matthias; Niedermeier, Rolf; Weller, Mathias
Abstract: Numerous applications in scheduling, such as resource allocation or steel manufacturing, can be modeled using the NP-hard Independent Set problem (given an undirected graph and an integer $$k$$k, find a set of at least $$k$$k pairwise non-adjacent vertices). Here, one encounters special graph classes like 2-union graphs (edge-wise unions of two interval graphs) and strip graphs (edge-wise unions of an interval graph and a cluster graph), on which Independent Set remains $$\mathrm{NP}$$NP-hard but admits constant ratio approximations in polynomial time. We study the parameterized complexity of Independent Set on 2-union graphs and on subclasses like strip graphs. Our investigations significantly benefit from a new structural “compactness” parameter of interval graphs and novel problem formulations using vertex-colored interval graphs. Our main contributions are as follows:1.We show a complexity dichotomy: restricted to graph classes closed under induced subgraphs and disjoint unions, Independent Set is polynomial-time solvable if both input interval graphs are cluster graphs, and is (Formula presented.)-hard otherwise.2.We chart the possibilities and limits of effective polynomial-time preprocessing (also known as kernelization).3.We extend Halldórsson and Karlsson (2006)’s fixed-parameter algorithm for Independent Set on strip graphs parameterized by the structural parameter “maximum number of live jobs” to show that the problem (also known as Job Interval Selection) is fixed-parameter tractable with respect to the parameter (Formula presented.) and generalize their algorithm from strip graphs to 2-union graphs. Preliminary experiments with random data indicate that Job Interval Selection with up to 15 jobs and (Formula presented.) intervals can be solved optimally in less than 5 min.
Wed, 01 Jan 2014 00:00:00 GMThttp://hdl.handle.net/11420/45362014-01-01T00:00:00Z
- A unifying framework for manipulation problemshttp://hdl.handle.net/11420/4630Title: A unifying framework for manipulation problems
Authors: Knop, Dušan; Koutecký, Martin; Mnich, Matthias
Mon, 01 Jan 2018 00:00:00 GMThttp://hdl.handle.net/11420/46302018-01-01T00:00:00Z
- Polynomial 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:00Z
- New deterministic algorithms for solving parity gameshttp://hdl.handle.net/11420/4572Title: New deterministic algorithms for solving parity games
Authors: Mnich, Matthias; Röglin, Heiko; Rösner, Clemens
Abstract: We study parity games in which one of the two players controls only a small number k of nodes and the other player controls the n−k other nodes of the game. Our main result is a fixed-parameter algorithm that solves bipartite parity games in time kO(k√)⋅O(n3) and general parity games in time (p+k)O(k√)⋅O(pnm), where p denotes the number of distinct priorities and m denotes the number of edges. For all games with k=o(n)
this improves the previously fastest algorithm by Jurdziński, Paterson, and Zwick (SICOMP 2008).
We also obtain novel kernelization results and an improved deterministic algorithm for graphs with small average degree.
Tue, 22 Mar 2016 00:00:00 GMThttp://hdl.handle.net/11420/45722016-03-22T00:00:00Z
- Parameterized 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:00Z
- A 7/3-approximation for feedback vertex sets in tournamentshttp://hdl.handle.net/11420/4573Title: A 7/3-approximation for feedback vertex sets in tournaments
Authors: Mnich, Matthias; Vassilevska Williams, Virginia; Végh, Lászlo A.
Abstract: We consider the minimum-weight feedback vertex set problem in tournaments: given a tournament with non-negative vertex weights, remove a minimum-weight set of vertices that intersects all cycles. This problem is NP-hard to solve exactly, and Unique Games-hard to approximate by a factor better than 2. We present the first 7/3 approximation algorithm for this problem, improving on the previously best known ratio 5/2 given by Cai et al. [FOCS 1998, SICOMP 2001].
Fri, 01 Jan 2016 00:00:00 GMThttp://hdl.handle.net/11420/45732016-01-01T00:00:00Z
- Large independent sets in triangle-free planar graphshttp://hdl.handle.net/11420/4610Title: Large independent sets in triangle-free planar graphs
Authors: Dvořák, Zdeněk; Mnich, Matthias
Abstract: Every triangle-free planar graph on n vertices has an independent set of size at least (n + 1)/3, and this lower bound is tight. We give an algorithm that, given a triangle-free planar graph G on n vertices and an integer k ≥ 0, decides whether G has an independent set of size at least (n + k)/3, in time 2O(√k)n. Thus, the problem is fixed-parameter tractable when parameterized by k. Furthermore, as a corollary of the result used to prove the correctness of the algorithm, we show that there exists ϵ > 0 such that every planar graph of girth at least five on n vertices has an independent set of size at least n/(3-ϵ). We further give an algorithm that, given a planar graph G of maximum degree 4 on n vertices and an integer k ≥ 0, decides whether G has an independent set of size at least (n + k)/4, in time 2O(√k)n. 7copy; 2017 Zdeňek Dvořák, Matthias Mnich.
Sun, 01 Jan 2017 00:00:00 GMThttp://hdl.handle.net/11420/46102017-01-01T00:00:00Z
- Improved bounds for minimal feedback vertex sets in tournamentshttp://hdl.handle.net/11420/4534Title: Improved bounds for minimal feedback vertex sets in tournaments
Authors: Mnich, Matthias; Teutrine, Eva Lotta
Abstract: We study feedback vertex sets (FVS) in tournaments, which are orientations of complete graphs. As our main result, we show that any tournament on n nodes has at most 1.5949n minimal FVS. This significantly improves the previously best upper bound of 1.6667^n by Fomin et al. [STOC 2016] and 1.6740^n by Gaspers and Mnich [J. Graph Theory 72(1):72–89, 2013]. Our new upper bound almost matches the best-known lower bound of 21^n/7≈1.5448^n, due to Gaspers and Mnich. Our proof is algorithmic, and shows that all minimal FVS of tournaments can be enumerated in time O(1.5949^n).
Fri, 08 Dec 2017 00:00:00 GMThttp://hdl.handle.net/11420/45342017-12-08T00:00:00Z
- Linear kernel for planar connected dominating sethttp://hdl.handle.net/11420/4546Title: Linear kernel for planar connected dominating set
Authors: Lokshtanov, Daniel; Mnich, Matthias; Saurabh, Saket
Abstract: We provide polynomial time data reduction rules for Connected Dominating Set in planar graphs and analyze these to obtain a linear kernel for the planar Connected Dominating Set problem. To obtain the desired kernel we introduce a method that we call reduce or refine. Our kernelization algorithm analyzes the input graph and either finds an appropriate reduction rule that can be applied, or zooms in on a region of the graph which is more amenable to reduction. We find this method of independent interest and believe that it will be useful to obtain linear kernels for other problems on planar graphs.
Thu, 01 Jan 2009 00:00:00 GMThttp://hdl.handle.net/11420/45462009-01-01T00:00:00Z
- Parameterized 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:00Z
- Voting and bribing in single-exponential timehttp://hdl.handle.net/11420/4569Title: Voting and bribing in single-exponential time
Authors: Knop, Dušan; Koutecký, Martin; Mnich, Matthias
Abstract: We introduce a general problem about bribery in voting systems. In the R-Multi-Bribery problem, the goal is to bribe a set of voters at minimum cost such that a desired candidate wins the manipulated election under the voting rule R. Voters assign prices for withdrawing their vote, for swapping the positions of two consecutive candidates in their preference order, and for perturbing their approval count for a candidate. As our main result, we show that R-Multi-Bribery is fixed-parameter tractable parameterized by the number of candidates for many natural voting rules R, including Kemeny rule, all scoring protocols, maximin rule, Bucklin rule, fallback rule, SP-AV, and any C1 rule. In particular, our result resolves the parameterized of R-Swap Bribery for all those voting rules, thereby solving a long-standing open problem and "Challenge #2" of the 9 Challenges in computational social choice by Bredereck et al. Further, our algorithm runs in single-exponential time for arbitrary cost; it thus improves the earlier double-exponential time algorithm by Dorn and Schlotter that is restricted to the unit-cost case for all scoring protocols, the maximin rule, and Bucklin rule.
Sun, 01 Jan 2017 00:00:00 GMThttp://hdl.handle.net/11420/45692017-01-01T00:00:00Z
- Linear kernels and linear-time algorithms for finding large cutshttp://hdl.handle.net/11420/4693Title: Linear kernels and linear-time algorithms for finding large cuts
Authors: Etscheid, Michael; Mnich, Matthias
Abstract: The maximum cut problem in graphs and its generalizations are fundamental combinatorial problems. Several of these cut problems were recently shown to be fixed-parameter tractable and admit polynomial kernels when parameterized above the tight lower bound measured by the size and order of the graph. In this paper we continue this line of research and considerably improve several of those results:
– We show that an algorithm by Crowston et al. (Algorithmica 72(3):734–757, 2015) for (Signed) Max- Cut Above Edwards−ErdÖs Bound can be implemented so as to run in linear time 8k ·O(m); this significantly improves the previous analysis with run time 8k · O(n4).
– We give an asymptotically optimal kernel for (Signed) Max- Cut Above Edwards−ErdÖs Bound with O(k) vertices, improving a kernel with O(k3) vertices by Crowston et al. (Theor Comput Sci 513:53–64, 2013).
– We improve all known kernels for parameterizations above strongly λ-extendible properties (a generalization of the Max- Cut results) by Crowston et al. (Proceedings of FSTTCS 2013, Leibniz international proceedings in informatics,Guwahati, 2013) from O(k3) vertices to O(k) vertices.
Wed, 25 Oct 2017 00:00:00 GMThttp://hdl.handle.net/11420/46932017-10-25T00:00:00Z
- Polynomial 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:00Z
- Linear kernels and linear-time algorithms for finding large cutshttp://hdl.handle.net/11420/4611Title: Linear kernels and linear-time algorithms for finding large cuts
Authors: Etscheid, Michael; Mnich, Matthias
Abstract: The maximum cut problem in graphs and its generalizations are fundamental combinatorial problems. Several of these cut problems were recently shown to be fixed-parameter tractable and admit polynomial kernels when parameterized above the tight lower bound measured by the size and order of the graph. In this paper we continue this line of research and considerably improve several of those results:
We show that an algorithm by Crowston et al. [ICALP 2012] for (Signed) Max-Cut Above Edwards-Erdös Bound can be implemented in such a way that it runs in linear time 8k · O(m); this significantly improves the previous analysis with run time 8k · O(n4).
We give an asymptotically optimal kernel for (Signed) Max-Cut Above Edwards-Erdös Bound with O(k) vertices, improving a kernel with O(k3) vertices by Crowston et al. [COCOON 2013].
We improve all known kernels for strongly λ-extendable properties parameterized above tight lower bound by Crowston et al. [FSTTCS 2013] from O(k3) vertices to O(k) vertices.
As a consequence, Max Acyclic Subdigraph parameterized above Poljak-Turzík bound admits a kernel with O(k) vertices and can be solved in time 2O(k) · nO(1); this answers an open question by Crowston et al. [FSTTCS 2012].
All presented kernels can be computed in time O(km).
Thu, 01 Dec 2016 00:00:00 GMThttp://hdl.handle.net/11420/46112016-12-01T00:00:00Z
- Feedback vertex sets in tournamentshttp://hdl.handle.net/11420/4677Title: Feedback vertex sets in tournaments
Authors: Gaspers, Serge; Mnich, Matthias
Fri, 01 Jan 2010 00:00:00 GMThttp://hdl.handle.net/11420/46772010-01-01T00:00:00Z
- Improved integrality gap upper bounds for TSP with distances one and twohttp://hdl.handle.net/11420/4562Title: Improved integrality gap upper bounds for TSP with distances one and two
Authors: Mnich, Matthias; Mömke, Tobias
Mon, 01 Jan 2018 00:00:00 GMThttp://hdl.handle.net/11420/45622018-01-01T00:00:00Z
- Improved bounds for minimal feedback vertex sets in tournamentshttp://hdl.handle.net/11420/4674Title: Improved bounds for minimal feedback vertex sets in tournaments
Authors: Mnich, Matthias; Teutrine, Eva-Lotta
Fri, 01 Jan 2016 00:00:00 GMThttp://hdl.handle.net/11420/46742016-01-01T00:00:00Z
- Book review "Exact Exponential Algorithms" Springer Verlag, Berlin (2010)http://hdl.handle.net/11420/4543Title: Book review "Exact Exponential Algorithms" Springer Verlag, Berlin (2010)
Authors: Mnich, Matthias
Abstract: Fedor V. Fomin, Dieter Kratsch,
p. 204, € 58.80
ISBN: 978-3-642-16532-0
Sat, 01 Jan 2011 00:00:00 GMThttp://hdl.handle.net/11420/45432011-01-01T00:00:00Z
- Allemaal op een rijtjehttp://hdl.handle.net/11420/4548Title: Allemaal op een rijtje
Authors: Mnich, Matthias
Sat, 01 Jan 2011 00:00:00 GMThttp://hdl.handle.net/11420/45482011-01-01T00:00:00Z
- Parameterized complexity of machine scheduling: 15 open problemshttp://hdl.handle.net/11420/4605Title: Parameterized complexity of machine scheduling: 15 open problems
Authors: Mnich, Matthias; van Bevern, René
Abstract: Machine scheduling problems are a long-time key domain of algorithms and complexity research. A novel approach to machine scheduling problems are fixed-parameter algorithms. To stimulate this thriving research direction, we propose 15 open questions in this area whose resolution we expect to lead to the discovery of new approaches and techniques both in scheduling and parameterized complexity theory.
Sat, 01 Dec 2018 00:00:00 GMThttp://hdl.handle.net/11420/46052018-12-01T00:00:00Z
- Polynomial kernels for weighted problemshttp://hdl.handle.net/11420/4692Title: Polynomial kernels for weighted problems
Authors: Etscheid, Michael; Kratsch, Stefan; Mnich, Matthias; Röglin, Heiko
Tue, 11 Aug 2015 00:00:00 GMThttp://hdl.handle.net/11420/46922015-08-11T00:00:00Z
- Large independent sets in triangle-free planar graphshttp://hdl.handle.net/11420/7627Title: Large independent sets in triangle-free planar graphs
Authors: Dvořák, Zdeněk; Mnich, Matthias
Abstract: Every triangle-free planar graph on n vertices has an independent set of size at least (n+1)/3, and this lower bound is tight. We give an algorithm that, given a triangle-free planar graph G on n vertices and an integer k≥0, decides whether G has an independent set of size at least (n+k)/3, in time 20(√k). Thus, the problem is fixed-parameter tractable when parameterized by k. Furthermore, as a corollary of the result used to prove the correctness of the algorithm, we show that there exists ε>0 such that every planar graph of girth at least five on n vertices has an independent set of size at least n/(3-ε).
Wed, 01 Jan 2014 00:00:00 GMThttp://hdl.handle.net/11420/76272014-01-01T00:00:00Z
- Induced matchings in subcubic planar graphshttp://hdl.handle.net/11420/7626Title: Induced matchings in subcubic planar graphs
Authors: Kang, Ross J.; Mnich, Matthias; Müller, Tobias
Abstract: We present a linear-time algorithm that, given a planar graph with m edges and maximum degree 3, finds an induced matching of size at least m/9. This is best possible.
Mon, 22 Nov 2010 00:00:00 GMThttp://hdl.handle.net/11420/76262010-11-22T00:00:00Z
- Domination 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
- Kernel and fast algorithm for dense triplet inconsistencyhttp://hdl.handle.net/11420/4694Title: Kernel and fast algorithm for dense triplet inconsistency
Authors: Guillemot, Sylvain; Mnich, Matthias
Fri, 01 Jan 2010 00:00:00 GMThttp://hdl.handle.net/11420/46942010-01-01T00:00:00Z