×

Contraction blockers for graphs with forbidden induced paths. (English) Zbl 1459.68156

Paschos, Vangelis Th. (ed.) et al., Algorithms and complexity. 9th international conference, CIAC 2015, Paris, France, May 20–22, 2015. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 9079, 194-207 (2015).
Summary: We consider the following problem: can a certain graph parameter of some given graph be reduced by at least \(d\) for some integer \(d\) via at most \(k\) edge contractions for some given integer \(k\)? We examine three graph parameters: the chromatic number, clique number and independence number. For each of these graph parameters we show that, when \(d\) is part of the input, this problem is polynomial-time solvable on \(P_4\)-free graphs and NP-complete as well as W[1]-hard, with parameter \(d\), for split graphs. As split graphs form a subclass of \(P_5\)-free graphs, both results together give a complete complexity classification for \(P_\ell \)-free graphs. The W[1]-hardness result implies that it is unlikely that the problem is fixed-parameter tractable for split graphs with parameter \(d\). But we do show, on the positive side, that the problem is polynomial-time solvable, for each parameter, on split graphs if \(d\) is fixed, i.e., not part of the input. We also initiate a study into other subclasses of perfect graphs, namely cobipartite graphs and interval graphs.
For the entire collection see [Zbl 1316.68024].

MSC:

68R10 Graph theory (including graph drawing) in computer science
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68Q25 Analysis of algorithms and problem complexity
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Alekseev, VE, On easy and hard hereditary classes of graphs with respect to the independent set problem, Discrete Applied Math., 132, 17-26 (2004) · Zbl 1029.05140 · doi:10.1016/S0166-218X(03)00387-1
[2] Bazgan, C.; Bentz, C.; Picouleau, C.; Ries, B., Blockers for the stability number and the chromatic number, Graphs and Combinatorics, 31, 73-90 (2015) · Zbl 1306.05051 · doi:10.1007/s00373-013-1380-2
[3] Bazgan, C.; Toubaline, S.; Tuza, Z.; Iliopoulos, CS; Smyth, WF, Complexity of Most Vital Nodes for Independent Set in Graphs Related to Tree Structures, Combinatorial Algorithms, 154-166 (2011), Heidelberg: Springer, Heidelberg · Zbl 1326.05103 · doi:10.1007/978-3-642-19222-7_17
[4] Bazgan, C.; Toubaline, S.; Tuza, Z., The most vital nodes with respect to independent set and vertex cover, Discrete Applied Mathematics, 159, 17, 1933-1946 (2011) · Zbl 1236.05141 · doi:10.1016/j.dam.2011.06.023
[5] Belmonte, R.; Golovach, PA; van’ t. Hof, P., Parameterized complexity of three edge contraction problems with degree constraints, Acta Informatica, 51, 473-497 (2014) · Zbl 1360.68489 · doi:10.1007/s00236-014-0204-z
[6] Bodlaender, HL; Möhring, RH, The pathwidth and treewidth of cographs, SIAM J. Discrete Math., 6, 181-188 (1993) · Zbl 0773.05091 · doi:10.1137/0406014
[7] Brandstädt, A., Le, V.B., Spinrad, J.: Graph Classes: A Survey. SIAM Monographs on Discrete Mathematics and Applications (1999) · Zbl 0919.05001
[8] Chvátal, V.; Hoàng, CT; Mahadev, NVR; de Werra, D., Four classes of perfectly orderable graphs, J. Graph Theory, 11, 481-495 (1987) · Zbl 0654.05032 · doi:10.1002/jgt.3190110405
[9] Corneil, DG; Lerchs, H.; Stewart Burlingham, L., Complement reducible graphs, Discrete Applied Mathematics, 3, 163-174 (1981) · Zbl 0463.05057 · doi:10.1016/0166-218X(81)90013-5
[10] Corneil, DG; Perl, Y.; Stewart, LK, A linear recognition algorithm for cographs, SIAM J. Comput., 14, 926-934 (1985) · Zbl 0575.68065 · doi:10.1137/0214065
[11] Costa, M-C; de Werra, D.; Picouleau, C., Minimum d-blockers and d-transversals in graphs, Journal of Combinatorial Optimization, 22, 857-872 (2011) · Zbl 1263.90110 · doi:10.1007/s10878-010-9334-6
[12] Földes, S., Hammer, P.L.: Split graphs. In: 8th South-Eastern Conf. on Combinatorics, Graph Theory and Computing, Congressus Numerantium. vol. 19, pp. 311-315 (1977) · Zbl 0407.05071
[13] Fulkerson, D.; Gross, O., Incidence matrices and interval graphs, Pacific Journal of Mathematics, 15, 835-855 (1965) · Zbl 0132.21001 · doi:10.2140/pjm.1965.15.835
[14] Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman (1979) · Zbl 0411.68039
[15] Golovach, PA; Heggernes, P.; van ’t Hof, P.; Paul, C.; Kratsch, D.; Todinca, I., Hadwiger number of graphs with small chordality, Graph-Theoretic Concepts in Computer Science, 201-213 (2014), Heidelberg: Springer, Heidelberg · Zbl 1417.05209 · doi:10.1007/978-3-319-12340-0_17
[16] Golumbic, MC, Algorithmic Graph Theory and Perfect Graphs (1980), New York: Academic Press, New York · Zbl 0541.05054
[17] Gutin, G.; Jones, M.; Yeo, A., Kernels for Below-Upper-Bound Parameterizations of the Hitting Set and Directed Dominating Set Problems, Theor. Comput. Sci., 412, 5744-5751 (2011) · Zbl 1225.68096 · doi:10.1016/j.tcs.2011.06.018
[18] Heggernes, P.; van t. Hof, P.; Lokshtanov, D.; Paul, C., Obtaining a Bipartite Graph by Contracting Few Edges, SIAM Journal on Discrete Mathematics, 27, 2143-2156 (2013) · Zbl 1285.05167 · doi:10.1137/130907392
[19] Král’, D.; Kratochvíl, J.; Tuza, Z.; Woeginger, GJ; Brandstädt, A.; Le, VB, Complexity of coloring graphs without forbidden induced subgraphs, Graph-Theoretic Concepts in Computer Science, 254 (2001), Heidelberg: Springer, Heidelberg · Zbl 1042.68639 · doi:10.1007/3-540-45477-2_23
[20] Lokshtanov, D., Vatshelle, M., Villanger, Y.: Independent Set in P5-Free Graphs in Polynomial Time. In: Proc. SODA, pp. 570-581 (2014) · Zbl 1422.68126
[21] Pajouh, FM; Boginski, V.; Pasiliao, EL, Minimum vertex blocker clique problem, Networks, 64, 48-64 (2014) · Zbl 1390.90183 · doi:10.1002/net.21556
[22] Ries, B.; Bentz, C.; Picouleau, C.; de Werra, D.; Costa, M-C; Zenklusen, R., Blockers and Transversals in some subclasses of bipartite graphs : when caterpillars are dancing on a grid, Discrete Mathematics, 310, 132-146 (2010) · Zbl 1223.05240 · doi:10.1016/j.disc.2009.08.009
[23] Toubaline, S.: Détermination des éléments les plus vitaux pour des problèmes de graphes, Ph. D. thesis, Université Paris-Dauphine (2010)
[24] Watanabe, T.; Tadashi, AE; Nakamura, A., On the removal of forbidden graphs by edge-deletion or by edge-contraction, Discrete Applied Mathematics, 3, 151-153 (1981) · Zbl 0448.05052 · doi:10.1016/0166-218X(81)90039-1
[25] Watanabe, T.; Tadashi, AE; Nakamura, A., On the NP-hardness of edge-deletion and -contraction problems, Discrete Applied Mathematics, 6, 63-78 (1983) · Zbl 0511.68028 · doi:10.1016/0166-218X(83)90101-4
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.