Volume 24, No 3, 2017, P. 35-60

UDC 519.17
D. S. Malyshev and D. V. Sirotkin
Polynomial-time 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 non-adjacent vertices. In this paper we prove polynomial-time 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 ¹
Dmitry V. Sirotkin ¹
1. National Research University Higher School of Economics,
25/12 Bolshaya Pechyorskaya St., 603155 Nizhny Novgorod, Russia
e-mail: 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. ACM-SIAM 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.