The complexity of minimum-length path decompositions

作者：

Highlights：

• We consider graphs of pathwidth k and focus on minimum-length path decompositions.

• We give a polynomial-time algorithm for k≤3.

• The problem is NP-hard for k≥4.

• The problem is NP-hard even for connected graphs for k≥5.

• The complexity for connected graphs with k=4 remains open.

摘要

•We consider graphs of pathwidth k and focus on minimum-length path decompositions.•We give a polynomial-time algorithm for k≤3.•The problem is NP-hard for k≥4.•The problem is NP-hard even for connected graphs for k≥5.•The complexity for connected graphs with k=4 remains open.

论文关键词：Graph searching,Path decomposition,Pathwidth

论文评审过程：Received 14 August 2013, Revised 9 March 2015, Accepted 10 June 2015, Available online 5 August 2015, Version of Record 25 August 2015.

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