Author name cluster

Joachim Kneis

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

3 papers

2 author rows

TCS Journal 2011 Journal Article

An exact algorithm for the Maximum Leaf Spanning Tree problem

Henning Fernau
Joachim Kneis
Dieter Kratsch
Alexander Langer
Mathieu Liedloff
Daniel Raible
Peter Rossmanith

Given an undirected graph with n vertices, the Maximum Leaf Spanning Tree problem is to find a spanning tree with as many leaves as possible. When parameterized in the number of leaves k, this problem can be solved in time O ( 4 k poly ( n ) ) using a simple branching algorithm introduced by a subset of the authors (Kneis et al. 2008 [16]). Daligault et al. (2010) [6] improved the branching and obtained a running time of O ( 3. 7 2 k poly ( n ) ). In this paper, we study the problem from an exponential time viewpoint, where it is equivalent to the Connected Dominating Set problem. Here, Fomin, Grandoni, and Kratsch showed how to break the Ω ( 2 n ) barrier and proposed an O ( 1. 940 7 n ) -time algorithm (Fomin et al. 2008 [11]). Based on some useful properties of Kneis et al. (2008) [16] and Daligault et al. (2010) [6], we present a branching algorithm whose running time of O ( 1. 896 6 n ) has been analyzed using the Measure-and-Conquer technique. Finally, we provide a lower bound of Ω ( 1. 442 2 n ) for the worst case running time of our algorithm.

Details DOI

TCS Journal 2009 Journal Article

Approximation hardness of deadline-TSP reoptimization

Hans-Joachim Böckenhauer
Joachim Kneis
Joachim Kupke

Given an instance of an optimization problem together with an optimal solution, we consider the scenario in which this instance is modified locally. In graph problems, e. g. , a singular edge might be removed or added, or an edge weight might be varied, etc. For a problem U and such a local modification operation, let lm- U (local-modification- U ) denote the resulting problem. The question is whether it is possible to exploit the additional knowledge of an optimal solution to the original instance or not, i. e. ,whether lm- U is computationally more tractable than U. While positive examples are known e. g. for metric TSP, we give some negative examples here: Metric TSP with deadlines (time windows), if a single deadline or the cost of a single edge is modified, exhibits the same lower bounds on the approximability in these local-modification versions as those currently known for the original problem.

Details DOI

MFCS Conference 2005 Conference Paper

On the Parameterized Complexity of Exact Satisfiability Problems

Joachim Kneis
Daniel Mölle
Stefan Richter 0001
Peter Rossmanith

Abstract For many problems, the investigation of their parameterized complexity provides an interesting and useful point of view. The most obvious natural parameterization for the maximum satisfiability problem—the number of satisfiable clauses—makes little sense, because at least half of the clauses can be satisfied in any formula. We look at two optimization variants of the exact satisfiability problem, where a clause is only said to be fulfilled iff exactly one of its literals is set to true. Interestingly, these variants behave quite differently. In the case of ResMaxExactSAT, where over-satisfied clauses are entirely forbidden, we show fixed parameter tractability. On the other hand, if we choose to ignore over-satisfied clauses, the MaxExactSAT problem is obtained. Surprisingly, it is W[1]-complete. Still, restricted variants of the problem turn out to be tractable.

Details