|
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
|
|
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. |
 Search Authors in
BASE:
De Loera, Jesús A.
;
Margulies, Susan
;
Pernpeintner, Michael
;
Riedl, Eric
;
Rolnick, David
;
Spencer, Gwen
;
Stasi, Despina
;
Swenson, Jon
Google Scholar:
De Loera, Jesús A.
;
Margulies, Susan
;
Pernpeintner, Michael
;
Riedl, Eric
;
Rolnick, David
;
Spencer, Gwen
;
Stasi, Despina
;
Swenson, Jon
ORCID:
De Loera, Jesús A., Margulies, Susan, Pernpeintner, Michael  ORCID: https://orcid.org/0000-0001-6939-1028, Riedl, Eric, Rolnick, David, Spencer, Gwen, Stasi, Despina and Swenson, Jon
You have found an error? Please let us know about your desired correction here: E-Mail
Actions (login required)
 |
Show item |
|
