2019/07/28 by Gutin, Gregory, Majumdar, Diptapriyo, Ordyniak, Sebastian +1 · 2 citations
#Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1907.12061
Golovach, Paulusma and Song (Inf. Comput. 2014) asked to determine the parameterized complexity of the following problems parameterized by k: (1) Given a graph G, a clique modulator D (a clique modulator is a set of vertices, whose removal results in a clique) of size k for G, and a list L(v) of colors for every v∈ V(G), decide whether G has a proper list coloring; (2) Given a graph G, a clique modulator D of size k for G, and a pre-coloring λP: X → Q for X ⊆ V(G), decide whether λP can be extended to a proper coloring of G using only colors from Q. For Problem 1 we design an O^*(2k)-time randomized algorithm and for Problem 2 we obtain a kernel with at most 3k vertices. Banik et al. (IWOCA 2019) proved the the following problem is fixed-parameter tractable and asked whether it admits a polynomial kernel: Given a graph G, an integer k, and a list L(v) of exactly n-k colors for every v ∈ V(G), decide whether there is a proper list coloring for G. We obtain a kernel with O(k2) vertices and colors and a compression to a variation of the problem with O(k) vertices and O(k2) colors.