In this paper, we study the parameterized dominating set problem in chordal graphs. The goal of the problem is to determine whether a given chordal graph G = (V, E) contains a dominating set of size k or not, where k ...
详细信息
In this paper, we study the parameterized dominating set problem in chordal graphs. The goal of the problem is to determine whether a given chordal graph G = (V, E) contains a dominating set of size k or not, where k is an integer parameter. We show that the problem is W[1]-hard and it cannot be solved in time vertical bar V vertical bar(o)((root k)) unless 3SAT can be solved in subexponential time. In addition, we show that the upper bound of this problem can be improved to O(2(root k)vertical bar V vertical bar(2 root k)) when the underlying graph G is an interval graph.
In this paper we study the notion of parameterized exponential time complexity. We show that a parameterized problem can be solved in parameterized 2(o(f(k)))p(n) time if and only if it is solvable in time O(2(delta f...
详细信息
In this paper we study the notion of parameterized exponential time complexity. We show that a parameterized problem can be solved in parameterized 2(o(f(k)))p(n) time if and only if it is solvable in time O(2(delta f(k))q(n)) for any constant delta>0, where p and q are polynomials. We then illustrate how this equivalence can be used to show that special instances of parameterized NP-hard problems are as difficult as the general instances. For example, we show that the PLANAR DOMINATING SET problem on degree-3 graphs can be solved in 2(0(root k))p(n) parameterized time if and only if the general PLANAR DOMINATING SET problem can. Apart from their complexity theoretic implications, our results have some interesting algorithmic implications as well. (C) 2009 Elsevier B.V. All rights reserved.
We study the parameterized complexity of four variants of pursuit-evasion on graphs: SEEDED PURSUIT EVASION, SHORT SEEDED PURSUIT EVASION, DIRECTED PURSUIT EVASION and SHORT DIRECTED PURSUIT EVASION. Both SEEDED PURSU...
详细信息
We study the parameterized complexity of four variants of pursuit-evasion on graphs: SEEDED PURSUIT EVASION, SHORT SEEDED PURSUIT EVASION, DIRECTED PURSUIT EVASION and SHORT DIRECTED PURSUIT EVASION. Both SEEDED PURSUIT EVASION and SHORT SEEDED PURSUIT EVASION are played on undirected graphs with given starting positions for both the cops and the robber. DIRECTED PURSUIT EVASION and its short variant are played on directed graphs, with the players free to choose their starting positions. We show for SEEDED PURSUIT EVASION and DIRECTED PURSUIT EVASION that finding a winning strategy for the cops is AW[*]-hard when we parameterize by the number of cops. Further, we show that the short (k-move) variants of these problems (SHORT SEEDED PURSUIT EVASION and SHORT DIRECTED PURSUIT EVASION) are AM[*]-complete when we parameterize by both the number of cops and turns. (C) 2010 Elsevier B.V. All rights reserved.
Given a set L of labels and a collection of rooted trees whose leaves are bijectively labeled by some elements of L, the Maximum Agreement Supertree (SMAST) problem is given as follows: find a tree T on a largest labe...
详细信息
Given a set L of labels and a collection of rooted trees whose leaves are bijectively labeled by some elements of L, the Maximum Agreement Supertree (SMAST) problem is given as follows: find a tree T on a largest label set L' subset of L that homeomorphically contains every input tree restricted to L'. The problem has phylogenetic applications to infer supertrees and perform tree congruence analyses. In this paper, we focus on the parameterized complexity of this NP-hard problem, considering different combinations of parameters as well as particular cases. We show that SMAST on k rooted binary trees on a label set of size n can be solved in O((8n)(k)) time, which is an improvement with respect to the previously known O(n(3k2)) time algorithm. In this case, we also give an O((2k)(p)kn(2)) time algorithm, where p is an upper bound on the number of leaves of L missing in a SMAST solution. This shows that SMAST can be solved efficiently when the input trees are mostly congruent. Then, for the particular case where any triple of leaves is contained in at least one input tree, we give O(4(p)n(3)) and O(3.12(p) + n(4)) time algorithms, obtaining the first fixed-parameter tractable algorithms on a single parameter for this problem. We also obtain intractability results for several combinations of parameters, thus indicating that it is unlikely that fixed-parameter tractable algorithms can be found in these particular cases.
We initiate the first systematic study of the NP-hard CLUSTER VERTEX DELETION (CVD) problem (unweighted and weighted) in terms of fixed-parameter algorithmics. In the unweighted case, one searches for a minimum number...
详细信息
We initiate the first systematic study of the NP-hard CLUSTER VERTEX DELETION (CVD) problem (unweighted and weighted) in terms of fixed-parameter algorithmics. In the unweighted case, one searches for a minimum number of vertex deletions to transform a graph into a collection of disjoint cliques. The parameter is the number of vertex deletions. We present efficient fixed-parameter algorithms for CVD applying the fairly new iterative compression technique. Moreover, we study the variant of CVD where the maximum number of cliques to be generated is pre-specified. Here, we exploit connections to fixed-parameter algorithms for (weighted) VERTEX COVER.
We show that Edge Dominating Set, Hamiltonian Cycle, and Graph Coloring are W[1]-hard parameterized by clique-width. It was an open problem, explicitly mentioned in several papers, whether any of these problems is fix...
详细信息
We show that Edge Dominating Set, Hamiltonian Cycle, and Graph Coloring are W[1]-hard parameterized by clique-width. It was an open problem, explicitly mentioned in several papers, whether any of these problems is fixed parameter tractable when parameterized by the clique-width, that is, solvable in time g(k) . n(O(1)) on n-vertex graphs of clique-width k, where g is some function of k only. Our results imply that the running time O(n(f(k))) of many clique-width-based algorithms is essentially the best we can hope for (up to a widely believed assumption from parameterized complexity, namely FPT not equal W[1]).
In the d-dimensional (vector) knapsack problem given is a set of items, each having a d-dimensional size vector and a profit, and a d-dimensional bin. The goal is to select a subset of the items of maximum total profi...
详细信息
In the d-dimensional (vector) knapsack problem given is a set of items, each having a d-dimensional size vector and a profit, and a d-dimensional bin. The goal is to select a subset of the items of maximum total profit such that the sum of all vectors is bounded by the bin capacity in each dimension. It is well known that, unless P = NP, there is no fully polynomial-time approximation scheme for d-dimensional knapsack, already for d = 2. The best known result is a polynomial-time approximation scheme (PEAS) due to Frieze and Clarke [A.M. Frieze, M. Clarke, Approximation algorithms for the m-dimensional 0-1 knapsack problem: worst-case and probabilistic analyses, European J. Operat. Res. 15 (1) (1984) 100-109] for the case where d >= 2 is some fixed constant. A fundamental open question is whether the problem admits an efficient PEAS (EPTAS). In this paper we resolve this question by showing that there is no EPTAS for d-dimensional knapsack, already for d = 2, unless W[1] = FPT. Furthermore, we show that unless all problems in SNP are solvable in sub-exponential time, there is no approximation scheme for two-dimensional knapsack whose running time is f(1/epsilon)vertical bar I vertical bar(0(root 1/epsilon)), for any function f. Together, the two results suggest that a significant improvement over the running time of the scheme of Frieze and Clarke is unlikely to exist. (C) 2010 Elsevier B.V. All rights reserved.
The classes of the W-hierarchy are the most important classes of intractable problems in parameterized complexity. These classes were originally defined via the weighted satisfiability problem for Boolean circuits. He...
详细信息
The classes of the W-hierarchy are the most important classes of intractable problems in parameterized complexity. These classes were originally defined via the weighted satisfiability problem for Boolean circuits. Here, besides the Boolean connectives we consider connectives such as majority, not-all-equal, and unique. For example, a gate labelled by the majority connective outputs TRUE if more than half of its inputs are TRUE. For any finite set C of connectives we construct the corresponding W(C)-hierarchy. We derive some general conditions which guarantee that the W-hierarchy and the W(C)-hierarchy coincide levelwise. If C only contains the majority connective then the first levels of the hierarchies coincide. We use this to show that a variant of the parameterized vertex cover problem, the majority vertex cover problem, is W[1]-complete.
We consider the constraint satisfaction problem (CSP) parameterized by the treewidth of primal, dual, and incidence graphs, combined with several other basic parameters such as domain size and arity. We determine all ...
详细信息
We consider the constraint satisfaction problem (CSP) parameterized by the treewidth of primal, dual, and incidence graphs, combined with several other basic parameters such as domain size and arity. We determine all combinations of the considered parameters that admit fixed-parameter tractability. (C) 2009 Elsevier Inc. All rights reserved.
We divide a string into k segments, each with only one sort of symbols, so as to minimize the total number of exceptions. Motivations come from machine learning and data mining. For binary strings we develop a linear-...
详细信息
We divide a string into k segments, each with only one sort of symbols, so as to minimize the total number of exceptions. Motivations come from machine learning and data mining. For binary strings we develop a linear-time algorithm for any k. Key to efficiency is a special-purpose data structure, called W-tree, which reflects relations between repetition lengths of symbols. For non-binary strings we give a nontrivial dynamic programming algorithm. Our problem is equivalent to finding weighted independent sets with certain size constraints, either in paths (binary case) or special interval graphs (general case). We also show that this problem is FPT in bounded-degree graphs.
暂无评论