We consider the SHORTEST ODD PATH problem, where given an undirected graph G, a weight function on its edges, and two vertices s and t in G, the aim is to find an (s, t)-path with odd length and, among all such paths,...
详细信息
We consider the SHORTEST ODD PATH problem, where given an undirected graph G, a weight function on its edges, and two vertices s and t in G, the aim is to find an (s, t)-path with odd length and, among all such paths, of minimum weight. For the case when the weight function is conservative, i.e., when every cycle has non-negative total weight, the complexity of the SHORTEST ODD PATH problem had been open for 20 years, and was recently shown to be NP-hard. We give a polynomial-time algorithm for the special case when the weight function is conservative and the set E- of negative-weight edges forms a single tree. Our algorithm exploits the strong connection between SHORTEST ODD PATH and the problem of finding two internally vertex-disjoint paths between two terminals in an undirected edgeweighted graph. It also relies on solving an intermediary problem variant called SHORTEST PARITY-CONSTRAINED ODD PATH where for certain edges we have parity constraints on their position along the path. Also, we exhibit two FPT algorithms for solving SHORTEST ODD PATH. The first FPT algorithm is parameterized by |E-|, the number of negative edges, or more generally, by the maximum size of a matching in the subgraph of G spanned by E-, when the weight function is conservative. Our second FPT algorithm is parameterized by the treewidth of G, and the algorithm does not rely on conservativeness. (c) 2024 The Authors. Published by Elsevier B.V. This is an open access article under the CC BY-NC license (http://***/licenses/by- nc/4.0/).
A graph is 2K(2)-partitionable if its vertex set can be partitioned into four nonempty parts A, B, C, D such that each vertex of A is adjacent to each vertex of B, and each vertex of C is adjacent to each vertex of D....
详细信息
A graph is 2K(2)-partitionable if its vertex set can be partitioned into four nonempty parts A, B, C, D such that each vertex of A is adjacent to each vertex of B, and each vertex of C is adjacent to each vertex of D. Determining whether an arbitrary graph is 2K(2)-partitionable is the only vertex-set partition problem into four nonempty parts according to external constraints whose computational complexity is open. We establish that the 2K(2)-partition problem parameterized by minimum degree is fixed-parameter tractable. We also show that for C-4-free graphs, circular-arc graphs, spiders, P-4-sparse graphs, and bipartite graphs the 2K(2)-partition problem can be solved in polynomial time. (C) 2009 Elsevier B.V. All rights reserved.
The parameterized complexity of the FACE COVER problem is considered. The input to this problem is a plane graph G with n vertices. The question asked is whether, for a given parameter value k, there exists a set of k...
详细信息
The parameterized complexity of the FACE COVER problem is considered. The input to this problem is a plane graph G with n vertices. The question asked is whether, for a given parameter value k, there exists a set of k or fewer faces whose boundaries collectively cover (contain) every vertex in G. Early attempts achieved run times of O*(12(k)) or worse, by reducing the problem into a special form of DOMINATING SET, namely RED-BLUE DOMINATING SET, restricted to planar graphs. Here, we consider a direct approach, where some surgical operation is performed on the graph at each branching decision. This paper builds on previous work of the authors and employs a structure theorem of Aksionov et al., with a detailed case analysis, to produce a FACE COVER algorithm that runs in O(4.6056(k) + n(2)) time. We also point to the tight connections with RED-BLUE DOMINATING SET on planar graphs via the annotated version of FACE COVER that we consider in our search tree algorithm. Hence, we get both a O(4.6056(k) + n(2)) time algorithm for solving RED-BLUE dominating SET on planar graphs and a polynomial time algorithm for producing a linear kernel for annotated face cover. (C) 2008 Elsevier B.V. All rights reserved.
Shortest common supersequence and longest common subsequence are two widely used measures to compare sequences in different fields, from AI planning to Bioinformatics. Inspired by recently proposed variants of these t...
详细信息
Shortest common supersequence and longest common subsequence are two widely used measures to compare sequences in different fields, from AI planning to Bioinformatics. Inspired by recently proposed variants of these two measures, we introduce a new version of the shortest common supersequence problem, where the solution is required to satisfy a given constraint on the number of occurrences of each symbol. First, we investigate the computational and approximation complexity of the problem, then we give a 3/2-approximation algorithm. Finally, we investigate the parameterized complexity of the problem, and we present a fixed-parameter algorithm. (C) 2013 Elsevier B.V. All rights reserved.
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). parameterized algorithms have been then developed to solve the problem when d is small. In this paper, with a new approach (called the 3-string approach), we first design a parameterized algorithm for binary strings that runs in O (nL + nd(3).6.731(d)) time, while the previous best runs in O (nL + nd.8(d)) time. We then extend the algorithm to arbitrary alphabet sizes, obtaining an algorithm that runs in time O(nL + nd.(1.612(vertical bar Sigma vertical bar + beta(2) + beta - 2))(d)), where vertical bar Sigma vertical bar is the alphabet size and beta = alpha(2) + 1 - 2 alpha(-1) + alpha(2) with alpha = 3 root root vertical bar Sigma vertical bar - 1 + 1. This new time bound is better than the previous best for small alphabets, including the very important case where vertical bar Sigma vertical bar = 4 (i.e., the case of DNA strings). (C) 2011 Elsevier Inc. All rights reserved.
The connected dominating set (CDS) problem is a well studied NP-hard problem with many important applications. Dorn et al. [ESA2005, LNCS3669,pp95-106] introduce a new technique to generate 2(O)(root n) time and fixed...
详细信息
ISBN:
(纸本)9783642174605
The connected dominating set (CDS) problem is a well studied NP-hard problem with many important applications. Dorn et al. [ESA2005, LNCS3669,pp95-106] introduce a new technique to generate 2(O)(root n) time and fixed-parameter algorithms for a number of non-local hard problems, including the CDS problem in planar graphs. The practical performance of this algorithm is yet to be evaluated. We perform a computational study for such an evaluation. The results show that the size of instances can be solved by the algorithm mainly depends on the branchwidth of the instances, coinciding with the theoretical result. 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. This suggests that the branch-decomposition based algorithms can be practical for the planar CDS problem.
We present a reduction procedure that takes an arbitrary instance of the 3-Set Packing problem and produces ail equivalent instance whose number of elements is bounded by a quadratic function of the input parameter. S...
详细信息
ISBN:
(纸本)9783642020162
We present a reduction procedure that takes an arbitrary instance of the 3-Set Packing problem and produces ail equivalent instance whose number of elements is bounded by a quadratic function of the input parameter. Such parameterized reductions are known as kernelization algorithms, and each reduced instance is called a problem kernel. Our result improves oil previously known kernelizations and call be generalized to produce improved kernels for the r-Set Packing problem whenever r is a fixed constant. Improved kernelization for r-Dimensional-Matching can also be inferred.
Recently, there has been significant theoretical progress towards fixed-parameter algorithms for the DOMINATING SET problem of planar graphs. It is known that the problem on a, planar graph with n vertices and dominat...
详细信息
ISBN:
(纸本)9783540850960
Recently, there has been significant theoretical progress towards fixed-parameter algorithms for the DOMINATING SET problem of planar graphs. It is known that the problem on a, planar graph with n vertices and dominating number k can be solved in O(c(root k)n) time using tree/branch-decomposition based algorithms, where c is some constant. However there has been no computational study report on the practical performances of the O(c(root k)n) time algorithms. In this paper, we report computational results of Fomin and Thilikos algorithm which uses the branch-decomposition based approach. The computational results show that the algorithm can solve the DOMINATING SET problem of large planar graphs in a practical time for the class of graphs with small branchwidth. For the class of graphs with large branchwidth, the size of instances that can be solved by the algorithm in a practical time is limited to a few hundreds edges. The practical performances of the algorithm coincide with the theoretical analysis of the algorithm. The results of this paper suggest that the branch-decomposition based algorithms can be practical for some applications on planar graphs.
The outerplanarity index of a planar graph G is the smallest k such that G has a k-outerplanar embedding. We show how to compute the outerplanarity index of an P.-vertex planar graph in O(n(2)) time, improving the pre...
详细信息
ISBN:
(纸本)9783540755197
The outerplanarity index of a planar graph G is the smallest k such that G has a k-outerplanar embedding. We show how to compute the outerplanarity index of an P.-vertex planar graph in O(n(2)) time, improving the previous best bound of O(k(3)n(2)). Using simple variations of the computation we can determine the radius of a planar graph in O(n(2)) time and its depth in O(n(3)) time. We also give a linear-time 4-approximation algorithm for the outerplanarity index and show how it can be used to solve maximum independent set and several other NP-hard problems faster on planar graphs with outerplanarity index within a constant factor of their treewidth.
We present a method for reducing the treewidth of a graph while preserving all the minimal s - t separators. This technique turns out to be very useful for establishing the fixed-parameter tractability of constrained ...
详细信息
ISBN:
(纸本)9783939897163
We present a method for reducing the treewidth of a graph while preserving all the minimal s - t separators. This technique turns out to be very useful for establishing the fixed-parameter tractability of constrained separation and bipartization problems. To demonstrate the power of this technique, we prove the fixed-parameter tractability of a number of well-known separation and bipartization problems with various additional restrictions (e.g., the vertices being removed from the graph form an independent set). These results answer a number of open questions in the area of parameterized complexity.
暂无评论