A fast parameterized algorithm for co-path set
From MaRDI portal
Abstract: The k-CO-PATH SET problem asks, given a graph G and a positive integer k, whether one can delete k edges from G so that the remainder is a collection of disjoint paths. We give a linear-time fpt algorithm with complexity O^*(1.588^k) for deciding k-CO-PATH SET, significantly improving the previously best known O^*(2.17^k) of Feng, Zhou, and Wang (2015). Our main tool is a new O^*(4^{tw(G)}) algorithm for CO-PATH SET using the Cut&Count framework, where tw(G) denotes treewidth. In general graphs, we combine this with a branching algorithm which refines a 6k-kernel into reduced instances, which we prove have bounded treewidth.
Recommendations
- Randomized parameterized algorithms for co-path set problem
- Kernelization and randomized parameterized algorithms for co-path set problem
- Faster deterministic algorithms for \textsc{Co-path Packing} and \textsc{Co-path/cycle Packing}
- An approximation algorithm for the minimum co-path set problem
- Faster deterministic parameterized algorithm for k-path
Cited in
(6)- Faster deterministic algorithm for \textsc{Co-Path Set}
- Fast RNC and NC algorithms for maximal path sets
- Randomized parameterized algorithms for co-path set problem
- Kernelization and randomized parameterized algorithms for co-path set problem
- An approximation algorithm for the minimum co-path set problem
- Faster deterministic algorithms for \textsc{Co-path Packing} and \textsc{Co-path/cycle Packing}
This page was built for publication: A fast parameterized algorithm for co-path set
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4634414)
