On Complexity of Minimum Leaf Out-branching Problem - Computer Science > Data Structures and AlgorithmsReport as inadecuate




On Complexity of Minimum Leaf Out-branching Problem - Computer Science > Data Structures and Algorithms - Download this document for free, or read online. Document in PDF available to download.

Abstract: Given a digraph $D$, the Minimum Leaf Out-Branching problem MinLOB is theproblem of finding in $D$ an out-branching with the minimum possible number ofleaves, i.e., vertices of out-degree 0. Gutin, Razgon and Kim 2008 provedthat MinLOB is polynomial time solvable for acyclic digraphs which are exactlythe digraphs of directed path-width DAG-width, directed tree-width,respectively 0. We investigate how much one can extend this polynomialityresult. We prove that already for digraphs of directed path-width directedtree-width, DAG-width, respectively 1, MinLOB is NP-hard. On the other hand,we show that for digraphs of restricted directed tree-width directedpath-width, DAG-width, respectively and a fixed integer $k$, the problem ofchecking whether there is an out-branching with at most $k$ leaves ispolynomial time solvable.



Author: Peter Dankelmann, Gregory Gutin, Eun Jung Kim

Source: https://arxiv.org/







Related documents