Document Open Access Logo

Parameterized Aspects of Strong Subgraph Closure

Authors Petr A. Golovach, Pinar Heggernes, Athanasios L. Konstantinidis, Paloma T. Lima, Charis Papadopoulos

PDF
Thumbnail PDF

File

LIPIcs.SWAT.2018.23.pdf
  • Filesize: 463 kB
  • 13 pages

Document Identifiers

Author Details

Petr A. Golovach
  • Department of Informatics, University of Bergen, Norway.
Pinar Heggernes
  • Department of Informatics, University of Bergen, Norway.
Athanasios L. Konstantinidis
  • Department of Mathematics, University of Ioannina, Greece.
Paloma T. Lima
  • Department of Informatics, University of Bergen, Norway.
Charis Papadopoulos
  • Department of Mathematics, University of Ioannina, Greece.

Funding

This work is supported by Research Council of Norway via project CLASSIS.

Cite As Get BibTex

Petr A. Golovach, Pinar Heggernes, Athanasios L. Konstantinidis, Paloma T. Lima, and Charis Papadopoulos. Parameterized Aspects of Strong Subgraph Closure. In 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 101, pp. 23:1-23:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.SWAT.2018.23

Abstract

Motivated by the role of triadic closures in social networks, and the importance of finding a maximum subgraph avoiding a fixed pattern, we introduce and initiate the parameterized study of the Strong F-closure problem, where F is a fixed graph. This is a generalization of Strong Triadic Closure, whereas it is a relaxation of F-free Edge Deletion. In Strong F-closure, we want to select a maximum number of edges of the input graph G, and mark them as strong edges, in the following way: whenever a subset of the strong edges forms a subgraph isomorphic to F, then the corresponding induced subgraph of G is not isomorphic to F. Hence the subgraph of G defined by the strong edges is not necessarily F-free, but whenever it contains a copy of F, there are additional edges in G to destroy that strong copy of F in G.
We study Strong F-closure from a parameterized perspective with various natural parameterizations. Our main focus is on the number k of strong edges as the parameter. We show that the problem is FPT with this parameterization for every fixed graph F, whereas it does not admit a polynomial kernel even when F =P_3. In fact, this latter case is equivalent to the Strong Triadic Closure problem, which motivates us to study this problem on input graphs belonging to well known graph classes. We show that Strong Triadic Closure does not admit a polynomial kernel even when the input graph is a split graph, whereas it admits a polynomial kernel when the input graph is planar, and even d-degenerate. Furthermore, on graphs of maximum degree at most 4, we show that Strong Triadic Closure is FPT with the above guarantee parameterization k - mu(G), where mu(G) is the maximum matching size of G. We conclude with some results on the parameterization of Strong F-closure by the number of edges of G that are not selected as strong.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph algorithms
Keywords
  • Strong triadic closure
  • Parameterized complexity
  • Forbidden subgraphs

Metrics

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

Related Versions

References

  1. N. Alon, G. Gutin, E. J. Kim, S. Szeider, and A. Yeo. Solving max-r-sat above a tight lower bound. Algorithmica, 61(3):638-655, 2011. Google Scholar
  2. L. Backstrom and J. Kleinberg. Romantic partnerships and the dispersion of social ties: a network analysis of relationship status on facebook. In CSCW 2014, pages 831-841, 2014. Google Scholar
  3. H. L. Bodlaender, R. G. Downey, M. R. Fellows, and D. Hermelin. On problems without polynomial kernels. J. Comput. Syst. Sci., 75(8):423-434, 2009. Google Scholar
  4. L. Cai. Fixed-parameter tractability of graph modification problems for hereditary properties. Information Processing Letters, 58:171-176, 1996. Google Scholar
  5. L. Cai and Y. Cai. Incompressibility of H-free edge modification problems. Algorithmica, 71:731-757, 2015. Google Scholar
  6. L. Cai, S.M. Chan, and S.O. Chan. Random separation: a new method for solving fixed-cardinality optimization problems. In IWPEC 2006, pages 239-250, 2006. Google Scholar
  7. R. Chitnis, M. Cygan, M. Hajiaghayi, M. Pilipczuk, and M. Pilipczuk. Designing FPT algorithms for cut problems using randomized contractions. SIAM J. Comput., 45(4):1171-1229, 2016. Google Scholar
  8. M. Cygan, F. V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh. Parameterized Algorithms. Springer, 2015. Google Scholar
  9. R. Diestel. Graph Theory, 4th Edition, volume 173 of Graduate Texts in Mathematics. Springer, 2012. Google Scholar
  10. M. Dom, D. Lokshtanov, and S. Saurabh. Kernelization lower bounds through colors and ids. ACM Trans. Algorithms, 11(2):13:1-13:20, 2014. Google Scholar
  11. R. G. Downey and M. R. Fellows. Parameterized Complexity. Monographs in Computer Science, Springer, 1997. Google Scholar
  12. D. Easley and J. Kleinberg. Networks, Crowds, and Markets: Reasoning About a Highly Connected World. Cambridge University Press, 2010. Google Scholar
  13. K. Eickmeyer, A. C. Giannopoulou, S. Kreutzer, O. Kwon, M. Pilipczuk, R. Rabinovich, and S. Siebertz. Neighborhood complexity and kernelization for nowhere dense classes of graphs. In ICALP 2017, pages 63:1-63:14, 2017. Google Scholar
  14. P.A. Golovach, P. Heggernes, A.L. Konstantinidis, P.T. Lima, and C. Papadopoulos. Parameterized aspects of strong subgraph closure. Available on arxiv.org/abs/1802.10386, 2018. Google Scholar
  15. S. Khot and V. Raman. Parameterized complexity of finding subgraphs with hereditary properties. Theor. Comput. Sci., 289(2):997-1008, 2002. Google Scholar
  16. J. M. Kleinberg and É. Tardos. Algorithm design. Addison-Wesley, 2006. Google Scholar
  17. A. L. Konstantinidis, S. D. Nikolopoulos, and C. Papadopoulos. Strong triadic closure in cographs and graphs of low maximum degree. In COCOON 2017, pages 346-358, 2017. Google Scholar
  18. A. L. Konstantinidis and C. Papadopoulos. Maximizing the strong triadic closure in split graphs and proper interval graphs. In ISAAC 2017, pages 53:1-53:12, 2017. Google Scholar
  19. S. Kratsch and M. Wahlstrom. Two edge modification problems without polynomial kernels. Discrete Optimization, 10:193-199, 2013. Google Scholar
  20. S. Micali and V. V. Vazirani. An O(sqrt(|v|) |e|) algorithm for finding maximum matching in general graphs. In FOCS 1980, pages 17-27, 1980. Google Scholar
  21. J. Nesetril and P. Ossona de Mendez. Sparsity - Graphs, Structures, and Algorithms, volume 28 of Algorithms and combinatorics. Springer, 2012. Google Scholar
  22. S. Sintos and P. Tsaparas. Using strong triadic closure to characterize ties in social networks. In KDD 2014, pages 1466-1475, 2014. Google Scholar
  23. M. Yannakakis. Edge-deletion problems. SIAM Journal on Computing, 10(2):297-309, 1981. 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