Given n taxa, exactly one topology for every subset of four taxa, and a positive integer k (the parameter), the MINIMUM QUARTET INCONSISTENCY (MQI) problem is the question whether we can find an evolutionary tree indu...
详细信息
Given n taxa, exactly one topology for every subset of four taxa, and a positive integer k (the parameter), the MINIMUM QUARTET INCONSISTENCY (MQI) problem is the question whether we can find an evolutionary tree inducing a set of quartet topologies that differs from the given set in only k quartet topologies. The more general problem where we are not necessarily given a topology for every subset of four taxa appears to be fixed-parameter intractable. For MQI, however, which is also NP-complete, we can compute the required tree in time O(4(k)n + n(4)). This means that the problem is fixed-parameter tractable and that in the case of a small number k of "errors" the tree reconstruction can be done efficiently. In particular, for minimal k, our algorithm can produce all solutions that resolve k errors. Additionally, we discuss significant heuristic improvements. Experiments underline the practical relevance of our solutions. (C) 2003 Elsevier Inc. All rights reserved.
Kernelization is a polynomial-time algorithm that reduces an instance of a parameterized problem to a decision-equivalent instance, the kernel, whose size is bounded by a function of the parameter. In this paper we pr...
详细信息
Kernelization is a polynomial-time algorithm that reduces an instance of a parameterized problem to a decision-equivalent instance, the kernel, whose size is bounded by a function of the parameter. In this paper we present meta-theorems that provide polynomial kernels for large classes of graph problems parameterized by a structural parameter of the input graph. Let C be an arbitrary but fixed class of graphs of bounded rank-width (or, equivalently, of bounded clique-width). We define the C-cover number of a graph to be the smallest number of modules its vertex set can be partitioned into, such that each module induces a subgraph that belongs to C. We show that each decision problem on graphs which is expressible in Monadic Second Order (MSO) logic has a polynomial kernel with a linear number of vertices when parameterized by the C-cover number. We provide similar results for MSO expressible optimization and modulo-counting problems. (C) 2015 Elsevier Inc. All rights reserved.
The Weighted Vertex Integrity (wVI) problem takes as input an n-vertex graph G, a weight function , and an integer p. The task is to decide if there exists a set such that the weight of X plus the weight of a heaviest...
详细信息
The Weighted Vertex Integrity (wVI) problem takes as input an n-vertex graph G, a weight function , and an integer p. The task is to decide if there exists a set such that the weight of X plus the weight of a heaviest component of is at most p. Among other results, we prove thatwVI is NP-complete on co-bipartite graphs, even if each vertex has weight 1;wVI can be solved in time;wVI admits a kernel with at most vertices. wCOC can be solved in time on interval graphs, while the unweighted version can be solved in time on this graph class;wCOC is W[1]-hard on split graphs when parameterized by k or by;wCOC can be solved in time;wCOC admits a kernel with at most vertices. Result (1) refutes a conjecture by Ray and Deogun (J Comb Math Comb Comput 16: 65-73, 1994) and answers an open question by Ray et al. (Ars Comb 79: 77-95, 2006). It also complements a result by Kratsch et al. (Discret Appl Math 77(3): 259270, 1997), stating that the unweighted version of the problem can be solved in polynomial time on co-comparability graphs of bounded dimension, provided that an intersection model of the input graph is given as part of the input. An instance of the Weighted Component Order Connectivity (wCOC) problem consists of an nvertex graph G, a weight function w : V(G). N, and two integers k and, and the task is to decide if there exists a set X. V(G) such that the weight of X is at most k and the weight of a heaviest component of G -X is at most. In some sense, the wCOC problem can be seen as a refined version of the wVI problem. We obtain several classical and parameterized complexity results on thewCOC problem, uncovering interesting similarities and differences between wCOC and wVI. We prove, among other results, that: (4) wCOC can be solved in O(min{k, n3) time on interval graphs, while the unweighted version can be solved in O(n2) time on this graph class;(5) wCOC is W[ 1]-hard on split graphs when parameterized by k or by (6) wCOC can be solved in 2O(k log ) n time;(7) w
The NP-complete Permutation Pattern Matching problem asks whether a k-permutation P is contained in a n-permutation T as a pattern. This is the case if there exists an order-preserving embedding of P into T. In this p...
详细信息
The NP-complete Permutation Pattern Matching problem asks whether a k-permutation P is contained in a n-permutation T as a pattern. This is the case if there exists an order-preserving embedding of P into T. In this paper, we present a fixed-parameter algorithm solving this problem with a worst-case runtime of , where denotes the number of alternating runs of T. This algorithm is particularly well-suited for instances where T has few runs, i.e., few ups and downs. Moreover, since , this can be seen as a algorithm which is the first to beat the exponential runtime of brute-force search. Furthermore, we prove that under standard complexity theoretic assumptions such a fixed-parameter tractability result is not possible for run(P).
It has long been known that Feedback Vertex Set can be solved in time 2 O-(w log w) n(O(1)) on n-vertex graphs of treewidth w, but it was only recently that this running time was improved to 2(O(w))n(O(1)), that is, t...
详细信息
It has long been known that Feedback Vertex Set can be solved in time 2 O-(w log w) n(O(1)) on n-vertex graphs of treewidth w, but it was only recently that this running time was improved to 2(O(w))n(O(1)), that is, to single-exponential parameterized by treewidth. We investigate which generalizations of Feedback Vertex Set can be solved in a similar running time. Formally, for a class P of graphs, the Bounded P-Block Vertex Deletion problem asks, given a graph G on n vertices and positive integers k and d, whether G contains a set S of at most k vertices such that each block of G -S has at most d vertices and is in P. Assuming that P is recognizable in polynomial time and satisfies a certain natural hereditary condition, we give a sharp characterization of when single-exponential parameterized algorithms are possible for fixed values of d: - if P consists only of chordal graphs, then the problem can be solved in time 2(O(wd2))n(O(1)), - if P contains a graph with an induced cycle of length l >= 4, then the problem is not solvable in time 2(o(w log w))n(O(1)) even for fixed d = l, unless the ETH fails. We also study a similar problem, called Bounded P-Component Vertex Deletion, where the target graphs have connected components of small size rather than blocks of small size, and we present analogous results. For this problem, we also show that if d is part of the input and P contains all chordal graphs, then it cannot be solved in time f(w)n(o(w)) for some function f, unless the ETH fails.
We consider the EDITING TO A GRAPH OF GIVEN DEGREES problem that asks for a graph G, non-negative integers d,k and a function delta: V(G) -> {1, ... , d}, whether it is possible to obtain a graph G' from G such...
详细信息
We consider the EDITING TO A GRAPH OF GIVEN DEGREES problem that asks for a graph G, non-negative integers d,k and a function delta: V(G) -> {1, ... , d}, whether it is possible to obtain a graph G' from G such that the degree of v is delta(v) for any vertex v by at most k vertex or edge deletions or edge additions. We construct an FPT-algorithm for EDITING TO A GRAPH OF GIVEN DEGREES parameterized by d + k. We complement this result by showing that the problem has no polynomial kernel unless NP subset of coNP/poly. (C) 2015 Elsevier B.V. All rights reserved.
We study the (n, 3)-MaxSAT problem where we are given an integer k and a CNF formula with n variables, each of which appears in at most 3 clauses, and the question is whether there is an assignment that satisfies at l...
详细信息
We study the (n, 3)-MaxSAT problem where we are given an integer k and a CNF formula with n variables, each of which appears in at most 3 clauses, and the question is whether there is an assignment that satisfies at least k clauses. Based on refined observations, we propose a branching algorithm for the (n, 3)-MaxSAT problem which significantly improves the previous results. More precisely, the running time of our algorithm can be bounded by O* (1.175(k)) and O* (1.194(n)), respectively. Prior to our study, the running time of the best known exact algorithm can be bounded by O* (1.194(k)) and O*(1.237n), respectively.
Given a graph G, a properk-coloring of G is a partition c=(Si)i is an element of[1,k] of V(G) into k stable sets S1, horizontal ellipsis ,Sk. Given a weight function w:V(G)-> R+, the weight of a colorSi is defined ...
详细信息
Given a graph G, a properk-coloring of G is a partition c=(Si)i is an element of[1,k] of V(G) into k stable sets S1, horizontal ellipsis ,Sk. Given a weight function w:V(G)-> R+, the weight of a colorSi is defined as w(i)=maxv is an element of Siw(v) and the weight of a coloringc as w(c)= n-ary sumation i=1kw(i). Guan and Zhu (Inf Process Lett 61(2):77-81, 1997) defined the weighted chromatic number of a pair (G, w), denoted by sigma(G,w), as the minimum weight of a proper coloring of G. The problem of determining sigma(G,w) has received considerable attention during the last years, and has been proved to be notoriously hard: for instance, it is NP-hard on split graphs, unsolvable on n-vertex trees in time no(logn) unless the ETH fails, and W[1]-hard on forests parameterized by the size of a largest tree. We focus on the so-called dual parameterization of the problem: given a vertex-weighted graph (G, w) and an integer k, is sigma(G,w)<= n-ary sumation v is an element of V(G)w(v)-k? This parameterization has been recently considered by Escoffier (in: Proceedings of the 42nd international workshop on graph-theoretic concepts in computer science (WG). LNCS, vol 9941, pp 50-61, 2016), who provided an FPT algorithm running in time 2O(klogk)center dot nO(1), and asked which kernel size can be achieved for the problem. We provide an FPT algorithm in time 9k center dot nO(1), and prove that no algorithm in time 2o(k)center dot nO(1) exists under the ETH. On the other hand, we present a kernel with at most (2k-1+1)(k-1) vertices, and rule out the existence of polynomial kernels unless NP subset of coNP/poly, even on split graphs with only two different weights. Finally, we identify classes of graphs allowing for polynomial kernels, namely interval graphs, comparability graphs, and subclasses of circular-arc and split graphs, and in the latter case we present lower bounds on the degrees of the polynomials.
A commonly studied means of parameterizing graph problems is the deletion distance from triviality (Guo et al., parameterized and exact computation, Springer, Berlin, pp. 162-173, 2004), which counts vertices that nee...
详细信息
A commonly studied means of parameterizing graph problems is the deletion distance from triviality (Guo et al., parameterized and exact computation, Springer, Berlin, pp. 162-173, 2004), which counts vertices that need to be deleted from a graph to place it in some class for which efficient algorithms are known. In the context of graph isomorphism, we define triviality to mean a graph with maximum degree bounded by a constant, as such graph classes admit polynomial-time isomorphism tests. We generalise deletion distance to a measure we call elimination distance to triviality, based on elimination trees or tree-depth decompositions. We establish that graph canonisation, and thus graph isomorphism, is when parameterized by elimination distance to bounded degree, extending results of Bouland et al. (parameterized and exact computation, Springer, Berlin, pp. 218-230, 2012).
Graph layout problems are a particular class of combinatorial optimization problems whose goal is to find a linear layout of an input graph in such way that a certain objective cost is optimized. This survey considers...
详细信息
Graph layout problems are a particular class of combinatorial optimization problems whose goal is to find a linear layout of an input graph in such way that a certain objective cost is optimized. This survey considers their motivation, complexity, approximation properties, upper and lower bounds, heuristics and probabilistic analysis on random graphs. The result is a complete view of the current state of the art with respect to layout problems from an algorithmic point of view.
暂无评论