Ruling out FPT algorithms for weighted coloring on forests

DOI10.1016/j.tcs.2018.03.013zbMath1391.68045arXiv1703.09726MaRDI QIDQ5916046

Ignasi Sau, Julio Araujo, Julien Baste

Publication date: 17 May 2018

Published in: Electronic Notes in Discrete Mathematics, Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

parameterized complexity; forests; weighted coloring; \(\mathsf{W}[1\)-hardness]; max-coloring; \(\mathsf{W[1}\)-hardness]

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

05C15: Coloring of graphs and hypergraphs

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

05C85: Graph algorithms (graph-theoretic aspects)

05C22: Signed and weighted graphs