首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 31 毫秒
1.
Cluster Editing is transforming a graph by at most k edge insertions or deletions into a disjoint union of cliques. This problem is fixed-parameter tractable (FPT). Here we compute concise enumerations of all minimal solutions in O(2.27 k +k 2 n+m) time. Such enumerations support efficient inference procedures, but also the optimization of further objectives such as minimizing the number of clusters. In an extended problem version, target graphs may have a limited number of overlaps of cliques, measured by the number t of edges that remain when the twin vertices are merged. This problem is still in FPT, with respect to the combined parameter k and t. The result is based on a property of twin-free graphs. We also give FPT results for problem versions avoiding certain artificial clusterings. Furthermore, we prove that all solutions with minimal edit sequences differ on a so-called full kernel with at most k 2/4+O(k) vertices, that can be found in polynomial time. The size bound is tight. We also get a bound for the number of edges in the full kernel, which is optimal up to a (large) constant factor. Numerous open problems are mentioned.  相似文献   

2.
The Convex Recoloring (CR) problem measures how far a tree of characters differs from exhibiting a so-called “perfect phylogeny”. For an input consisting of a vertex-colored tree T, the problem is to determine whether recoloring at most k vertices can achieve a convex coloring, meaning by this a coloring where each color class induces a subtree. The problem was introduced by Moran and Snir (J. Comput. Syst. Sci. 73:1078–1089, 2007; J. Comput. Syst. Sci. 74:850–869, 2008) who showed that CR is NP-hard, and described a search-tree based FPT algorithm with a running time of O(k(k/log k) k n 4). The Moran and Snir result did not provide any nontrivial kernelization. In this paper, we show that CR has a kernel of size O(k 2).  相似文献   

3.
The Feedback Vertex Set problem on unweighted, undirected graphs is considered. Improving upon a result by Burrage et al. (Proceedings 2nd International Workshop on Parameterized and Exact Computation, pp. 192–202, 2006), we show that this problem has a kernel with O(k 3) vertices, i.e., there is a polynomial time algorithm, that given a graph G and an integer k, finds a graph G′ with O(k 3) vertices and integer k′≤k, such that G has a feedback vertex set of size at most k, if and only if G′ has a feedback vertex set of size at most k′. Moreover, the algorithm can be made constructive: if the reduced instance G′ has a feedback vertex set of size k′, then we can easily transform a minimum size feedback vertex set of G′ into a minimum size feedback vertex set of G. This kernelization algorithm can be used as the first step of an FPT algorithm for Feedback Vertex Set, but also as a preprocessing heuristic for Feedback Vertex Set.  相似文献   

4.
《国际计算机数学杂志》2012,89(12):1477-1487
Based on a Directed Acyclic Graph approach, an O(kn 2) time sequential algorithm is presented to solve the maximum weight k-independent set problem on weighted-permutation graphs. The weights considered here are all non-negative and associated with each of the n vertices of the graph. This problem has many applications in practical problems like k-machines job scheduling problem, k-colourable subgraph problem, VLSI design and routing problem.  相似文献   

5.
We study extremal questions on induced matchings in certain natural graph classes. We argue that these questions should be asked for twinless graphs, that is graphs not containing two vertices with the same neighborhood. We show that planar twinless graphs always contain an induced matching of size at least n/40 while there are planar twinless graphs that do not contain an induced matching of size (n+10)/27. We derive similar results for outerplanar graphs and graphs of bounded genus. These extremal results can be applied to the area of parameterized computation. For example, we show that the induced matching problem on planar graphs has a kernel of size at most 40k that is computable in linear time; this significantly improves the results of Moser and Sikdar (2007). We also show that we can decide in time O(k91+n) whether a planar graph contains an induced matching of size at least k.  相似文献   

6.
We present an O(k3n2+n3) time FPT algorithm for the feedback vertex set problem in a bipartite tournament on n vertices with integral weights. This improves the previously best known O(k3.12n4) time FPT algorithm for the problem.  相似文献   

7.
We consider the multivariate interlace polynomial introduced by Courcelle (Electron. J. Comb. 15(1), 2008), which generalizes several interlace polynomials defined by Arratia, Bollobás, 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 23k2+O(k)·n2^{3k^{2}+O(k)}\cdot n arithmetic operations and can be efficiently implemented in parallel.  相似文献   

8.
We present a general framework for designing fast subexponential exact and parameterized algorithms on planar graphs. Our approach is based on geometric properties of planar branch decompositions obtained by Seymour and Thomas, combined with refined techniques of dynamic programming on planar graphs based on properties of non-crossing partitions. To exemplify our approach we show how to obtain an  $O(2^{6.903\sqrt{n}})We present a general framework for designing fast subexponential exact and parameterized algorithms on planar graphs. Our approach is based on geometric properties of planar branch decompositions obtained by Seymour and Thomas, combined with refined techniques of dynamic programming on planar graphs based on properties of non-crossing partitions. To exemplify our approach we show how to obtain an  O(26.903?n)O(2^{6.903\sqrt{n}}) time algorithm solving weighted Hamiltonian Cycle on an n-vertex planar graph. Similar technique solves Planar Graph Travelling Salesman Problem with n cities in time O(29.8594?n)O(2^{9.8594\sqrt{n}}) . Our approach can be used to design parameterized algorithms as well. For example, we give an algorithm that for a given k decides if a planar graph on n vertices has a cycle of length at least k in time O(213.6?kn+n3)O(2^{13.6\sqrt{k}}n+n^{3}) .  相似文献   

9.
Dániel Marx 《Algorithmica》2010,57(4):747-768
It is known to be NP-hard to decide whether a graph can be made chordal by the deletion of k vertices or by the deletion of k edges. Here we present a uniformly polynomial-time algorithm for both problems: the running time is f(k)⋅n α for some constant α not depending on k and some f depending only on k. For large values of n, such an algorithm is much better than trying all the O(n k ) possibilities. Therefore, the chordal deletion problem parameterized by the number k of vertices or edges to be deleted is fixed-parameter tractable. This answers an open question of Cai (Discrete Appl. Math. 127:415–429, 2003).  相似文献   

10.
There is substantial literature dealing with fixed parameter algorithms for the dominating set problem on various families of graphs. In this paper, we give a k O(dk) n time algorithm for finding a dominating set of size at most k in a d-degenerated graph with n vertices. This proves that the dominating set problem is fixed-parameter tractable for degenerated graphs. For graphs that do not contain K h as a topological minor, we give an improved algorithm for the problem with running time (O(h)) hk n. For graphs which are K h -minor-free, the running time is further reduced to (O(log h)) hk/2 n. Fixed-parameter tractable algorithms that are linear in the number of vertices of the graph were previously known only for planar graphs. For the families of graphs discussed above, the problem of finding an induced cycle of a given length is also addressed. For every fixed H and k, we show that if an H-minor-free graph G with n vertices contains an induced cycle of size k, then such a cycle can be found in O(n) expected time as well as in O(nlog n) worst-case time. Some results are stated concerning the (im)possibility of establishing linear time algorithms for the more general family of degenerated graphs. A preliminary version of this paper appeared in the Proceedings of the 13th Annual International Computing and Combinatorics Conference (COCOON), Banff, Alberta, Canada (2007), pp. 394–405. N. Alon research supported in part by a grant from the Israel Science Foundation, and by the Hermann Minkowski Minerva Center for Geometry at Tel Aviv University. This paper forms part of a Ph.D. thesis written by S. Gutner under the supervision of Prof. N. Alon and Prof. Y. Azar in Tel Aviv University.  相似文献   

11.
We show that the Dominating Set problem parameterized by solution size is fixed-parameter tractable (FPT) in graphs that do not contain the claw (K1,3, the complete bipartite graph on four vertices where the two parts have one and three vertices, respectively) as an induced subgraph. We present an algorithm that uses 2O(k2)nO(1) time and polynomial space to decide whether a claw-free graph on n vertices has a dominating set of size at most k. Note that this parameterization of Dominating Set is W[2]-hard on the set of all graphs, and thus is unlikely to have an FPT algorithm for graphs in general.The most general class of graphs for which an FPT algorithm was previously known for this parameterization of Dominating Set is the class of Ki,j-free graphs, which exclude, for some fixed i,jN, the complete bipartite graph Ki,j as a subgraph. For i,j≥2, the class of claw-free graphs and any class of Ki,j-free graphs are not comparable with respect to set inclusion. We thus extend the range of graphs over which this parameterization of Dominating Set is known to be fixed-parameter tractable.We also show that, in some sense, it is the presence of the claw that makes this parameterization of the Dominating Set problem hard. More precisely, we show that for any t≥4, the Dominating Set problem parameterized by the solution size is W[2]-hard in graphs that exclude the t-claw K1,t as an induced subgraph. Our arguments also imply that the related Connected Dominating Set and Dominating Clique problems are W[2]-hard in these graph classes.Finally, we show that for any tN, the Clique problem parameterized by solution size, which is W[1]-hard on general graphs, is FPT in t-claw-free graphs. Our results add to the small and growing collection of FPT results for graph classes defined by excluded subgraphs, rather than by excluded minors.  相似文献   

12.
This paper is composed of two parts. In the first part, an improved algorithm is presented for the problem of finding length-bounded two vertex-disjoint paths in an undirected planar graph. The presented algorithm requires O(n3bmin) time and O(n2bmin) space, where bmin is the smaller of the two given length bounds. In the second part of this paper, we consider the minmax k vertex-disjoint paths problem on a directed acyclic graph, where k?2 is a constant. An improved algorithm and a faster approximation scheme are presented. The presented algorithm requires O(nk+1Mk−1) time and O(nkMk−1) space, and the presented approximation scheme requires O((1/?)k−1n2klogk−1M) time and O((1/?)k−1n2k−1logk−1M) space, where ? is the given approximation parameter and M is the length of the longest path in an optimal solution.  相似文献   

13.
Kernels for feedback arc set in tournaments   总被引:1,自引:0,他引:1  
A tournament T=(V,A) is a directed graph in which there is exactly one arc between every pair of distinct vertices. Given a digraph on n vertices and an integer parameter k, the Feedback Arc Set problem asks whether the given digraph has a set of k arcs whose removal results in an acyclic digraph. The Feedback Arc Set problem restricted to tournaments is known as the k-Feedback Arc Set in Tournaments (k-FAST) problem. In this paper we obtain a linear vertex kernel for k-FAST. That is, we give a polynomial time algorithm which given an input instance T to k-FAST obtains an equivalent instance T on O(k) vertices. In fact, given any fixed ?>0, the kernelized instance has at most (2+?)k vertices. Our result improves the previous known bound of O(k2) on the kernel size for k-FAST. Our kernelization algorithm solves the problem on a subclass of tournaments in polynomial time and uses a known polynomial time approximation scheme for k-FAST.  相似文献   

14.
S. Sunder  Xin He 《Algorithmica》1996,16(3):243-262
We present a parallel algorithm for solving the minimum weighted completion time scheduling problem for transitive series parallel graphs. The algorithm takesO(log2 n) time withO(n 3) processors on a CREW PRAM, wheren is the number of vertices of the input graph. This is the first NC algorithm for solving the problem.Research supported in part by NSF Grants CCR-9011214 and CCR-9205982.  相似文献   

15.
Finding a dominating set of minimum cardinality is an NP-hard graph problem, even when the graph is bipartite. In this paper we are interested in solving the problem on graphs having a large independent set. Given a graph G with an independent set of size z, we show that the problem can be solved in time O(2nz), where n is the number of vertices of G. As a consequence, our algorithm is able to solve the dominating set problem on bipartite graphs in time O(2n/2). Another implication is an algorithm for general graphs whose running time is O(n1.7088).  相似文献   

16.
Given a stable marriage problem instance represented by a bipartite graph having 2n vertices and m edges, we describe an algorithm that can verify the stability of k different matchings in a batch fashion in O((m+kn)log 2 n) time. This affirmatively answers a longstanding open question of Gusfield and Irving as to whether stability can be verified in a batch setting (after sufficient preprocessing) in time sub-quadratic in n.  相似文献   

17.
The notion of distance constrained graph labelings, motivated by the Frequency Assignment Problem, reads as follows: A mapping from the vertex set of a graph G=(V,E) into an interval of integers {0,…,k} is an L(2,1)-labeling of G of span k if any two adjacent vertices are mapped onto integers that are at least 2 apart, and every two vertices with a common neighbor are mapped onto distinct integers. It is known that for any fixed k≥4, deciding the existence of such a labeling is an NP-complete problem. We present exact exponential time algorithms that are faster than the naive O *((k+1) n ) algorithm that would try all possible mappings. The improvement is best seen in the first NP-complete case of k=4, where the running time of our algorithm is O(1.3006 n ). Furthermore we show that dynamic programming can be used to establish an O(3.8730 n ) algorithm to compute an optimal L(2,1)-labeling.  相似文献   

18.
In this paper we present unified methods to solve the minus and signed total domination problems for chordal bipartite graphs and trees in O(n2) and O(n+m) time, respectively. We also prove that the decision problem for the signed total domination problem on doubly chordal graphs is NP-complete. Note that bipartite permutation graphs, biconvex bipartite graphs, and convex bipartite graphs are subclasses of chordal bipartite graphs.  相似文献   

19.
We present new efficient deterministic and randomized distributed algorithms for decomposing a graph with n nodes into a disjoint set of connected clusters with radius at most k−1 and having O(n 1+1/k ) intercluster edges. We show how to implement our algorithms in the distributed CONGEST\mathcal{CONGEST} model of computation, i.e., limited message size, which improves the time complexity of previous algorithms (Moran and Snir in Theor. Comput. Sci. 243(1–2):217–241, 2000; Awerbuch in J. ACM 32:804–823, 1985; Peleg in Distributed Computing: A Locality-Sensitive Approach, 2000) from O(n) to O(n 1−1/k ). We apply our algorithms for constructing low stretch graph spanners and network synchronizers in sublinear deterministic time in the CONGEST\mathcal{CONGEST} model.  相似文献   

20.
Given a digraph DD, the Minimum Leaf Out-Branching problem (MinLOB) is the problem of finding in DD an out-branching with the minimum possible number of leaves, i.e., vertices of out-degree 0. We prove that MinLOB is polynomial-time solvable for acyclic digraphs. In general, MinLOB is NP-hard and we consider three parameterizations of MinLOB. We prove that two of them are NP-complete for every value of the parameter, but the third one is fixed-parameter tractable (FPT). The FPT parameterization is as follows: given a digraph DD of order nn and a positive integral parameter kk, check whether DD contains an out-branching with at most n−knk leaves (and find such an out-branching if it exists). We find a problem kernel of order O(k2)O(k2) and construct an algorithm of running time O(2O(klogk)+n6)O(2O(klogk)+n6), which is an ‘additive’ FPT algorithm. We also consider transformations from two related problems, the minimum path covering and the maximum internal out-tree problems into MinLOB, which imply that some parameterizations of the two problems are FPT as well.  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号