5 citations · 10 across the 9 of their papers we have counts for
11 papers
Cycles of Well-Linked Sets II: an Elementary Bound for the Directed Grid Theorem
Meike Hatzel, Stephan Kreutzer, Marcelo Garlet Milani +1
In 2015, Kawarabayashi and Kreutzer proved the Directed Grid Theorem - the generalisation of the well-known Excluded Grid Theorem to directed graphs - confirming a conjecture by Re…
Cycles of Well-Linked Sets I: an Elementary Bound for Directed Cycle Packing
Meike Hatzel, Stephan Kreutzer, Marcelo Garlet Milani +1
In 1996, Reed, Robertson, Seymour and Thomas [Combinatorica 1996] proved Younger's Conjecture, which states that, for all directed graphs , there exists a function such that…
Computing complexity measures of degenerate graphs
Pål Grønås Drange, Patrick Greaves, Irene Muzi +1
We show that the VC-dimension of a graph can be computed in time , where is the degeneracy of the input graph. The core idea of our algorithm is a data s…
Decomposition of (infinite) digraphs along directed 1-separations
Nathan Bowler, Florian Gut, Meike Hatzel +3
We introduce torsoids, a canonical structure in matching covered graphs, corresponding to the bricks and braces of the graph. This allows a more fine-grained understanding of the s…
Harmless Sets in Sparse Classes
Pål Grønås Drange, Irene Muzi, Felix Reidl
In the classic TARGET SAT SELECTION problem, we are asked to minimise the number of nodes to activate so that, after the application of a certain propagation process, all nodes of…
Well-quasi-ordering digraphs with no long alternating paths by the strong immersion relation
Chun-Hung Liu, Irene Muzi
Nash-Williams' Strong Immersion Conjecture states that graphs are well-quasi-ordered by the strong immersion relation. That is, given infinitely many graphs, one graph contains ano…
Optimal Discretization is Fixed-parameter Tractable
Stefan Kratsch, Tomáš Masařík, Irene Muzi +2
Given two disjoint sets and of points in the plane, the Optimal Discretization problem asks for the minimum size of a family of horizontal and vertical lines that separ…
Packing Directed Cycles Quarter- and Half-Integrally
Tomáš Masařík, Irene Muzi, Marcin Pilipczuk +2
The celebrated Erdős-Pósa theorem states that every undirected graph that does not admit a family of vertex-disjoint cycles contains a feedback vertex set (a set of vertices hi…
Being even slightly shallow makes life hard
Irene Muzi, Michael P. O'Brien, Felix Reidl +1
We study the computational complexity of identifying dense substructures, namely -shallow topological minors and -subdivisions. Of particular interest is the case when $r=1…
Half-integral linkages in highly connected directed graphs
Katherine Edwards, Irene Muzi, Paul Wollan
We study the half-integral -Directed Disjoint Paths Problem (kDDPP) in highly strongly connected digraphs. The integral kDDPP is NP-complete even when restricted to in…
Degree-doubling graph families
János Körner, Irene Muzi
Let G be a family of n-vertex graphs of uniform degree 2 with the property that the union of any two member graphs has degree four. We determine the leading term in the asymptotics…