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

摘要

An out-tree T is an oriented tree with exactly one vertex of in-degree zero and a vertex x of T is called internal if its out-degree is positive. We design randomized and deterministic algorithms for deciding whether an input digraph contains a subgraph isomorphic to a given out-tree with k vertices. Both algorithms run in O~*(5.704~k) time. We apply the deterministic algorithm to obtain an algorithm of runtime O~*(c~k), where c is a constant, for deciding whether an input digraph contains a spanning out-tree with at least k internal vertices. This answers in affirmative a question of Gutin, Razgon and Kim (Proc. AAIM'08).