We consider GROUP CONTROL BY ADDING INDIVIDUALS(GCAI)in the setting of group identification for two procedural rules-the consensus-start-respecting rule and the liberal-start-respecting *** is known that GCAI for both...
详细信息
We consider GROUP CONTROL BY ADDING INDIVIDUALS(GCAI)in the setting of group identification for two procedural rules-the consensus-start-respecting rule and the liberal-start-respecting *** is known that GCAI for both rules are NP-hard,but whether they are fixed-parameter tractable with respect to the number of distinguished individuals remained *** resolve both open problems in the *** addition,we strengthen the NP-hardness of GCAI by showing that,with respect to the natural parameter the number of added individuals,GCAI for both rules are W[2]-***,the W[2]-hardness for the liberal-startrespecting rule holds even when restricted to a very special case where the qualifications of individuals satisfy the so-called consecutive ones ***,for the consensus-startrespecting rule,the problem becomes polynomial-time solvable in this special *** also study a dual restriction where the disqualifications of individuals fulfill the consecutive ones property,and show that under this restriction GCAI for both rules turn out to be polynomial-time *** reductions for showing W[2]-hardness also imply several algorithmic lowerbounds.
Cai and Yang initiated the systematic parameterized complexity study of the following set of problems around Eulerian graphs. For a given graph G and integer k, the task is to decide if G contains a (connected) subgra...
详细信息
ISBN:
(纸本)9783939897354
Cai and Yang initiated the systematic parameterized complexity study of the following set of problems around Eulerian graphs. For a given graph G and integer k, the task is to decide if G contains a (connected) subgraph with k vertices (edges) with all vertices of even (odd) degrees. They succeed to establish the parameterized complexity of all cases except two, when we ask about a connected k-EDGE subgraph with all vertices of odd degrees, the problem known as k-Edge CONNECTED ODD SUBGRAPH;and a connected k-vertex induced subgraph with all vertices of even degrees, the problem known as k-VERTEX EULERIAN SUBGRAPH. We resolve both open problems and thus complete the characterization of even/odd subgraph problems from parameterized complexity perspective. We show that k-EDGE CONNECTED ODD SUBGRAPH is FPT and that k-VERTEX EULERIAN SUBGRAPH IS W[1]-hard. Our FPT algorithm is based on a novel combinatorial result on the treewidth of minimal connected odd graphs with even amount of edges.
作者：
Lozin, Vadim V.DIMAP
Mathematics Institute University of Warwick Coventry United Kingdom
For a hereditary class X, the number Xn of n-vertex graphs in X (also known as the speed of X) satisfies limn → ∞ frac(log2 Xn, ((n;2))) = 1 - frac(1, k (X)) where k (X) is a natural number called the index of the c...
详细信息
Multiple-interval graphs are a natural generalization of interval graphs where each vertex may have more than one interval associated with it. Many applications of interval graphs also generalize to multiple-interval ...
详细信息
Multiple-interval graphs are a natural generalization of interval graphs where each vertex may have more than one interval associated with it. Many applications of interval graphs also generalize to multiple-interval graphs, often allowing for more robustness in the modeling of the specific application. With this motivation in mind, a recent systematic study of optimization problems in multiple-interval graphs was initiated. In this sequel, we Study multiple-interval graph problems from the perspective of parameterized complexity. The problems under consideration are k-INDEPENDENT SET, k-DOMINATING SET, and k-CLIQUE, which are all known to be W[1]-hard for general graphs, and NP-complete for multiple-interval graphs. We prove that k-CLIQUE is in FPT, while k-INDEPENDENT SET and k-DOMINATING SET are both W[1]-hard. We also prove that k-INDEPENDENT DOMINATING SET, a hybrid of the two above problems, is also W[1]-hard. Our hardness results hold even when each vertex is associated with at most two intervals, and all intervals have unit length. Furthermore, as an interesting byproduct of our hardness results, we develop a useful technique for showing W[1]-hardness via a reduction from the k-MULTICOLORED CLIQUE problem, a variant of k-CLIQUE. We believe this technique has interest in its own right, as it should help in simplifying W[1]-hardness results which are notoriously hard to construct and technically tedious. (C) 2008 Elsevier B.V. All rights reserved.
This paper considers four problems with possible applications in network design: Given a graph G with | G | = n and an integer k ≥ 0 , does G have a DFS tree with (i) ≤ k leaves, (ii) ≥ k leaves, (iii) ≤ n − k lea...
详细信息
This paper considers four problems with possible applications in network design: Given a graph G with | G | = n and an integer k ≥ 0 , does G have a DFS tree with (i) ≤ k leaves, (ii) ≥ k leaves, (iii) ≤ n − k leaves, and (iv) ≥ n − k leaves? We show that all four problems are NP-hard. When parameterized by k , we prove that while (i) is para-NP-hard and (ii) is W[1]-hard, both (iii) and (iv) admit polynomial kernels with O ( k 3 ) vertices, implying FPT algorithms running in k O ( k ) ⋅ n O ( 1 ) time. Our polynomial kernels are based on a O ( k ) -sized vertex cover structure associated with the solution of these problems. As a byproduct, we obtain polynomial kernels for these problems parameterized by the vertex cover number of the input graph.
The problem MAX W-LIGHT (MAX W-HEAVY) for an undirected graph is to assign a direction to each edge so that the number of vertices of outdegree at most W (resp. at least W) is maximized. It is known that these problem...
详细信息
The problem MAX W-LIGHT (MAX W-HEAVY) for an undirected graph is to assign a direction to each edge so that the number of vertices of outdegree at most W (resp. at least W) is maximized. It is known that these problems are NP-hard even for fixed W. For example, MAX 0- LIGHT is equivalent to the problem of finding a maximum independent set. In this paper, we show that for any fixed constant W, MAX W-HEAVY can be solved in linear time for hereditary graph classes for which treewidth is bounded by a function of degeneracy. We show that such graph classes include chordal graphs, circular-arc graphs, d-trapezoid graphs, chordal bipartite graphs, and graphs of bounded clique-width. To have a polynomial-time algorithm for MAX W-LIGHT, we need an additional condition of a polynomial upper bound on the number of potential maximal cliques to apply the metatheorem by Fomin et al. (SIAM J Comput 44:54-87, 2015). The aforementioned graph classes, except bounded clique-width graphs, satisfy such a condition. For graphs of bounded clique-width, we present a dynamic programming approach not using the metatheorem to show that it is actually polynomial-time solvable for this graph class too. We also study the parameterized complexity of the problems and show some tractability and intractability results.
The counting of minimum edge (S, T)-cuts in undirected graphs, parameterized by the size p of these cuts, is FPT. The best performance in the literature is O\ast(2O(p2)). We treat a more general problem of counting mi...
详细信息
The counting of minimum edge (S, T)-cuts in undirected graphs, parameterized by the size p of these cuts, is FPT. The best performance in the literature is O\ast(2O(p2)). We treat a more general problem of counting minimum (S, T)-cuts composed of vertices instead of edges. We propose an FPT algorithm with running time O\ast(2O(p log p)). As it may be applied to the edge version as well, we improve the time complexity of the minimum edge (S, T )-cuts counting.
Computing posterior and marginal probabilities constitutes the backbone of almost all inferences in Bayesian networks. These computations are known to be intractable in general, both to compute exactly and to approxim...
详细信息
Computing posterior and marginal probabilities constitutes the backbone of almost all inferences in Bayesian networks. These computations are known to be intractable in general, both to compute exactly and to approximate (e.g., by sampling algorithms). While it is well known under what constraints exact computation can be rendered tractable (viz., bounding tree-width of the moralized network and bounding the cardinality of the variables) it is less known under what constraints approximate Bayesian inference can be tractable. Here, we extend the existing formal framework of fixed-error randomized tractability (a randomized analogue of fixed-parameter tractability), and use it to address this problem, both by re-interpreting known results from the literature and by providing some additional new results, including results on fixed parameter tractable de-randomization of approximate inference. (C) 2017 Elsevier Inc. All rights reserved.
We show that the fixed alphabet shortest common supersequence (SCS) and the fixed alphabet longest common subsequence (LCS) problems parameterized in the number of strings are W[1]-hard. Unless W[1] = FPT, this rules ...
详细信息
We show that the fixed alphabet shortest common supersequence (SCS) and the fixed alphabet longest common subsequence (LCS) problems parameterized in the number of strings are W[1]-hard. Unless W[1] = FPT, this rules out the existence of algorithms with time complexity of O(f(k)n(alpha)) for those problems. Here n is the size of the problem instance, alpha is constant, k is the number of strings and f is any function of k. The fixed alphabet version of the LCS problem is of particular interest considering the importance of sequence comparison (e.g. multiple sequence alignment) in the fixed length alphabet world of DNA and protein sequences. (C) 2003 Elsevier Inc. All rights reserved.
We give machine characterizations of most parameterized complexity classes, in particular, of W[P], of the classes of the W-hierarchy, and of the A-hierarchy. For example, we characterize W[P] as the class of all para...
详细信息
We give machine characterizations of most parameterized complexity classes, in particular, of W[P], of the classes of the W-hierarchy, and of the A-hierarchy. For example, we characterize W[P] as the class of all parameterized problems decidable by a nondeterministic fixed-parameter tractable algorithm whose number of nondeterministic steps is bounded in terms of the parameter. The machine characterizations suggest the introduction of a hierarchy W-func between the W- and the A-hierarchy. We study the basic properties of this hierarchy. (c) 2005 Elsevier B.V. All rights reserved.
暂无评论