Exploring the gap between treedepth and vertex cover through vertex integrity. (English) Zbl 07667136
Calamoneri, Tiziana (ed.) et al., Algorithms and complexity. 12th international conference, CIAC 2021, virtual event, May 10–12, 2021. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12701, 271-285 (2021).
Summary: For intractable problems on graphs of bounded treewidth, two graph parameters treedepth and vertex cover number have been used to obtain fine-grained complexity results. Although the studies in this direction are successful, we still need a systematic way for further investigations because the graphs of bounded vertex cover number form a rather small subclass of the graphs of bounded treedepth. To fill this gap, we use vertex integrity, which is placed between the two parameters mentioned above. For several graph problems, we generalize fixed-parameter tractability results parameterized by vertex cover number to the ones parameterized by vertex integrity. We also show some finer complexity contrasts by showing hardness with respect to vertex integrity or treedepth.
For the entire collection see [Zbl 1507.68025].
For the entire collection see [Zbl 1507.68025].
MSC:
| 68Wxx | Algorithms in computer science |
References:
| [1] | Abu-Khzam, FN, Maximum common induced subgraph parameterized by vertex cover, Inf. Process. Lett., 114, 3, 99-103 (2014) · Zbl 1284.68274 · doi:10.1016/j.ipl.2013.11.007 |
| [2] | Arnborg, S.; Lagergren, J.; Seese, D., Easy problems for tree-decomposable graphs, J. Algorithms, 12, 2, 308-340 (1991) · Zbl 0734.68073 · doi:10.1016/0196-6774(91)90006-K |
| [3] | Asahiro, Y.; Miyano, E.; Ono, H., Graph classes and the complexity of the graph orientation minimizing the maximum weighted outdegree, Discret. Appl. Math., 159, 7, 498-508 (2011) · Zbl 1210.05161 · doi:10.1016/j.dam.2010.11.003 |
| [4] | Assmann, SF; Peck, GW; Sysło, MM; Zak, J., The bandwidth of caterpillars with hairs of length 1 and 2, SIAM J. Algebraic Discrete Methods, 2, 4, 387-393 (1981) · Zbl 0494.05059 · doi:10.1137/0602041 |
| [5] | Barefoot, CA; Entringer, RC; Swart, HC, Vulnerability in graphs – a comparative survey, J. Combin. Math. Combin. Comput., 1, 13-22 (1987) · Zbl 0646.05042 |
| [6] | Belmonte, R.; Fomin, FV; Golovach, PA; Ramanujan, MS, Metric dimension of bounded tree-length graphs, SIAM J. Discret. Math., 31, 2, 1217-1243 (2017) · Zbl 1371.68103 · doi:10.1137/16M1057383 |
| [7] | Rémy, B., Hanaka, T., Katsikarelis, I., Kim, E.J., Lampis, M.: New results on directed edge dominating set. In: MFCS 2018, volume 117 of LIPIcs, pp. 67:1-67:16 (2018). doi:10.4230/LIPIcs.MFCS.2018.67 · Zbl 1512.68191 |
| [8] | Rémy, B., Kim, E.J., Lampis, M., Mitsou, V., Otachi, Y.: Grundy distinguishes treewidth from pathwidth. In: ESA 2020, volume 173 of LIPIcs, pp. 14:1-14:19 (2020). doi:10.4230/LIPIcs.ESA.2020.14 · Zbl 07651153 |
| [9] | Biedl, TC; Chan, TM; Ganjali, Y.; Hajiaghayi, MT; Wood, DR, Balanced vertex-orderings of graphs, Discret. Appl. Math., 148, 1, 27-48 (2005) · Zbl 1060.05088 · doi:10.1016/j.dam.2004.12.001 |
| [10] | Bodlaender, HL; Lepistö, T.; Salomaa, A., Dynamic programming on graphs with bounded treewidth, Automata, Languages and Programming, 105-118 (1988), Heidelberg: Springer, Heidelberg · Zbl 0649.68039 · doi:10.1007/3-540-19488-6_110 |
| [11] | Bodlaender, H.L., Hanaka, T., Jaffke, L., Ono, H., Otachi, Y., van der Zanden, T.C.: Hedonic seat arrangement problems (extended abstract). In: AAMAS 2020, pp. 1777-1779 (2020) doi:10.5555/3398761.3398979 |
| [12] | Bodlaender, HL; Hanaka, T.; Okamoto, Y.; Otachi, Y.; van der Zanden, TC; Heggernes, P., SubGraph isomorphism on graph classes that exclude a substructure, Algorithms and Complexity, 87-98 (2019), Cham: Springer, Cham · Zbl 1525.68092 · doi:10.1007/978-3-030-17402-6_8 |
| [13] | Bonnet, É., Purohit, N.: Metric dimension parameterized by treewidth. In: IPEC 2019, volume 148 of LIPIcs, pp. 5:1-5:15 (2019). doi:10.4230/LIPIcs.IPEC.2019.5 · Zbl 1515.68227 |
| [14] | Bonnet, É.; Sikora, F., The graph motif problem parameterized by the structure of the input graph, Discret. Appl. Math., 231, 78-94 (2017) · Zbl 1369.05195 · doi:10.1016/j.dam.2016.11.016 |
| [15] | Courcelle, B., The monadic second-order logic of graphs III: tree-decompositions, minor and complexity issues, RAIRO Theor. Inform. Appl., 26, 257-286 (1992) · Zbl 0754.03006 · doi:10.1051/ita/1992260302571 |
| [16] | Cygan, M., Parameterized Algorithms (2015), Cham: Springer, Cham · Zbl 1334.90001 · doi:10.1007/978-3-319-21275-3 |
| [17] | Dom, M.; Lokshtanov, D.; Saurabh, S.; Villanger, Y.; Grohe, M.; Niedermeier, R., Capacitated domination and covering: a parameterized perspective, Parameterized and Exact Computation, 78-90 (2008), Heidelberg: Springer, Heidelberg · Zbl 1142.68371 · doi:10.1007/978-3-540-79723-4_9 |
| [18] | Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, Cham (1999). doi:10.1007/978-1-4612-0515-9 |
| [19] | Drange, P.G., Dregi, M.S., van ’t Hof, P.: On the computational complexity of vertex integrity and component order connectivity. Algorithmica, 76(4), 1181-1202 (2016). doi:10.1007/s00453-016-0127-x · Zbl 1355.68115 |
| [20] | Dvořák, P., Eiben, E., Ganian, R., Knop, D., Ordyniak, S.: Solving integer linear programs with a small number of global variables and constraints. In: IJCAI 2017, pp. 607-613 (2017). doi:10.24963/ijcai.2017/85 |
| [21] | Dvořák, P.; Knop, D., Parameterized complexity of length-bounded cuts and multicuts, Algorithmica, 80, 12, 3597-3617 (2018) · Zbl 1400.90258 · doi:10.1007/s00453-018-0408-7 |
| [22] | Enciso, R.; Fellows, MR; Guo, J.; Kanj, I.; Rosamond, F.; Suchý, O.; Chen, J.; Fomin, FV, What makes equitable connected partition easy, Parameterized and Exact Computation, 122-133 (2009), Heidelberg: Springer, Heidelberg · Zbl 1273.68164 · doi:10.1007/978-3-642-11269-0_10 |
| [23] | Fellows, MR, On the complexity of some colorful problems parameterized by treewidth, Inf. Comput., 209, 2, 143-153 (2011) · Zbl 1223.05070 · doi:10.1016/j.ic.2010.11.026 |
| [24] | Fellows, MR; Lokshtanov, D.; Misra, N.; Rosamond, FA; Saurabh, S.; Hong, S-H; Nagamochi, H.; Fukunaga, T., Graph layout problems parameterized by vertex cover, Algorithms and Computation, 294-305 (2008), Heidelberg: Springer, Heidelberg · Zbl 1183.68424 · doi:10.1007/978-3-540-92182-0_28 |
| [25] | Fiala, J.; Golovach, PA; Kratochvíl, J., Parameterized complexity of coloring problems: treewidth versus vertex cover, Theor. Comput. Sci., 412, 23, 2513-2523 (2011) · Zbl 1216.68127 · doi:10.1016/j.tcs.2010.10.043 |
| [26] | Ganian, R., Klute, F., Ordyniak, S.: On structural parameterizations of the bounded-degree vertex deletion problem. Algorithmica (2020). doi:10.1007/s00453-020-00758-8 · Zbl 1487.68178 |
| [27] | Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, W. H (1979) · Zbl 0411.68039 |
| [28] | Gassner, E., The steiner forest problem revisited, J. Discrete Algorithms, 8, 2, 154-163 (2010) · Zbl 1186.90117 · doi:10.1016/j.jda.2009.05.002 |
| [29] | Gima, T., Hanaka, T., Kiyomi, M., Kobayashi, Y., Otachi, Y.: Exploring the gap between treedepth and vertex cover through vertex integrity. CoRR, abs/2101.09414, arXiv preprint arXiv:2101.09414 (2021) |
| [30] | Jansen, K.; Kratsch, S.; Marx, D.; Schlotter, I., Bin packing with fixed number of bins revisited, J. Comput. Syst. Sci., 79, 1, 39-49 (2013) · Zbl 1261.68065 · doi:10.1016/j.jcss.2012.04.004 |
| [31] | Kellerhals, L., Koana, T.: Parameterized complexity of geodetic set. In: IPEC 2020, volume 180 of LIPIcs, pp. 20:1-20:14 (2020). doi:10.4230/LIPIcs.IPEC.2020.20 · Zbl 07764111 |
| [32] | Lenstra Jr, H.W.: Integer programming with a fixed number of variables. Math. Oper. Res. 8, 538-548 (1983). doi:10.1287/moor.8.4.538 · Zbl 0524.90067 |
| [33] | Lokshtanov, D.: Parameterized integer quadratic programming: variables and coefficients. CoRR, abs/1511.00310 (2015). arXiv preprint arXiv:1511.00310 |
| [34] | Lokshtanov, D.; Misra, N.; Saurabh, S., Imbalance is fixed parameter tractable, Inf. Process. Lett., 113, 19-21, 714-718 (2013) · Zbl 1284.68471 · doi:10.1016/j.ipl.2013.06.010 |
| [35] | Meeks, K.; Alexander, S., The parameterised complexity of list problems on graphs of bounded treewidth, Inf. Comput., 251, 91-103 (2016) · Zbl 1353.68134 · doi:10.1016/j.ic.2016.08.001 |
| [36] | Misra, N.; Mittal, H.; Kim, D.; Uma, RN; Cai, Z.; Lee, DH, Imbalance parameterized by twin cover revisited, Computing and Combinatorics, 162-173 (2020), Cham: Springer, Cham · Zbl 1514.68225 · doi:10.1007/978-3-030-58150-3_13 |
| [37] | Monien, B., The bandwidth minimization problem for caterpillars with hair length 3 is NP-complete, SIAM J. Algebraic Discrete Methods, 7, 4, 505-512 (1986) · Zbl 0624.68059 · doi:10.1137/0607057 |
| [38] | Muradian, D., The bandwidth minimization problem for cyclic caterpillars with hair length 1 is NP-complete, Theor. Comput. Sci., 307, 3, 567-572 (2003) · Zbl 1070.68123 · doi:10.1016/S0304-3975(03)00238-X |
| [39] | Nešetřil, J., de Mendez, P.O.: Sparsity: Graphs, Structures, and Algorithms. Algorithms and Combinatorics. Springer, Cham (2012). doi:10.1007/978-3-642-27875-4 · Zbl 1268.05002 |
| [40] | Szeider, S.: Not so easy problems for tree decomposable graphs. Ramanujan Mathematical Society, Lecture Notes Series, No. 13, pp. 179-190 (2010) arXiv preprint arXiv:1107.1177 · Zbl 1231.05252 |
| [41] | Szeider, S.: Monadic second order logic on graphs with local cardinality constraints. ACM Trans. Comput. Log. 12(2), 12:1-12:21 (2011). doi:10.1145/1877714.1877718 · Zbl 1351.68121 |
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.
