Esther Galby

collaborators

2 papers

cs.DS2025

Metric Dimension and Geodetic Set Parameterized by Vertex Cover

Florent Foucaud, Esther Galby, Liana Khazaliya +4

For a graph $G$ , a subset $S \subseteq V (G)$ is called a resolving set of $G$ if, for any two vertices $u, v \in V (G)$ , there exists a vertex $w \in S$ such that $d (w, u) \neq = d (w, v)$ . T…

cs.CC2025

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…