Document Open Access Logo

k-Distinct Branchings Admits a Polynomial Kernel

Authors Jørgen Bang-Jensen, Kristine Vitting Klinkby, Saket Saurabh

PDF
Thumbnail PDF

File

LIPIcs.ESA.2021.11.pdf
  • Filesize: 0.91 MB
  • 15 pages

Document Identifiers

Author Details

Jørgen Bang-Jensen
  • University of Southern Denmark, Odense, Denmark
Kristine Vitting Klinkby
  • University of Bergen, Bergen, Norway
  • University of Southern Denmark, Odense, Denmark
Saket Saurabh
  • University of Bergen, Bergen, Norway
  • The Institute of Mathematical Sciences, HBNI, Chennai, India

Cite AsGet BibTex

Jørgen Bang-Jensen, Kristine Vitting Klinkby, and Saket Saurabh. k-Distinct Branchings Admits a Polynomial Kernel. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 11:1-11:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.ESA.2021.11

Abstract

Unlike the problem of deciding whether a digraph D = (V,A) has 𝓁 in-branchings (or 𝓁 out-branchings) is polynomial time solvable, the problem of deciding whether a digraph D = (V,A) has an in-branching B^- and an out-branching B^+ which are arc-disjoint is NP-complete. Motivated by this, a natural optimization question that has been studied in the realm of Parameterized Complexity is called Rooted k-Distinct Branchings. In this problem, a digraph D = (V,A) with two prescribed vertices s,t are given as input and the question is whether D has an in-branching rooted at t and an out-branching rooted at s such that they differ on at least k arcs. Bang-Jensen et al. [Algorithmica, 2016 ] showed that the problem is fixed parameter tractable (FPT) on strongly connected digraphs. Gutin et al. [ICALP, 2017; JCSS, 2018 ] completely resolved this problem by designing an algorithm with running time 2^{𝒪(k² log² k)}n^{𝒪(1)}. Here, n denotes the number of vertices of the input digraph. In this paper, answering an open question of Gutin et al., we design a polynomial kernel for Rooted k-Distinct Branchings. In particular, we obtain the following: Given an instance (D,k,s,t) of Rooted k-Distinct Branchings, in polynomial time we obtain an equivalent instance (D',k',s,t) of Rooted k-Distinct Branchings such that |V(D')| ≤ 𝒪(k²) and the treewidth of the underlying undirected graph is at most 𝒪(k). This result immediately yields an FPT algorithm with running time 2^{𝒪(klog k)}+ n^{𝒪(1)}; improving upon the previous running time of Gutin et al. For our algorithms, we prove a structural result about paths avoiding many arcs in a given in-branching or out-branching. This result might turn out to be useful for getting other results for problems concerning in-and out-branchings.

Subject Classification

ACM Subject Classification
  • Theory of computation → Fixed parameter tractability
Keywords
  • Digraphs
  • Polynomial Kernel
  • In-branching
  • Out-Branching

Metrics

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

References

  1. Noga Alon, Fedor V. Fomin, Gregory Gutin, Michael Krivelevich, and Saket Saurabh. Spanning directed trees with many leaves. SIAM J. Discrete Math., 23(1):466-476, 2009. URL: https://doi.org/10.1137/070710494.
  2. J. Bang-Jensen. Edge-disjoint in- and out-branchings in tournaments and related path problems. J. Combin. Theory Ser. B, 51(1):1-23, 1991. Google Scholar
  3. J. Bang-Jensen and J. Huang. Decomposing locally semicomplete digraphs into strong spanning subdigraphs. J. Combin. Theory Ser. B, 102:701-714, 2010. Google Scholar
  4. J. Bang-Jensen, S. Saurabh, and S. Simonsen. Parameterized algorithms for non-separating trees and branchings in digraphs. Algorithmica, 76(1):279-296, 2016. Google Scholar
  5. J. Bang-Jensen and S. Simonsen. Arc-disjoint paths and trees in 2-regular digraphs. Discrete Applied Mathematics, 161(16-17):2724-2730, 2013. Google Scholar
  6. J. Bang-Jensen, S. Thomassé, and A. Yeo. Small degree out-branchings. J. Graph Theory, 42(4):297-307, 2003. Google Scholar
  7. J. Bang-Jensen and A. Yeo. The minimum spanning strong subdigraph problem is fixed parameter tractable. Discrete Appl. Math., 156:2924-2929, 2008. Google Scholar
  8. J. Bang-Jensen and A. Yeo. Arc-disjoint spanning sub(di)graphs in digraphs. Theor. Comput. Sci., 438:48-54, 2012. Google Scholar
  9. K. Bérczi, S. Fujishige, and N. Kamiyama. A linear-time algorithm to find a pair of arc-disjoint spanning in-arborescence and out-arborescence in a directed acyclic graph. Inform. Process. Lett., 109(23-24):1227-1231, 2009. Google Scholar
  10. Daniel Binkele-Raible, Henning Fernau, Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, and Yngve Villanger. Kernel(s) for problems with no kernel: On out-trees with many leaves. ACM Transactions on Algorithms, 8(4):38, 2012. URL: https://doi.org/10.1145/2344422.2344428.
  11. Nathann Cohen, Fedor V. Fomin, Gregory Gutin, Eun Jung Kim, Saket Saurabh, and Anders Yeo. Algorithm for finding k-vertex out-trees and its application to k-internal out-branching problem. J. Comput. Syst. Sci., 76(7):650-662, 2010. URL: https://doi.org/10.1016/j.jcss.2010.01.001.
  12. M. Cygan, F.V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh. Parameterized Algorithms. Springer, 2015. Google Scholar
  13. J. Daligault, G. Gutin, E.J. Kim, and A. Yeo. FPT algorithms and kernels for the directed k-leaf problem. J. Comput. Syst. Sci., 76:144-152, 2010. Google Scholar
  14. Frederic Dorn, Fedor V. Fomin, Daniel Lokshtanov, Venkatesh Raman, and Saket Saurabh. Beyond bidimensionality: Parameterized subexponential algorithms on directed graphs. In STACS, volume 5, pages 251-262, 2010. URL: https://doi.org/10.4230/LIPIcs.STACS.2010.2459.
  15. Rodney G. Downey and Michael R. Fellows. Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, 2013. Google Scholar
  16. J. Edmonds. Edge-disjoint branchings. In Combinatorial Algorithms, pages 91-96. Academic Press, 1973. Google Scholar
  17. J. Flum and M. Grohe. Parameterized Complexity Theory. Springer-Verlag, 2006. Google Scholar
  18. Fedor V. Fomin, Serge Gaspers, Saket Saurabh, and Stéphan Thomassé. A linear vertex kernel for maximum internal spanning tree. J. Comput. Syst. Sci., 79(1):1-6, 2013. URL: https://doi.org/10.1016/j.jcss.2012.03.004.
  19. Fedor V. Fomin, Fabrizio Grandoni, Daniel Lokshtanov, and Saket Saurabh. Sharp separation and applications to exact and parameterized algorithms. Algorithmica, 63(3):692-706, 2012. URL: https://doi.org/10.1007/s00453-011-9555-9.
  20. Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan, and Saket Saurabh. Efficient computation of representative families with applications in parameterized and exact algorithms. J. ACM, 63(4):29:1-29:60, 2016. Google Scholar
  21. Fedor V Fomin, Daniel Lokshtanov, Saket Saurabh, and Meirav Zehavi. Kernelization: theory of parameterized preprocessing. Cambridge University Press, 2019. Google Scholar
  22. Gregory Z. Gutin, Felix Reidl, and Magnus Wahlström. k-distinct in- and out-branchings in digraphs. J. Comput. Syst. Sci., 95:86-97, 2018. Google Scholar
  23. J. Kneis, A. Langer, and P. Rossmanith. A new algorithm for finding trees with many leaves. Algorithmica, 61(4):882-897, 2011. Google Scholar
  24. R. Niedermeier. Invitation to Fixed Parameter Algorithms. Oxford University Press, Oxford, 2006. 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 Imprint Privacy Contact