Tight lower bounds for the complexity of multicoloring

DOI10.4230/LIPICS.ESA.2017.18MaRDI QIDQ5111704zbMATHOpenAlexFDO

Authors Marthe Bonamy, Łukasz Kowalik, Michał Pilipczuk, Arkadiusz Socała, Marcin Wrochna

Publication date 27 May 2020

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

zbMATH Keywords

Kneser graphhomomorphismmulticoloringETH lower bound

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Coloring of graphs and hypergraphs (05C15)

Abstract: In the multicoloring problem, also known as ($a$:$b$)-coloring or $b$-fold coloring, we are given a graph G and a set of $a$ colors, and the task is to assign a subset of $b$ colors to each vertex of G so that adjacent vertices receive disjoint color subsets. This natural generalization of the classic coloring problem (the $b=1$ case) is equivalent to finding a homomorphism to the Kneser graph $K{G}_{a,b}$, and gives relaxations approaching the fractional chromatic number. We study the complexity of determining whether a graph has an ($a$:$b$)-coloring. Our main result is that this problem does not admit an algorithm with running time $f(b)cdot{2}^{o(logb)cdotn}$, for any computable $f(b)$, unless the Exponential Time Hypothesis (ETH) fails. A $(b+1{)}^{n}cdotextpoly(n)$-time algorithm due to Nederlof [2008] shows that this is tight. A direct corollary of our result is that the graph homomorphism problem does not admit a $2^{O(n+h)}$ algorithm unless ETH fails, even if the target graph is required to be a Kneser graph. This refines the understanding given by the recent lower bound of Cygan et al. [SODA 2016]. The crucial ingredient in our hardness reduction is the usage of detecting matrices of Lindstr"om [Canad. Math. Bull., 1965], which is a combinatorial tool that, to the best of our knowledge, has not yet been used for proving complexity lower bounds. As a side result, we prove that the running time of the algorithms of Abasi et al. [MFCS 2014] and of Gabizon et al. [ESA 2015] for the r-monomial detection problem are optimal under ETH.

Recommendations

• Tight lower bounds for the complexity of multicoloring
• Lower bounds for the graph homomorphism problem
• Finer tight bounds for coloring on clique-width
• Finer tight bounds for coloring on clique-width
• Tight lower bounds for list edge coloring

Cites work

• scientific article; zbMATH DE number 5776838 (Why is no real title available?)
• scientific article; zbMATH DE number 1929966 (Why is no real title available?)
• A simplified NP-complete satisfiability problem
• A technique for multicoloring triangle-free hexagonal graphs
• Approximation algorithms for multicoloring planar graphs and powers of square and triangular meshes
• Channel assignment and multicolouring of the induced subgraphs of the triangular lattice
• Channel assignment and weighted coloring
• Dynamic programming based algorithms for set multicover and multiset multicover problems
• Exact algorithms for graph homomorphisms
• Fast algorithms for parameterized problems with relaxed disjointness constraints
• Fast polynomial-space algorithms using inclusion-exclusion. Improving on Steiner tree and related problems
• Fractional colorings with large denominators
• Introduction to algorithms.
• Kneser's conjecture, chromatic number, and homotopy
• Local Multicoloring Algorithms: Computing a Nearly-Optimal TDMA Schedule in Constant Time
• Mastermind
• Mathematical Foundations of Computer Science 2004
• Multicoloring and Mycielski construction
• Multicoloring trees.
• New plain-exponential time classes for graph homomorphism
• On a Combinatorial Problem in Number Theory
• On cliques in graphs
• On r-Simple k-Path
• On the complexity of H-coloring
• On the complexity of \(k\)-SAT
• Online Multi-Coloring with Advice
• Optimal reconstruction of graphs under the additive model
• Parameterized algorithms
• Set partitioning via inclusion-exclusion
• The ellipsoid method and its consequences in combinatorial optimization
• Tight Bounds for Graph Homomorphism and Subgraph Isomorphism
• Tight lower bounds for the complexity of multicoloring
• Two Results Concerning Multicoloring
• Which problems have strongly exponential complexity?

Cited in

(12)

• Tight Lower and Upper Bounds for the Complexity of Canonical Colour Refinement
• Graph-Theoretic Concepts in Computer Science
• Lower bounds on strip discrepancy for nonatomic colorings
• Tight complexity lower bounds for integer linear programming with few constraints
• Tight lower bounds for the complexity of multicoloring
• Tight lower bounds for the complexity of multicoloring
• On low rank-width colorings
• Finer tight bounds for coloring on clique-width
• Finer tight bounds for coloring on clique-width
• scientific article; zbMATH DE number 1114021 (Why is no real title available?)
• Tight lower and upper bounds for the complexity of canonical colour refinement
• Optimal bounds for the colored Tverberg problem

This page was built for publication: Tight lower bounds for the complexity of multicoloring

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