Document Open Access Logo

Maximum Edge-Colorable Subgraph and Strong Triadic Closure Parameterized by Distance to Low-Degree Graphs

Authors Niels Grüttemeier , Christian Komusiewicz , Nils Morawietz

PDF

File

Thumbnail PDF
PDF
LIPIcs.SWAT.2020.26.pdf
  • Filesize: 0.57 MB
  • 17 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Theory of computation → Parameterized complexity and exact algorithms
  • Theory of computation → Fixed parameter tractability
Keywords
  • Graph coloring
  • social networks
  • parameterized complexity
  • kernelization

Metrics

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

Abstract

Given an undirected graph G and integers c and k, the Maximum Edge-Colorable Subgraph problem asks whether we can delete at most k edges in G to obtain a graph that has a proper edge coloring with at most c colors. We show that Maximum Edge-Colorable Subgraph admits, for every fixed c, a linear-size problem kernel when parameterized by the edge deletion distance of G to a graph with maximum degree c-1. This parameterization measures the distance to instances that, due to Vizing’s famous theorem, are trivial yes-instances. For c≤ 4, we also provide a linear-size kernel for the same parameterization for Multi Strong Triadic Closure, a related edge coloring problem with applications in social network analysis. We provide further results for Maximum Edge-Colorable Subgraph parameterized by the vertex deletion distance to graphs where every component has order at most c and for the list-colored versions of both problems.

Cite As Get BibTex

Niels Grüttemeier, Christian Komusiewicz, and Nils Morawietz. Maximum Edge-Colorable Subgraph and Strong Triadic Closure Parameterized by Distance to Low-Degree Graphs. In 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 162, pp. 26:1-26:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.SWAT.2020.26

Author Details

Niels Grüttemeier
  • Philipps-Universität Marburg, Fachbereich Mathematik und Informatik, Germany
Christian Komusiewicz
  • Philipps-Universität Marburg, Fachbereich Mathematik und Informatik, Germany
Nils Morawietz
  • Philipps-Universität Marburg, Fachbereich Mathematik und Informatik, Germany

References

  1. Laurent Bulteau, Niels Grüttemeier, Christian Komusiewicz, and Manuel Sorge. Your rugby mates don't need to know your colleagues: Triadic closure with edge colors. In Proc. 11th CIAC, volume 11485 of LNCS, pages 99-111. Springer, 2019. Google Scholar
  2. Benny Chor, Mike Fellows, and David W. Juedes. Linear kernels in linear time, or how to save k colors in O(n²) steps. In Proc. 30th WG, volume 3353 of LNCS, pages 257-269. Springer, 2004. Google Scholar
  3. Richard Cole and John E. Hopcroft. On edge coloring bipartite graphs. SIAM J. Comput., 11(3):540-546, 1982. Google Scholar
  4. Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. Google Scholar
  5. Rodney G. Downey and Michael R. Fellows. Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, 2013. Google Scholar
  6. Uriel Feige, Eran Ofek, and Udi Wieder. Approximating maximum edge coloring in multigraphs. In Proc. 5th APPROX, volume 2462 of LNCS, pages 108-121. Springer, 2002. Google Scholar
  7. Jörg Flum and Martin Grohe. Parameterized Complexity Theory. Texts in Theoretical Computer Science. An EATCS Series. Springer, 2006. Google Scholar
  8. Harold N. Gabow. An efficient reduction technique for degree-constrained subgraph and bidirected network flow problems. In Proc. 15th STOC, pages 448-456. ACM, 1983. Google Scholar
  9. Petr A. Golovach, Pinar Heggernes, Athanasios L. Konstantinidis, Paloma T. Lima, and Charis Papadopoulos. Parameterized aspects of strong subgraph closure. In Proc. 16th SWAT, volume 101 of LIPIcs, pages 23:1-23:13. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2018. Google Scholar
  10. Niels Grüttemeier and Christian Komusiewicz. On the relation of strong triadic closure and cluster deletion. Algorithmica, 82(4):853-880, 2020. Google Scholar
  11. Jiong Guo, Falk Hüffner, and Rolf Niedermeier. A structural view on parameterizing problems: Distance from triviality. In Proc. 1st IWPEC, volume 3162 of LNCS, pages 162-173. Springer, 2004. Google Scholar
  12. S. Louis Hakimi and Oded Kariv. A generalization of edge-coloring in graphs. J. Graph Theor., 10(2):139-154, 1986. Google Scholar
  13. Ian Holyer. The NP-Completeness of Edge-Coloring. SIAM J. Comput., 10(4):718-720, 1981. Google Scholar
  14. Tommy R Jensen and Bjarne Toft. Graph coloring problems, volume 39. John Wiley & Sons, 2011. Google Scholar
  15. Marcin Jakub Kaminski and Lukasz Kowalik. Beyond the Vizing’s bound for at most seven colors. SIAM J. Discrete Math., 28(3):1334-1362, 2014. Google Scholar
  16. Athanasios L. Konstantinidis, Stavros D. Nikolopoulos, and Charis Papadopoulos. Strong triadic closure in cographs and graphs of low maximum degree. Theor. Comput. Sci., 740:76-84, 2018. Google Scholar
  17. Athanasios L. Konstantinidis and Charis Papadopoulos. Maximizing the Strong Triadic Closure in Split Graphs and Proper Interval Graphs. In Proc. 28th ISAAC, volume 92 of LIPIcs, pages 53:1-53:12. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2017. Google Scholar
  18. Adrian Kosowski. Approximating the maximum 2- and 3-edge-colorable subgraph problems. Discrete Appl. Math., 157(17):3593-3600, 2009. Google Scholar
  19. Lukasz Kowalik. Improved edge-coloring with three colors. Theor. Comput. Sci., 410(38-40):3733-3742, 2009. Google Scholar
  20. Mithilesh Kumar and Daniel Lokshtanov. A 2𝓁 k kernel for 𝓁-component order connectivity. In Proc. 11th IPEC, pages 20:1-20:14, 2016. Google Scholar
  21. Daniel Leven and Zvi Galil. NP completeness of finding the chromatic index of regular graphs. J. Algorithms, 4(1):35-44, 1983. Google Scholar
  22. Rolf Niedermeier. Invitation to Fixed-Parameter Algorithms. Oxford University Press, 2006. Google Scholar
  23. Romeo Rizzi. Approximating the maximum 3-edge-colorable subgraph problem. Discrete Math., 309(12):4166-4170, 2009. Google Scholar
  24. Elena Prieto Rodríguez. Systematic kernelization in FPT algorithm design. PhD thesis, The University of Newcastle, 2005. Google Scholar
  25. Stavros Sintos and Panayiotis Tsaparas. Using strong triadic closure to characterize ties in social networks. In Proc. 20th KDD, pages 1466-1475. ACM, 2014. Google Scholar
  26. Michael Stiebitz, Diego Scheide, Bjarne Toft, and Lene M Favrholdt. Graph edge coloring: Vizing’s theorem and Goldberg’s conjecture, volume 75. John Wiley & Sons, 2012. Google Scholar
  27. Vadim G Vizing. On an estimate of the chromatic class of a p-graph. Discret Analiz, 3:25-30, 1964. 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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact