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

Speaker(s)

Michał Pilipczuk

Language of the talk

English

Date

March 14, 2025, 2:15 p.m.

Room

room 5060

Seminar

Seminar Algorithms

---

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.

---