Structural Parameterizations for Equitable Coloring: Complexity, FPT Algorithms, and Kernelization
Tóm tắt
An n-vertex graph is equitably k-colorable if there is a proper coloring of its vertices such that each color is used either
$$\left\lfloor n/k\right\rfloor $$
or
$$\left\lceil n/k\right\rceil $$
times. While classic Vertex Coloring is fixed parameter tractable under well established parameters such as pathwidth and feedback vertex set, equitable coloring is W[1]-hard. We present an extensive study of structural parameterizations of Equitable Coloring, tackling both tractability and kernelization questions. We begin by showing that the problem is fixed parameter tractable when parameterized by distance to cluster or by distance to co-cluster—improving on the FPT algorithm of Fiala et al. (Theor Comput Sci 412(23):2513–2523, 2011) parameterized by vertex cover—and also when parameterized by distance to disjoint paths of bounded length. To justify the latter result, we adapt a proof of Fellows et al. (Inf Comput 209(2):143–153, 2011) to show that Equitable Coloring is W[1]-hard when simultaneously parameterized by distance to disjoint paths and number of colors. In terms of kernelization, on the positive side we present a linear kernel for the distance to clique parameter and a cubic kernel when parameterized by the maximum leaf number; on the other hand, we show that, unlike Vertex Coloring, Equitable Coloring does not admit a polynomial kernel when jointly parameterized by vertex cover and number of colors, unless
$$\textsf {NP}\subseteq \textsf {coNP}/\textsf {poly}$$
. We also revisit the literature and derive other results on the parameterized complexity of the problem through minor reductions or other observations.
Tài liệu tham khảo
Baker, B.S., Coffman, E.G.: Mutual exclusion scheduling. Theor. Comput. Sci. 162(2), 225–243 (1996)
Bodlaender, H.L., Fomin, F.V.: Equitable colorings of bounded treewidth graphs. Theor. Comput. Sci. 349(1), 22–30 (2005)
Bodlaender, H.L., Jansen, B.M.P., Kratsch, S.: Cross-composition: a new technique for kernelization lower bounds. In: Proceedings of the 28th International Symposium on Theoretical Aspects of Computer Science (STACS), LIPIcs, vol. 9, pp. 165–176 (2011)
Bodlaender, H.L., Jansen, K.: Restrictions of graph partition problems. Part I. Theor. Comput. Sci. 148(1), 93–109 (1995)
Bondy, J.A., Murty, U.S.R.: Graph Theory with Applications, vol. 290. Macmillan, London (1976)
Boral, A., Cygan, M., Kociumaka, T., Pilipczuk, M.: Fast branching algorithm for cluster vertex deletion (2013). CoRR, arXiv:1306.3877
Cai, L.: Parameterized complexity of vertex colouring. Discret. Appl. Math. 127(3), 415–429 (2003)
Cappelle, M.R., Gomes, G., Santos, V.F.D.: Parameterized algorithms for locating-dominating sets (2020)
Chen, B.-L., Ko, M.-T., Lih, K.-W.: Equitable and \(m\)-bounded coloring of split graphs, pp. 1–5. Springer, Berlin (1996)
Cordasco, G., Gargano, L., Rescigno, A.A.: Iterated type partitions. In: Gąsieniec, L., Klasing, R., Radzik, T. (eds.) Combinatorial Algorithms, pp. 195–210. Springer, Cham (2020)
Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 3rd edn. The MIT Press (2009)
Cygan, M., Fomin, F. V., Kowalik, Ł., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms, vol. 3. Springer (2015)
Edmonds, J.: Paths, trees, and flowers. Can. J. Math. 17, 449–467 (1965)
Enciso, R., Fellows, M.R., Guo, J., Kanj, I., Rosamond, F., Suchý, O.: What makes equitable connected partition easy. In: Chen, J., Fomin, F.V. (eds.) Parameterized and Exact Computation, pp. 122–133. Springer, Berlin (2009)
Estivill-Castro, V., Fellows, M., Langston, M., Rosamond, F.: FPT is P-Time Extremal Structure I (Fixed-parameter tractability is polynomial-time extremal structure theory), pp. 1–41. King’s College Publications (2005)
Fellows, M.R., Fomin, F.V., Lokshtanov, D., Rosamond, F., Saurabh, S., Szeider, S., Thomassen, C.: On the complexity of some colorful problems parameterized by treewidth. Inf. Comput. 209(2), 143–153 (2011)
Fiala, J., Golovach, P.A., Kratochvíl, J.: Parameterized complexity of coloring problems: treewidth versus vertex cover. Theor. Comput. Sci. 412(23), 2513–2523 (2011). (Theory and Applications of Models of Computation (TAMC 2009))
Ganian, R.: Improving vertex cover as a graph parameter. Discrete Math. Theor. Comput. Sci. 17(2) (2015)
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York (1979)
Gomes, G.C.M., Guedes, M.R., dos Santos, V.F.: Structural parameterizations for equitable coloring. In: Kohayakawa, Y., Miyazawa, F.K. (eds.) LATIN 2020: Theoretical Informatics, pp. 129–140. Springer, Cham (2020)
Gomes, G., Lima, C.V.G.C., Santos, V.F.D.: Parameterized Complexity of Equitable Coloring. Discrete Math. Theor. Comput. Sci. 21(1), ICGT 2018 (2019)
Hajnal, A., Szemerédi, E.: Proof of a conjecture of P. Erdos. Combin. Theory Appl. 2, 601–623 (1970)
Irani, S., Leung, V.: Scheduling with conflicts, and applications to traffic signal control. In: Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’96, pp. 85-94. Society for Industrial and Applied Mathematics (1996)
Jansen, B.M., Kratsch, S.: Data reduction for graph coloring problems. Inf. Comput. 231, 70–88 (2013). (Fundamentals of Computation Theory)
Jarvis, M., Zhou, B.: Bounded vertex coloring of trees. Discret. Math. 232(1–3), 145–151 (2001)
Kierstead, H.A., Kostochka, A.V., Mydlarz, M., Szemerédi, E.: A fast algorithm for equitable coloring. Combinatorica 30(2), 217–224 (2010)
Lenstra, H.W.: Integer programming with a fixed number of variables. Math. Oper. Res. 8(4), 538–548 (1983)
Lih, K.-W.: Equitable coloring of graphs. In: Handbook of Combinatorial Optimization, pp. 1199–1248. Springer (2013)
Meyer, W.: Equitable coloring. Am. Math. Mon. 80(8), 920–922 (1973)
Reddy, I.V.: Parameterized coloring problems on threshold graphs (2019)
Smith, B., Bjorstad, P., Gropp, W.: Domain Decomposition: Parallel Multilevel Methods for Elliptic Partial Differential Equations. Cambridge University Press (2004)
Sorge, M., Weller, M.: The graph parameter hierarchy. Unpublished manuscript (2019)