1 citations · 1 across the 1 of their papers we have counts for
7 papers
Tractability of Hard Digraph Cut Problems on Eulerian Instances: Treewidth Reduction and Reducing CMSO to Unbreakable Eulerian Instances
Esther Galby, Roohani Sharma, Bart van der Steenhoven
Eulerian digraphs retain the directional structure of general digraphs while exhibiting a symmetry of cuts reminiscent of undirected graphs. We show that this symmetry extends beyo…
Metric Dimension and Geodetic Set Parameterized by Vertex Cover
Florent Foucaud, Esther Galby, Liana Khazaliya +4
For a graph , a subset is called a resolving set of if, for any two vertices , there exists a vertex such that . T…
Problems in NP can Admit Double-Exponential Lower Bounds when Parameterized by Treewidth or Vertex Cover
Florent Foucaud, Esther Galby, Liana Khazaliya +4
Treewidth (tw) is an important parameter that, when bounded, yields tractability for many problems. For example, graph problems expressible in Monadic Second Order (MSO) logic and…
Subexponential Parameterized Directed Steiner Network Problems on Planar Graphs: a Complete Classification
Esther Galby, Sandor Kisfaludi-Bak, Daniel Marx +1
In the Directed Steiner Network problem, the input is a directed graph G, a subset T of k vertices of G called the terminals, and a demand graph D on T. The task is to find a subgr…
Domination and Cut Problems on Chordal Graphs with Bounded Leafage
Esther Galby, Daniel Marx, Philipp Schepper +2
The leafage of a chordal graph G is the minimum integer l such that G can be realized as an intersection graph of subtrees of a tree with l leaves. We consider structural parameter…
Metric Dimension Parameterized by Feedback Vertex Set and Other Structural Parameters
Esther Galby, Liana Khazaliya, Fionn Mc Inerney +2
For a graph , a subset is called a \emph{resolving set} if for any two vertices , there exists a vertex such that …
Parameterized Complexity of Weighted Multicut in Trees
Esther Galby, Dániel Marx, Philipp Schepper +2
The Edge Multicut problem is a classical cut problem where given an undirected graph , a set of pairs of vertices , and a budget , the goal is to determine if th…