TY - GEN
T1 - Graph Classes 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:
Acknowledgments. We would like to thank the anonymous referees for their helpful comments, especially pointing out small errors in the proof of Theorem 4. 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:
© 2020, Springer Nature Switzerland AG.
PY - 2020
Y1 - 2020
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 and a subset of vertices, a vertex v is happy if v and all its neighbors are in S; otherwise unhappy. Given an undirected graph and an integer k, the goal of MaxHS is to find a subset 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-approximation algorithm for MaxHS on graphs with maximum degree. Next, we show that the approximation ratio can be improved to if the input is a connected graph and its maximum degree is a constant. Then, we show that MaxHS can be solved in polynomial time if the input graph is restricted to proper interval graphs, or block graphs. We prove nevertheless that MaxHS remains NP-hard even for bipartite graphs or for cubic graphs.
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 and a subset of vertices, a vertex v is happy if v and all its neighbors are in S; otherwise unhappy. Given an undirected graph and an integer k, the goal of MaxHS is to find a subset 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-approximation algorithm for MaxHS on graphs with maximum degree. Next, we show that the approximation ratio can be improved to if the input is a connected graph and its maximum degree is a constant. Then, we show that MaxHS can be solved in polynomial time if the input graph is restricted to proper interval graphs, or block graphs. We prove nevertheless that MaxHS remains NP-hard even for bipartite graphs or for cubic graphs.
UR - http://www.scopus.com/inward/record.url?scp=85091112536&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85091112536&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-58150-3_27
DO - 10.1007/978-3-030-58150-3_27
M3 - Conference contribution
AN - SCOPUS:85091112536
SN - 9783030581497
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 335
EP - 346
BT - Computing and Combinatorics - 26th International Conference, COCOON 2020, Proceedings
A2 - Kim, Donghyun
A2 - Uma, R.N.
A2 - Cai, Zhipeng
A2 - Lee, Dong Hoon
PB - Springer Science and Business Media Deutschland GmbH
T2 - 26th International Conference on Computing and Combinatorics, COCOON 2020
Y2 - 29 August 2020 through 31 August 2020
ER -