2026-07-25T02:13:36Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6937 2024-03-06T10:38:50Z ddc:004 open_access

A Fast Parameterized Algorithm for Co-Path Set Sullivan, Blair D. van der Poel, Andrew co-path set parameterized complexity Cut&Count bounded treewidth 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, randomized 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Blair D. Sullivan and Andrew van der Poel 2017 Is Part Of LIPIcs, Volume 63, 11th International Symposium on Parameterized and Exact Computation (IPEC 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.IPEC.2016.28 urn:nbn:de:0030-drops-69371 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2016.28 eng https://creativecommons.org/licenses/by/3.0/legalcode