Given a graph G = (V, E) with n vertices and m edges, and a subset T of k vertices called terminals, the Edge (respectively, Vertex) Multiterminal Cut problem is to find a set of at most l edges (non-terminal vertices...
详细信息
Given a graph G = (V, E) with n vertices and m edges, and a subset T of k vertices called terminals, the Edge (respectively, Vertex) Multiterminal Cut problem is to find a set of at most l edges (non-terminal vertices), whose removal from G separates each terminal from all the others. These two problems are NP-hard for k = 3 but well-known to be polynomial-time solvable for k = 2 by the flow technique. In this paper, based on a notion farthest minimum isolating cut, we design several simple and improved algorithms for Multiterminal Cut. We show that Edge Multiterminal Cut can be solved in O(2(l)kT (n, m)) time and Vertex Multiterminal Cut can be solved in O(k(l)T (n, m)) time, where T (n, m) = O(min(n(2/3), m(1/2)) m) is the running time of finding a minimum (s, t) cut in an unweighted graph. Furthermore, the running time bounds of our algorithms can be further reduced for small values of k: Edge 3-Terminal Cut can be solved in O(1.415(l)T (n, m)) time, and Vertex {3, 4, 5, 6}-Terminal Cuts can be solved in O(2.059(l)T (n, m)), O(2.772(l)T (n, m)), O(3.349(l)T (n, m)) and O(3.857(l)T (n, m)) time respectively. Our results on Multiterminal Cut can also be used to obtain faster algorithms for Multicut: O((min(root 2k, l) + 1)(2k)2(l)T (n, m))-time algorithm for Edge Multicut and O((2k)Tk+l/2 (n, m))-time algorithm for Vertex Multicut.
We consider the multivariate interlace polynomial introduced by Courcelle (Electron. J. Comb. 15(1), 2008), which generalizes several interlace polynomials defined by Arratia, Bollobas, and Sorkin (J. Comb. Theory Ser...
详细信息
We consider the multivariate interlace polynomial introduced by Courcelle (Electron. J. Comb. 15(1), 2008), which generalizes several interlace polynomials defined by Arratia, Bollobas, and Sorkin (J. Comb. Theory Ser. B 92(2):199-233, 2004) and by Aigner and van der Holst (Linear Algebra Appl., 2004). We present an algorithm to evaluate the multivariate interlace polynomial of a graph with n vertices given a tree decomposition of the graph of width k. The best previously known result (Courcelle, Electron. J. Comb. 15(1), 2008) employs a general logical framework and leads to an algorithm with running time f(k).n, where f(k) is doubly exponential in k. Analyzing the GF(2)-rank of adjacency matrices in the context of tree decompositions, we give a faster and more direct algorithm. Our algorithm uses 23k(2)+O(k).n arithmetic operations and can be efficiently implemented in parallel.
Given a graph G = (V, E), the edge dominating set problem is to find a minimum set M subset of E such that each edge in E - M has at least one common endpoint with an edge in M. The edge dominating set problem is an i...
详细信息
ISBN:
(纸本)9783642174605
Given a graph G = (V, E), the edge dominating set problem is to find a minimum set M subset of E such that each edge in E - M has at least one common endpoint with an edge in M. The edge dominating set problem is an important graph problem and has been extensively studied. It is well known that the problem is NP-hard, even when the graph is restricted to a planar or bipartite graph with maximum degree 3. In this paper, we show that the edge dominating set problem in graphs with maximum degree 3 can be solved in O*(1.2721(n)) time and polynomial space, where n is the number of vertices in the graph. We also show that there is an O*(2.2306(k))-time polynomial-space algorithm to decide whether a graph with maximum degree 3 has an edge dominating set of size k or not. Above two results improve previously known results on exact and parameterized algorithms for this problem.
Rank-width is a structural graph measure introduced by Oum and Seymour and aimed at better handling of graphs of bounded clique-width. We propose a formal mathematical framework and tools for easy design of dynamic al...
详细信息
Rank-width is a structural graph measure introduced by Oum and Seymour and aimed at better handling of graphs of bounded clique-width. We propose a formal mathematical framework and tools for easy design of dynamic algorithms running directly on a rank-decomposition of a graph (on contrary to the usual approach which translates a rank-decomposition into a clique-width expression, with a possible exponential jump in the parameter). The main advantage of this framework is a fine control over the runtime dependency on the rank-width parameter. Our new approach is linked to a work of Courcelle and Kante[7] who first proposed algebraic expressions with a so-called bilinear graph product as a better way of handling rank-decompositions, and to a parallel recent research of Bui-Xuan, Telle and Vatshelle. (c) 2009 Elsevier B.V. All rights reserved.
This paper presents an O(1.2738(k) + kn)-time polynomial-space algorithm for VERTEX COVER improving the previous O(1.286(k) + kn)-time polynomial-space upper bound by Chen, Kanj, and Jia. Most of the previous algorith...
详细信息
This paper presents an O(1.2738(k) + kn)-time polynomial-space algorithm for VERTEX COVER improving the previous O(1.286(k) + kn)-time polynomial-space upper bound by Chen, Kanj, and Jia. Most of the previous algorithms rely on exhaustive case-by-case branching rules, and an underlying conservative worst-case-scenario assumption. The contribution of the paper lies in the simplicity, uniformity, and obliviousness of the algorithm presented. Several new techniques, as well as generalizations of previous techniques, are introduced including: general folding, struction, tuples, and local amortized analysis. The algorithm also improves the O(1.2745(k)k(4) + kn)-time exponential-space upper bound for the problem by Chandran and Grandoni. (C) 2010 Elsevier B.V. All rights reserved.
Haplotypes play an important role in genetic association studies of complex diseases. Recently, computational techniques helping to determine human haplotypes were studied extensively. Given the genotype and the align...
详细信息
Haplotypes play an important role in genetic association studies of complex diseases. Recently, computational techniques helping to determine human haplotypes were studied extensively. Given the genotype and the aligned single nucleotide polymorphism (SNP) fragments of an individual, Minimum Error Correction with Genotype Information (MEC/GI) is an important computational model to infer a pair of haplotypes compatible with the genotype by correcting minimum number of SNPs in the given SNP fragments. The MEC/GI problem has been proven NP-hard, for which there is no practical exact algorithm. Despite the rapid advances in molecular biological techniques, modern high-throughput sequencers cannot sequence directly a DNA fragment that contains more than 1200 nucleotide bases. With low SNP density, current available data reveal that the number k of SNP sites that a DNA fragment covers is usually smaller than 10. Based on the above fact, we develop a new dynamic programming algorithm with running time O(mk2 (k) +mlog m+mk), where m is the number of fragments. Since k is small in real biological applications, the algorithm is practical and efficient.
We study the preemptive scheduling problem of a set of n jobs with release times and equal processing times on a single machine. The objective is to minimize the sum of the weighted completion times Sigma(n)(i=1) w(i)...
详细信息
We study the preemptive scheduling problem of a set of n jobs with release times and equal processing times on a single machine. The objective is to minimize the sum of the weighted completion times Sigma(n)(i=1) w(i)C(i) of the jobs. We propose for this problem the first parameterized algorithm on the number k of different weights. The runtime of the proposed algorithm is O ((n/k + 1 )(k) n(8)) and hence, the problem is polynomially solvable for any fixed number k of different weights.
The r-Regular Induced Subgraph problem asks, given a graph G and a non-negative integer k, whether G contains an r-regular induced subgraph of size at least k, that is, an induced subgraph in which every vertex has de...
详细信息
The r-Regular Induced Subgraph problem asks, given a graph G and a non-negative integer k, whether G contains an r-regular induced subgraph of size at least k, that is, an induced subgraph in which every vertex has degree exactly r. In this paper we examine its parameterization k-Size r-Regular Induced Subgraph with k as parameter and prove that it is W[1]-hard. We also examine the parameterized complexity of the dual parameterized problem, namely, the k-Almost r-Regular Graph problem, which asks for a given graph G and a non-negative integer k whether G can be made r-regular by deleting at most k vertices. For this problem, we prove the existence of a problem kernel of size O(kr(r + k)(2)). (C) 2008 Elsevier B.V. All rights reserved.
The computational complexity of counting the number of matchings of size k in a given triple set has been open. It is conjectured that the problem is not fixed parameter tractable. In this paper, we present a fixed pa...
详细信息
The computational complexity of counting the number of matchings of size k in a given triple set has been open. It is conjectured that the problem is not fixed parameter tractable. In this paper, we present a fixed parameter tractable randomized approximation scheme (FPTRAS) for the problem. More precisely, we develop a randomized algorithm that, on given positive real numbers is an element of and delta, and a given set S of n triples and an integer k, produces a number h in time O(5.48(3k)n(2)ln(2/delta)/is an element of(2)) such that Prob[(1 - is an element of)h(0) <= h <= (1 + is an element of)h(0)] >= 1 - delta, where h(0) is the total number of matchings of size k in the triple set S. Our algorithm is based on the recent improved color-coding techniques and the Monte-Carlo self-adjusting coverage algorithm developed by Karp, Luby and Madras.
We survey results and open questions on complexity of parameterized problems on digraphs. The problems include the feedback vertex and arc set problems, induced subdigraph problems and directed k-leaf problems. We als...
详细信息
We survey results and open questions on complexity of parameterized problems on digraphs. The problems include the feedback vertex and arc set problems, induced subdigraph problems and directed k-leaf problems. We also prove some new results on the topic. Most of these new results are on parameterizations of the backward paired comparison problem.
暂无评论