Space complexity of list H-colouring: a dichotomy

DOI10.1137/1.9781611973402.26MaRDI QIDQ5383985zbMATH OpenOpenAlexFDO

Authors László Egri, Benoît Larose, Arash Rafiey, Pavol Hell

Publication date 20 June 2019

Published in Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Abstract: The Dichotomy Conjecture for constraint satisfaction problems (CSPs) states that every CSP is in P or is NP-complete (Feder-Vardi, 1993). It has been verified for conservative problems (also known as list homomorphism problems) by A. Bulatov (2003). We augment this result by showing that for digraph templates H, every conservative CSP, denoted LHOM(H), is solvable in logspace or is hard for NL. More precisely, we introduce a digraph structure we call a circular N, and prove the following dichotomy: if H contains no circular N then LHOM(H) admits a logspace algorithm, and otherwise LHOM(H) is hard for NL. Our algorithm operates by reducing the lists in a complex manner based on a novel decomposition of an auxiliary digraph, combined with repeated applications of Reingold's algorithm for undirected reachability (2005). We also prove an algebraic version of this dichotomy: the digraphs without a circular N are precisely those that admit a finite chain of polymorphisms satisfying the Hagemann-Mitschke identities. This confirms a conjecture of Larose and Tesson (2007) for LHOM(H). Moreover, we show that the presence of a circular N can be decided in time polynomial in the size of H.

Recommendations

• A complexity trichotomy for approximately counting list H-colourings
• Descriptive complexity of list H-coloring problems in logspace: a refined dichotomy
• A Complexity Trichotomy for Approximately Counting List H -Colorings
• Complexity of list coloring problems with a fixed total number of colors
• Algorithmic complexity of list colorings
• Exploring the complexity boundary between coloring and list-coloring
• Exploring the complexity boundary between coloring and list-coloring
• Sparsification lower bounds for list \(H\)-coloring
• Publication:4934399
• On the complexity of a restricted list-coloring problem

Cited in

(13)

• On Maltsev digraphs
• Parameterized algorithms for min-max multiway cut and list digraph homomorphism
• Descriptive complexity of list H-coloring problems in logspace: a refined dichotomy
• A Complexity Trichotomy for Approximately Counting List H -Colorings
• Algebra and the complexity of digraph CSPs: a survey
• Constraint satisfaction with counting quantifiers
• The dichotomy of list homomorphisms for digraphs
• Exploring the complexity boundary between coloring and list-coloring
• Sparsification lower bounds for list \(H\)-coloring
• List colouring trees in logarithmic space
• Sparsification lower bounds for list H-coloring
• Complexity of the list homomorphism problem in hereditary graph classes
• List homomorphisms by deleting edges and vertices: tight complexity bounds for bounded-treewidth graphs

This page was built for publication: Space complexity of list H-colouring: a dichotomy

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