Fast Algorithms for Max Independent Set in Graphs of Small Average Degree
| dc.creator | Bourgeois, Nicolas | |
| dc.creator | Escoffier, Bruno | |
| dc.creator | Paschos, Vangelis Th. | |
| dc.creator | van Rooij, Johan M. M | |
| dc.date | 2009-01-12 | |
| dc.date.accessioned | 2026-07-07T12:28:25Z | |
| dc.date.available | 2026-07-07T12:28:25Z | |
| dc.description | Max Independent Set (MIS) is a paradigmatic problem in theoretical computer science and numerous studies tackle its resolution by exact algorithms with non-trivial worst-case complexity. The best such complexity is, to our knowledge, the $O^*(1.1889^n)$ algorithm claimed by J.M. Robson (T.R. 1251-01, LaBRI, Univ. Bordeaux I, 2001) in his unpublished technical report. We also quote the $O^*(1.2210^n)$ algorithm by Fomin and al. (in Proc. SODA'06, pages 18-25, 2006), that is the best published result about MIS. In this paper we settle MIS in (connected) graphs with "small" average degree, more precisely with average degree at most 3, 4, 5 and 6. Dealing with graphs of average degree at most 3, the best bound known is the recent $O^*(1.0977^n)$ bound by N. Bourgeois and al. in Proc. IWPEC'08, pages 55-65, 2008). Here we improve this result down to $O^*(1.0854^n)$ by proposing finer and more powerful reduction rules. We then propose a generic method showing how improvement of the worst-case complexity for MIS in graphs of average degree $d$ entails improvement of it in any graph of average degree greater than $d$ and, based upon it, we tackle MIS in graphs of average degree 4, 5 and 6. For MIS in graphs with average degree 4, we provide an upper complexity bound of $O^*(1.1571^n)$ that outperforms the best known bound of $O^*(1.1713^n)$ by R. Beigel (Proc. SODA'99, pages 856-857, 1999). For MIS in graphs of average degree at most 5 and 6, we provide bounds of $O^*(1.1969^n)$ and $O^*(1.2149^n)$, respectively, that improve upon the corresponding bounds of $O^*(1.2023^n)$ and $O^*(1.2172^n)$ in graphs of maximum degree 5 and 6 by (Fomin et al., 2006). | |
| dc.identifier | https://arxiv.org/abs/0901.1563 | |
| dc.identifier | http://arxiv.org/abs/0901.1563 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/215535 | |
| dc.subject | Discrete Mathematics | |
| dc.subject | Data Structures and Algorithms | |
| dc.title | Fast Algorithms for Max Independent Set in Graphs of Small Average Degree | |
| dc.type | text |