An exact algorithm for maximum independent set in degree-5 graphs

详细信息    查看全文

• 作者：Mingyu Xiao^a ; ^{myxiao@gmail.com" class="auth_mail" title="E-mail the corresponding author} ; ^{myxiao@uestc.edu.cn" class="auth_mail" title="E-mail the corresponding author} ; Hiroshi Nagamochi^b ; ^{nag@amp.i.kyoto-u.ac.jp" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Exact algorithm ; Graph algorithm ; Maximum independent set ; Measure and Conquer ; Amortized analysis
• 刊名：Discrete Applied Mathematics
• 出版年：2016
• 出版时间：30 January 2016
• 年：2016
• 卷：199
• 期：Complete
• 页码：137-155
• 全文大小：842 K

文摘

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 a 1-s2.0-S0166218X14003102&_mathId=si8.gif&_user=111111111&_pii=S0166218X14003102&_rdoc=1&_issn=0166218X&md5=300158fcf7c663d3446e4f3110ed6e14" title="Click to view the MathML source">1.1736ⁿn^O(1)$\mathrm{<font\; color="red">1</font>.<font\; color="red">1</font>73}{6}^n{n}^{O\left(\mathrm{<font\; color="red">1</font>}\right)}$-time exact algorithm for the maximum independent set problem in an 1-s2.0-S0166218X14003102&_mathId=si403.gif&_user=111111111&_pii=S0166218X14003102&_rdoc=1&_issn=0166218X&md5=b70aeb0a7dd58115a8c0d7948b303ab5" title="Click to view the MathML source">n$n$-vertex graph with degree bounded by 10" class="mathmlsrc">1-s2.0-S0166218X14003102&_mathId=si10.gif&_user=111111111&_pii=S0166218X14003102&_rdoc=1&_issn=0166218X&md5=e42b30a401816b1b938e03be519a7376" title="Click to view the MathML source">5, improving the previous running time bound of 11" class="mathmlsrc">1-s2.0-S0166218X14003102&_mathId=si11.gif&_user=111111111&_pii=S0166218X14003102&_rdoc=1&_issn=0166218X&md5=2d9219c440557804876ff0188a269cdf" title="Click to view the MathML source">1.1895ⁿn^O(1). In our algorithm, we show that the graph after applying reduction rules always has a good local structure branching on which will effectively reduce the instance. Based on this, we obtain an improved algorithm without introducing a large number of branching rules.