Abstract
The maximum independent set problem is one of the most important problems in theoretical analysis on time and space complexities of exact algorithms. Theoretical improvement on upper bounds on time complexity to solve this problem in low-degree graphs can lead to an improvement on that to the problem in general graphs. In this paper, we derive an upper bound \(O^*(1.1376^n)\) on the time complexity of a polynomial-space algorithm that solves the maximum independent set problem in an n-vertex graph with degree bounded by 4, improving all previous upper bounds on the time complexity of exact algorithms to this problem. Our algorithm is a branch-and-reduce algorithm and analyzed by using the measure-and-conquer method. To make an amortized analysis of the running time bound, we use an idea of “shift” to save some decrease of the measure from good branches to bad branches. Our algorithm first deals with small vertex cuts and vertices of degree \({\ge }5\), which may be created in our algorithm even if the input graph has maximum degree 4, then eliminates cycles of length 3 and 4 containing degree-4 vertices, and finally branches on degree-4 vertices. We invoke an exact algorithm for this problem in graphs with maximum degree 3 directly when the graph has no vertices of degree \({\ge }4\). Branching on degree-4 vertices on special local structures will be the bottleneck case, and we carefully design rules of choosing degree-4 vertices to branch on so that the resulting instances after branching decrease the measure effectively in the next step.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Notes
The notion of unconfined vertices is originally defined by Xiao and Nagamochi (2013a) in a more general way.
References
Akiba T, Iwata Y (2016) Branch-and-reduce exponential/FPT algorithms in practice: a case study of vertex cover. Theor Comput Sci 609:211–225
Bourgeois N, Escoffier B, Paschos VT, van Rooij JMM (2010) Maximum independent set in graphs of average degree at most three in \({O}(1.08537^n)\). In: TAMC, LNCS 6108, pp 373–384
Bourgeois N, Escoffier B, Paschos VT, van Rooij JMM (2012) Fast algorithms for max independent set. Algorithmica 62(1–2):382–415
Chen J, Kanj IA, Xia G (2010) Improved upper bounds for vertex cover. Theor Comput Sci 411(40–42):3736–3756
Chor B, Fellows M, Juedes DW (2004) Linear kernels in linear time, or how to save k colors in \({O}(n^2)\) steps. In: WG 2004. LNCS 3353, Springer, pp 257–269
Eppstein D (2006) Quasiconvex analysis of multivariate recurrence equations for backtracking algorithms. ACM Trans Algorithms 2(4):492–509
Fomin FV, Høie K (2006) Pathwidth of cubic graphs and exact algorithms. Inf Process Lett 97(5):191–196
Fomin FV, Kratsch D (2010) Exact exponential algorithms. Springer, New York
Fomin FV, Grandoni F, Kratsch D (2009) A measure and conquer approach for the analysis of exact algorithms. J ACM 56(5):1–32
Fürer M (2006) A faster algorithm for finding maximum independent sets in sparse graphs. In: LATIN 2006. LNCS 3887 , Springer, pp 491–501
Issac D, Jaiswal R (2015) An \(O^*(1.0821^n)\)-time algorithm for computing maximum independent set in graphs with bounded degree 3. arXiv:1308.1351v3
Jian T (1986) An \({O}(2^{0.304n})\) algorithm for solving maximum independent set problem. IEEE Trans Comput 35(9):847–851
Kneis J, Langer A, Rossmanith P (2009) A fine-grained analysis of a simple independent set algorithm. In: Kannan R, Kumar KN (eds) FSTTCS 2009, vol 4. Dagstuhl, Germany, LIPIcs, pp 287–298
Razgon I (2009) Faster computation of maximum independent set and parameterized vertex cover for graphs with maximum degree 3. J Discrete Algorithms 7(2):191–212
Robson J (1986) Algorithms for maximum independent sets. J Algorithms 7(3):425–440
Tarjan R, Trojanowski A (1977) Finding a maximum independent set. SIAM J Comput 6(3):537–546
West D (1996) Introduction to graph theory. Prentice Hall, Englewood Cliffs
Xiao M (2010) A simple and fast algorithm for maximum independent set in 3-degree graphs. In: Rahman M, Fujita S: WALCOM 2010, LNCS 5942, pp 281–292
Xiao M, Nagamochi H (2011) Further improvement on maximum independent set in graphs with maximum degree 4. In: COCOA 2011. LNCS 6831, pp 163–178
Xiao M, Nagamochi H (2013a) Confining sets and avoiding bottleneck cases: a simple maximum independent set algorithm in degree-3 graphs. Theor Comput Sci 469:92–104
Xiao M, Nagamochi H (2013b) Exact algorithms for maximum independent set. In: ISAAC 2013, LNCS 8283 , pp 328–338 (Also see: Xiao M, Nagamochi H. Exact algorithms for maximum independent set. arXiv:1312.6260)
Xiao M, Nagamochi H (2016) An exact algorithm for maximum independent set in degree-5 graphs. Discrete Appl Math 199:137–155
Acknowledgements
The first author was supported in part by National Natural Science Foundation of China under the Grants 61370071 and Fundamental Research Funds for the Central Universities under the Grant ZYGX2015J057. The second author was supported in part by Grant-in-Aid for Scientific Research from the Ministry of Education, Culture, Sports, Science and Technology of Japan.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Xiao, M., Nagamochi, H. A refined algorithm for maximum independent set in degree-4 graphs. J Comb Optim 34, 830–873 (2017). https://doi.org/10.1007/s10878-017-0115-3
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10878-017-0115-3