Parameterized Complexity of Maximum Edge Colorable Subgraph
share
A graph H is p-edge colorable if there is a coloring ψ: E(H) →{1,2,…,p}, such that for distinct uv, vw ∈ E(H), we have ψ(uv) ≠ψ(vw). The Maximum Edge-Colorable Subgraph problem takes as input a graph G and integers l and p, and the objective is to find a subgraph H of G and a p-edge-coloring of H, such that |E(H)| ≥ l. We study the above problem from the viewpoint of Parameterized Complexity. We obtain algorithms when parameterized by: (1) the vertex cover number of G, by using Integer Linear Programming, and (2) l, a randomized algorithm via a reduction to Rainbow Matching, and a deterministic algorithm by using color coding, and divide and color. With respect to the parameters p+k, where k is one of the following: (1) the solution size, l, (2) the vertex cover number of G, and (3) l - (G), where (G) is the size of a maximum matching in G; we show that the (decision version of the) problem admits a kernel with 𝒪(k · p) vertices. Furthermore, we show that there is no kernel of size 𝒪(k^1-ϵ· f(p)), for any ϵ > 0 and computable function f, unless ⊆.
READ FULL TEXT