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

2009/03/05 by Nathann Cohen, Cohen, Nathann, Fedor V. Fomin +9
Computer Science · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #cs.DS

paper · pdf · doi:10.48550/arxiv.0903.0938

arxiv created 2009/03/05 · arxiv updated 2009/12/01

Abstract

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 algorithms for deciding whether an input digraph contains a given out-tree with k vertices. The algorithms are of runtime O^*(5.704^k) and O^*(5.704^k(1+o(1))), respectively. We apply the deterministic algorithm to obtain a deterministic 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).

Related

• An FPT Algorithm for Directed Spanning k-Leaf
• FPT Algorithms and Kernels for the Directed k-Leaf Problem
• Spanning directed trees with many leaves
• Minimum Leaf Out-branching and Related Problems
• Spotting Trees with Few Leaves