Masarík, Tomás ;
Muzi, Irene ;
Pilipczuk, Marcin ;
Rzazewski, Pawel ;
Sorge, Manuel
Packing Directed Circuits QuarterIntegrally
Abstract
The celebrated ErdösPósa theorem states that every undirected graph that does not admit a family of k vertexdisjoint cycles contains a feedback vertex set (a set of vertices hitting all cycles in the graph) of size O(k log k). After being known for long as Younger's conjecture, a similar statement for directed graphs has been proven in 1996 by Reed, Robertson, Seymour, and Thomas. However, in their proof, the dependency of the size of the feedback vertex set on the size of vertexdisjoint cycle packing is not elementary.
We show that if we compare the size of a minimum feedback vertex set in a directed graph with quarterintegral cycle packing number, we obtain a polynomial bound. More precisely, we show that if in a directed graph G there is no family of k cycles such that every vertex of G is in at most four of the cycles, then there exists a feedback vertex set in G of size O(k^4). On the way there we prove a more general result about quarterintegral packing of subgraphs of high directed treewidth: for every pair of positive integers a and b, if a directed graph G has directed treewidth Omega(a^6 b^8 log^2(ab)), then one can find in G a family of a subgraphs, each of directed treewidth at least b, such that every vertex of G is in at most four subgraphs.
BibTeX  Entry
@InProceedings{masark_et_al:LIPIcs:2019:11193,
author = {Tom{\'a}s Masar{\'\i}k and Irene Muzi and Marcin Pilipczuk and Pawel Rzazewski and Manuel Sorge},
title = {{Packing Directed Circuits QuarterIntegrally}},
booktitle = {27th Annual European Symposium on Algorithms (ESA 2019)},
pages = {72:172:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771245},
ISSN = {18688969},
year = {2019},
volume = {144},
editor = {Michael A. Bender and Ola Svensson and Grzegorz Herman},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/11193},
URN = {urn:nbn:de:0030drops111938},
doi = {10.4230/LIPIcs.ESA.2019.72},
annote = {Keywords: Directed graphs, graph algorithms, linkage, Erd{\"o}sP{\'o}sa property}
}
2019
Keywords: 

Directed graphs, graph algorithms, linkage, ErdösPósa property 
Seminar: 

27th Annual European Symposium on Algorithms (ESA 2019)

Issue date: 

2019 
Date of publication: 

2019 