We propose a general proof technique based on the Turing machine halting problem that allows us to establish membership results for the classes W[1], W[2], and W[P]. Using this technique, we prove that Perfect Code be...
详细信息
We propose a general proof technique based on the Turing machine halting problem that allows us to establish membership results for the classes W[1], W[2], and W[P]. Using this technique, we prove that Perfect Code belongs to W[l], Steiner Tree belongs to W[2], and alpha-Balanced Separator, Maximal Irredundant Set, and Bounded DFA Intersection belong to W[P]. (C) 2003 Elsevier Science (USA). All rights reserved.
We prove a (m/delta)(O(kappa)) (.) n(a) time bound for finding minimum solutions S-min of FEATURE SET problems, where n is the total size of a given FEATURE SET problem, K <= vertical bar S-min vertical bar, m equa...
详细信息
We prove a (m/delta)(O(kappa)) (.) n(a) time bound for finding minimum solutions S-min of FEATURE SET problems, where n is the total size of a given FEATURE SET problem, K <= vertical bar S-min vertical bar, m equals the number of non-target features, a is a (relatively small) constant, and 1 - delta is the confidence that the solution is of minimum length. In terms of parameterized complexity of NP-complete problems, our time bound differs from an FPT-type bound by the factor m(O(kappa)) for fixed delta. The algorithm is applied to a prominent microarray dataset: The classification of gene-expression data related to acute myeloid leukaemia (AML) and acute lymphoblastic leukaemia (ALL). From the set of potentially significant features calculated by the algorithm we can identify three genes (D88422, M92287, L09209) that produce zero errors on the test set by using a simple, straightforward evaluation procedure (performing the test on the single gene M84526 produces only one error). (c) 2006 Elsevier Inc. All rights reserved.
A feedback vertex set (fvs) of a graph is a set of vertices whose removal results in an acyclic graph. We show that if an undirected graph on n vertices with minimum degree at least 3 has a fvs on at most 1/3n(1-epsil...
详细信息
A feedback vertex set (fvs) of a graph is a set of vertices whose removal results in an acyclic graph. We show that if an undirected graph on n vertices with minimum degree at least 3 has a fvs on at most 1/3n(1-epsilon) vertices, then there is a cycle of length at most 6/epsilon (for epsilon >= 1/2, we can even improve this to just 6). Using this, we obtain a O (( 12 logk/log log + 6)(k) n(omega)) algorithm for testing whether an undirected graph on n vertices has a fvs of size at most k. Here n(omega) is the complexity of the best matrix multiplication algorithm. The previous best parameterized algorithm for this problem took O ((2k + 1)(k) n(2)) time. We also investigate the fixed parameter complexity of weighted feedback vertex set problem in weighted undirected graphs.
In model checking, the state-explosion problem occurs when one checks a nonflat system, i.e., a system implicitly described as a synchronized product of elementary subsystems. In this paper, we investigate the complex...
详细信息
In model checking, the state-explosion problem occurs when one checks a nonflat system, i.e., a system implicitly described as a synchronized product of elementary subsystems. In this paper, we investigate the complexity of a wide variety of model-checking problems for nonflat systems under the light of parameterized complexity, taking the number of synchronized components as a parameter. We provide precise complexity measures (in the parameterized sense) for most of the problems we investigate, and evidence that the results are robust. (C) 2006 Elsevier Inc. All rights reserved.
In this paper we consider the problem of testing an arbitrary digraph G = (V, E) for upward planarity. In particular we describe two fixed-parameter tractable algorithms for testing the upward planarity of G. The firs...
详细信息
In this paper we consider the problem of testing an arbitrary digraph G = (V, E) for upward planarity. In particular we describe two fixed-parameter tractable algorithms for testing the upward planarity of G. The first algorithm that we present can test the upward planarity of G in 0(2(t) (.) t! (.) vertical bar V vertical bar(2))-time where t is the number of triconnected components of G. The second algorithm that we present uses a standard technique known as kernelisation and can test the upward planarity of G in O(vertical bar V vertical bar(2) + k(4) (.) (2k)!)-time, where k = vertical bar E vertical bar - vertical bar V vertical bar.
parameterized complexity has, so far, been largely confined to consideration of computational problems as decision or search problems. However, it is becoming evident that the parameterized point of view can lead to n...
详细信息
parameterized complexity has, so far, been largely confined to consideration of computational problems as decision or search problems. However, it is becoming evident that the parameterized point of view can lead to new insight into counting problems. The goal of this article is to introduce a formal framework in which one may consider parameterized counting problems. (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...
详细信息
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 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...
详细信息
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.
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 ...
详细信息
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.
暂无评论