Parameterized Pre-coloring Extension and List Coloring Problems
| Autor: | Gregory Gutin, Magnus Wahlström, Sebastian Ordyniak, Diptapriyo Majumdar |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2019 |
| Předmět: |
FOS: Computer and information sciences
Discrete Mathematics (cs.DM) General Mathematics Parameterized complexity 0102 computer and information sciences List Coloring Computational Complexity (cs.CC) 01 natural sciences Combinatorics Polynomial kernel Computer Science - Data Structures and Algorithms Data Structures and Algorithms (cs.DS) Graph coloring Mathematics List coloring Discrete mathematics Parameterized Algorithms W-hardness Graph Randomized algorithm Computer Science - Computational Complexity 010201 computation theory & mathematics Kernelization Graph Coloring Computer Science - Discrete Mathematics |
| ISSN: | 0895-4801 |
| Popis: | 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*(2^k)-time randomized algorithm and for Problem 2 we obtain a kernel with at most 3k vertices. Banik et al. (IWOCA 2019) proved 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(k²) vertices and colors and a compression to a variation of the problem with O(k) vertices and O(k²) colors. LIPIcs, Vol. 154, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020), pages 19:1-19:18 |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|