Happy set problem on subclasses of co-comparability graphs. (English) Zbl 07767692
Summary: In this paper, we investigate the complexity of the Maximum Happy Set problem on subclasses of co-comparability graphs. For a graph \(G\) and its vertex subset \(S\), a vertex \(v \in S\) is happy if all \(v\)’s neighbors in \(G\) are contained in \(S\). Given a graph \(G\) and a non-negative integer \(k\),Maximum Happy Set is the problem of finding a vertex subset \(S\) of \(G\) such that \(|S|= k\) and the number of happy vertices in \(S\) is maximized. In this paper, we first show that Maximum Happy Set is NP-hard even for co-bipartite graphs. We then give an algorithm for \(n\)-vertex interval graphs whose running time is \(O(n^2 + k^3n)\); this improves the best known running time \(O(kn^8)\) for interval graphs. We also design algorithms for \(n\)-vertex permutation graphs and \(d\)-trapezoid graphs which run in \(O(n^2 + k^3n)\) and \(O(n^2 + d^2(k+1)^{3d}n)\) time, respectively. These algorithmic results provide a nice contrast to the fact that Maximum Happy Set remains NP-hard for chordal graphs, comparability graphs, and co-comparability graphs.
Keywords:
graph algorithm; co-comparability graphs; interval graphs; permutation graphs; \(d\)-trapezoid graphs; happy set problemReferences:
| [1] | Eto, H., Ito, T., Miyano, E., Suzuki, A., Tamura, Y.: Happy set problem on subclasses of co-comparability graphs. In: Mutzel, P., Rahman, M.S., Slamin (eds.) Proceedings of the 16th International Conference and Workshop on Algorithms and Computation (WALCOM 2022). Lecture Notes in Computer Science, vol. 13174, pp. 149-160. Springer, Cham (2022). doi:10.1007/978-3-030-96731-4_13 · Zbl 07556568 |
| [2] | Easley, D.; Kleinberg, J., Networks, Crowds, and Markets: Reasoning About a Highly Connected World (2010), Cambridge: Cambridge University Press, Cambridge · Zbl 1205.91007 · doi:10.1017/CBO9780511761942 |
| [3] | Zhang, P.; Li, A., Algorithmic aspects of homophyly of networks, Theor. Comput. Sci., 593, 117-131 (2015) · Zbl 1330.68127 · doi:10.1016/j.tcs.2015.06.003 |
| [4] | Asahiro, Y.; Eto, H.; Hanaka, T.; Lin, G.; Miyano, E.; Terabaru, I., Parameterized algorithms for the happy set problem, Discrete Appl. Math., 304, 32-44 (2021) · Zbl 1473.05218 · doi:10.1016/j.dam.2021.07.005 |
| [5] | Asahiro, Y.; Eto, H.; Hanaka, T.; Lin, G.; Miyano, E.; Terabaru, I., Complexity and approximability of the happy set problem, Theor. Comput. Sci., 866, 123-144 (2021) · Zbl 1477.68195 · doi:10.1016/j.tcs.2021.03.023 |
| [6] | Kratsch, D.; Stewart, L., Domination on cocomparability graphs, SIAM J. Discrete Math., 6, 3, 400-417 (1993) · Zbl 0780.05032 · doi:10.1137/0406032 |
| [7] | Deogun, JS; Steiner, G., Polynomial algorithms for Hamiltonian cycle in cocomparability graphs, SIAM J. Comput., 23, 3, 520-552 (1994) · Zbl 0811.05043 · doi:10.1137/S0097539791200375 |
| [8] | Coorg, SR; Rangan, CP, Feedback vertex set on cocomparability graphs, Networks, 26, 2, 101-111 (1995) · Zbl 0856.90113 · doi:10.1002/net.3230260205 |
| [9] | Feige, U.; Kortsarz, G.; Peleg, D., The dense \(k\)-subgraph problem, Algorithmica, 29, 3, 410-421 (2001) · Zbl 0969.68117 · doi:10.1007/s004530010050 |
| [10] | Booth, KS; Lueker, GS, Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms, J. Comput. Syst. Sci., 13, 3, 335-379 (1976) · Zbl 0367.68034 · doi:10.1016/S0022-0000(76)80045-1 |
| [11] | Corneil, DG; Olariu, S.; Stewart, L., The LBFS structure and recognition of interval graphs, SIAM J. Discrete Math., 23, 4, 1905-1953 (2010) · Zbl 1207.05131 · doi:10.1137/S0895480100373455 |
| [12] | Hsu, W-L; Ma, T-H, Fast and simple algorithms for recognizing chordal comparability graphs and interval graphs, SIAM J. Comput., 28, 3, 1004-1020 (1998) · Zbl 0918.68047 · doi:10.1137/S0097539792224814 |
| [13] | McConnell, RM; Spinrad, JP, Modular decomposition and transitive orientation, Discrete Math., 201, 1, 189-241 (1999) · Zbl 0933.05146 · doi:10.1016/S0012-365X(98)00319-7 |
| [14] | Bodlaender, HL; Kloks, T.; Kratsch, D.; Müller, H., Treewidth and minimum fill-in on \(d\)-trapezoid graphs, J. Graph Algorithms Appl., 2, 5, 1-23 (1998) · Zbl 0905.68101 · doi:10.7155/jgaa.00008 |
| [15] | Yannakakis, M., The complexity of the partial order dimension problem, SIAM J. Algebr. Discrete Methods, 3, 3, 351-358 (1982) · Zbl 0516.06001 · doi:10.1137/0603036 |
| [16] | Ma, T-H; Spinrad, JP, On the 2-chain subgraph cover and related problems, J. Algorithms, 17, 2, 251-268 (1994) · Zbl 0821.68097 · doi:10.1006/jagm.1994.1034 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
