## Abstrakt

Unlike the problem of deciding whether a digraph D = (V, A) has ℓ in-branchings (or ℓ out-branchings) is polynomial time solvable, the problem of deciding whether a digraph D = (V, A) has an in-branching B^{−} and an out-branching B^{+} which are arc-disjoint is NP-complete. Motivated by this, a natural optimization question that has been studied in the realm of Parameterized Complexity is called Rooted k-Distinct Branchings. In this problem, a digraph D = (V, A) with two prescribed vertices s, t are given as input and the question is whether D has an in-branching rooted at t and an out-branching rooted at s such that they differ on at least k arcs. Bang-Jensen et al. [Algorithmica, 2016 ] showed that the problem is fixed parameter tractable (FPT) on strongly connected digraphs. Gutin et al. [ICALP, 2017; JCSS, 2018 ] completely resolved this problem by designing an algorithm with running time 2^{O}(^{k}^{2 log2 k)}n^{O}^{(1)}. Here, n denotes the number of vertices of the input digraph. In this paper, answering an open question of Gutin et al., we design a polynomial kernel for Rooted k-Distinct Branchings. In particular, we obtain the following: Given an instance (D, k, s, t) of Rooted k-Distinct Branchings, in polynomial time we obtain an equivalent instance (D^{′}, k^{′}, s, t) of Rooted k-Distinct Branchings such that |V (D^{′})| ≤ O(k^{2}) and the treewidth of the underlying undirected graph is at most O(k). This result immediately yields an FPT algorithm with running time 2^{O}(k log k^{)} + n^{O}^{(1)}; improving upon the previous running time of Gutin et al. For our algorithms, we prove a structural result about paths avoiding many arcs in a given in-branching or out-branching. This result might turn out to be useful for getting other results for problems concerning in-and out-branchings.

Originalsprog | Engelsk |
---|---|

Titel | 29th Annual European Symposium on Algorithms, ESA 2021 |

Redaktører | Petra Mutzel, Rasmus Pagh, Grzegorz Herman |

Antal sider | 15 |

Forlag | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |

Publikationsdato | sep. 2021 |

Artikelnummer | 11 |

ISBN (Elektronisk) | 9783959772044 |

DOI | |

Status | Udgivet - sep. 2021 |

Begivenhed | 29th Annual European Symposium on Algorithms, ESA 2021 - Vitual, Lisbon, Portugal Varighed: 6. sep. 2021 → 8. sep. 2021 |

### Konference

Konference | 29th Annual European Symposium on Algorithms, ESA 2021 |
---|---|

Land/Område | Portugal |

By | Vitual, Lisbon |

Periode | 06/09/2021 → 08/09/2021 |

Navn | Leibniz International Proceedings in Informatics, LIPIcs |
---|---|

Vol/bind | 204 |

ISSN | 1868-8969 |

### Bibliografisk note

Publisher Copyright:© Jørgen Bang-Jensen, Kristine Vitting Klinkby, and Saket Saurabh; licensed under Creative Commons License CC-BY 4.0