Department of Applied Mathematics & Physics, Kyoto University

Technical Report 2013-003 (Apil 11, 2013)

An Exact Algorithm for Maximum Independent Set in Degree-5 Graphs
by Mingyu Xiao and Hiroshi Nagamochi

pdf File

The maximum independent set problem is a basic NP-hard problem and has been extensively studied in exact algorithms. The maximum independent set problems in low-degree graphs are also important and may be bottlenecks of the problem in general graphs. In this paper, we present an $O^*(1.1737^n)$-time exact algorithm for the maximum independent set problem in an $n$-vertex graph with degree bounded by $5$, improving the previous running time bound of $O^*(1.1895^n)$. In our algorithm, we introduce an effective divide-and-conquer procedure to deal with vertex cuts of size at most two in graphs, and design branching rules on some special structure of triconnected graphs of maximum degree 5. These result in an improved algorithm without introducing a large number of branching rules.