Iterated type partitions. (English) Zbl 07601008
Gąsieniec, Leszek (ed.) et al., Combinatorial algorithms. 31st international workshop, IWOCA 2020, Bordeaux, France, June 8–10, 2020, Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12126, 195-210 (2020).
Summary: This paper introduces a novel parameter, called iterated type partition, that can be computed in polynomial time and nicely places between modular-width and neighborhood diversity. We prove that the Equitable Coloring problem is W[1]-hard when parametrized by the iterated type partition. This result extends to modular-width, answering an open question on the complexity of Equitable Coloring when parametrized by modular-width. On the contrary, we show that the Equitable Coloring problem is FPT when parameterized by neighborhood diversity. Furthermore, we present a scheme for devising FPT algorithms parameterized by iterated type partition, which enables us to find optimal solutions for several graph problems. While the considered problems are already known to be FPT with respect to modular-width, the novel algorithms are both simpler and more efficient. As an example, in this paper, we give an algorithm for the Dominating Set problem that outputs an optimal set in time \(O({2^t}+\mathit{poly}(n))\), where \(n\) and \(t\) are the size and the iterated type partition of the input graph, respectively.
For the entire collection see [Zbl 1496.68019].
For the entire collection see [Zbl 1496.68019].
MSC:
| 68Rxx | Discrete mathematics in relation to computer science |
| 68Wxx | Algorithms in computer science |
Keywords:
parameterized complexity; fixed-parameter tractable algorithms; W[1]-hardness; neighborhood diversity; modular-widthReferences:
| [1] | Abu-Khzam, F.N., Li, S., Markarian, C., Meyer auf der Heide, F., Podlipyan, P.: Modular-width: an auxiliary parameter for parameterized parallel complexity. In: Xiao, M., Rosamond, F. (eds.) FAW 2017. LNCS, vol. 10336, pp. 139-150. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-59605-1_13 · Zbl 1477.68128 · doi:10.1007/978-3-319-59605-1_13 |
| [2] | Belmonte, R., Fomin, F.V., Golovach, P.A., Ramanujan, M.S.: Metric dimension of bounded width graphs. In: Italiano, G.F., Pighizzini, G., Sannella, D.T. (eds.) MFCS 2015. LNCS, vol. 9235, pp. 115-126. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-48054-0_10 · Zbl 1466.68054 · doi:10.1007/978-3-662-48054-0_10 |
| [3] | Bodlaender, H.L., Fomin, F.V.: Equitable colorings of bounded treewidth graphs. Theoret. Comput. Sci. 349, 22-30 (2005). https://doi.org/10.1016/j.tcs.2005.09.027 · Zbl 1086.68096 · doi:10.1016/j.tcs.2005.09.027 |
| [4] | Cockayne, E.J., Dawes, R.M., Hedetniemi, S.T.: Total domination in graphs. Networks 10(3), 211-219 (1980) · Zbl 0447.05039 · doi:10.1002/net.3230100304 |
| [5] | Cordasco, G., Gargano, L., Rescigno, A.A., Vaccaro, U.: Evangelism in social networks: algorithms and complexity. Networks 71(4), 346-357 (2018) · Zbl 1396.91606 · doi:10.1002/net.21756 |
| [6] | Cordasco, G., Gargano, L., Rescigno, A.A.: Iterated Type Partitions. arXiv 2001.08122, https://arxiv.org/abs/2001.08122 (2020) |
| [7] | Coudert, D., Ducoffe, G., Popa, A.: Fully polynomial FPT algorithms for some classes of bounded clique-width graphs. In: Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2018), pp. 2765-2784 (2018) · Zbl 1403.68157 |
| [8] | 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 |
| [9] | Courcelle, B., Makowsky, J.A., 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 |
| [10] | Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, Heidelberg (2012) · Zbl 0914.68076 |
| [11] | Doucha, M., Kratochvíl, J.: Cluster vertex deletion: a parameterization between vertex cover and clique-width. In: Rovan, B., Sassone, V., Widmayer, P. (eds.) MFCS 2012. LNCS, vol. 7464, pp. 348-359. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-32589-2_32 · Zbl 1365.68278 · doi:10.1007/978-3-642-32589-2_32 |
| [12] | Dvorák, P., Knop, D., Toufar, T.: Target set selection in dense graph classes. In: Proceedings of 29th International Symposium on Algorithms and Computation (ISAAC 2018) (2018). https://doi.org/10.4230/LIPIcs.ISAAC.2018.18 · Zbl 1533.68234 |
| [13] | Fellows, M.R., Lokshtanov, D., Misra, N., Rosamond, F.A., Saurabh, S.: Graph layout problems parameterized by vertex cover. In: Hong, S.-H., Nagamochi, H., Fukunaga, T. (eds.) ISAAC 2008. LNCS, vol. 5369, pp. 294-305. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-92182-0_28 · Zbl 1183.68424 · doi:10.1007/978-3-540-92182-0_28 |
| [14] | Fellows, M.R., et al.: 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 |
| [15] | Fellows, M.R., Rosamond, F.A., Rotics, U., Szeider, S.: Clique-width is NP- complete. SIAM J. Discr. Math. 23(2), 909-939 (2009) · Zbl 1207.68159 · doi:10.1137/070687256 |
| [16] | Fiala, J., Golovach, P.A., Kratochvil, J.: Parameterized complexity of coloring problems: treewidth versus vertex cover. Theor. Comput. Sci. 412, 2513-2523 (2011) · Zbl 1216.68127 · doi:10.1016/j.tcs.2010.10.043 |
| [17] | Fiala, J., Gavenciak, T., Knop, D., Koutecky, M., Kratochvíl, J.: Fixed parameter complexity of distance constrained labeling and uniform channel assignment problems. http://arxiv.org/abs/1507.00640arXiv:1507.00640 (2015) · Zbl 1476.68207 |
| [18] | Gavenciak, T., Knop, D., Koutecký, M.: Integer programming in parameterized complexity: three miniatures. In: Proceedings of 13th International Symposium on Parameterized and Exact Computation, IPEC 2018 (2018). https://doi.org/10.4230/LIPIcs.IPEC.2018.21 · Zbl 1520.68049 |
| [19] | Fomin, F.V., Golovach, P.A., Lokshtanov, D., Saurabh, S.: Clique-width: on the price of generality. In: Proceedings of SODA (2009) · Zbl 1421.68125 |
| [20] | Fomin, F.V., Golovach, P., Lokshtanov, D., Saurabh, S.: Intractability of clique-width parameterizations. SIAM J. Comput. 39(5), 1941-1956 (2010) · Zbl 1207.68161 · doi:10.1137/080742270 |
| [21] | Fomin, F.V., Liedloff, M., Montealegre, P., Todinca, I.: Algorithms parameterized by vertex cover and modular width, through potential maximal cliques. In: Ravi, R., Gørtz, I.L. (eds.) SWAT 2014. LNCS, vol. 8503, pp. 182-193. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-08404-6_16 · Zbl 1386.68068 · doi:10.1007/978-3-319-08404-6_16 |
| [22] | Gajarský, J., Lampis, M., Ordyniak, S.: Parameterized algorithms for modular-width. In: Gutin, G., Szeider, S. (eds.) IPEC 2013. LNCS, vol. 8246, pp. 163-176. Springer, Cham (2013). https://doi.org/10.1007/978-3-319-03898-8_15 · Zbl 1406.68080 · doi:10.1007/978-3-319-03898-8_15 |
| [23] | Gallai, T.: Transitiv orientierbare Graphen. Acta Math. Acad. Sci. Hung. 18, 26-66 (1967) · Zbl 0153.26002 · doi:10.1007/BF02020961 |
| [24] | Ganian, R.: Using neighborhood diversity to solve hard problems. arXiv:1201.3091 (2012) |
| [25] | Gargano, L., Rescigno, A.A.: Complexity of conflict-free colorings of graphs. Theoret. Comput. Sci. 566, 39-49 (2015) · Zbl 1317.68071 · doi:10.1016/j.tcs.2014.11.029 |
| [26] | de C. M. Gomes, G., Lima, C.V.G.C., dos Santos, V.F.: Parameterized complexity of equitable coloring. Discrete Math. Theoret. Comput. Sci. 21(1) (2019) · Zbl 1411.05089 |
| [27] | 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 |
| [28] | Knop, D.: Partitioning graphs into induced subgraphs. Discrete Appl. Math. 272, 31-42 (2019) · Zbl 1429.05166 |
| [29] | Knop, D., Koutecký, M., Masarík, T., Toufar, T.: Simplified algorithmic metatheorems beyond MSO: treewidth and neighborhood diversity. Logical Methods Comput. Sci. 15(4) (2019) · Zbl 1427.68125 |
| [30] | Koutecký, M.: Solving hard problems on neighborhood diversity. Master thesis, Charles University in Prague (2013) |
| [31] | Lampis, M.: Algorithmic meta-theorems for restrictions of treewidth. Algorithmica 64, 19-37 (2012). In: Proc. Eur. Sym. on Alg. (ESA), 549-560 (2010) · Zbl 1287.68078 |
| [32] | Lenstra, H.W.: 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 |
| [33] | Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. Oxford University Press, Oxford (2006) · Zbl 1095.68038 |
| [34] | Románek, M.: Parameterized algorithms for modular-width. Bachelor thesis, Masaryk University, Brno (2016). https://is.muni.cz/th/tobmd/Thesis.pdf |
| [35] | Tedder, M., Corneil, D., Habib, M., Paul, C.: Simpler linear-time modular decomposition via recursive factorizing permutations. In: Aceto, L., Damgård, I., Goldberg, L.A., Halldórsson, M.M., Ingólfsdóttir, A., Walukiewicz, I. (eds.) ICALP 2008. LNCS, vol. 5125, pp. 634-645. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-70575-8_52 · Zbl 1153.68410 · doi:10.1007/978-3-540-70575-8_52 |
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.
