Maximum weight independent sets for (\(S_{1,2,4}\), triangle)-free graphs in polynomial time. (English) Zbl 1517.05164
Summary: The Maximum Weight Independent Set (MWIS) problem on finite undirected graphs with vertex weights asks for a set of pairwise nonadjacent vertices of maximum weight sum. MWIS is one of the most investigated and most important algorithmic graph problems; it is well known to be NP-complete, and it remains NP-complete even under various strong restrictions such as for triangle-free graphs. Its complexity for \(P_k\)-free graphs, \(k \geq 7\), is an open problem. In [A. Brandstädt and R. Mosca, Discrete Appl. Math. 236, 57–65 (2018; Zbl 1377.05185)], it is shown that MWIS can be solved in polynomial time for (\( P_7\),triangle)-free graphs. This result is extended by F. Maffray and L. Pastor [Discrete Math. 341, No. 5, 1449–1458 (2018; Zbl 1383.05145)] showing that MWIS can be solved in polynomial time for (\( P_7\),bull)-free graphs. In the same paper, they also showed that MWIS can be solved in polynomial time for (\( S_{1 , 2 , 3}\),bull)-free graphs. In this paper, using a similar approach as in [Brandstädt and Mosca, loc. cit.], we show that MWIS can be solved in polynomial time for (\( S_{1 , 2 , 4}\),triangle)-free graphs which generalizes the result for (\(P_7\),triangle)-free graphs.
MSC:
| 05C85 | Graph algorithms (graph-theoretic aspects) |
| 05C69 | Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) |
| 68W40 | Analysis of algorithms |
Keywords:
\( S_{1, 2, 4}\)-free graphs; triangle-free graphs; polynomial-time algorithm; anti-neighborhood approachReferences:
| [1] | Ahuja, R. K.; Magnanti, T. L.; Orlin, J. B., Network Flows (1993), Prentice Hall · Zbl 1201.90001 |
| [2] | Alekseev, V. E., On the local restriction effect on the complexity of finding the graph independence number, (Combinatorial-Algebraic Methods in Applied Mathematics (1983), Gorkiy University Press: Gorkiy University Press Gorkiy), 3-13, (in Russian) |
| [3] | Alekseev, V. E., A polynomial algorithm for finding largest independent sets in fork-free graphs, Discrete Anal. Oper. Res. Ser. 1, 6, 3-19 (1999), (in Russian) (see also [4] for the English version) · Zbl 0931.05078 |
| [4] | Alekseev, V. E., A polynomial algorithm for finding largest independent sets in graphs without forks, Discrete Appl. Math., 135, 3-16 (2004) · Zbl 0931.05078 |
| [5] | Alekseev, V. E., On easy and hard hereditary classes of graphs with respect to the independent set problem, Discrete Appl. Math., 132, 17-26 (2004) · Zbl 1029.05140 |
| [6] | Brandstädt, A.; Le, V. B.; Spinrad, J. P., Graph Classes: A Survey, SIAM Monographs on Discrete Math. Appl., vol. 3 (1999), SIAM: SIAM Philadelphia · Zbl 0919.05001 |
| [7] | Brandstädt, A.; Mosca, R., Maximum weight independent sets for \(( P_7\),triangle)-free graphs in polynomial time, Discrete Appl. Math., 236, 57-65 (2018) · Zbl 1377.05185 |
| [8] | Brandstädt, A.; Mosca, R., Maximum weight independent set for ℓclaw-free graphs in polynomial time, Discrete Appl. Math., 237, 57-64 (2018) · Zbl 1380.05147 |
| [9] | Desler, J. F.; Hakimi, S. L., On finding a maximum stable set of a graph, (Proc. 4th Annual Princeton Conf. on Information Science and Systems. Proc. 4th Annual Princeton Conf. on Information Science and Systems, Princeton, NJ (1970)) |
| [10] | Faenza, Y.; Oriolo, G.; Stauffer, G., An algorithmic decomposition of claw-free graphs leading to an \(O( n^3)\)-algorithm for the weighted independent set problem, SODA 2011. SODA 2011, J. ACM, 61, 4, Article 20 pp. (July 2014) · Zbl 1321.05260 |
| [11] | Farber, M.; Hujter, M.; Tuza, Zs., An upper bound on the number of cliques in a graph, Networks, 23, 75-83 (1993) |
| [12] | Garey, M. R.; Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness (1979), Freeman: Freeman San Francisco, CA · Zbl 0411.68039 |
| [13] | Grötschel, M.; Lovász, L.; Schrijver, A., Geometric Algorithms and Combinatorial Optimization (1988), Springer: Springer Berlin · Zbl 0634.05001 |
| [14] | Grzesik, A.; Klimosova, T.; Pilipczuk, Marcin; Pilipczuk, Michal, Polynomial-time algorithm for maximum weight independent set on P6-free graphs, (Chan, Timothy M., Proceedings of the 18 Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms. Proceedings of the 18 Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019 (2019), SIAM), 1257-1271 · Zbl 1431.68047 |
| [15] | Hujter, M.; Tuza, Zs., The number of maximal independent sets in triangle-free graphs, SIAM J. Discrete Math., 6, 2, 284-288 (1993) · Zbl 0779.05025 |
| [16] | Karp, R. M., Reducibility among combinatorial problems, (Miller, R. E.; Thatcher, J. W., Complexity of Computer Computations (1972), Plenum Press: Plenum Press New York), 85-103 · Zbl 1467.68065 |
| [17] | Lokshtanov, D.; Pilipczuk, M.; van Leeuwen, E. J., Independence and efficient domination on \(P_6\)-free graphs, Proc. SODA 2016. Proc. SODA 2016, ACM Trans. Algorithms, 14, 1, Article 3 pp. (2018) · Zbl 1431.68049 |
| [18] | Lokshantov, D.; Vatshelle, M.; Villanger, Y., Independent set in \(P_5\)-free graphs in polynomial time, (Chekuri, C., Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms. Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014 (2014), SIAM), 570-581 · Zbl 1422.68126 |
| [19] | Lozin, V. V., From matchings to independent sets, Discrete Appl. Math., 231, 4-14 (2017) · Zbl 1369.05174 |
| [20] | Lozin, V. V.; Milanič, M., A polynomial algorithm to find an independent set of maximum weight in a fork-free graph, J. Discret. Algorithms, 6, 595-604 (2008) · Zbl 1154.90607 |
| [21] | Maffray, F.; Pastor, L., The maximum weight stable set problem in \(( P_6\),bull)-free graphs, extended abstract, (Heggernes, P., Graph-Theoretic Concepts in Computer Science - 42nd International Workshop, Revised Selected Papers. Graph-Theoretic Concepts in Computer Science - 42nd International Workshop, Revised Selected Papers, WG 2016, Istanbul, Turkey, June 22-24, 2016. Graph-Theoretic Concepts in Computer Science - 42nd International Workshop, Revised Selected Papers. Graph-Theoretic Concepts in Computer Science - 42nd International Workshop, Revised Selected Papers, WG 2016, Istanbul, Turkey, June 22-24, 2016, LNCS, vol. 9941 (2015)), 85-96, Full version: CoRR · Zbl 1417.05223 |
| [22] | Maffray, F.; Pastor, L., Maximum weight stable set in \(( P_7\), bull)-free graphs and \(( S_{1 , 2 , 3}\), bull)-free graphs, Discrete Math., 341, 1449-1458 (2018) · Zbl 1383.05145 |
| [23] | Minty, G. J., On maximal independent sets of vertices in claw-free graphs, J. Comb. Theory, Ser. B, 28, 284-304 (1980) · Zbl 0434.05043 |
| [24] | Mosca, R., Independent sets in \(( P_4 + P_4\), triangle)-free graphs, CoRR arXiv · Zbl 1479.05282 |
| [25] | Nakamura, D.; Tamura, A., A revision of Minty’s algorithm for finding a maximum weight independent set in a claw-free graph, J. Oper. Res. Soc. Jpn., 44, 194-204 (2001) · Zbl 1128.05318 |
| [26] | Nobili, P.; Sassano, A., An \(O( n^2 l o g(n))\) algorithm for the weighted stable set problem in claw-free graphs, Math. Program., 186, 409-437 (2021) · Zbl 1458.05203 |
| [27] | McConnell, R. M.; Spinrad, J. P., Modular decomposition and transitive orientation, Discrete Math., 201, 189-241 (1999) · Zbl 0933.05146 |
| [28] | Möhring, R. H.; Radermacher, F. J., Substitution decomposition for discrete structures and connections with combinatorial optimization, Ann. Discrete Math., 19, 257-356 (1984) · Zbl 0567.90073 |
| [29] | Olariu, S., Paw-free graphs, Inf. Process. Lett., 28, 53-54 (1988) · Zbl 0654.05063 |
| [30] | Olariu, S., On the closure of triangle-free graphs under substitution, Inf. Process. Lett., 34, 97-101 (1990) · Zbl 0702.68056 |
| [31] | Poljak, S., A note on independent sets and colorings of graphs, Commun. Math. Univ. Carolinae, 15, 307-309 (1974) · Zbl 0284.05105 |
| [32] | Prömel, H.-J.; Schickinger, T.; Steger, A., A note on triangle-free and bipartite graphs, Discrete Math., 257, 531-540 (2002) · Zbl 1008.05077 |
| [33] | Sbihi, N., Algorithme de recherche d’un independent de cardinalité maximum dans un graphe sans étoile, Discrete Math., 29, 53-76 (1980) · Zbl 0444.05049 |
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.
