Document Open Access Logo

Connecting Vertices by Independent Trees

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

PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2014.73.pdf
  • Filesize: 0.53 MB
  • 12 pages

Document Identifiers

Author Details

Manu Basavaraju
Fedor V. Fomin
Petr A. Golovach
Saket Saurabh

Cite As Get BibTex

Manu Basavaraju, Fedor V. Fomin, Petr A. Golovach, and Saket Saurabh. Connecting Vertices by Independent Trees. In 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 29, pp. 73-84, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014) https://doi.org/10.4230/LIPIcs.FSTTCS.2014.73

Abstract

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.

Subject Classification

Keywords
  • Parameterized complexity
  • FPT-algorithms
  • completely independent spanning trees

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Hans L. Bodlaender, Rodney G. Downey, Michael R. Fellows, and Danny Hermelin. On problems without polynomial kernels. J. Comput. Syst. Sci., 75(8):423-434, 2009. Google Scholar
  2. Holger Dell and Dieter van Melkebeek. Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses. In Leonard J. Schulman, editor, Proc. of the 42nd ACM Symp. on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5-8 June 2010, pages 251-260. ACM, 2010. Google Scholar
  3. Danny Dolev, Joseph Y. Halpern, Barbara Simons, and H. Raymond Strong. A new look at fault-tolerant network routing. Inf. Comput., 72(3):180-196, 1987. Google Scholar
  4. Fedor V. Fomin, Daniel Lokshtanov, and Saket Saurabh. Efficient computation of representative sets with applications in parameterized and exact algorithms. In Chandra Chekuri, editor, Proc. of the 25th Annual ACM-SIAM Symp. on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014, pages 142-151. SIAM, 2014. Google Scholar
  5. Lance Fortnow and Rahul Santhanam. Infeasibility of instance compression and succinct pcps for NP. In Cynthia Dwork, editor, Proc. of the 40th Annual ACM Symp. on Theory of Computing, Victoria, BC, Canada, May 17-20, 2008, pages 133-142. ACM, 2008. Google Scholar
  6. Martin Grohe, Ken-ichi Kawarabayashi, Dániel Marx, and Paul Wollan. Finding topological subgraphs is fixed-parameter tractable. In Lance Fortnow and Salil P. Vadhan, editors, Proc. of the 43rd ACM Symp. on Theory of Computing, STOC 2011, San Jose, CA, USA, 6-8 June 2011, pages 479-488. ACM, 2011. Google Scholar
  7. Toru Hasunuma. Completely independent spanning trees in the underlying graph of a line digraph. Discrete Mathematics, 234(1-3):149-157, 2001. Google Scholar
  8. Toru Hasunuma. Completely independent spanning trees in maximal planar graphs. In Ludek Kucera, editor, Graph-Theoretic Concepts in Computer Science, 28th International Workshop, WG 2002, Cesky Krumlov, Czech Republic, June 13-15, 2002, Revised Papers, volume 2573 of Lecture Notes in Computer Science, pages 235-245. Springer, 2002. Google Scholar
  9. Toru Hasunuma and Chie Morisaka. Completely independent spanning trees in torus networks. Networks, 60(1):59-69, 2012. Google Scholar
  10. Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have strongly exponential complexity? J. Comput. Syst. Sci., 63(4):512-530, 2001. Google Scholar
  11. Alon Itai and Michael Rodeh. The multi-tree approach to reliability in distributed networks. Inf. Comput., 79(1):43-59, 1988. Google Scholar
  12. Ferenc Péterfalvi. Two counterexamples on completely independent spanning trees. Discrete Math., 312(4):808-810, 2012. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact