Re: minimum disjoint paths covering of a graph - algorithm needed


Marcin wrote:
> >> John Gabbriel:
> > Ah, well that makes the problem hard.
> > I think it is NP-Complete as Hamiltonian path problem can be reduced to
> > this.
> [...]
>
> yes, u are right. i have spent some hours googling, and i have found that
> for bipartite graphs it's NP-complete ...
> there are only some special graph types where its polynomial-time or less.
>
> for example : directed acyclic graphs, cographs, trees.
>
> i also tried to find how to compute the number of minimum path cover (not
> the solution, just the number of paths i need), but with no resoults :/
>
> AFAIK it's not NP-complete,
>

Even knowing just the value of the minimum path cover is NP-Complete,
as the decision problem of finding out if a graph has a Hamiltonian
path or not is NP-Complete.

.

Relevant Pages
Loading