A multivariate analysis of the strict terminal connection problem

摘要

A strict connection tree of a graph G for a set W is a tree subgraph of G whose leaf set equals W. The Strict terminal connection problem (S-TCP) is a network design problem whose goal is to decide whether G admits a strict connection tree T for W with at most ℓ vertices of degree 2 and r vertices of degree at least 3. We establish a Poly vs. NP-c dichotomy for S-TCP with respect to ℓ and Δ(G). We prove that S-TCP parameterized by r is W[2]-hard even if ℓ is bounded by a constant; we provide a kernelization for S-TCP parameterized by ℓ, r and Δ(G), and we prove that such a version of the problem does not admit a polynomial kernel, unless NP⊆coNP/poly. Finally, we analyze S-TCP on split graphs and cographs.