We study variants and generalizations of the problem of finding an r-regular subgraph (where r ≤ 3) in a given graph by deleting at most k vertices. Moser and Thilikos (2006) have shown that the problem is fixed-para...
详细信息
ISBN:
(纸本)9781920682583
We study variants and generalizations of the problem of finding an r-regular subgraph (where r ≤ 3) in a given graph by deleting at most k vertices. Moser and Thilikos (2006) have shown that the problem is fixed-parameter tractable (FPT) if parameterized by (k, r). They asked whether the problem remains fixed-parameter tractable if parameterized by k alone. We answer this question negatively: we show that if parameterized by k alone the problem is W[1]-hard and therefore very unlikely fixed-parameter tractable. We also give W[1]-hardness results for variants of the problem where the parameter is the number of vertex and edge deletions allowed, and for a new generalized form of the problem where the obtained subgraph is not necessarily regular but its vertices have certain prescribed degrees. Following this we demonstrate fixed-parameter tractability for the considered problems if the parameter includes the regularity r or an upper bound on the prescribed degrees in the generalized form of the problem. These FPT results are obtained via kernelization, so also provide a practical approach to the problems presented.
A circle graph is the intersection graph of a set of chords in a circle. Keil [Discrete Applied Mathematics, 42(1):51-63, 1993] proved that Dominating Set, Connected Dominating Set, and Total Dominating Set are NP-com...
详细信息
ISBN:
(纸本)9783642346118;9783642346101
A circle graph is the intersection graph of a set of chords in a circle. Keil [Discrete Applied Mathematics, 42(1):51-63, 1993] proved that Dominating Set, Connected Dominating Set, and Total Dominating Set are NP-complete in circle graphs. To the best of our knowledge, nothing was known about the parameterized complexity of these problems in circle graphs. In this paper we prove the following results, which contribute in this direction: Dominating Set, Independent Dominating Set, Connected Dominating Set, Total Dominating Set, and Acyclic Dominating Set are W[1]-hard in circle graphs, parameterized by the size of the solution. Whereas both Connected Dominating Set and Acyclic Dominating Set are W[1]-hard in circle graphs, it turns out that Connected Acyclic Dominating Set is polynomial-time solvable in circle graphs. If T is a given tree, deciding whether a circle graph has a dominating set isomorphic to T is NP-complete when T is in the input, and FPT when parameterized by vertical bar V(T)vertical bar. We prove that the FPT algorithm is subexponential.
In this Letter, we consider the parameterized complexity of the following problem: Given a hereditary property P on digraphs, an input digraph D and a positive integer k, does D have an induced subdigraph on k vertice...
详细信息
In this Letter, we consider the parameterized complexity of the following problem: Given a hereditary property P on digraphs, an input digraph D and a positive integer k, does D have an induced subdigraph on k vertices with property P? We completely characterize hereditary properties for which this induced subgraph problem is W[1]-complete for two classes of directed graphs: general directed graphs and oriented graphs. We also characterize those properties for which the induced subgraph problem is,W[l]-complete for general directed graphs but fixed parameter tractable for oriented graphs. These results are among the very few parameterized complexity results on directed graphs. (c) 2007 Elsevier B.V. All rights reserved.
Let C denote one of the complexity classes "polynomial time," "logspace," or "nondeterministic logspace." We introduce a logic L(C)(inv) and show generalizations and variants of the equiv...
详细信息
Let C denote one of the complexity classes "polynomial time," "logspace," or "nondeterministic logspace." We introduce a logic L(C)(inv) and show generalizations and variants of the equivalence (L(C)(inv) captures C if and only if there is an almost C-optimal algorithm in C for the set TAUT of tautologies of propositional logic.) These statements are also equivalent to the existence of a listing of subsets in C of TAUT by corresponding Turing machines and equivalent to the fact that a certain parameterized halting problem is in the parameterized complexity class XCuni.
This work introduces two new parameterizations of graph problems generalizing vertex cover which fill part of the space between vertex cover and clique width in the hierarchy of graf parameterizations. We also study p...
详细信息
This work introduces two new parameterizations of graph problems generalizing vertex cover which fill part of the space between vertex cover and clique width in the hierarchy of graf parameterizations. We also study parameterized complexity of Hamiltonian path and cycle, vertex coloring, precoloring extension and equitable coloring parameterized by these two parameterizations. With the exception of precoloring extension which is W[1]-hard in one case, all the other problems listed above are tractable for both parameterizations. The boundary between tractability and intractability of these problems can therefore be moved closer to parameterization by clique width.
One of Courcelle's celebrated results states that if C is a class of graphs of bounded tree-width, then model-checking for monadic second order logic (MSO2) is fixed-parameter tractable (fpt) on C by linear time p...
详细信息
One of Courcelle's celebrated results states that if C is a class of graphs of bounded tree-width, then model-checking for monadic second order logic (MSO2) is fixed-parameter tractable (fpt) on C by linear time parameterized algorithms, where the parameter is the tree-width plus the size of the formula. An immediate question is whether this is best possible or whether the result can be extended to classes of unbounded tree-width. In this paper we show that in terms of tree-width, the theorem cannot be extended much further. More specifically, we show that if C is a class of graphs which is closed under colourings and satisfies certain constructibility conditions and is such that the tree-width of C is not bounded by log(84) n then MSO2-model checking is not fpt unless Sat can be solved in sub-exponential time. If the tree-width of C is not poly-logarithmically bounded, then MSO2-model checking is not fpt unless all problems in the polynomial-time hierarchy can be solved in sub-exponential time.
Given an undirected graph G = (V, E), the (uniform, unweighted) sparsest cut problem is to find a vertex subset S subset of V minimizing vertical bar E(S, (S) over bar)vertical bar/(vertical bar S vertical bar vertica...
详细信息
Given an undirected graph G = (V, E), the (uniform, unweighted) sparsest cut problem is to find a vertex subset S subset of V minimizing vertical bar E(S, (S) over bar)vertical bar/(vertical bar S vertical bar vertical bar(S) over bar vertical bar). We show that this problem is NP-complete, and give polynomial time algorithms for various graph classes. In particular, we show that the sparsest cut problem can be solved in linear time for unit interval graphs, and in cubic time for graphs of bounded treewidth. For cactus graphs and outerplanar graphs this can be improved to linear time and quadratic time, respectively. For graphs of clique-width k for which a short decomposition is given, we show that the problem can be solved in time O(n(2k+1)), where n is the number of vertices in the input graph. We also establish that a running time of the form n(O(k)) is optimal in this case, assuming that the Exponential Time Hypothesis holds. (C) 2012 Elsevier B.V. All rights reserved.
We provide a new characterization of the NP-hard arc routing problem Rural Postman in terms of a constrained variant of minimum-weight perfect matching on bipartite graphs. To this end, we employ a parameterized equiv...
详细信息
We provide a new characterization of the NP-hard arc routing problem Rural Postman in terms of a constrained variant of minimum-weight perfect matching on bipartite graphs. To this end, we employ a parameterized equivalence between Rural Postman and Eulerian Extension, a natural arc addition problem in directed multigraphs. We indicate the NP-hardness of the introduced matching problem. In particular, we use the matching problem to make partial progress towards answering the open question about the parameterized complexity of Rural Postman with respect to the parameter " number of weakly connected components in the graph induced by the required arcs". This is a more than thirty years open and long-neglected question with significant practical relevance. (C) 2012 Elsevier B.V. All rights reserved.
A general framework for parameterized proof complexity was introduced by Dantchev et al. [2007]. There, the authors show important results on tree-like parameterized Resolution-a parameterized version of classical Res...
详细信息
A general framework for parameterized proof complexity was introduced by Dantchev et al. [2007]. There, the authors show important results on tree-like parameterized Resolution-a parameterized version of classical Resolution-and their gap complexity theorem implies lower bounds for that system. The main result of this article significantly improves upon this by showing optimal lower bounds for a parameterized version of bounded-depth Frege. More precisely, we prove that the pigeonhole principle requires proofs of size n(Omega(k)) in parameterized bounded-depth Frege, and, as a special case, in dag-like parameterized Resolution. This answers an open question posed in Dantchev et al. [2007]. In the opposite direction, we interpret a well-known technique for FPT algorithms as a DPLL procedure for parameterized Resolution. Its generalization leads to a proof search algorithm for parameterized Resolution that in particular shows that tree-like parameterized Resolution allows short refutations of all parameterized contradictions given as bounded-width CNFs.
We establish a close connection between (sub) exponential time complexity and parameterized complexity by proving that the so-called miniaturization mapping is a reduction preserving isomorphism between the two theories.
We establish a close connection between (sub) exponential time complexity and parameterized complexity by proving that the so-called miniaturization mapping is a reduction preserving isomorphism between the two theories.
暂无评论