Volume 24, No 3, 2017, P. 3560
UDC 519.17
D. S. Malyshev and D. V. Sirotkin
Polynomialtime solvability of the independent set problem in a certain class of subcubic planar graphs
Abstract:
The independent set problem for a given simple graph is to compute the size of a maximum subset of its pairwise nonadjacent vertices. In this paper we prove polynomialtime solvability of the problem for subcubic planar graphs not containing an induced tree, obtained by coinciding ends of three paths of lengths 3, 3, and 2 correspondingly.
Bibliogr. 10.
Keywords: independent set problem, graph reduction, efficient algorithm.
DOI: 10.17377/daio.2017.24.549
Dmitry S. Malyshev ^{1}
Dmitry V. Sirotkin ^{1}
1. National Research University Higher School of Economics,
25/12 Bolshaya Pechyorskaya St., 603155 Nizhny Novgorod, Russia
email: dmalishev@hse.ru, dsmalyshev@rambler.ru, dmitriy.v.sirotkin@gmail.com
Received 25 July 2016
Revised 12 January 2017
References
[1] V. E. Alekseev, On compressible graphs, in Problemy kibernetiki (Problems of Cybernetics), Vol. 36, pp. 23–31, Nauka, Moscow, 1979 [Russian].
[2] V. E. Alekseev and V. V. Lozin, On local graph transformations preserving independence number, Diskretn. Anal. Issled. Oper., Ser. 1, 5, No. 1, 3–19, 1998 [Russian].
[3] V. E. Alekseev and D. S. Malyshev, Planar graph classes with the independent set problem solvable in polynomial time, Diskretn. Anal. Issled. Oper., 15, No. 1, 3–10, 2008 [Russian]. Translated in J. Appl. Ind. Math., 3, No. 1, 1–4, 2009.
[4] D. S. Malyshev, Classes of subcubic planar graphs for which the independent set problem is polynomially solvable, Diskretn. Anal. Issled. Oper., 20, No. 3, 26–44, 2013 [Russian]. Translated in J. Appl. Ind. Math., 7, No. 4, 537–548, 2013.
[5] V. E. Alekseev, On easy and hard hereditary classes of graphs with respect to the independent set problem, Discrete Appl. Math., 132, No. 1–3, 17–26, 2003.
[6] V. E. Alekseev, V. V. Lozin, D. S. Malyshev, and M. Milanic, The maximum independent set problem in planar graphs, in Mathematical Foundations of Computer Science 2008 (Proc. 33rd Int. Symp. MFCS, Torun, Poland, Aug. 25–29, 2008), pp. 96–107, Springer, Heidelberg, 2008 (Lect. Notes Comput. Sci., Vol. 5162).
[7] J. E. Hopcroft and R. E. Tarjan, Efficient planarity testing, J. ACM, 21, No. 4, 549–568, 1974.
[8] V. V. Lozin and M. Milanic, Maximum independent sets in graphs of low degree, in Proc. 18th Annu. ACMSIAM Symp. Discrete Algorithms, New Orleans, USA, Jan. 7–9, 2007, pp. 874–880, SIAM, Philadelphia, PA, 2007.
[9] V. V. Lozin and M. Milanic, On the maximum independent set problem in subclasses of planar graphs, J. Graph Algorithms Appl., 14, No. 2, 269–286, 2010.
[10] V. V. Lozin, J. Monnot, and B. Ries, On the maximum independent set problem in subclasses of subcubic graphs, J. Discrete Algorithms, 31, 104–112, 2015.
