Coloring Graphs Having Few Colorings Over Path Decompositions
(2016) 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016) In 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016) p.113 Abstract
 Lokshtanov, Marx, and Saurabh SODA 2011 proved that there is no (kepsilon)^pw(G)poly(n) time algorithm for deciding if an nvertex 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 kcolorable graphs having at most s proper kcolorings and... (More)
 Lokshtanov, Marx, and Saurabh SODA 2011 proved that there is no (kepsilon)^pw(G)poly(n) time algorithm for deciding if an nvertex 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 kcolorable graphs having at most s proper kcolorings and nonkcolorable graphs. We also show how to obtain a kcoloring 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 AlonTarsi 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 kcolorable, 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 nonzero value if the graph has few kcolorings. Yet every nonkcolorable graph gives a zero difference, so a random set of constraints stands a good chance of being useful for separating the two cases. (Less)
Please use this url to cite or link to this publication:
http://lup.lub.lu.se/record/ecd648ee506b43319d7e59cda13bb2bb
 author
 Björklund, Andreas ^{LU}
 organization
 publishing date
 2016
 type
 Chapter in Book/Report/Conference proceeding
 publication status
 published
 subject
 in
 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)
 pages
 1  13
 conference name
 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)
 external identifiers

 scopus:85012016505
 DOI
 10.4230/LIPIcs.SWAT.2016.13
 language
 English
 LU publication?
 yes
 id
 ecd648ee506b43319d7e59cda13bb2bb
 date added to LUP
 20160728 12:54:39
 date last changed
 20170226 04:40:12
@inproceedings{ecd648ee506b43319d7e59cda13bb2bb, abstract = {Lokshtanov, Marx, and Saurabh SODA 2011 proved that there is no (kepsilon)^pw(G)poly(n) time algorithm for deciding if an nvertex 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 kcolorable graphs having at most s proper kcolorings and nonkcolorable graphs. We also show how to obtain a kcoloring 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 AlonTarsi 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 kcolorable, 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 nonzero value if the graph has few kcolorings. Yet every nonkcolorable graph gives a zero difference, so a random set of constraints stands a good chance of being useful for separating the two cases. }, author = {Björklund, Andreas}, booktitle = {15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)}, language = {eng}, pages = {113}, title = {Coloring Graphs Having Few Colorings Over Path Decompositions}, url = {http://dx.doi.org/10.4230/LIPIcs.SWAT.2016.13}, year = {2016}, }