2026-07-23T21:51:31Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:17379 2024-03-06T10:59:36Z ddc:004 open_access

Parameterized Complexity of Maximum Happy Set and Densest k-Subgraph Mizutani, Yosuke Sullivan, Blair D. parameterized algorithms maximum happy set densest k-subgraph modular-width clique-width neighborhood diversity cluster deletion number twin cover 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Yosuke Mizutani and Blair D. Sullivan 2022 Is Part Of LIPIcs, Volume 249, 17th International Symposium on Parameterized and Exact Computation (IPEC 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.IPEC.2022.23 urn:nbn:de:0030-drops-173795 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2022.23 eng https://creativecommons.org/licenses/by/4.0/legalcode