×

An \(\mathcal{O} (n^2 \log{n})\) algorithm for the weighted stable set problem in claw-free graphs. (English) Zbl 1458.05203

Summary: A graph \(G(V, E)\) is claw-free if no vertex has three pairwise non-adjacent neighbours. The maximum weight stable set (MWSS) problem in a claw-free graph is a natural generalization of the matching problem and has been shown to be polynomially solvable by Minty and Sbihi in 1980. In a remarkable paper, Y. Faenza et al. [J. ACM 61, No. 4, Article No. 20, 41 p. (2014; Zbl 1321.05260)] have shown that, in a two-step procedure, a claw-free graph can be first turned into a quasi-line graph by removing strips containing all the irregular nodes and then decomposed into {claw, net}-free strips and strips with stability number at most three. Through this decomposition, the MWSS problem can be solved in \(\mathcal{O} (|V|(|V| \log |V| + |E|))\) time. In this paper, we describe a direct decomposition of a claw-free graph into {claw, net}-free strips and strips with stability number at most three which can be performed in \(\mathcal{O}(|V|^2)\) time. In two companion papers we showed that the MWSS problem can be solved in \(\mathcal{O}(|E| \log |V|)\) time in claw-free graphs with \(\alpha (G) \le 3\) and in \(\mathcal{O}(|V| \sqrt{|E|})\) time in {claw, net}-free graphs with \(\alpha (G) \ge 4\). These results prove that the MWSS problem in a claw-free graph can be solved in \(\mathcal{O}(|V|^2 \log |V|)\) time, the same complexity of the best and long standing algorithm for the MWSS problem in line graphs.

MSC:

05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C85 Graph algorithms (graph-theoretic aspects)
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

Citations:

Zbl 1321.05260

References:

[1] Ball, MO; Derigs, U., An analysis of alternative strategies for implementing matching algorithms, Networks, 13, 4, 517-549 (1983) · Zbl 0519.68055 · doi:10.1002/net.3230130406
[2] Chudnovsky, M., Seymour, P.D.: The structure of claw-free graphs. In: Surveys in Combinatorics (2005). doi:10.1017/CBO9780511734885.008 · Zbl 1109.05092
[3] Faenza, Y.; Oriolo, G.; Stauffer, G., Solving the weighted stable set problem in claw-free graphs via decomposition, J. ACM, 61, 4, 20 (2014) · Zbl 1321.05260 · doi:10.1145/2629600
[4] Fouquet, J., A strengthening of Ben Rebea’s lemma, J. Comb. Theory Ser. B, 59, 1, 35-40 (1993) · Zbl 0793.05123 · doi:10.1006/jctb.1993.1052
[5] Gabow, H.N.: Data structures for weighted matching and nearest common ancestors with linking. In: SODA, pp. 434-443 (1990) · Zbl 0800.68617
[6] Galil, Z., Micali, S., Gabow, H.N.: Priority queues with variable priority and an O(EV log V) algorithm for finding a maximal weighted matching in general graphs. In: 23rd Annual Symposium on Foundations of Computer Science, Chicago, Illinois, USA, 3-5 November 1982, pp. 255-261 (1982)
[7] Kloks, T.; Kratsch, D.; Müller, H., Finding and counting small induced subgraphs efficiently, Inf. Process. Lett., 74, 3-4, 115-121 (2000) · Zbl 1339.05394 · doi:10.1016/S0020-0190(00)00047-8
[8] Lovász, L., Plummer, M.: Matching theory. In: Annals of Discrete Mathematics, 29. North-Holland Mathematics Studies, 121. Amsterdam etc.: North-Holland. XXXIII, 544 p. (1986) · Zbl 0618.05001
[9] Minty, GJ, On maximal independent sets of vertices in claw-free graphs, J. Comb. Theory Ser. B, 28, 284-304 (1980) · Zbl 0434.05043 · doi:10.1016/0095-8956(80)90074-X
[10] Nobili, P.; Sassano, A., An \({O}(n \sqrt{m})\) algorithm for the weighted stable set problem in Claw, Net-free graphs with \(\alpha ({G}) \ge 4\), Discrete Optim., 19, C, 63-78 (2016) · Zbl 1387.05256 · doi:10.1016/j.disopt.2016.01.002
[11] Nobili, P.; Sassano, A., An \({O}(m \log n)\) algorithm for the weighted stable set problem in claw-free graphs with \(\alpha ({G}) \le 3\), Math. Program., 164, 1, 157-165 (2017) · Zbl 1367.05161 · doi:10.1007/s10107-016-1080-9
[12] Schrijver, A., Combinatorial Optimization: Polyhedra and Efficiency (2003), Berlin: Springer, Berlin · Zbl 1041.90001
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.