Extended MSO model checking via small vertex integrity. (English) Zbl 07785278
Summary: We study the model checking problem of an extended \(\mathsf{MSO}\) with local and global cardinality constraints, called \(\mathsf{MSO}^{\mathsf{GL}}_{\mathsf{Lin}}\), introduced recently by Knop et al. (Log Methods Comput Sci, 15(4), 2019. doi:10.23638/LMCS-15(4:12)2019). We show that the problem is fixed-parameter tractable parameterized by vertex integrity, where vertex integrity is a graph parameter standing between vertex cover number and treedepth. Our result thus narrows the gap between the fixed-parameter tractability parameterized by vertex cover number and the W[1]-hardness parameterized by treedepth.
Keywords:
vertex integrity; monadic second-order logic; cardinality constraint; fixed-parameter tractabilityReferences:
| [1] | 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 |
| [2] | Barefoot, CA; Entringer, RC; Swart, HC, Vulnerability in graphs – a comparative survey, J. Combin. Math. Combin. Comput., 1, 13-22 (1987) · Zbl 0646.05042 |
| [3] | Belmonte, R., Jung Kim, E., 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 |
| [4] | Belmonte, R.; Lampis, M.; Mitsou, V., Parameterized (approximate) defective coloring, SIAM J. Discret. Math., 34, 2, 1084-1106 (2020) · Zbl 1433.68178 · doi:10.1137/18M1223666 |
| [5] | Bliem, B.; Woltran, S., Defensive alliances in graphs of bounded treewidth, Discret. Appl. Math., 251, 334-339 (2018) · Zbl 1401.05211 · doi:10.1016/j.dam.2018.04.001 |
| [6] | Bodlaender, HL, A partial \(k\)-arboretum of graphs with bounded treewidth, Theor. Comput. Sci., 209, 1-2, 1-45 (1998) · Zbl 0912.68148 · doi:10.1016/S0304-3975(97)00228-4 |
| [7] | Bodlaender, HL; Hanaka, T.; Kobayashi, Y.; Kobayashi, Y.; Okamoto, Y.; Otachi, Y.; van der Zanden, TC, Subgraph isomorphism on graph classes that exclude a substructure, Algorithmica, 82, 12, 3566-3587 (2020) · Zbl 1492.68102 · doi:10.1007/s00453-020-00737-z |
| [8] | Borie, RB; Gary Parker, R.; Tovey, CA, Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families, Algorithmica, 7, 5-6, 555-581 (1992) · Zbl 0753.05062 · doi:10.1007/BF01758777 |
| [9] | Bulteaum, L., Dabrowski, L.K., Köhler, N., Ordyniak, S., Paulusma, D.: An algorithmic framework for locally constrained homomorphisms. CoRR abs/2201.11731 (2022). arXiv:2201.11731 · Zbl 07682405 |
| [10] | Cami, A.; Balakrishnan, H.; Deo, N.; Dutton, RD, On the complexity of finding optimal global alliances, J. Combin. Math. Combin. Comput., 58, 23-31 (2006) · Zbl 1113.05074 |
| [11] | Courcelle, B., The monadic second-order logic of graphs. I. Recognizable sets of finite graphs, Inf. Comput., 85, 1, 12-75 (1990) · Zbl 0722.03008 · doi:10.1016/0890-5401(90)90043-H |
| [12] | 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 |
| [13] | Courcelle, B.; Engelfriet, J., Graph structure and monadic second-order logic—a language-theoretic approach (2012), Cambridge University Press · Zbl 1257.68006 · doi:10.1017/CBO9780511977619 |
| [14] | Courcelle, B.; Makowsky, JA; Rotics, U., Linear time solvable optimization problems on graphs of bounded clique-width, Theory Comput. Syst., 33, 2, 125-150 (2000) · Zbl 1009.68102 · doi:10.1007/s002249910009 |
| [15] | Cowen, LJ; Cowen, R.; Woodall, DR, Defective colorings of graphs in surfaces: partitions into subgraphs of bounded valency, J. Graph Theory, 10, 2, 187-195 (1986) · Zbl 0596.05024 · doi:10.1002/jgt.3190100207 |
| [16] | Cygan, M.; Fomin, FV; Kowalik, Ł.; Lokshtanov, D.; Marx, D.; Pilipczuk, M.; Pilipczuk, M.; Saurabh, S., Parameterized algorithms (2015), Springer · Zbl 1334.90001 · doi:10.1007/978-3-319-21275-3 |
| [17] | Dom, M., Lokshtanov, D., Saurabh, S., Villanger, Y.: Capacitated domination and covering: a parameterized perspective. In: IWPEC 2008, volume 5018 of Lecture Notes in Computer Science, pp. 78-90. Springer, (2008). doi:10.1007/978-3-540-79723-4_9 · Zbl 1142.68371 |
| [18] | Drange, PG; Dregi, MS; Hof, P., On the computational complexity of vertex integrity and component order connectivity, Algorithmica, 76, 4, 1181-1202 (2016) · Zbl 1355.68115 · doi:10.1007/s00453-016-0127-x |
| [19] | 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 vol. 2017, pp. 607-613 (2017). doi:10.24963/ijcai.2017/85 · Zbl 1520.90171 |
| [20] | Enciso, R., Fellows, M.R., Guo, J., Kanj, I.A., Rosamond, F.A., Suchý, O.: What makes equitable connected partition easy. In: IWPEC 2009, volume 5917 of Lecture Notes in Computer Science, pp. 122-133, (2009). doi:10.1007/978-3-642-11269-0_10 · Zbl 1273.68164 |
| [21] | Fellows, MR; Fomin, FV; Lokshtanov, D.; Rosamond, FA; Saurabh, S.; Szeider, S.; Thomassen, C., 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 |
| [22] | Fellows, M.R., Lokshtanov, D., Misra, N., Rosamond, F.A., Saurabh, S.: Graph layout problems parameterized by vertex cover. In: ISAAC 2008, volume 5369 of Lecture Notes in Computer Science, pp. 294-305 (2008). doi:10.1007/978-3-540-92182-0_28 · Zbl 1183.68424 |
| [23] | Fernau, H.; Rodríguez-Velázquez, JA, A survey on alliances and related parameters in graphs, Electron. J. Graph Theory Appl., 2, 1, 70-86 (2014) · Zbl 1306.05180 · doi:10.5614/ejgta.2014.2.1.7 |
| [24] | 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 |
| [25] | Frank, A.; Tardos, É., An application of simultaneous diophantine approximation in combinatorial optimization, Combinatorica, 7, 49-65 (1987) · Zbl 0641.90067 · doi:10.1007/BF02579200 |
| [26] | Frick, M.; Grohe, M., The complexity of first-order and monadic second-order logic revisited, Ann. Pure Appl. Log., 130, 1-3, 3-31 (2004) · Zbl 1062.03032 · doi:10.1016/j.apal.2004.01.007 |
| [27] | Fricke, GH; Lawson, LM; Haynes, TW; Hedetniemi, SM; Hedetniemi, ST, A note on defensive alliances in graphs, Bull. Inst. Combin. Appl., 38, 37-41 (2003) · Zbl 1050.05096 |
| [28] | Fujita, S.; Furuya, M., Safe number and integrity of graphs, Discret. Appl. Math., 247, 398-406 (2018) · Zbl 1394.05062 · doi:10.1016/j.dam.2018.03.074 |
| [29] | Fujita, S.; MacGillivray, G.; Sakuma, T., Safe set problem on graphs, Discret. Appl. Math., 215, 106-111 (2016) · Zbl 1346.05141 · doi:10.1016/j.dam.2016.07.020 |
| [30] | Gajarský, J., Hliněný, P.: Kernelizing MSO properties of trees of fixed height, and some consequences. Log. Methods Comput. Sci. 11(1), (2015). doi:10.2168/LMCS-11(1:19)2015 · Zbl 1392.03022 |
| [31] | Ganian, R.: Twin-cover: beyond vertex cover in parameterized algorithmics. In: IPEC 2011, volume 7112 of Lecture Notes in Computer Science, pp. 259-271 (2011). doi:10.1007/978-3-642-28050-4_21 · Zbl 1352.68105 |
| [32] | Ganian, R., Hlinený, P., Nesetril, J., Obdrzálek, J., de Mendez, P.O., Ramadurai, R.: When trees grow low: Shrubs and fast MSO1. In: MFCS 2012, volume 7464 of Lecture Notes in Computer Science, pp. 419-430 (2012). doi:10.1007/978-3-642-32589-2_38 · Zbl 1365.68323 |
| [33] | Ganian, R.; Klute, F.; Ordyniak, S., On structural parameterizations of the bounded-degree vertex deletion problem, Algorithmica, 83, 1, 297-336 (2021) · Zbl 1487.68178 · doi:10.1007/s00453-020-00758-8 |
| [34] | Ganian, R., Obdržálek, J.: Expanding the expressive power of monadic second-order logic on restricted graph classes. In: IWOCA 2013, volume 8288 of Lecture Notes in Computer Science, pp. 164-177 (2013). doi:10.1007/978-3-642-45278-9_15 · Zbl 1284.68463 |
| [35] | Gima, T., Hanaka, T., Kiyomi, M., Kobayashi, Y., Otachi, Y.: Exploring the gap between treedepth and vertex cover through vertex integrity. In: CIAC 2021, volume 12701 of Lecture Notes in Computer Science, pp. 271-285, (2021). doi:10.1007/978-3-030-75242-2_19 · Zbl 07667136 |
| [36] | Grohe, M., Kreutzer, S.: Methods for algorithmic meta theorems. In: Model theoretic methods in finite combinatorics, volume 558 of contemporary mathematics, pp. 181-206 (2009) · Zbl 1278.68099 |
| [37] | Hliněný, P.; Oum, S.; Seese, D.; Gottlob, G., Width parameters beyond tree-width and their applications, Comput. J., 51, 3, 326-362 (2008) · doi:10.1093/comjnl/bxm052 |
| [38] | Jansen, B.M., Marx, D.: Characterizing the easy-to-find subgraphs from the viewpoint of polynomial-time algorithms, kernels, and Turing kernels. In: SODA 2015, pp. 616-629 (2015). doi:10.1137/1.9781611973730.42 · Zbl 1371.68212 |
| [39] | 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 |
| [40] | Kannan, R., Minkowski’s convex body theorem and integer programming, Math. Oper. Res., 12, 415-440 (1987) · Zbl 0639.90069 · doi:10.1287/moor.12.3.415 |
| [41] | Knop, D., Masarík, T., Toufar, T.: Parameterized complexity of fair vertex evaluation problems. In: MFCS 2019, volume 138 of LIPIcs, pp. 33:1-33:16 (2019). doi:10.4230/LIPIcs.MFCS.2019.33 · Zbl 1541.68292 |
| [42] | Knop, D., Koutecký, M., Masařík, T., Toufar, T.: Simplified algorithmic metatheorems beyond MSO: treewidth and neighborhood diversity. Log. Methods Comput. Sci. (2019) · Zbl 1427.68125 |
| [43] | Kreutzer, S.: Algorithmic meta-theorems. In: Esparza, J., Michaux, C., Steinhorn, C., (eds), Finite and algorithmic model theory, volume 379 of London mathematical society lecture note series, pp. 177-270. (2011). doi:10.1017/cbo9780511974960.006 · Zbl 1262.03058 |
| [44] | Kristiansen, P.; Hedetniemi, SM; Hedetniemi, ST, Alliances in graphs, J. Combin. Math. Combin. Comput., 48, 157-177 (2004) · Zbl 1051.05068 |
| [45] | Lampis, M., Algorithmic meta-theorems for restrictions of treewidth, Algorithmica, 64, 1, 19-37 (2012) · Zbl 1252.68154 · doi:10.1007/s00453-011-9554-x |
| [46] | Lampis, M., Mitsou, V.: Fine-grained meta-theorems for vertex integrity. In: ISAAC 2021, volume 212 of LIPIcs, pp. 34:1-34:15 (2021). doi:10.4230/LIPIcs.ISAAC.2021.34 · Zbl 07788607 |
| [47] | Lenstra, HW Jr, Integer programming with a fixed number of variables, Math. Oper. Res., 8, 4, 538-548 (1983) · Zbl 0524.90067 · doi:10.1287/moor.8.4.538 |
| [48] | Lin, L-S; Sahni, S., Fair edge deletion problems, IEEE Trans. Comput., 38, 5, 756-761 (1989) · Zbl 1395.68213 · doi:10.1109/12.24280 |
| [49] | Masařík, T.; Toufar, T., Parameterized complexity of fair deletion problems, Discret. Appl. Math., 278, 51-61 (2020) · Zbl 1437.05227 · doi:10.1016/j.dam.2019.06.001 |
| [50] | Szeider, S., Not so easy problems for tree decomposable graphs, Ramanujan Math. Soc., 13, 179-190 (2010) · Zbl 1231.05252 |
| [51] | Szeider, S., Monadic second order logic on graphs with local cardinality constraints, ACM Trans. Comput. Log., 12, 2, 12:1-12:21 (2011) · Zbl 1351.68121 · doi:10.1145/1877714.1877718 |
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.
