## Connecting Vertices by Independent Trees

##### Type

Conference object###### Not peer reviewed

###### publishedVersion

##### View/Open

##### Date

2014

##### Metadata

Show full item record##### 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.

##### Citation

Leibniz International Proceedings in Informatics 2014, 29:73-84##### Publisher

Schloss Dagstuhl – Leibniz-Zentrum für Informatik GmbH##### Collections

Copyright Manu Basavaraju, Fedor V. Fomin, Petr A. Golovach, and Saket Saurabh