4 papers
A deterministic -approximation for directed feedback vertex sets in tournaments
Ebrahim Ghorbani, Matthias Mnich
We nearly settle the polynomial-time approximability of the Directed Feedback Vertex Set problem in tournaments. This problem is Vertex Cover-hard, and thus cannot have a $(2 - \va…
A generalisation of Menger's theorem in bidirected graphs
Ebrahim Ghorbani, Jana Katharina Nickel, Florian Reich
Menger's theorem - the maximum number of vertex-disjoint - paths is equal to the minimum size of an - separator - is generally not true in bidirected graphs. We prove t…
Hitting cycles through prescribed vertices or edges
Nathan Bowler, Ebrahim Ghorbani, Florian Gut +2
We prove that for every set of vertices of a directed graph , the maximum number of vertices in contained in a collection of vertex-disjoint cycles in is at least th…
A Hall-type theorem with algorithmic consequences in planar graphs
Ebrahim Ghorbani, Hossein Jowhari
Given a graph , for a vertex set , let denote the set of vertices in that have a neighbor in . Extending the concept of binding number of graph…