|
Let $D$ be a digraph. A \emph{path partition} of $D$ is called $k$-optimal if the sum of the $k$-norms of its paths is minimal. The \emph{k-norm} of a path $P$ is $\min(|V(P)|,k)$. Berge's path partition conjecture claims that for every $k$-optimal path partition $\mathcal{P}$ there are $k$ disjoint stable sets orthogonal to $\mathcal{P}$. For general digraphs the conjecture has been proven for $k=1,2$ and $k\geq\lambda-3$, where $\lambda$ is the length of a longest path in the digraph. In this paper we give an algorithm which given a path partition $\mathcal{P}$, if it stops after a finite number of steps, it either finds $k$ disjoint stable sets orthogonal to $\mathcal{P}$ or finds a better path partition. We prove that the algorithm stops after a finite number of steps for $k=1$ and $k\geq \lambda-3$.
Bibtex entry:
| AUTHOR | = | {Herskovics, D{\'a}vid}, |
| TITLE | = | {Berge's path partition conjecture: an algorithm for almost all known cases}, |
| NOTE | = | {{\tt www.cs.elte.hu/egres}}, |
| INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
| YEAR | = | {2015}, |
| NUMBER | = | {TR-2015-13} |