Erdős-Pósa property of tripods in directed graphs

Prelegent(ci)

Michał Pilipczuk

Język referatu

angielski

Termin

14 marca 2025 14:15

Pokój

p. 5060

Seminarium

Seminarium "Algorytmika"

---

A tripod in a directed graph D with sources S and sinks T is a subgraph consisting of the union of two S-T-paths that have distinct start-vertices and the same end-vertex, and are disjoint apart from sharing a suffix. We prove that tripods in directed graphs exhibit the Erdős-Pósa property: there is a function f such that for every digraph D with sources S and sinks T, if D does not contain k vertex-disjoint tripods, then there is a set of at most f(k) vertices that meets all the tripods in D.

Joint work with Marcin Briański, Meike Hatzel, and Karolina Okrasa.

---