dc.contributor.author | Basavaraju, Manu | |
dc.contributor.author | Fomin, Fedor | |
dc.contributor.author | Golovach, Petr | |
dc.contributor.author | Saurabh, Saket | |
dc.date.accessioned | 2016-04-26T12:12:30Z | |
dc.date.available | 2016-04-26T12:12:30Z | |
dc.date.issued | 2014 | |
dc.identifier.issn | 1868-8969 | en_US |
dc.identifier.uri | https://hdl.handle.net/1956/11950 | |
dc.description.abstract | We study the paramereteized complexity of the following connectivity problem. For a vertex subset U of a graph G, trees T1, . . . , Ts of G are completely independent spanning trees of U if each of them contains U , and for every two distinct vertices u, v ∈ U , the paths from u to v in T1, . . . , Ts 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 2O(k)nO(1). For s = 2 the problem does not admit a polynomial kernel unless NP ⊆ coNP /poly. For arbitrary s, we show that the problem is solvable in time f (s, k)nO(1) for some function f of s and k only. | en_US |
dc.language.iso | eng | eng |
dc.publisher | Schloss Dagstuhl – Leibniz-Zentrum für Informatik GmbH | en_US |
dc.rights | Attribution CC BY | eng |
dc.rights.uri | https://creativecommons.org/licenses/by/3.0/ | eng |
dc.subject | Parameterized complexity | eng |
dc.subject | FPT-algorithms | eng |
dc.subject | completely independent spanning trees | eng |
dc.title | Connecting Vertices by Independent Trees | en_US |
dc.type | Journal article | |
dc.type | Peer reviewed | |
dc.date.updated | 2016-03-31T09:45:19Z | |
dc.description.version | publishedVersion | en_US |
dc.rights.holder | Copyright Manu Basavaraju, Fedor V. Fomin, Petr A. Golovach, and Saket Saurabh | en_US |
dc.identifier.doi | https://doi.org/10.4230/lipics.fsttcs.2014.73 | |
dc.identifier.cristin | 1216381 | |
dc.source.journal | Leibniz International Proceedings in Informatics | |
dc.source.pagenumber | 73-84 | |
dc.subject.nsi | VDP::Matematikk og Naturvitenskap: 400 | en_US |
dc.identifier.citation | Leibniz International Proceedings in Informatics 2014, 29:73-84 | |
dc.source.volume | 29 | |