TY - JOUR

T1 - Complexity and approximability of the happy set problem

AU - Asahiro, Yuichi

AU - Eto, Hiroshi

AU - Hanaka, Tesshu

AU - Lin, Guohui

AU - Miyano, Eiji

AU - Terabaru, Ippei

N1 - Funding Information:
This work was partially supported by the Natural Sciences and Engineering Research Council of Canada , the Grants-in-Aid for Scientific Research of Japan ( KAKENHI ) Grant Numbers JP17K00016 and JP17K00024 , JP19K21537 , and JST CREST JPMJR1402 .
Publisher Copyright:
© 2021 Elsevier B.V.

PY - 2021/4/18

Y1 - 2021/4/18

N2 - In this paper we study the approximability of the MAXIMUM HAPPY SET problem (MaxHS) and the computational complexity of MaxHS on graph classes: For an undirected graph G=(V,E) and a subset S⊆V of vertices, a vertex v is happy if v and all its neighbors are in S; otherwise unhappy. Given an undirected graph G=(V,E) and an integer k, the goal of MaxHS is to find a subset S⊆V of k vertices such that the number of happy vertices is maximized. MaxHS is known to be NP-hard. In this paper, we design a (2Δ+1)-approximation algorithm for MaxHS on graphs with maximum degree Δ. Next, we show that the approximation ratio can be improved to Δ if the maximum degree Δ of the input graph is a constant. Then, we show that MaxHS can be solved in polynomial time if the input graph is restricted to block graphs, or interval graphs. We prove nevertheless that MaxHS on bipartite graphs or on cubic graphs remains NP-hard.

AB - In this paper we study the approximability of the MAXIMUM HAPPY SET problem (MaxHS) and the computational complexity of MaxHS on graph classes: For an undirected graph G=(V,E) and a subset S⊆V of vertices, a vertex v is happy if v and all its neighbors are in S; otherwise unhappy. Given an undirected graph G=(V,E) and an integer k, the goal of MaxHS is to find a subset S⊆V of k vertices such that the number of happy vertices is maximized. MaxHS is known to be NP-hard. In this paper, we design a (2Δ+1)-approximation algorithm for MaxHS on graphs with maximum degree Δ. Next, we show that the approximation ratio can be improved to Δ if the maximum degree Δ of the input graph is a constant. Then, we show that MaxHS can be solved in polynomial time if the input graph is restricted to block graphs, or interval graphs. We prove nevertheless that MaxHS on bipartite graphs or on cubic graphs remains NP-hard.

KW - Approximability

KW - Bipartite graphs

KW - Block graphs

KW - Computational complexity

KW - Cubic graphs

KW - Interval graphs

KW - Maximum happy set problem

UR - http://www.scopus.com/inward/record.url?scp=85103285503&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85103285503&partnerID=8YFLogxK

U2 - 10.1016/j.tcs.2021.03.023

DO - 10.1016/j.tcs.2021.03.023

M3 - Article

AN - SCOPUS:85103285503

SN - 0304-3975

VL - 866

SP - 123

EP - 144

JO - Theoretical Computer Science

JF - Theoretical Computer Science

ER -