Roohani Sharma

activity

20122026

most citedTreedepth vs circumference

4 citations · 13 across the 17 of their papers we have counts for

collaborators

Showing cs.DMShow all

3 papers · 1 filter

cs.DM2026

Multiway $f$ -Cut is fixed-parameter tractable

Tony Huynh, Eun Jung Kim, Sang-il Oum +2

A connectivity function on a finite set $E$ is a function $f : 2^{E} \to Z$ that is submodular and symmetric, with $f (\emptyset) = 0$ . Given a connectivity function $f$ via…

cs.DM2026

Reducing CMSO to Unbreakable Graphs Cannot be Computable

Colin Geniet, Roohani Sharma

Lokshtanov, Ramanujan, Saurabh, and Zehavi [ICALP 2018] proved that for any CMSO formula $ϕ$ , testing $ϕ$ on arbitrary graphs can be reduced to testing it on $(q, k)$ -unbreakable gr…

cs.DM2022

Metric Dimension Parameterized by Feedback Vertex Set and Other Structural Parameters

Esther Galby, Liana Khazaliya, Fionn Mc Inerney +2

For a graph $G$ , a subset $S \subseteq V (G)$ is called a \emph{resolving set} 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)$ …

Multiway f-Cut is fixed-parameter tractable

Reducing CMSO to Unbreakable Graphs Cannot be Computable

Metric Dimension Parameterized by Feedback Vertex Set and Other Structural Parameters

Multiway $f$ -Cut is fixed-parameter tractable