Faster graph coloring in polynomial space

DOI10.1007/978-3-319-62389-4_31MaRDI QIDQ5920158zbMATH OpenOpenAlexFDO

Authors Serge Gaspers, Edward J. Lee

Publication date 23 October 2017

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1607.06201

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Abstract: We present a polynomial-space algorithm that computes the number independent sets of any input graph in time $O(1.1387^n)$ for graphs with maximum degree 3 and in time $O(1.2355^n)$ for general graphs, where n is the number of vertices. Together with the inclusion-exclusion approach of Bj"orklund, Husfeldt, and Koivisto [SIAM J. Comput. 2009], this leads to a faster polynomial-space algorithm for the graph coloring problem with running time $O(2.2355^n)$. As a byproduct, we also obtain an exponential-space $O(1.2330^n)$ time algorithm for counting independent sets. Our main algorithm counts independent sets in graphs with maximum degree 3 and no vertex with three neighbors of degree 3. This polynomial-space algorithm is analyzed using the recently introduced Separate, Measure and Conquer approach [Gaspers & Sorkin, ICALP 2015]. Using Wahlstr"om's compound measure approach, this improvement in running time for small degree graphs is then bootstrapped to larger degrees, giving the improvement for general graphs. Combining both approaches leads to some inflexibility in choosing vertices to branch on for the small-degree cases, which we counter by structural graph properties.

Recommendations

• Faster graph coloring in polynomial space
• A polyhedral approach for graph coloring
• Polynomial approximation and graph-coloring
• Polynomial graph-colorings
• Polynomial graph-colorings
• Polynomial-time approximation algorithms for the coloring problem in some cases
• Fast algorithms for edge-coloring planar graphs
• Graph coloring in linear time
• scientific article; zbMATH DE number 889953
• scientific article; zbMATH DE number 4089573

Cited in

(10)

• Designing deterministic polynomial-space algorithms by color-coding multivariate polynomials
• Faster exponential-time algorithms for approximately counting independent sets
• Small Maximal Independent Sets and Faster Exact Graph Coloring
• A procedure for the strategic planning of locations, capacities and districting of jails: application to Chile
• Families with infants: speeding up algorithms for NP-hard problems using FFT
• NP-completeness results for partitioning a graph into total dominating sets
• Faster graph coloring in polynomial space
• Exponential-time quantum algorithms for graph coloring problems
• Approximately counting independent sets in bipartite graphs via graph containers
• Enumerating maximal independent sets with applications to graph colouring.

This page was built for publication: Faster graph coloring in polynomial space

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5920158)