Algorithms (Feb 2025)

Enumerating Minimal Vertex Covers and Dominating Sets with Capacity and/or Connectivity Constraints

  • Yasuaki Kobayashi,
  • Kazuhiro Kurita,
  • Kevin Mann,
  • Yasuko Matsui,
  • Hirotaka Ono

DOI
https://doi.org/10.3390/a18020112
Journal volume & issue
Vol. 18, no. 2
p. 112

Abstract

Read online

In this paper, we consider the minimal vertex cover and minimal dominating sets with capacity and/or connectivity constraint enumeration problems. We develop polynomial-delay enumeration algorithms for these problems on bounded-degree graphs. For the case of minimal connected vertex covers, our algorithms run in polynomial delay, even on the class of d-claw free graphs. This result is extended for bounded-degree graphs and outputs in quasi-polynomial time on general graphs. To complement these algorithmic results, we show that the minimal connected vertex cover, minimal connected dominating set, and minimal capacitated vertex cover enumeration problems in 2-degenerated bipartite graphs are at least as hard as enumerating minimal transversals in hypergraphs.

Keywords