Существуют ли точные методы решения покрытия Path в двудольных графах?
Рассмотрим простой граф G =(V; E). Хорошо известная проблема Path Cover ( https://en.wikipedia.org/wiki/Path_cover) является NP-полной для всех классов графов, для которых NP-полная для гамильтоновой задачи, включая планарные графы, двудольные графы и хордовые графы. Многие полиномиальные алгоритмы были предложены в литературе для специальных классов графов, для которых эта задача является полиномиальной, но я не нашел точных методов для нахождения минимального непересекающегося вершинного пути для двудольных графов (или даже для плоских графов и хордовых графов) особенно ветвление и связывание алгоритмов.
Знаете ли вы какие-либо точные методы, в частности алгоритмы Ветвления и Связи, для задачи покрытия пути на классах графов, для которых эта задача NP-трудна (двудольные графы, плоские графы и хордовые графы)?
Заранее спасибо.