|
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
|
|
Weitere URL:
|
https://www.issac-conference.org/2015/Slides/Rolni...
|
|
Dokumenttyp:
|
Konferenzveröffentlichung
|
|
Erscheinungsjahr:
|
2015
|
|
Buchtitel:
|
ISSAC '15 : proceedings of the 2015 ACM International Symposium on Symbolic and Algebraic Computation : July 6-9, 2015, Bath, United Kingdom
|
|
Seitenbereich:
|
133-140
|
|
Veranstaltungstitel:
|
40th ISSAC '15
|
|
Veranstaltungsort:
|
Bath, UK
|
|
Veranstaltungsdatum:
|
06.-09.07.2015
|
|
Herausgeber:
|
Robertz, Daniel
|
|
Ort der Veröffentlichung:
|
New York, NY
|
|
Verlag:
|
ACM
|
|
ISBN:
|
978-1-4503-3881-3 , 1-4503-3881-X , 978-1-4503-3435-8
|
|
Sprache der Veröffentlichung:
|
Englisch
|
|
Einrichtung:
|
Außerfakultäre Einrichtungen > Institut für Enterprise Systems (InES)
|
|
Fachgebiet:
|
510 Mathematik
|
|
Freie Schlagwörter (Englisch):
|
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. |
 Suche Autoren 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
Sie haben einen Fehler gefunden? Teilen Sie uns Ihren Korrekturwunsch bitte hier mit: E-Mail
Actions (login required)
 |
Eintrag anzeigen |
|
