TR-2015-13

Berge's path partition conjecture: an algorithm for almost all known cases

Dávid Herskovics



Abstract

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:

@techreport{egres-15-13,
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}
}


Last modification: 5.6.2018. Please email your comments to Tamás Király!