Recently it has been shown that the miniaturization mapping M faithfully translates subexponential parameterized complexity into (unbounded) parameterized complexity. We determine the pre-images under M of various (cl...
详细信息
Recently it has been shown that the miniaturization mapping M faithfully translates subexponential parameterized complexity into (unbounded) parameterized complexity. We determine the pre-images under M of various (classes of) problems. For many parameterized problems whose underlying classical problem is in NP we show that the pre-images coincide with natural reparameterizations that take into account the amount of non-determinism needed to solve them.
We first present a method to rule out the existence of strong polynomial kernelizations of parameterized problems under the hypothesis P not equal NP. This method is applicable, for example, to the problem SAT paramet...
详细信息
ISBN:
(纸本)9783642030727
We first present a method to rule out the existence of strong polynomial kernelizations of parameterized problems under the hypothesis P not equal NP. This method is applicable, for example, to the problem SAT parameterized by the number of variables of the input formula. Then we obtain improvements of related results in [ 1,6] by refining the central lemma of their proof method, a lemma due to Fortnow and Santhanam. In particular, assuming that PH not equal Sigma(P)(3), i.e., that the polynomial hierarchy does not collapse to its third level, we show that every parameterized problem with a "linear OR" and with NP-hard underlying classical problem does not have polynomial reductions to itself that assign to every instance :e with parameter k an instance y with vertical bar y vertical bar = k(O(1)) . vertical bar x vertical bar(1-epsilon) (here epsilon is any given real number greater than zero).
We prove a parameterized analog of Schaefer's Dichotomy Theorem: we show that for every finite boolean constraint family F, deciding whether a formula containing constraints from F has a satisfying assignment of w...
详细信息
ISBN:
(纸本)0769521207
We prove a parameterized analog of Schaefer's Dichotomy Theorem: we show that for every finite boolean constraint family F, deciding whether a formula containing constraints from F has a satisfying assignment of weight exactly k is either fixed-parameter tractable (FPT) or W[1]-complete. We give a simple characterization of those constraints that make the problem fixed-parameter tractable. The special cases when the formula is restricted to be bounded occurrence, bounded treewidth, or planar are also considered: it turns out that in these cases the problem is in FPT for every constraint family F.
We present subexponential parameterized algorithms on planar graphs for a family of problems that consist in, given a graph G, finding a connected (induced) subgraph H with bounded maximum degree, while maximising the...
详细信息
Recently it has been shown that the miniaturization mapping M faithfully translates subexponential parameterized complexity into (unbounded) parameterized complexity. We determine the pre-images under M of various (cl...
详细信息
Recently it has been shown that the miniaturization mapping M faithfully translates subexponential parameterized complexity into (unbounded) parameterized complexity. We determine the pre-images under M of various (classes of) problems. For many parameterized problems whose underlying classical problem is in NP we show that the pre-images coincide with natural reparameterizations that take into account the amount of non-determinism needed to solve them.
We give machine characterizations of most parameterized complexity classes, in particular, of W[P], of the classes of the W-hierarchy, and of the A-hierarchy. For example, we characterize W[P] as the class of all para...
详细信息
We give machine characterizations of most parameterized complexity classes, in particular, of W[P], of the classes of the W-hierarchy, and of the A-hierarchy. For example, we characterize W[P] as the class of all parameterized problems decidable by a nondeterministic fixed-parameter tractable algorithm whose number of nondeterministic steps is bounded in terms of the parameter. The machine characterizations suggest the introduction of a hierarchy W-func between the W- and the A-hierarchy. We study the basic properties of this hierarchy. (c) 2005 Elsevier B.V. All rights reserved.
We present a new method of solving graph problems related to VERTEX COVER by enumerating and expanding appropriate sets of nodes. As an application, we obtain dramatically improved runtime bounds for two variants of t...
详细信息
We present a new method of solving graph problems related to VERTEX COVER by enumerating and expanding appropriate sets of nodes. As an application, we obtain dramatically improved runtime bounds for two variants of the VERTEX COVER problem. In the case of CONNECTED VERTEX COVER, we take the upper bound from O*(6k) to O*(2.7606(k)) without large hidden factors. For TREE COVER, we show a complexity of O*(3.2361(k)), improving over the previous bound of O*((2k)(k)). In the process, faster algorithms for solving subclasses of the Steiner tree problem on graphs are investigated.
MULTICUT is a fundamental network communication and connectivity problem. It is defined as: given an undirected graph and a collection of pairs of terminal vertices, find a minimum set of edges or vertices whose remov...
详细信息
MULTICUT is a fundamental network communication and connectivity problem. It is defined as: given an undirected graph and a collection of pairs of terminal vertices, find a minimum set of edges or vertices whose removal disconnects each pair. We mainly focus on the case of removing vertices, where we distinguish between allowing or disallowing the removal of terminal vertices. Complementing and refining previous results from the literature, we provide several NP-completeness and (fixed-parameter) tractability results for restricted classes of graphs such as trees, interval graphs, and graphs of bounded treewidth. (C) 2007 Elsevier B.V. All rights reserved.
We show that searching the k-change neighborhood is W[1]-hard for metric TSP, which means that finding the best tour in the k-change neighborhood essentially requires complete search (modulo some complexity-theoretic ...
详细信息
We show that searching the k-change neighborhood is W[1]-hard for metric TSP, which means that finding the best tour in the k-change neighborhood essentially requires complete search (modulo some complexity-theoretic assumptions). (c) 2007 Elsevier B.V. All rights reserved.
We study two pattern matching problems that are motivated by applications in computational biology. In the Closest Substring problem k strings s(1),..., s(k) are given, and the task is to find a string s of length L s...
详细信息
We study two pattern matching problems that are motivated by applications in computational biology. In the Closest Substring problem k strings s(1),..., s(k) are given, and the task is to find a string s of length L such that each string si has a consecutive substring of length L whose distance is at most d from s. We present two algorithms that aim to be efficient for small fixed values of d and k: for some functions f and g, the algorithms have running time f(d) center dot n(O(log d)) and g(d, k) center dot n(O(log log k)), respectively. The second algorithm is based on connections with the extremal combinatorics of hypergraphs. The Closest Substring problem is also investigated from the parameterized complexity point of view. Answering an open question from [P. A. Evans, A. D. Smith, and H. T. Wareham, Theoret. Comput. Sci., 306 (2003), pp. 407-430, M. R. Fellows, J. Gramm, and R. Niedermeier, Combinatorica, 26 (2006), pp. 141-167, J. Gramm, J. Guo, and R. Niedermeier, Lecture Notes in Comput. Sci. 2751, Springer, Berlin, 2003, pp. 195-209, J. Gramm, R. Niedermeier, and P. Rossmanith, Algorithmica, 37 (2003), pp. 25-42], we show that the problem is W[1]-hard even if both d and k are parameters. It follows as a consequence of this hardness result that our algorithms are optimal in the sense that the exponent of n in the running time cannot be improved to o(log d) or to o(log log k) (modulo some complexity-theoretic assumptions). Consensus Patterns is the variant of the problem where, instead of the requirement that each s(i) has a substring that is of distance at most d from s, we have to select the substrings in such a way that the average of these k distances is at most delta. By giving an f(delta) center dot n(9) time algorithm, we show that the problem is fixed-parameter tractable. This answers an open question from [M. R. Fellows, J. Gramm, and R. Niedermeier, Combinatorica, 26 (2006), pp. 141-167].
暂无评论