Roohani Sharma

activity

20242026

collaborators

Showing cs.DMShow all

2 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…

Multiway f-Cut is fixed-parameter tractable

Reducing CMSO to Unbreakable Graphs Cannot be Computable

Multiway $f$ -Cut is fixed-parameter tractable