## Abstract

The DIRECTED MAXIMUM LEAF OUT-BRANCHING problem is to find an out-branching (i.e., a rooted oriented spanning tree) in a given digraph with the maximum number of leaves. In this paper, we obtain two combinatorial results on the number of leaves in out-branchings. We show that (1) every strongly connected n-vertex digraph D with minimum in-degree at least 3 has an outbranching with at least (n/4)^{1/3} - 1 leaves; (2) if a strongly connected digraph D does not contain an out-branching with k leaves, then the pathwidth of its underlying graph UG(D) is O(k log k), and if the digraph is acyclic with a single vertex of in-degree zero, then the pathwidth is at most 4k. The last result implies that it can be decided in time 2^{O(k log2 k)} · n^{O(1)} whether a strongly connected digraph on n vertices has an out-branching with at least k leaves. On acyclic digraphs the running time of our algorithm is 2^{O(k log k)} · n^{O(1)}.

Original language | English (US) |
---|---|

Pages (from-to) | 466-476 |

Number of pages | 11 |

Journal | SIAM Journal on Discrete Mathematics |

Volume | 23 |

Issue number | 1 |

DOIs | |

State | Published - 2008 |

Externally published | Yes |

## All Science Journal Classification (ASJC) codes

- General Mathematics

## Keywords

- Directed graphs
- Fixed parameter tractability
- Maximum leaf
- Out-branching
- Rooted tree