我们考虑一个简单的图 G =(V; E)。众所周知的路径覆盖问题 ( https://en.wikipedia.org/wiki/Path_cover ) 在哈密顿路径问题是 NP 完全的所有图类上都是 NP 完全的，包括平面图、二分图和弦图。文献中已经为这个问题是多项式的特殊图类提出了许多多项式算法，但是我没有找到任何精确的方法来找到二部图（甚至平面图和弦图）的最小顶点不相交路径覆盖，尤其是分支定界算法。
您是否知道任何确切的方法，特别是分支定界算法，用于解决该问题是 NP-hard 的图类（二分图、平面图和弦图）上的路径覆盖问题？
先感谢您。