2026-07-22T06:36:48Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:4834 2024-03-06T10:35:23Z ddc:004 open_access

Connecting Vertices by Independent Trees Basavaraju, Manu Fomin, Fedor V. Golovach, Petr A. Saurabh, Saket Parameterized complexity FPT-algorithms completely independent spanning trees We study the paramereteized complexity of the following connectivity problem. For a vertex subset U of a graph G, trees T_1,...,T_s of G are completely independent spanning trees of U if each of them contains U, and for every two distinct vertices u,v in U, the paths from u to v in T_1,...,T_s are pairwise vertex disjoint except for end-vertices u and v. Then for a given s >= 2 and a parameter k, the task is to decide if a given n-vertex graph G contains a set U of size at least k such that there are s completely independent spanning trees of U. The problem is known to be NP-complete already for s=2. We prove the following results: (*) For s=2 the problem is solvable in time 2^{O(k)}*n^{O(1)}. (*) For s=2 the problem does not admit a polynomial kernel unless NP subseteq coNP/poly. (*) For arbitrary s, we show that the problem is solvable in time f(s,k)n^{O(1)} for some function f of s and k only. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Manu Basavaraju and Fedor V. Fomin and Petr A. Golovach and Saket Saurabh 2014 Is Part Of LIPIcs, Volume 29, 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2014.73 urn:nbn:de:0030-drops-48340 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2014.73 eng https://creativecommons.org/licenses/by/3.0/legalcode