Tight lower bounds for the complexity of multicoloring

DOI10.4230/LIPICS.ESA.2017.18zbMATH Open1434.68186arXiv1607.03432OpenAlexW4391089961MaRDI QIDQ5111704FDOQ5111704

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

Publication date: 27 May 2020

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.

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

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

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)

Cites Work

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

Cited In (12)

• Graph-Theoretic Concepts in Computer Science
• 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
• Tight lower and upper bounds for the complexity of canonical colour refinement
• Lower bounds on strip discrepancy for nonatomic colorings
• Tight Lower and Upper Bounds for the Complexity of Canonical Colour Refinement
• Tight lower bounds for the complexity of multicoloring
• Optimal bounds for the colored Tverberg problem
• Title not available (Why is that?)
• Tight complexity lower bounds for integer linear programming with few constraints

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)