Document Open Access Logo

Parameterized Complexity of Maximum Happy Set and Densest k-Subgraph

Authors Yosuke Mizutani , Blair D. Sullivan

PDF
Thumbnail PDF

File

LIPIcs.IPEC.2022.23.pdf
  • Filesize: 0.87 MB
  • 18 pages

Document Identifiers

Author Details

Yosuke Mizutani
  • School of Computing, University of Utah, Salt Lake City, UT, USA
Blair D. Sullivan
  • School of Computing, University of Utah, Salt Lake City, UT, USA

Funding

This work was supported in part by the Gordon & Betty Moore Foundation under award GBMF4560 to Blair D. Sullivan.

Acknowledgements

We thank Arnab Banerjee, Oliver Flatt and Thanh Son Nguyen for their contributions to a course project that led to this research.

Cite As Get BibTex

Yosuke Mizutani and Blair D. Sullivan. Parameterized Complexity of Maximum Happy Set and Densest k-Subgraph. In 17th International Symposium on Parameterized and Exact Computation (IPEC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 249, pp. 23:1-23:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.IPEC.2022.23

Abstract

We present fixed-parameter tractable (FPT) algorithms for two problems, Maximum Happy Set (MaxHS) and Densest k-Subgraph (DkS) - also known as Maximum Edge Happy Set. Given a graph G and an integer k, MaxHS asks for a set S of k vertices such that the number of happy vertices with respect to S is maximized, where a vertex v is happy if v and all its neighbors are in S. We show that MaxHS can be solved in time 𝒪(2^mw ⋅ mw ⋅ k² ⋅ |V(G)|) and 𝒪(8^cw ⋅ k² ⋅ |V(G)|), where mw and cw denote the modular-width and the clique-width of G, respectively. This answers the open questions on fixed-parameter tractability posed in [Asahiro et al., 2021].
The DkS problem asks for a subgraph with k vertices maximizing the number of edges. If we define happy edges as the edges whose endpoints are in S, then DkS can be seen as an edge-variant of MaxHS. In this paper we show that DkS can be solved in time f(nd)⋅|V(G)|^𝒪(1) and 𝒪(2^{cd}⋅ k² ⋅ |V(G)|), where nd and cd denote the neighborhood diversity and the cluster deletion number of G, respectively, and f is some computable function. This result implies that DkS is also fixed-parameter tractable by twin cover number.

Subject Classification

ACM Subject Classification
  • Theory of computation → Graph algorithms analysis
  • Theory of computation → Fixed parameter tractability
Keywords
  • parameterized algorithms
  • maximum happy set
  • densest k-subgraph
  • modular-width
  • clique-width
  • neighborhood diversity
  • cluster deletion number
  • twin cover

Metrics

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

References

  1. Yuichi Asahiro, Hiroshi Eto, Tesshu Hanaka, Guohui Lin, Eiji Miyano, and Ippei Terabaru. Parameterized algorithms for the happy set problem. Discrete Applied Mathematics, 304:32-44, 2021. Google Scholar
  2. Hans L. Bodlaender, Bart M. P. Jansen, and Stefan Kratsch. Kernelization lower bounds by cross-composition. SIAM Journal on Discrete Mathematics, 28(1):277-305, 2014. Google Scholar
  3. Nicolas Bourgeois, Aristotelis Giannakos, Giorgio Lucarelli, Ioannis Milis, and Vangelis Th. Paschos. Exact and approximation algorithms for densest k-subgraph. In 7th International Workshop on Algorithms and Computation (WALCOM 2013), volume 7748, pages 114-125, 2013. Google Scholar
  4. Hajo Broersma, Petr A. Golovach, and Viresh Patel. Tight complexity bounds for fpt subgraph problems parameterized by the clique-width. Theoretical Computer Science, 485:69-84, 2013. Google Scholar
  5. Maurizio Bruglieri, Matthias Ehrgott, Horst W. Hamacher, and Francesco Maffioli. An annotated bibliography of combinatorial optimization problems with fixed cardinality constraints. Discrete Applied Mathematics, 154(9):1344-1357, 2006. Google Scholar
  6. Leizhen Cai. Parameterized Complexity of Cardinality Constrained Optimization Problems. The Computer Journal, 51(1):102-121, 2007. Google Scholar
  7. D. G. Corneil and Y. Perl. Clustering and domination in perfect graphs. Discrete Applied Mathematics, 9(1):27-39, 1984. Google Scholar
  8. Bruno Courcelle and Stephan Olariu. Upper bounds to the clique width of graphs. Discrete Applied Mathematics, 101(1):77-114, 2000. Google Scholar
  9. Marek Cygan, Fedor V Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh. Parameterized algorithms, volume 5. Springer, 2015. Google Scholar
  10. Reinhard Diestel. Graph theory. fifth. vol. 173. Graduate Texts in Mathematics. Springer, Berlin, 2018. Google Scholar
  11. David Easley, Jon Kleinberg, et al. Networks, crowds, and markets: Reasoning about a highly connected world. Significance, 9(1):43-44, 2012. Google Scholar
  12. Uriel Feige and Michael Seltser. On the Densest K-Subgraph Problem. Algorithmica, 29:2001, 1997. Google Scholar
  13. Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov, and Saket Saurabh. Clique-width: On the Price of Generality. In Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 825-834. Society for Industrial and Applied Mathematics, 2009. Google Scholar
  14. Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov, and Saket Saurabh. Algorithmic lower bounds for problems parameterized by clique-width. In Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete algorithms, SODA '10, pages 493-502, USA, 2010. Society for Industrial and Applied Mathematics. Google Scholar
  15. Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov, and Saket Saurabh. Intractability of Clique-Width Parameterizations. SIAM Journal on Computing, 39(5):1941-1956, 2010. Google Scholar
  16. Santo Fortunato. Community detection in graphs. Physics Reports, 486(3):75-174, 2010. Google Scholar
  17. Jakub Gajarský, Michael Lampis, and Sebastian Ordyniak. Parameterized algorithms for modular-width. In Gregory Gutin and Stefan Szeider, editors, Parameterized and Exact Computation, pages 163-176. Springer International Publishing, 2013. Google Scholar
  18. G. Gallo, P. L. Hammer, and B. Simeone. Quadratic knapsack problems. In M. W. Padberg, editor, Combinatorial Optimization, Mathematical Programming Studies, pages 132-149. Springer, Berlin, Heidelberg, 1980. Google Scholar
  19. Robert Ganian. Improving Vertex Cover as a Graph Parameter. Discrete Mathematics & Theoretical Computer Science, Vol. 17 no.2, 2015. Google Scholar
  20. Michael R. Garey and David S. Johnson. Computers and Intractability; A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., USA, 1979. Google Scholar
  21. Tesshu Hanaka. Computing Densest k-Subgraph with Structural Parameters, 2022. URL: http://arxiv.org/abs/2207.09803.
  22. G. Kortsarz and D. Peleg. On choosing a dense subgraph. Proceedings of 1993 IEEE 34th Annual Foundations of Computer Science, 1993. Google Scholar
  23. Michael Lampis. Algorithmic Meta-theorems for Restrictions of Treewidth. Algorithmica, 64(1):19-37, 2012. Google Scholar
  24. Angsheng Li and Pan Peng. Community Structures in Classical Network Models. Internet Mathematics, 7(2), 2011. Google Scholar
  25. Daniel Lokshtanov. Parameterized integer quadratic programming: Variables and coefficients, 2015. URL: http://arxiv.org/abs/1511.00310.
  26. Miller McPherson, Lynn Smith-Lovin, and James M Cook. Birds of a feather: Homophily in social networks. Annual review of sociology, 27(1):415-444, 2001. Google Scholar
  27. Hannes Moser. Exact algorithms for generalizations of vertex cover. Institut für Informatik, Friedrich-Schiller-Universität Jena, 2005. Google Scholar
  28. Neil Robertson and P. D. Seymour. Graph minors. II. Algorithmic aspects of tree-width. Journal of Algorithms. Academic Press Inc., 7(3):309-322, 1986. Google Scholar
  29. Marc Tedder, Derek Corneil, Michel Habib, and Christophe Paul. Simpler linear-time modular decomposition via recursive factorizing permutations. In Automata, Languages and Programming, pages 634-645, Berlin, Heidelberg, 2008. Springer Berlin Heidelberg. Google Scholar
  30. Peng Zhang and Angsheng Li. Algorithmic aspects of homophyly of networks. Theoretical Computer Science, 593:117-131, 2015. 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