Graph colouring is hard for algorithms based on Hilbert's Nullstellensatz and Gröbner bases
From MaRDI portal
Publication:5111132
DOI10.4230/LIPICS.CCC.2017.2zbMATH Open1440.68105MaRDI QIDQ5111132FDOQ5111132
Authors: Massimo Lauria, Jakob Nordstrom 
Publication date: 26 May 2020
Recommendations
- A general approach to deriving the \(g\)-good-neighbor conditional diagnosability of interconnection networks
- Graph-coloring ideals: Nullstellensatz certificates, Gröbner bases for chordal graphs, and hardness of Gröbner bases
- Expressing combinatorial problems by systems of polynomial equations and Hilbert's Nullstellensatz
- Hilbert's Nullstellensatz and an Algorithm for Proving Combinatorial Infeasibility
- Computing infeasibility certificates for combinatorial problems through Hilbert's Nullstellensatz
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) (13P10) Coloring of graphs and hypergraphs (05C15) Complexity of proofs (03F20)
Cited In (11)
- Proof Complexity Meets Algebra
- Graphs with large girth and chromatic number are hard for Nullstellensatz
- Limitations of algebraic approaches to graph isomorphism testing
- Graph-coloring ideals: Nullstellensatz certificates, Gröbner bases for chordal graphs, and hardness of Gröbner bases
- A general approach to deriving the \(g\)-good-neighbor conditional diagnosability of interconnection networks
- On vanishing sums of roots of unity in polynomial calculus and sum-of-squares
- Proof complexity and beyond. Abstracts from the workshop held March 24--29, 2024
- Low degree Nullstellensatz certificates for 3-colorability
- Hilbert's Nullstellensatz and an Algorithm for Proving Combinatorial Infeasibility
- Computing infeasibility certificates for combinatorial problems through Hilbert's Nullstellensatz
- Expressing combinatorial problems by systems of polynomial equations and Hilbert's Nullstellensatz
Uses Software
This page was built for publication: Graph colouring is hard for algorithms based on Hilbert's Nullstellensatz and Gröbner bases
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5111132)
