2 papers
cs.DS2021
Upper Dominating Set: Tight Algorithms for Pathwidth and Sub-Exponential Approximation
Louis Dublois, Michael Lampis, Vangelis Th. Paschos
An upper dominating set is a minimal dominating set in a graph. In the \textsc{Upper Dominating Set} problem, the goal is to find an upper dominating set of maximum size. We study…
cs.CC2020
(In)approximability of Maximum Minimal FVS
Louis Dublois, Tesshu Hanaka, Mehdi Khosravian Ghadikolaei +2
We study the approximability of the NP-complete \textsc{Maximum Minimal Feedback Vertex Set} problem. Informally, this natural problem seems to lie in an intermediate space between…