Parameterized algorithms for recognizing monopolar and 2-subcolorable graphs

作者：

Highlights：

• We formulate the Inductive Recognition technique.

• This technique gives FPT algorithms for Monopolar Recognition and 2-Subcoloring.

• We extend these FPT algorithms to further vertex-partition problems.

• The respective parameters are smaller than the size of the partite sets.

• We obtain hardness results for many vertex-partition problems.

摘要

•We formulate the Inductive Recognition technique.•This technique gives FPT algorithms for Monopolar Recognition and 2-Subcoloring.•We extend these FPT algorithms to further vertex-partition problems.•The respective parameters are smaller than the size of the partite sets.•We obtain hardness results for many vertex-partition problems.

论文关键词：Vertex-partition problems,Graph classes,Monopolar graphs,Subcolorings,Split graphs,Unipolar graphs,Fixed-parameter algorithms

论文评审过程：Received 14 December 2016, Revised 19 June 2017, Accepted 11 August 2017, Available online 31 August 2017, Version of Record 13 November 2017.

论文官网地址：https://doi.org/10.1016/j.jcss.2017.08.002