Blocking total dominating sets via edge contractions. (English) Zbl 1478.68239
Summary: In this paper, we study the problem of deciding whether the total domination number of a given graph \(G\) can be reduced using exactly one edge contraction (called 1-Edge Contraction(\(\gamma_t\))). We focus on several graph classes and determine the computational complexity of this problem. By putting together these results, we manage to obtain a complete complexity dichotomy for \(H\)-free graphs.
MSC:
| 68R10 | Graph theory (including graph drawing) in computer science |
| 05C69 | Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) |
| 68Q25 | Analysis of algorithms and problem complexity |
Keywords:
total dominating set; edge contraction; \(H\)-free graphs; computational complexity; blocker problemReferences:
| [1] | Babel, L.; Kloks, T.; Kratochvíl, J.; Kratsch, D.; Müller, K.; Olariu, S., Efficient algorithms for graphs with few p4’s, Discrete Math., 235, 29-51 (2001) · Zbl 0980.05045 |
| [2] | Bazgan, C.; Toubaline, S.; Tuza, Z., The most vital nodes with respect to independent set and vertex cover, Discrete Appl. Math., 159, 1933-1946 (2011) · Zbl 1236.05141 |
| [3] | Bazgan, C.; Toubaline, S.; Vanderpooten, D., Critical edges for the assignment problem: complexity and exact resolution, Oper. Res. Lett., 41, 685-689 (2013) · Zbl 1287.90080 |
| [4] | Bentz, C.; Marie-Christine, C.; de Werra, D.; Picouleau, C.; Ries, B., Blockers and transversals in some subclasses of bipartite graphs: when caterpillars are dancing on a grid, Discrete Math., 310, 132-146 (2010) · Zbl 1223.05240 |
| [5] | Bentz, C.; Marie-Christine, C.; de Werra, D.; Picouleau, C.; Ries, B., Weighted transversals and blockers for some optimization problems in graphs, (Progress in Combinatorial Optimization (2012), ISTE-Wiley), 203-222 · Zbl 1263.90109 |
| [6] | Costa, M.-C.; de Werra, D.; Picouleau, C., Minimum d-blockers and d-transversals in graphs, J. Comb. Optim., 22, 857-872 (2011) · Zbl 1263.90110 |
| [7] | Diestel, R., Graph Theory, Graduate Texts in Mathematics, vol. 173 (2010), Springer: Springer Heidelberg, New York · Zbl 1204.05001 |
| [8] | Diner, Ö. Y.; Paulusma, D.; Picouleau, C.; Ries, B., Contraction blockers for graphs with forbidden induced paths, (Algorithms and Complexity (2015), Springer International Publishing), 194-207 · Zbl 1459.68156 |
| [9] | Diner, Ö. Y.; Paulusma, D.; Picouleau, C.; Ries, B., Contraction and deletion blockers for perfect graphs and H-free graphs, Theor. Comput. Sci., 746, 49-72 (2018) · Zbl 1400.68087 |
| [10] | Galby, E.; Lima, P. T.; Ries, B., Reducing the domination number of graphs via edge contractions and vertex deletions, Discrete Math., 344, 1, Article 112169 pp. (2021) · Zbl 1455.05055 |
| [11] | E. Galby, F. Mann, B. Ries, Blocking the domination number in H-free graphs, manuscript, 2020. |
| [12] | Galby, E.; Munaro, A.; Ries, B., Semitotal domination: new hardness results and a polynomial-time algorithm for graphs of bounded mim-width, Theor. Comput. Sci., 814 (2020) · Zbl 1435.68112 |
| [13] | Garey, M. R.; Johnson, D. S., Computers and Intractability; A Guide to the Theory of NP-Completeness (1990), W. H. Freeman & Co.: W. H. Freeman & Co. New York, NY, USA |
| [14] | Huang, J.; Xu, J.-M., Domination and total domination contraction numbers of graphs, Ars Comb., 94, 431-443 (2010) · Zbl 1240.05226 |
| [15] | Mahdavi Pajouh, F.; Boginski, V.; Pasiliao, E., Minimum vertex blocker clique problem, Networks, 64, 48-64 (2014) · Zbl 1390.90183 |
| [16] | Moore, C.; Robson, J. M., Hard tiling problems with simple tiles, Discrete Comput. Geom., 26, 573-590 (2001) · Zbl 1021.68097 |
| [17] | Paulusma, D.; Picouleau, C.; Ries, B., Reducing the clique and chromatic number via edge contractions and vertex deletions, (ISCO 2016. ISCO 2016, LNCS, vol. 9849 (2016)), 38-49 · Zbl 1432.05074 |
| [18] | Paulusma, D.; Picouleau, C.; Ries, B., Blocking independent sets for H-free graphs via edge contractions and vertex deletions, (TAMC 2017. TAMC 2017, LNCS, vol. 10185 (2017)), 470-483 · Zbl 1485.68197 |
| [19] | Paulusma, D.; Picouleau, C.; Ries, B., Critical vertices and edges in H-free graphs, Discrete Appl. Math., 257, 361-367 (2019) · Zbl 1406.05037 |
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.
