In the precoloring extension problem (PREXT) a graph is given with some of the vertices having preassigned colors and it has to be decided whether this coloring can be extended to a proper coloring of the graph with t...
详细信息
In the precoloring extension problem (PREXT) a graph is given with some of the vertices having preassigned colors and it has to be decided whether this coloring can be extended to a proper coloring of the graph with the given number of colors. Two parameterized versions of the problem are studied in the paper: either the number of precolored vertices or the number of colors used in the precoloring is restricted to be at most k. We show that for chordal graphs these problems are polynornial-time solvable for every fixed k, but W[1]-hard if k is the parameter. For a graph class F, let F- + ke (resp., F + kv) denote those graphs that can be made to be a member of F by deleting at most k edges (resp., vertices). We investigate the connection between PREXT in F (with the two parameters defined above) and the coloring of F- + ke, F- + kv graphs (with k being the parameter). Answering an open question of Leizhen Cai [parameterized complexity of vertex colouring, Discrete Appl. Math. 127 (2003) 415-4291, we show that coloring chordal+ke graphs is fixed-parameter tractable. (c) 2005 Elsevier B.V. All rights reserved.
We consider the parameterized problems of whether a given set of clauses can be refuted within k resolution steps, and whether a given set of clauses contains an unsatisfiable subset of size at most k. We show that bo...
详细信息
We consider the parameterized problems of whether a given set of clauses can be refuted within k resolution steps, and whether a given set of clauses contains an unsatisfiable subset of size at most k. We show that both problems are complete for the class W[1], the first level of the W-hierarchy of fixed-parameter intractable problems. Our results remain true if restricted to 3-SAT instances and/or to various restricted versions of resolution including tree-like resolution, input resolution, and read-once resolution. Applying a metatheorem of Frick and Grohe, we show that, restricted to classes of sets of clauses of locally bounded treewidth, the considered problems are fixed-parameter tractable. For example, the problems are fixed-parameter tractable for planar CNF formulas. (c) 2005 Elsevier B.V. All rights reserved.
In the precoloring extension problem (PREXT) a graph is given with some of the vertices having preassigned colors and it has to be decided whether this coloring can be extended to a proper coloring of the graph with t...
详细信息
ISBN:
(纸本)9783540230717
In the precoloring extension problem (PREXT) a graph is given with some of the vertices having preassigned colors and it has to be decided whether this coloring can be extended to a proper coloring of the graph with the given number of colors. Two parameterized versions of the problem are studied in the paper: either the number of precolored vertices or the number of colors used in the precoloring is restricted to be at most k. We show that for chordal graphs these problems are polynornial-time solvable for every fixed k, but W[1]-hard if k is the parameter. For a graph class F, let F- + ke (resp., F + kv) denote those graphs that can be made to be a member of F by deleting at most k edges (resp., vertices). We investigate the connection between PREXT in F (with the two parameters defined above) and the coloring of F- + ke, F- + kv graphs (with k being the parameter). Answering an open question of Leizhen Cai [parameterized complexity of vertex colouring, Discrete Appl. Math. 127 (2003) 415-4291, we show that coloring chordal+ke graphs is fixed-parameter tractable. (c) 2005 Elsevier B.V. All rights reserved.
We study parameterized enumeration problems where we are interested in all solutions of limited size rather than just some solution of minimum cardinality. (Actually, we have to enumerate the inclusion-minimal solutio...
详细信息
ISBN:
(纸本)9783540230717
We study parameterized enumeration problems where we are interested in all solutions of limited size rather than just some solution of minimum cardinality. (Actually, we have to enumerate the inclusion-minimal solutions in order to get fixed-parameter tractable (FPT) results.) Two novel concepts are the notion of a full kernel that contains all small solutions and implicit enumeration of solutions in form of compressed descriptions. In particular, we study combinatorial and computational bounds for the transversal hypergraph (vertex covers in graphs is a special case), restricted to hyperedges with at most k elements. As an example, we apply the results and further special-purpose techniques to almost-perfect phylogeny reconstruction, a problem in computational biology. (c) 2005 Elsevier B.V. All rights reserved.
The parameterized feedback vertex (arc) set problem is to find whether there are k vertices (arcs) in a given graph whose removal makes the graph acyclic. The parameterized complexity of this problem in general direct...
详细信息
The parameterized feedback vertex (arc) set problem is to find whether there are k vertices (arcs) in a given graph whose removal makes the graph acyclic. The parameterized complexity of this problem in general directed graphs is a long standing open problem. We investigate the problems on tournaments, a well studied class of directed graphs. We consider both weighted and unweighted versions. We also address the parametric dual problems which are also natural optimization problems. We show that they are fixed parameter tractable not just in tournaments but in oriented directed graphs (where there is at most one directed arc between a pair of vertices). More specifically, the dual problem we show fixed parameter tractable are: Given an oriented directed graph, is there a subset of k Vertices (arcs) that forms an acyclic directed subgraph of the graph? Our main results include: circle an O((2.4143)(k)n(omega) 1 algorithm for weighted feedback vertex set problem, and an O((2.415)(k)n(omega) algorithm for weighted feedback arc set problem in tournaments;circle an O((e2(k)/k)(k)k(2) + min{n lg n, n(2)}) algorithm for the dual of feedback vertex set problem (maxi m u m vertex i nd uced acycl ic graph) in oriented directed graphs, and an O(4(k)k + m) algorithm for the dual of feedback arc set problem (maximum arc induced acyclic graph) in general directed graphs. We also show that the dual of feedback vertex set is W[1]-hard in general directed graphs and the feedback arc set problem is fixed parameter tractable in dense directed graphs. Our results are the first non-trivial results for these problems. (c) 2005 Elsevier B.V. All rights reserved.
作者：
Haas, RHoffmann, METH
Inst Theoret Comp Sci CH-8092 Zurich Switzerland IBM Res GmbH
Zurich Res Lab CH-8803 Ruschlikon Switzerland
Consider the following problem, which we call "Chordless path through three vertices" or CP3v, for short: Given a simple undirected graph G = (V, E), a positive integer k, and three distinct vertices s, t, a...
详细信息
ISBN:
(纸本)9783540230717
Consider the following problem, which we call "Chordless path through three vertices" or CP3v, for short: Given a simple undirected graph G = (V, E), a positive integer k, and three distinct vertices s, t, and V is an element of V, is there a chordless path of length at most k from s via v to t in G? In a chordless path, no two vertices are connected by an edge that is not in the path. Alternatively, one could say that the subgraph induced by the vertex set of the path in G is the path itself. The problem has arisen in the context of service deployment in communication networks. We resolve the parametric complexity of Cp3v by proving it W[l]-complete with respect to its natural parameter k. Our reduction extends to a number of related problems about chordless paths and cycles. In particular, deciding on the existence of a single directed chordless (s, t)-path in a digraph is also W[l]-complete with respect to the length of the path. (c) 2005 Published by Elsevier B.V.
We consider parameterized problems where some separation property has to be achieved by deleting as few vertices as possible. The following five problems are studied: delete k vertices such that (a) each of the given ...
详细信息
ISBN:
(纸本)9783540230717
We consider parameterized problems where some separation property has to be achieved by deleting as few vertices as possible. The following five problems are studied: delete k vertices such that (a) each of the given l terminals is separated from the others, (b) each of the given C pairs of terminals is separated, (c) exactly e vertices are cut away from the graph, (d) exactly e connected vertices are cut away from the graph, (e) the graph is separated into at least l components. We show that if both k and l are parameters, then (a), (b) and (d) are fixed-parameter tractable, while (c) and (e) are W[1]-hard. (c) 2005 Elsevier B.V. All rights reserved.
We consider the parameterized problems of whether a given set of clauses can be refuted within k resolution steps, and whether a given set of clauses contains an unsatisfiable subset of size at most k. We show that bo...
详细信息
ISBN:
(纸本)9783540230717
We consider the parameterized problems of whether a given set of clauses can be refuted within k resolution steps, and whether a given set of clauses contains an unsatisfiable subset of size at most k. We show that both problems are complete for the class W[1], the first level of the W-hierarchy of fixed-parameter intractable problems. Our results remain true if restricted to 3-SAT instances and/or to various restricted versions of resolution including tree-like resolution, input resolution, and read-once resolution. Applying a metatheorem of Frick and Grohe, we show that, restricted to classes of sets of clauses of locally bounded treewidth, the considered problems are fixed-parameter tractable. For example, the problems are fixed-parameter tractable for planar CNF formulas. (c) 2005 Elsevier B.V. All rights reserved.
We consider the parameterized complexity of the following problem under the framework introduced by Downey and Fellows: Given a graph G, an integer parameter k and a nontrivial hereditary property Pi, are there k vert...
详细信息
We consider the parameterized complexity of the following problem under the framework introduced by Downey and Fellows: Given a graph G, an integer parameter k and a nontrivial hereditary property Pi, are there k vertices of G that induce a subgraph with property Pi? This problem has been proved NP-hard by Lewis and Yarmakakis. We show that if Pi includes all trivial graphs but not all complete graphs or vice versa, then the problem is complete for the parameterized class W[1] and is fixed parameter tractable other-wise. Our proofs of both the tractability and hardness involve nontrivial use of the theory of Ramsey numbers. (C) 2002 Elsevier Science B.V. All rights reserved.
We consider the parameterized complexity of the following problem under the framework introduced by Downey and Fellows: Given a graph G, an integer parameter k and a nontrivial hereditary property Pi, are there k vert...
详细信息
We consider the parameterized complexity of the following problem under the framework introduced by Downey and Fellows: Given a graph G, an integer parameter k and a nontrivial hereditary property Pi, are there k vertices of G that induce a subgraph with property Pi? This problem has been proved NP-hard by Lewis and Yarmakakis. We show that if Pi includes all trivial graphs but not all complete graphs or vice versa, then the problem is complete for the parameterized class W[1] and is fixed parameter tractable other-wise. Our proofs of both the tractability and hardness involve nontrivial use of the theory of Ramsey numbers. (C) 2002 Elsevier Science B.V. All rights reserved.
暂无评论