Algorithm for Finding $k$-Vertex Out-trees and its Application to $k$-Internal Out-branching Problem

Nathann Cohen, Fedor V. Fomin, Gregory Gutin +3

An out-tree $T$ is an oriented tree with only one vertex of in-degree zero. A vertex $x$ of $T$ is internal if its out-degree is positive. We design randomized and deterministic al…