Happy set problem on subclasses of co-comparability graphs
Happy set problem on subclasses of co-comparability graphs
复制标题
协同可比图子类的快乐集问题
DOI：
10.1007/978-3-030-96731-4_13
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Yuma Tamura
中科院分区：
文献类型：
--
作者：
Hiroshi Eto;Takehiro Ito;Eiji Miyano;Akira Suzuki;Yuma Tamura
本文研究了可比较图子类上的最大快乐集问题的复杂性。对于一个图G及其顶点子集S，如果G中所有v的邻居都包含在S中，则该顶点是快乐的。给定一个图G和一个非负整数，最大快乐集是找到G的顶点子集使得S中快乐顶点的数目最大化的问题。在本文中，我们首先证明了最大快乐集是NP-难的，即使是对共同二部图。然后，我们给出了一个算法的n-顶点区间图的运行时间是，这提高了最好的已知运行时间为区间图。我们还设计了n-顶点置换图和d-梯形图的算法，分别运行于和时间。这些算法的结果提供了一个很好的对比的事实thatMaximum快乐Setremains NP-难的弦图，可比性图，和cocomparativity图。
In this paper, we investigate the complexity of theMaximum Happy Setproblem on subclasses of co-comparability graphs. For a graphGand its vertex subsetS, a vertexis happy if allv’s neighbors inGare contained inS. Given a graphGand a non-negative integerk,Maximum Happy Setis the problem of finding a vertex subsetSofGsuch thatand the number of happy vertices inSis maximized. In this paper, we first show thatMaximum Happy Setis NP-hard even for co-bipartite graphs. We then give an algorithm forn-vertex interval graphs whose running time is; this improves the best known running timefor interval graphs. We also design algorithms forn-vertex permutation graphs andd-trapezoid graphs which run inandtime, respectively. These algorithmic results provide a nice contrast to the fact thatMaximum Happy Setremains NP-hard for chordal graphs, comparability graphs, and co-comparability graphs.