Name
Abstract | ||
|---|---|---|
In this paper we consider generalized versions of four well-studied problems in parameterized complexity and exact exponential time algorithms: k-PATH, SET PACKING, MULTILINEAR MONOMIAL TESTING and HAMILTONIAN PATH. The generalization is in every case obtained by introducing a relaxation parameter, which relaxes the constraints on feasible solutions. For example, the k-PATH problem is generalized to rSIMPLE k-PATH where the task is to find a walk of length k that never visits any vertex more than r times. This problem was first considered by Abasi et al. [1]. HAMILTONIAN PATH is generalized to DEGREE BOUNDED SPANNING TREE, where the input is a graph G and integer d, and the task is to find a spanning tree T of G such that every vertex has degree at most d in T. The generalized problems can easily be shown to be NP-complete for every fixed value of the relaxation parameter. On the other hand, we give algorithms for the generalized problems whose worst-case running time (a) matches the running time of the best algorithms for the original problems up to constants in the exponent, and (b) improves significantly as the relaxation parameter increases. For example, we give a deterministic algorithm with running time 0* (2) for T-SIMPLE k-PATH matching up to a constant in the exponent the randomized algorithm of Abasi et al. [1], and a randomized algorithm with running time 0* (29(ni2i)) for DEGREE BOUNDED SPANNING TREE improving upon an 0(2) algorithm of Fomin et al. [8]. On the way to obtain our results we generalize the notion of representative sets to multisets, and give an efficient algorithm to compute such representative sets. Both the generalization of representative sets to multisets and the algorithm to compute them may be of independent interest. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1007/978-3-662-48350-3_46 | ALGORITHMS - ESA 2015 |
Field | DocType | Volume |
Discrete mathematics,Parameterized complexity,Combinatorics,Exact algorithm,Vertex (geometry),Hamiltonian path,Algorithm,Set packing,Spanning tree,Monomial,Multilinear map,Mathematics | Conference | 9294 |
ISSN | Citations | PageRank |
0302-9743 | 4 | 0.42 |
References | Authors | |
19 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ariel Gabizon | 1 | 156 | 13.97 |
| Daniel Lokshtanov | 2 | 1438 | 110.05 |
| michal pilipczuk | 3 | 403 | 51.93 |