Connecting Vertices by Independent Trees

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.