We study the parameterized complexity of the pseudo-achromatic number problem: Given an undirected graph and a parameter k, determine if the graph can be partitioned into k, groups such that every two groups are conne...
详细信息
ISBN:
(纸本)9783540922476
We study the parameterized complexity of the pseudo-achromatic number problem: Given an undirected graph and a parameter k, determine if the graph can be partitioned into k, groups such that every two groups are connected by at least one edge. This problem has been extensively studied in graph theory and combinatorial optimization. We show that the problem has a kernel of at most (k-2) (k+1) vertices that is constructable in time O(m root n), where n and m are the number of vertices and edges, respectively, in the graph, and k is the parameter. This directly implies that the problem is fixed-parameter tractable. We also study generalizations of the problem and show that they are parameterized intractable.
Smooth 4-regular hamiltonian graphs are generalizations of cycle plus triangles graphs. It has been shown that both the independent set and 3-colorability problems are NP-Complete in this class of graphs. In this pape...
详细信息
Smooth 4-regular hamiltonian graphs are generalizations of cycle plus triangles graphs. It has been shown that both the independent set and 3-colorability problems are NP-Complete in this class of graphs. In this paper we show that these problems are fixed parameter tractable if we choose the number of inner cycles as parameter.
The OR-SAT problem asks, given Boolean formulae phi(1), ... , phi(m) each of size at most n, whether at least one of the phi(i)'s is satisfiable. We show that there is no reduction from OR-SAT to any set A where t...
详细信息
ISBN:
(纸本)9781605580470
The OR-SAT problem asks, given Boolean formulae phi(1), ... , phi(m) each of size at most n, whether at least one of the phi(i)'s is satisfiable. We show that there is no reduction from OR-SAT to any set A where the length of the output is bounded by a polynomial in n, unless NP subset of coNP/poly, and the Polynomial-Time Hierarchy collapses. This result settles an open problem proposed by Bodlaender et. al. [4] and Harnik and Naor [15] and has a number of implications. A number of parametric NP problems, including Satisfiability, Clique, Dominating Set and Integer Programming, are not instance compressible or polynomially kernelizable unless NP subset of coNP/poly. Satisfiability does not have PCPs of size polynomial in the number of variables unless NP subset of coNP/poly. An approach of Harnik and Naor to constructing collision-resistant hash functions from one-way functions is unlikely to be viable in its present form. (Buhrman-Hitchcock) There are no subexponential-size hard sets for NP unless NP is in co-NP/poly. We also study probabilistic variants of compression, and show various results about and connections between these variants. To this end, we introduce a new strong derandomization hypothesis, the Oracle Derandomization Hypothesis, and discuss how it relates to traditional derandomization assumptions.
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...
详细信息
ISBN:
(纸本)3540341668
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.
Given a string s on an alphabet Sigma, a word-length k and a budget D, we want to determine the smallest number of distinct k-mers that can be left in s, if we are allowed to replace up to D letters of s. This problem...
详细信息
ISBN:
(纸本)8001035336
Given a string s on an alphabet Sigma, a word-length k and a budget D, we want to determine the smallest number of distinct k-mers that can be left in s, if we are allowed to replace up to D letters of s. This problem has several parameters, and we discuss its complexity under all sorts of restrictions on the parameters values. We prove that some versions of the problem axe polynomial, while others are NP-hard. We also introduce some Integer Programming formulations to model the NP-hard cases.
We place our focus on the gap between treewidth's success in producing fixed-parameter polynomial algorithms for hard graph problems, and specifically HAMILTONIAN CIRCUIT and MAX CUT, and the failure of its direct...
详细信息
ISBN:
(纸本)9783540921813
We place our focus on the gap between treewidth's success in producing fixed-parameter polynomial algorithms for hard graph problems, and specifically HAMILTONIAN CIRCUIT and MAX CUT, and the failure of its directed variants (directed tree-width [9], DAG-width [11] and kelly-width [8]) to replicate it in the realm of digraphs. We answer the question of why this gap exists by giving two hardness results: we show that DIRECTED HAMILTONIAN CIRCUIT is W[2]-hard when the parameter is the width of the input graph, for any of these widths, and that MAX DI CUT remains NP-hard even when restricted to DAGs, which have the minimum possible width under all these definitions. Our results also apply to directed pathwidth.
The Cops and Robbers game is played oil undirected graphs where a group of cops tries to catch a robber. The game was defined independently by Winkler-Nowakowski and Quilliot in the 1980s and since that time has been ...
详细信息
ISBN:
(纸本)9780387096797
The Cops and Robbers game is played oil undirected graphs where a group of cops tries to catch a robber. The game was defined independently by Winkler-Nowakowski and Quilliot in the 1980s and since that time has been studied intensively. Despite of that, its computation complexity is still all open question. In this paper we prove that computing the minimum number of cops that can catch a robber oil a given graph is NP-hard. Also we show that the parameterized version of the problem is W[2]-hard. Our proof call be extended to the variant of the game where the robber call move s times faster than cops. We also provide a number of algorithmic and complexity results oil classes of chordal graphs and oil graphs of bounded cliquewidth. For example, we show that when the velocity of the robber is twice cop's velocity, the problem is NP-hard oil split graphs, while it is polynomial time solvable oil split graphs when players posses the same speed. Finally, we establish that oil graphs of bounded cliquewidth (this class of graphs contains, for example, graphs of bounded treewidth), the problem is solvable in polynomial time in the case the robber's speed is at most twice the speed of cops.
We discuss general techniques, centered around the "Layerwise Separation Property" (LSP) of a planar graph problem, that allow to develop algorithms with running time c(rootk)\G\, given an instance G of a pr...
详细信息
We discuss general techniques, centered around the "Layerwise Separation Property" (LSP) of a planar graph problem, that allow to develop algorithms with running time c(rootk)\G\, given an instance G of a problem on planar graphs with parameter k. Problems having LSP include PLANAR VERTEX COVER, PLANAR INDEPENDENT SET, and PLANAR DOMINATING SET. Extensions of our speed-up technique to basically all fixed-parameter tractable planar graph problems are also exhibited. Moreover, we relate, e.g., the domination number or the vertex cover number, with the treewidth of a plane graph. (C) 2004 Elsevier Inc. All rights reserved.
We demonstrate hardness results for the detection of small backdoor sets with respect to base classesMrof CNF formulas with maximum deficiency⩽r(M0is the class of matched formulas). One of the results applies also to ...
详细信息
We demonstrate hardness results for the detection of small backdoor sets with respect to base classes
M
r
of CNF formulas with maximum deficiency
⩽
r
(
M
0
is the class of matched formulas). One of the results applies also to a wide range of base classes with added ‘empty clause detection’ as recently considered by Dilkina, Gomes, and Sabharwal. We obtain the hardness results in the framework of parameterized complexity, considering the upper bound on the size of smallest backdoor sets as the parameter. Furthermore we compare the generality of the parameters maximum deficiency and the size of a smallest
M
r
-backdoor set.
We study the consistency problem for extended global cardinality (EGC) constraints. An EGC constraint consists of a set X of variables, a set D of values, a domain D(x) ⊆ D for each variable x, and a "cardinality...
详细信息
ISBN:
(纸本)9781920682583
We study the consistency problem for extended global cardinality (EGC) constraints. An EGC constraint consists of a set X of variables, a set D of values, a domain D(x) ⊆ D for each variable x, and a "cardinality set" K(d) of non-negative integers for each value d. The problem is to instantiate each variable x with a value in D(x) such that for each value d, the number of variables instantiated with d belongs to the cardinality set K(d). It is known that this problem is NP-complete in general, but solvable in polynomial time if all cardinality sets are *** we pinpoint connections between EGC constraints and general factors in graphs. This allows us to extend the known polynomial-time case to certain non-interval cardinality *** we consider EGC constraints under restrictions in terms of the treewidth of the value graph (the bipartite graph representing variable-value pairs) and the cardinality-width (the largest integer occurring in the cardinality sets). We show that EGC constraints can be solved in polynomial time for instances of bounded treewidth, where the order of the polynomial depends on the treewidth. We show that (subject to the complexity theoretic assumption FPT ≠ W[1]) this dependency cannot be avoided without imposing additional restrictions. If, however, also the cardinality-width is bounded, this dependency gets removed and EGC constraints can be solved in linear time.
暂无评论