Graph coloring ideals : Nullstellensatz certificates, Gröbner bases for chordal graphs, and hardness of Gröbner bases


De Loera, Jesús A. ; Margulies, Susan ; Pernpeintner, Michael ; Riedl, Eric ; Rolnick, David ; Spencer, Gwen ; Stasi, Despina ; Swenson, Jon


DOI: https://doi.org/10.1145/2755996.2756639
URL: http://doi.acm.org/10.1145/2755996.2756639
Additional URL: https://www.issac-conference.org/2015/Slides/Rolni...
Document Type: Conference or workshop publication
Year of publication: 2015
Book title: ISSAC '15 : proceedings of the 2015 ACM International Symposium on Symbolic and Algebraic Computation : July 6-9, 2015, Bath, United Kingdom
Page range: 133-140
Conference title: 40th ISSAC '15
Location of the conference venue: Bath, UK
Date of the conference: 06.-09.07.2015
Author/Publisher of the book
(only the first ones mentioned)
:
Robertz, Daniel
Place of publication: New York, NY
Publishing house: ACM
ISBN: 978-1-4503-3881-3 , 1-4503-3881-X , 978-1-4503-3435-8
Publication language: English
Institution: Außerfakultäre Einrichtungen > Institut für Enterprise Systems (InES)
Subject: 510 Mathematics
Keywords (English): coloring ideal , graph coloring , groebner basis , inapproximability , infeasibility certificate , nullstellensatz
Abstract: We consider a well-known family of polynomial ideals encoding the problem of graph k-colorability. Our paper describes how the inherent combinatorial structure of the ideals implies several interesting algebraic properties. Specifically, we provide lower bounds on the difficulty of computing Gröbner bases and Nullstellensatz certificates for the coloring ideals of general graphs. We revisit the fact that computing a Gröbner basis is NP-hard and prove a robust notion of hardness derived from the inapproximability of coloring problems. For chordal graphs, however, we explicitly describe a Gröbner basis for the coloring ideal and provide a polynomial-time algorithm to construct it.

Dieser Datensatz wurde nicht während einer Tätigkeit an der Universität Mannheim veröffentlicht, dies ist eine Externe Publikation.




+ Citation Example and Export

De Loera, Jesús A. ; Margulies, Susan ; Pernpeintner, Michael ORCID: 0000-0001-6939-1028 ; Riedl, Eric ; Rolnick, David ; Spencer, Gwen ; Stasi, Despina ; Swenson, Jon Graph coloring ideals : Nullstellensatz certificates, Gröbner bases for chordal graphs, and hardness of Gröbner bases. Robertz, Daniel 133-140 In: ISSAC '15 : proceedings of the 2015 ACM International Symposium on Symbolic and Algebraic Computation : July 6-9, 2015, Bath, United Kingdom (2015) New York, NY 40th ISSAC '15 (Bath, UK) [Conference or workshop publication]


+ Search Authors in

+ Page Views

Hits per month over past year

Detailed information



You have found an error? Please let us know about your desired correction here: E-Mail


Actions (login required)

Show item Show item