In this paper, we present a faster exact algorithm which solves the Maximum Induced Matching problem for subcubic graphs. Here let n be the overall number of vertices and k be the number of those vertices of degree 3 ...
详细信息
ISBN:
(数字)9789819705665
ISBN:
(纸本)9789819705658;9789819705665
In this paper, we present a faster exact algorithm which solves the Maximum Induced Matching problem for subcubic graphs. Here let n be the overall number of vertices and k be the number of those vertices of degree 3 where all neighbours have also at least degree 2. Then the runtime is at most O(1.2335(k)) center dot Poly(n), giving an FPT bound for the time used by the algorithm;the algorithm uses the result of Monien and Preis combined with a bound obtained by applying the measure and conquer technique where the number k replaces n as the measure used;note that k <= n.
We give a new general approach for designing exact exponential -timealgorithms for subset problems. In a subset problem the input implicitly describes a family of sets over a universe of size n and the task is to det...
详细信息
ISBN:
(纸本)9781450341325
We give a new general approach for designing exact exponential -timealgorithms for subset problems. In a subset problem the input implicitly describes a family of sets over a universe of size n and the task is to determine whether the family contains at least one set. A typical example of a subset problem is WEIGHTED d-SAT. Here, the input is a CNF-formula with clauses of size at most d, and an integer W. The universe is the set of variables and the variables have integer weights. The family contains all the subsets S of variables such that the total weight of the variables in S does not exceed W, and setting the variables in S to 1 and the remaining variables to 0 satisfies the formula. Our approach is based on "monotone local search", where the goal is to extend a partial solution to a solution by adding as few elements as possible. More formally, in the extension problem we are also given as input a subset X of the universe and an integer k. The task is to determine whether one can add at most k elements to X to obtain a set in the (implicitly defined) family. Our main result is that a c(k)n(O(1)) time algorithm for the extension problem immediately yields a randomized algorithm for finding a solution of any size with running time O((2-1/c)n). In many cases, the extension problem can be reduced to simply finding a solution of size at most k. Furthermore, efficient algorithms for finding small solutions have been extensively studied in the field of parameterized algorithms. Directly applying these algorithms, our theorem yields in one stroke significant improvements over the best known exponential-timealgorithms for several well-studied problems, including d-HITTING SET, FEEDBACK VERTEX SET, NODE UNIQUE LABEL COVER, and WEIGHTED d-SAT. Our results demonstrate an interesting and very concrete connection between parameterized algorithms and exact exponential time algorithms. We also show how to derandomize our algorithms at the cost of a subexponential multiplicat
The symmetric traveling salesman problem (TSP) is the problem of finding the shortest Hamiltonian cycle in an edge-weighted undirected graph. In 1962 Bellman, and independently Held and Karp, showed that TSP instances...
详细信息
ISBN:
(纸本)9781450369794
The symmetric traveling salesman problem (TSP) is the problem of finding the shortest Hamiltonian cycle in an edge-weighted undirected graph. In 1962 Bellman, and independently Held and Karp, showed that TSP instances with n cities can be solved in O(n(2)2(n)) time. Since then it has been a notorious problem to improve the runtime to O((2-epsilon)(n)) for some constant epsilon > 0. In this work we establish the following progress: If (sx s)-matrices can be multiplied in s(2+o(1)) time, than all instances of TSP in bipartite graphs can be solved in O(1.9999(n)) time by a randomized algorithm with constant error probability. We also indicate how our methods may be useful to solve TSP in non-bipartite graphs. On a high level, our approach is via a new problem called MINHAMPAIR: Given two families of weighted perfect matchings, find a combination of minimum weight that forms a Hamiltonian cycle. As our main technical contribution, we give a fast algorithm for MINHAMPAIR based on a new sparse cut-based factorization of the 'matchings connectivity matrix', introduced by Cygan et al. [JACM'18].
A graph with forbidden paths is a pair (G, F) where G is a graph and F is a subset of the set of paths in G. A simple path avoiding forbidden paths in (G, F) is a simple path in G such that each subpath is not in F. I...
详细信息
ISBN:
(纸本)9783319731179;9783319731162
A graph with forbidden paths is a pair (G, F) where G is a graph and F is a subset of the set of paths in G. A simple path avoiding forbidden paths in (G, F) is a simple path in G such that each subpath is not in F. It is shown in [S. Szeider, Finding paths in graphs avoiding forbidden transitions, DAM 126] that the problem of deciding the existence of a simple path avoiding forbidden paths in a graph with forbidden paths is Np-complete even when the forbidden paths are restricted to be transitions, i.e., of length two. We give an exact exponentialtime algorithm that decides in O(2(n)n(2k+O(1))) time and O(n(k+O(1))) space whether there exists a simple path between two vertices of a given n-vertex graph where k is the length of the longest forbidden path. We also obtain an exact O(2(n) n(2k+O(1))) time and O(n(k+O(1))) space algorithm to check the existence of a Hamiltonian path avoiding forbidden paths and for the graphs with forbidden transitions an exact O * (2(n)) time and polynomial space algorithm to check the existence of a Hamiltonian cycle avoiding forbidden transitions. In the last section, we present a new sufficient condition for graphs to have a Hamiltonian cycle, which gives us some interesting corollaries for graphs with forbidden paths.
The symmetric traveling salesman problem (TSP) is the problem of finding the shortest Hamiltonian cycle in an edge-weighted undirected graph. In 1962 Bellman, and independently Held and Karp, showed that TSP instances...
详细信息
ISBN:
(纸本)9781450369794
The symmetric traveling salesman problem (TSP) is the problem of finding the shortest Hamiltonian cycle in an edge-weighted undirected graph. In 1962 Bellman, and independently Held and Karp, showed that TSP instances with n cities can be solved in O(n 22 n ) time. Since then it has been a notorious problem to improve the runtime to O((2−є) n ) for some constant є>0. In this work we establish the following progress: If (s× s)-matrices can be multiplied in s 2+o(1) time, than all instances of TSP in bipartite graphs can be solved in O(1.9999 n ) time by a randomized algorithm with constant error probability. We also indicate how our methods may be useful to solve TSP in non-bipartite graphs. On a high level, our approach is via a new problem called MinHamPair: Given two families of weighted perfect matchings, find a combination of minimum weight that forms a Hamiltonian cycle. As our main technical contribution, we give a fast algorithm for MinHamPair based on a new sparse cut-based factorization of the ‘matchings connectivity matrix’, introduced by Cygan et al. [JACM’18].
暂无评论