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

Additional URL:
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
Publisher: 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.

Metadata export


+ 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