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…