## Abstract

A well known result in graph algorithms, due to Edmonds, states that given a digraph D and a positive integer ℓ , we can test whether D contains ℓ arc-disjoint out-branchings in polynomial time. However, if we ask whether there exists an out-branching and an in-branching which are arc-disjoint, then the problem becomes NP-complete. In fact, even deciding whether a digraph D contains an out-branching which is arc-disjoint from some spanning tree in the underlying undirected graph remains NP-complete. In this paper we formulate some natural optimization questions around these problems and initiate its study in the realm of parameterized complexity. More precisely, the problems we study are the following: Arc-Disjoint Branchings and Non-Disconnecting Out-Branching. In Arc-Disjoint Branchings (Non-Disconnecting Out-Branching), a digraph D and a positive integer k are given as input and the goal is to test whether there exist an out-branching and in-branching (respectively, a spanning tree in the underlying undirected graph) that differ on at least k arcs. We obtain the following results for these problems.

Non-Disconnecting Out-Branching is fixed parameter tractable (FPT) and admits a linear vertex kernel.

Arc-Disjoint Branchings is FPT on strong digraphs.

The algorithm for Non-Disconnecting Out-Branching runs in time 2O(k)nO(1) and the approach we use to obtain this algorithms seems useful in designing other moderately exponential time algorithms for edge/arc partitioning problems.

Non-Disconnecting Out-Branching is fixed parameter tractable (FPT) and admits a linear vertex kernel.

Arc-Disjoint Branchings is FPT on strong digraphs.

The algorithm for Non-Disconnecting Out-Branching runs in time 2O(k)nO(1) and the approach we use to obtain this algorithms seems useful in designing other moderately exponential time algorithms for edge/arc partitioning problems.

Original language | English |
---|---|

Journal | Algorithmica |

Volume | 76 |

Issue number | 1 |

Pages (from-to) | 279-296 |

ISSN | 0178-4617 |

DOIs | |

Publication status | Published - 2016 |

## Keywords

- Branching
- Exponential time algorithm
- Fixed parameter tractable
- Linear vertex kernel
- Parameterized complexity
- Partitioning problem
- Spanning tree