On Fine-Grained Exact Computation in Regular Graphs
share
We show that there is no subexponential time algorithm for computing the exact solution of the maximum independent set problem in d-regular graphs, for any constant d>2, unless ETH fails. We also discuss the extensions of our construction to other problems and other classes of graphs, including 5-regular planar graphs.
READ FULL TEXT