id:"swepub:oai:lup.lub.lu.se:ecd648ee-506b-4331-9d7e-59cda13bb2bb"
Search: id:"swepub:oai:lup.lub.lu.se:ecd648ee-506b-4331-9d7e-59cda13bb2bb" > Coloring Graphs Hav...
- 1 of 1
- Previous record
- Next record
- To hitlist
- Björklund, AndreasLund University,Lunds universitet,Institutionen för datavetenskap,Institutioner vid LTH,Lunds Tekniska Högskola,Department of Computer Science,Departments at LTH,Faculty of Engineering, LTH (author)
Coloring Graphs Having Few Colorings Over Path Decompositions
- Article/chapterEnglish2016
Publisher, publication year, extent ...
- 2016
Numbers
- LIBRIS-ID:oai:lup.lub.lu.se:ecd648ee-506b-4331-9d7e-59cda13bb2bb
- https://lup.lub.lu.se/record/ecd648ee-506b-4331-9d7e-59cda13bb2bbURI
- https://doi.org/10.4230/LIPIcs.SWAT.2016.13DOI
Supplementary language notes
- Language:English
- Summary in:English
Part of subdatabase
- SwePubSwePub
Classification
Notes
- Lokshtanov, Marx, and Saurabh SODA 2011 proved that there is no (k-epsilon)^pw(G)poly(n) time algorithm for deciding if an n-vertex graph G with pathwidth pw admits a proper vertex coloring with k colors unless the Strong Exponential Time Hypothesis (SETH) is false, for any constant epsilon>0. We show here that nevertheless, when k>lfloor Delta/2 rfloor + 1, where Delta is the maximum degree in the graph G, there is a better algorithm, at least when there are few colorings. We present a Monte Carlo algorithm that given a graph G along with a path decomposition of G with pathwidth pw(G) runs in (lfloor Delta/2 rfloor + 1)^pw(G)poly(n)s time, that distinguishes between k-colorable graphs having at most s proper k-colorings and non-k-colorable graphs. We also show how to obtain a k-coloring in the same asymptotic running time. Our algorithm avoids violating SETH for one since high degree vertices still cost too much and the mentioned hardness construction uses a lot of them. We exploit a new variation of the famous Alon--Tarsi theorem that has an algorithmic advantage over the original form. The original theorem shows a graph has an orientation with outdegree less than k at every vertex, with a different number of odd and even Eulerian subgraphs only if the graph is k-colorable, but there is no known way of efficiently finding such an orientation. Our new form shows that if we instead count another difference of even and odd subgraphs meeting modular degree constraints at every vertex picked uniformly at random, we have a fair chance of getting a non-zero value if the graph has few k-colorings. Yet every non-k-colorable graph gives a zero difference, so a random set of constraints stands a good chance of being useful for separating the two cases.
Subject headings and genre
Added entries (persons, corporate bodies, meetings, titles ...)
- Institutionen för datavetenskapInstitutioner vid LTH (creator_code:org_t)
Related titles
- In:15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016), s. 1-139783959770118
Internet link
Find in a library
- 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016) (Search for host publication in LIBRIS)
To the university's database
- 1 of 1
- Previous record
- Next record
- To hitlist
Find more in SwePub
- By the author/editor
- Björklund, Andre ...
- About the subject
-
- NATURAL SCIENCES
- NATURAL SCIENCES
- and Computer and Inf ...
- and Computer Science ...
- Articles in the publication
- 15th Scandinavia ...
- By the university
- Lund University
Search outside SwePub
- Extend your search to:
- Google Book Search
- Google Scholar
Kungliga biblioteket hanterar dina personuppgifter i enlighet med EU:s dataskyddsförordning (2018), GDPR. Läs mer om hur det funkar här.
Så här hanterar KB dina uppgifter vid användning av denna tjänst.
- Copyright © LIBRIS - National Library Systems
- LIBRIS.kb.se
