MAX-CUT is a well-known classical NP-hard problem. This problem asks whether the vertex-set of a given graph G = (V, E) can be partitioned into two disjoint subsets, A and B, such that there exist at least p edges wit...
详细信息
MAX-CUT is a well-known classical NP-hard problem. This problem asks whether the vertex-set of a given graph G = (V, E) can be partitioned into two disjoint subsets, A and B, such that there exist at least p edges with one endpoint in A and the other endpoint in B. It is well known that if p <= vertical bar E vertical bar/2, the answer is necessarily positive. A widely-studied variant of particular interest to parameterized complexity, called (k, n - k)-MAX-CUT, restricts the size of the subset A to be exactly k. For the (k, n - k)-MAX-CUT problem, we obtain an O* (2(p))-time algorithm, improving upon the previous best O* (4(p+o(p)))-time algorithm, as well as the first polynomial kernel. Our algorithm relies on a delicate combination of methods and notions, including independent sets, depth-search trees, bounded search trees, dynamic programming and treewidth, while our kernel relies on examination of the closed neighborhood of the neighborhood of a certain independent set of the graph G.
In this paper, we employ the multilinear detection technique, combined with proper colorings of graphs, to develop algorithms for two problems in bounded degree graphs. We focus mostly on the k-Internal Out-Branching ...
详细信息
In this paper, we employ the multilinear detection technique, combined with proper colorings of graphs, to develop algorithms for two problems in bounded degree graphs. We focus mostly on the k-Internal Out-Branching (k-IOB) problem, which asks if a given directed graph has an out-branching (i.e., a spanning tree with exactly one node of in-degree 0) with at least k internal nodes. The second problem, k-Tree, asks if a given undirected graph G has a (not necessarily induced) copy of a given tree T. That is, k-Tree asks whether T is a subgraph of G. We present an O*(4(k)) time randomized algorithm for k-IOB, which improves the O* running time of the previous best known algorithm for this problem. Then, for directed graphs whose underlying (simple, undirected) graphs have bounded degree Delta, we modify our algorithm to solve k-IOB in time O*(2(2-Delta+1/Delta(Delta-1))(k)). For k-Tree in graphs of bounded degree 3, we obtain an O*(1.914(k)) time randomized algorithm. In particular, all of our algorithms use polynomial space.
Given a digraph G, two vertices s, t is an element of V (G) and a non-negative integer k, the LONG DIRECTED (s, t)-PATH problem asks whether G has a path of length at least k from s to t. We present a simple algorithm...
详细信息
Given a digraph G, two vertices s, t is an element of V (G) and a non-negative integer k, the LONG DIRECTED (s, t)-PATH problem asks whether G has a path of length at least k from s to t. We present a simple algorithm that solves LONG DIRECTED (s, t)-PATH in time O*(4.884(k)). This results also in an improvement upon the previous fastest algorithm for LONG DIRECTED CYCLE. (C) 2018 Elsevier B.V. All rights reserved.
The edge dominating set problem is NP-hard, even when the graph is restricted to planar or bipartite graphs with maximum degree three. In this paper, we prove that in every graph where each vertex is incident to at mo...
详细信息
The edge dominating set problem is NP-hard, even when the graph is restricted to planar or bipartite graphs with maximum degree three. In this paper, we prove that in every graph where each vertex is incident to at most one vertex of degree one, the cardinality of maximum matching is at least 2 vertical bar V vertical bar/(3 + max(3, Delta(G))). Using the aforementioned result together with a simple reduction rule, we obtain a linear kernel of size 6k for the edge dominating set problem for graphs with maximum degree three. (C) 2018 Elsevier B.V. All rights reserved.
In an undirected graph, a matching cut is a partition of vertices into two sets such that the edges across the sets induce a matching. The MATCHING CUT problem is the problem of deciding whether a given graph has a ma...
详细信息
In an undirected graph, a matching cut is a partition of vertices into two sets such that the edges across the sets induce a matching. The MATCHING CUT problem is the problem of deciding whether a given graph has a matching cut. Let H be a fixed undirected graph. A vertex coloring of an undirected input graph G is said to be an H -FREE COLORING if none of the color classes contain H as an induced subgraph. The H -FREE CHROMATIC NUMBER of G is the minimum number of colors required for an H -FREE COLORING of G. Both The MATCHING CUT problem and the H -FREE COLORING problem can be expressed using a monadic second-order logic (MSOL) formula and hence is solvable in linear time for graphs with bounded tree-width. However, this approach leads to a running time of f (||phi||, t)n(O(1)), where ||phi|| is the length of the MSOL formula, t is the tree-width of the graph and n is the number of vertices of the graph. The dependency of f (||phi||, t) on ||phi|| can be as bad as a tower of exponentials. In this paper, we provide explicit combinatorial FPT algorithms for MATCHING CUT problem and H -FREE COLORING problem, parameterized by the tree-width of G. The single exponential FPT algorithm for the MATCHING CUT problem answers an open question posed by Kratsch and Le (2016). The techniques used in the paper are also used to provide an FPT algorithm for a variant of H-free coloring, where H is forbidden as a subgraph (not necessarily induced) in the color classes of G. (c) 2021 Elsevier B.V. All rights reserved.
Let G = (V, E) be a graph of order n and let B(D) be the set of vertices in V\D that have a neighbor in the vertex set D. The differential of D is defined as partial derivative(D) = vertical bar B(D)vertical bar - ver...
详细信息
Let G = (V, E) be a graph of order n and let B(D) be the set of vertices in V\D that have a neighbor in the vertex set D. The differential of D is defined as partial derivative(D) = vertical bar B(D)vertical bar - vertical bar D vertical bar and the differential of a graph G, written partial derivative(G), is equal to max{partial derivative(D) : D subset of V}. If G is connected and n >= 3, partial derivative(G) >= n/5 is known. This immediately leads to a linear vertex kernel result (in the terminology of parameterized complexity) for the problem of deciding whether partial derivative(G) >= k, taking k as the parameter. We then establish a new combinatorial result which establishes that partial derivative(G) >= n/4 if G is a connected graph of order n >= 6 and if G contains no induced path of five vertices whose midpoint is a cut vertex and whose endpoints have degree one. This technical combinatorial theorem can be used to derive an even smaller linear vertex kernel for general graphs. Also, we show that the related maximization problem allows for a polynomial-time factor-1/4 approximation algorithm. (C) 2014 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.
We consider an augmentation problem on undirected and directed graphs, where given a directed (an undirected) graph G and p pairs of vertices , one has to find the minimum weight set of arcs (edges) to be added to the...
详细信息
We consider an augmentation problem on undirected and directed graphs, where given a directed (an undirected) graph G and p pairs of vertices , one has to find the minimum weight set of arcs (edges) to be added to the graph so that the resulting graph has (can be oriented to have) directed paths between the specified pairs of vertices. In the undirected case, we present an FPT-algorithm with respect to the number of new edges. Also, we have implemented and evaluated the algorithm on some real-world networks to show its efficiency in decreasing the size of input graphs and converting them to much smaller kernels. In the directed case, we consider the complexity of the problem with respect to the various parameters and present some parameterized algorithms and parameterized complexity results for it.
The (parameterized) Minimum Link-Length Rectilinear Spanning Path problem in the d-dimensional Euclidean space R-d (d-RSP), for a given set S of n points in R-d and a positive integer k, is to find a piecewise-linear ...
详细信息
The (parameterized) Minimum Link-Length Rectilinear Spanning Path problem in the d-dimensional Euclidean space R-d (d-RSP), for a given set S of n points in R-d and a positive integer k, is to find a piecewise-linear path P with at most k line-segments that covers (i.e., contains) all points in S, where all line-segments in P are axis-parallel. We first prove that the problem 2-RSP is NP-complete, improving the previously known result that the problem 10-RSP is NP-complete. We then consider a constrained d-RSP problem in which each line-segment s in the spanning path must cover all the points in the given set that share the same line with s. We present a new parameterized algorithm with running time O-center dot((2d)(k)) for the constrained d-RSP problem, which significantly improves the previous best result and is the first parameterized algorithm of running time O-center dot(k(O(k))) for the constrained d-RSP problem for a fixed d. We show that these results can be extended to the Minimum Link-Length Rectilinear Traveling Salesman problem.
The "jump number scheduling problem" has been shown to be NP-complete. However, for a fixed parameter k, El-Zahar and Schmerl show that the decision problem "is the jump number less than or equal to k?&...
详细信息
The "jump number scheduling problem" has been shown to be NP-complete. However, for a fixed parameter k, El-Zahar and Schmerl show that the decision problem "is the jump number less than or equal to k?" is solvable in polynomial time. Their algorithm has a running time in excess of O(n(k!)), where n is the size of the schedule and k is a fixed parameter bounding the number of jumps permitted. We obtain a significant improvement on this by giving a linear-time constructive algorithm that outputs a schedule with less than or equal to k jumps, if one exists, or no otherwise. (C) 2001 Elsevier Science B.V. All rights reserved.
暂无评论