2026-08-17T23:24:21Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:22220 2024-12-05T15:18:04Z ddc:004 open_access

Parameterized Algorithms and Hardness for the Maximum Edge q-Coloring Problem Mathew, Rogers Panolan, Fahad Seshikanth FPT algorithm Edge coloring Treewidth W[1]-hardness An edge q-coloring of a graph G is a coloring of its edges such that every vertex sees at most q colors on the edges incident on it. The size of an edge q-coloring is the total number of colors used in the coloring. Given a graph G and a positive integer t, the Maximum Edge q-Coloring problem is about whether G has an edge q-coloring of size t. Studies on this coloring problem were motivated by its application in the channel assignment problem in wireless networks. Goyal, Kamat, and Misra (MFCS 2013) studied Maximum Edge 2-Coloring from the perspective of parameterized complexity. Given a graph on n vertices, they considered the standard parameter t, the number of colors in an optimal edge 2-coloring, and the dual parameter 𝓁, where n-𝓁 is the number of colors in an optimal edge 2-coloring. They designed FPT algorithms for Maximum Edge 2-Coloring parameterized by t and 𝓁. In this paper, we revisit and study Maximum Edge 2-Coloring from the perspective of parameterized complexity and show the following results. 1) Let γ(G) denote the maximum matching size in a given graph G. It is easy to see that a maximum edge 2-coloring of G is of size at least γ(G). Goyal, Kamat, and Misra (MFCS 2013) had asked if there exists an FPT algorithm for Maximum Edge 2-Coloring parameterized by k, where k: = (size of a maximum edge 2-coloring of G) - γ(G). We show that Maximum Edge 2-Coloring parameterized by k is W[1] hard. 2) On the positive side, we show that there is an algorithm that, given a graph G on n vertices and a tree decomposition of width tw, runs in time 2^{O(qtw log {q tw})}n and outputs a maximum edge q-coloring of G. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Rogers Mathew and Fahad Panolan and Seshikanth 2024 Is Part Of LIPIcs, Volume 323, 44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2024.31 urn:nbn:de:0030-drops-222202 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2024.31 eng https://creativecommons.org/licenses/by/4.0/legalcode