Reconfiguration on sparse graphs

作者：

Highlights：

• A study of reconfiguration problems on sparse graphs.

• Parameterizing by solution size and sparsity measure.

• Independent Set Reconfiguration is FPT on degenerate and nowhere dense graphs.

• Dominating Set Reconfiguration is FPT on biclique-free graphs.

摘要

•A study of reconfiguration problems on sparse graphs.•Parameterizing by solution size and sparsity measure.•Independent Set Reconfiguration is FPT on degenerate and nowhere dense graphs.•Dominating Set Reconfiguration is FPT on biclique-free graphs.

论文关键词：Reconfiguration,Dominating set,Independent set,Sparse graphs,Parameterized complexity

论文评审过程：Received 24 August 2017, Revised 22 February 2018, Accepted 26 February 2018, Available online 2 April 2018, Version of Record 30 April 2018.

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