Parameterized algorithms for the Happy Set problem
Parameterized algorithms for the Happy Set problem
复制标题
Happy Set 问题的参数化算法
DOI：
10.1016/j.dam.2021.07.005
复制
发表时间：
2021
影响因子：
1.1
通讯作者：
Terabaru Ippei
中科院分区：
文献类型：
--
作者：
Asahiro Yuichi;Eto Hiroshi;Hanaka Tesshu;Lin Guohui;Miyano Eiji;Terabaru Ippei
本文研究了极大幸福集问题的参数复杂性：对于一个无向图G=(V，E)和一个点的子集S⊆V，如果v和它的所有邻域都在S中，则一个顶点v是高兴的，否则是不高兴的。给定一个无向图G=(V，E)和一个整数k，MaxHS的目标是找到k个顶点的子集S⊆V，使得快乐顶点的数目最大化。本文首先证明了当输入图是分裂图时，MaxHS关于k是W[1]-困难的。然后，我们证明了当以树宽、团宽加k、邻域多样性或簇删除数为参数时，MaxHS的固定参数可处理性。
In this paper we study the parameterized complexity for the Maximum Happy Set problem (MaxHS): 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. In this paper we first show that MaxHS is W [1]-hard with respect to k even if the input graph is a split graph. Then, we prove the fixed-parameter tractability of MaxHS when parameterized by tree-width, by clique-width plus k, by neighborhood diversity, or by cluster deletion number.