2026-10-01T23:07:39Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24950 2026-09-23T23:22:37Z ddc:004 open_access

Parameterized Reunion with Achromatic Number Jana, Satyabrata Saha, Souvik Saurabh, Saket Upasana, Anannya Achromatic number Coloring Fixed-parameter tractability Kernelization Lower bound W-hardness In this paper, we study the Achromatic Number problem. Given a graph G and an integer k, the task is to determine whether there exists a proper coloring of G, using at least k colors, in which every pair of distinct colors appears on the endpoints of some edge. It was established early on that the problem is fixed-parameter tractable (FPT)- even before the formal development of parameterized complexity. In fact, Farber, Hahn, Hell, and Miller [JCTB, 1986] devised an algorithm with a running time of 𝒪(f(k) ⋅ |E(G)|). Although the exact form of f(k) was not specified, it appears to be at least doubly exponential in k. In our work, we first present an algorithm with an explicit dependence on k, and then introduce another algorithm that is parameterized by the vertex cover number of the graph. More formally, we show the following. - Achromatic Number is solvable in time 2^𝒪(k⁵)+𝒪(|E(G)|). - Achromatic Number admits a polynomial kernel when the input is restricted to a d-degenerate graph and a more efficient kernel on trees. - We also study the parameterized complexity of the problem with respect to Vertex Cover and show that it admits an FPT algorithm running in time 2^𝒪(𝓁²) ⋅ n^𝒪(1), where 𝓁 is the size of a vertex cover. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Satyabrata Jana and Souvik Saha and Saket Saurabh and Anannya Upasana 2025 Is Part Of LIPIcs, Volume 359, 36th International Symposium on Algorithms and Computation (ISAAC 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2025.42 urn:nbn:de:0030-drops-249502 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2025.42 eng https://creativecommons.org/licenses/by/4.0/legalcode