Complexity and approximability of the happy set problem
Complexity and approximability of the happy set problem
复制标题
DOI：
10.1016/j.tcs.2021.03.023
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Y. Asahiro;Hiroshi Eto;T. Hanaka;Guohui Lin;Eiji Miyano;Ippei Terabaru
中科院分区：
文献类型：
--
作者：
Y. Asahiro;Hiroshi Eto;T. Hanaka;Guohui Lin;Eiji Miyano;Ippei Terabaru
本文研究了最大幸福集问题（MaxHS）在图类上的近似性和MaxHS的计算复杂度：对于无向图G=（V， E）和一个顶点的子集S V，当V及其所有相邻点在S内时，顶点V是幸福的；否则不开心。给定一个无向图G=（V， E）和一个整数k， MaxHS的目标是求k个顶点的子集S⊥V，使快乐顶点数最大化。MaxHS是NP-hard。本文在最大度为Δ的图上设计了一个（2 Δ+ 1）-逼近算法。接下来，我们证明，如果输入图的最大度Δ是一个常数，则近似比率可以提高到Δ。然后，我们证明了如果输入图被限制为块图或区间图，则MaxHS可以在多项式时间内求解。然而，我们证明了在二部图或三次图上的MaxHS仍然是np困难的。
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.