Vertex deletion problems ask whether it is possible to delete at most k vertices from a graph so that the resulting graph belongs to a specified graph class. Over the past years, the parameterized complexity of vertex...
详细信息
Vertex deletion problems ask whether it is possible to delete at most k vertices from a graph so that the resulting graph belongs to a specified graph class. Over the past years, the parameterized complexity of vertex deletion to a plethora of graph classes has been systematically researched. Here we present the first single-exponential fixed-parameter tractable algorithm for vertex deletion to distance-hereditary graphs, a well-studied graph class which is particularly important in the context of vertex deletion due to its connection to the graph parameter rank-width. We complement our result with matching asymptotic lower bounds based on the exponential time hypothesis. As an application of our algorithm, we show that a vertex deletion set to distance-hereditary graphs can be used as a parameter which allows single-exponential fixed-parameter tractable algorithms for classical NP-hard problems. (C) 2018 Elsevier Inc. All rights reserved.
We consider the following problem. Given a 2-CNF formula, is it possible to remove at most k clauses so that the resulting 2-CNF formula is satisfiable? This problem is known to different research communities in theor...
详细信息
We consider the following problem. Given a 2-CNF formula, is it possible to remove at most k clauses so that the resulting 2-CNF formula is satisfiable? This problem is known to different research communities in theoretical computer science under the names Almost 2-SAT, All-but-k 2-SAT, 2-CNF deletion, and 2-SAT deletion. The status of the fixed-parameter tractability of this problem is a long-standing open question in the area of parameterized complexity. We resolve this open question by proposing an algorithm that solves this problem in O(15(k), x k x m(3)) time showing that this problem is fixed-parameter tractable. (C) 2009 Elsevier Inc. All rights reserved.
The input of the Edge Multicut problem consists of an undirected graph G and pairs of terminals {s(1), t(1)),...,{s(m), t(m));the task is to remove a minimum set of edges such that s(i) and t(i) are disconnected for e...
详细信息
The input of the Edge Multicut problem consists of an undirected graph G and pairs of terminals {s(1), t(1)),...,{s(m), t(m));the task is to remove a minimum set of edges such that s(i) and t(i) are disconnected for every 1 <= i <= m. The parameterized complexity of the problem, parameterized by the maximum number k of edges that are allowed to be removed, is currently open. The main result of the paper is a parameterized 2-approximation algorithm: in time f (k).n(0(1)), we can either find a solution of size 2k or correctly conclude that there is no solution of size k. The proposed algorithm is based on a transformation of the Edge Multicut problem into a variant of the parameterized Max-2SAT problem, where the parameter is related to the number of clauses that are not satisfied. It follows from previous results that the latter problem can be 2-approximated in a fixed-parameter time: on the other hand, we show here that it is W[1]-hard. Thus the additional contribution of the present paper is introducing the first natural W[1]-hard problem that is constant-ratio fixed-parameter approximable. (c) 2009 Elsevier B.V. All rights reserved.
We study the parameterized complexity of several vertex- and edge-deletion problems on graphs, parameterized by the number p of deletions. The first kind of problems are separation problems on undirected graphs, where...
详细信息
We study the parameterized complexity of several vertex- and edge-deletion problems on graphs, parameterized by the number p of deletions. The first kind of problems are separation problems on undirected graphs, where we aim at separating distinguished vertices in a graph. The second kind of problems are feedback set problems on group-labelled graphs, where we aim at breaking nonnull cycles in a graph having its arcs labelled by elements of a group. We obtain new FPT algorithms for these different problems, relying on a generic O*(4(p)) algorithm for breaking paths of a homogeneous path system. (C) 2010 Elsevier B.V. All rights reserved.
We first present a randomized fixed-parameter algorithm for the NP-hard problem of deciding if there are two matchings M-1 and M-2 in a given graph G such that vertical bar M-1 vertical bar+ vertical bar M-2 vertical ...
详细信息
We first present a randomized fixed-parameter algorithm for the NP-hard problem of deciding if there are two matchings M-1 and M-2 in a given graph G such that vertical bar M-1 vertical bar+ vertical bar M-2 vertical bar is a given number k. The algorithm runs in O (2(k)k(m + n)) expected time and can be derandomized to run in O (2(2k+12 log2 (2k)) kn (m + n) time, where n (respectively, m) is the number of vertices (respectively, edges) in G. We then extend the algorithm to the weighted version of the problem. We further present a combinatorial approximation algorithm for the NP-hard problem of finding two disjoint matchings in a given edge-weighted graph G so that their total weight is maximized. The algorithm achieves an approximation ratio close to 0.76 and runs in O(m + n(3) alpha(n)) time, where alpha is the inverse Ackermann function. (C) 2014 Elsevier B.V. All rights reserved.
We investigate the computational complexity of the DENSEST k-SUBGRAPH problem, where the input is an undirected graph G = (V, E) and one wants to find a subgraph on exactly k vertices with the maximum number of edges....
详细信息
We investigate the computational complexity of the DENSEST k-SUBGRAPH problem, where the input is an undirected graph G = (V, E) and one wants to find a subgraph on exactly k vertices with the maximum number of edges. We extend previous work on DENSEST k-SUBGRAPH by studying its parameterized complexity for parameters describing the sparseness of the input graph and for parameters related to the solution size k. On the positive side, we show that, when fixing some constant minimum density mu of the sought subgraph, DENSEST k-SUBGRAPH becomes fixed-parameter tractable with respect to either of the parameters maximum degree of G and h-index of G. Furthermore, we obtain a fixed-parameter algorithm for DENSEST k-SUBGRAPH with respect to the combined parameter "degeneracy of G and vertical bar V vertical bar - k". On the negative side, we find that DENSEST k-SUBGRAPH is W[1]-hard with respect to the combined parameter "solution size k and degeneracy of G". We furthermore strengthen a previous hardness result for DENSEST k-SUBGRAPH (Cai, 2008) by showing that for every fixed mu, 0 < mu < 1, the problem of deciding whether G contains a subgraph of density at least mu is W[1]-hard with respect to the parameter vertical bar V] - k. Our positive results are obtained by an algorithmic framework that can be applied to a wide range of fixed-CARDINALITY OPTIMIZATION problems. (C) 2015 Elsevier B.V. All rights reserved.
The connected dominating set (CDS) problem is a well studied NP-hard problem with many important applications. Dorn et al. (Algorithmica 58:790-810 2010) introduce a branch-decomposition based algorithm design techniq...
详细信息
The connected dominating set (CDS) problem is a well studied NP-hard problem with many important applications. Dorn et al. (Algorithmica 58:790-810 2010) introduce a branch-decomposition based algorithm design technique for NP-hard problems in planar graphs and give an algorithm (DPBF algorithm) which solves the planar CDS problem in time and time, with a conventional method and fast matrix multiplication in the dynamic programming step of the algorithm, respectively. We show that DPBF algorithm solves the planar CDS problem in time with a conventional method and in time with a fast matrix multiplication. For a graph , let be the branchwidth of and be the connected dominating number of . We prove . From this result, the planar CDS problem admits an time fixed-parameter algorithm. We report computational study results on the practical performance of DPBF algorithm, which show that the size of instances can be solved by the algorithm mainly depends on the branchwidth of the instances, coinciding with the theoretical analysis. For graphs with small or moderate branchwidth, the CDS problem instances with size up to a few thousands edges can be solved in a practical time and memory space.
We give a fixed-parameter algorithm for the problem of enumerating all minimum-cost LCA-reconciliations involving gene duplications, gene losses, and lateral gene transfers (LGTs) for a given species tree S and a give...
详细信息
We give a fixed-parameter algorithm for the problem of enumerating all minimum-cost LCA-reconciliations involving gene duplications, gene losses, and lateral gene transfers (LGTs) for a given species tree S and a given gene tree G. Our algorithm can work for the weighted version of the problem, where the costs of a gene duplication, a gene loss, and an LGT are left to the user's discretion. The algorithm runs in O(m + 3(k/c)n) time, where m is the number of vertices in S, n is the number of vertices in G, c is the smaller between a gene duplication cost and an LGT cost, and k is the minimum cost of an LCA-reconciliation between S and G. The time complexity is indeed better if the cost of a gene loss is greater than 0. In particular, when the cost of a gene loss is at least 0.614c, the running time of the algorithm is O(m + 2.78(k/c)n).
Analyzing genomic data for finding those gene variations which are responsible for hereditary diseases is one of the great challenges in modern bioinformatics. In many living beings (including the human), every gene i...
详细信息
Analyzing genomic data for finding those gene variations which are responsible for hereditary diseases is one of the great challenges in modern bioinformatics. In many living beings (including the human), every gene is present in two copies, inherited from the two parents, the so-called haplotypes. In this paper, we propose a simple combinatorial model for classifying the set of haplotypes in a population according to their responsibility for a certain genetic disease. This model is based on the minimum-ones 2SAT problem with uniform clauses. The minimum-ones 2SAT problem asks for a satisfying assignment to a satisfiable formula in 2CNF which sets a minimum number of variables to true. This problem is well-known to be NP-hard, even in the case where all clauses are uniform, i.e., do not contain a positive and a negative literal. We analyze the approximability and present the first non-trivial exact algorithm for the uniform minimum-ones 2SAT problem with a running time of O(1.21061(n)) on a 2SAT formula with n variables. We also show that the problem is fixed-parameter tractable by showing that our algorithm can be adapted to verify in O*(2(k)) time whether an assignment with at most k true variables exists.
Given a set of n strings of length L and a radius d, the closest string problem (CSP for short) asks for a string t(sol) that is within a Hamming distance of d to each of the given strings. It is known that the proble...
详细信息
Given a set of n strings of length L and a radius d, the closest string problem (CSP for short) asks for a string t(sol) that is within a Hamming distance of d to each of the given strings. It is known that the problem is NP-hard and its optimization version admits a polynomial time approximation scheme (PTAS). A number of parameterized algorithms have been then developed to solve the problem when d is small. Among them, the relatively new ones have not been implemented before and their performance in practice was unknown. In this study, we implement all of them by careful engineering. For those that have been implemented before, our implementation is much faster. For some of those that have not been implemented before, our experimental results show that there exist huge gaps between their theoretical and practical performances. We also design a new parameterized algorithm for the binary case of CSP. The algorithm is deterministic and runs in O (n(2)L + n(2)d. 6.16(d)) time, while the previously best deterministic algorithm runs in O (nL + nd(3). 6.731(d)) time. (C) 2018 Elsevier B.V. All rights reserved.
暂无评论