Enumerating minimal dominating sets in $K_t$-free graphs and variants

Jean-Florent Raymond; Marc Heinrich; Marthe Bonamy; Micha{\l} Pilipczuk; Oscar Defrain

REVIEW

Enumerating minimal dominating sets in K_t-free graphs and variants

Not yet reviewed by Pith; the record is open.

Re-run · record.json Download PDF Read on arXiv ↗

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 1810.00789 v3 pith:XGTWRNLM submitted 2018-10-01 cs.DM cs.DS

Enumerating minimal dominating sets in K_t-free graphs and variants

Marthe Bonamy , Oscar Defrain , Marc Heinrich , Jean-Florent Raymond , Micha{\l} Pilipczuk This is my paper

classification cs.DM cs.DS

keywords graphsdominatingfreegraphminimaloutput-polynomialproblemsets

verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

0 comments

read the original abstract

It is a long-standing open problem whether the minimal dominating sets of a graph can be enumerated in output-polynomial time. In this paper we investigate this problem in graph classes defined by forbidding an induced subgraph. In particular, we provide output-polynomial time algorithms for $K_t$-free graphs and variants. This answers a question of Kant\'e et al. about enumeration in bipartite graphs.

Enumerating minimal dominating sets in K_t-free graphs and variants

discussion (0)