Parameterized pre-coloring extension and list coloring problems

DOI10.1137/20M1323369MaRDI QIDQ5857010zbMATH OpenOpenAlexFDO

Authors G. Gutin, Diptapriyo Majumdar, Sebastian Ordyniak, Magnus Wahlström

Publication date 30 March 2021

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1907.12061

zbMATH Keywords

graph coloringkernelizationlist coloringparameterized complexity

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Parameterized complexity, tractability and kernelization (68Q27) Graph theory (including graph drawing) in computer science (68R10) Nonnumerical algorithms (68W05) Randomized algorithms (68W20)

Abstract: 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 $vinV(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 $lambd{a}_P:XightarrowQ$ for $XsubseteqV(G),$ decide whether $lambd{a}_P$ can be extended to a proper coloring of $G$ using only colors from $Q.$ For Problem 1 we design an $O^{\ast }(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 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 $vinV(G),$ decide whether there is a proper list coloring for $G.$ We obtain a kernel with $O(k^2)$ vertices and colors and a compression to a variation of the problem with $O(k)$ vertices and $O(k^2)$ colors.

Recommendations

• Fixed-parameter tractability of \((n-k)\) list coloring
• Fixed-parameter tractability of (n-k) list coloring
• List-coloring -- parameterizing from triviality
• Some (in)tractable parameterizations of coloring and list-coloring
• Parameterized and Exact Computation

Cites work

• A survey on the computational complexity of coloring graphs with forbidden subgraphs
• Abusing the Tutte matrix: an algebraic instance compression for the K-set-cycle problem
• Closing complexity gaps for coloring problems on \(H\)-free graphs
• Coloring graphs with forbidden induced subgraphs
• Constrained multilinear detection and generalized graph motifs
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• Fixed-parameter tractability of \((n-k)\) list coloring
• Fundamentals of parameterized complexity
• Graph colorings with local constraints -- a survey
• Graph theory
• Graph-Theoretic Concepts in Computer Science
• scientific article; zbMATH DE number 3651744 (Why is no real title available?)
• scientific article; zbMATH DE number 3503283 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 821271 (Why is no real title available?)
• Improved bounds on Bell numbers and on moments of sums of random variables
• Improved upper bounds for vertex cover
• Kernel bounds for path and cycle problems
• Kernelization lower bounds through colors and IDs
• Kernelization. Theory of parameterized preprocessing
• Narrow sieves for parameterized paths and packings
• On problems as hard as CNF-SAT
• Open problems on graph coloring for special graph classes
• Parameterized algorithms
• Parameterized complexity of vertex colouring
• Saving colors and max coloring: some fixed-parameter tractability results
• Set partitioning via inclusion-exclusion
• Solving MAX-\(r\)-SAT above a tight lower bound
• Some (in)tractable parameterizations of coloring and list-coloring
• Sparsification upper and lower bounds for graph problems and not-all-equal SAT
• The set cover conjecture and subgraph isomorphism with a tree pattern
• Triangular Factorization and Inversion by Fast Matrix Multiplication
• Vertex colouring and forbidden subgraphs -- a survey

Cited in

(12)

• Parameterized complexity of the list coloring reconfiguration problem with graph parameters
• Parameterized complexity of list coloring and max coloring
• Structural parameterizations of budgeted graph coloring
• On structural parameterizations of star coloring
• Dominator coloring and CD coloring in almost cluster graphs
• Multicut problems in embedded graphs: the dependency of complexity on the demand pattern
• Determinantal sieving
• Further parameterized results on weak Grundy coloring
• Dominator coloring and CD coloring in almost cluster graphs
• Graph coloring below guarantees via co-triangle packing
• Precoloring extension with demands on paths
• Parameterizing role coloring on forests

This page was built for publication: Parameterized pre-coloring extension and list coloring problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5857010)