Output-polynomial enumeration for incomparability graphs of StS_t-free posets

Let tt be a positive integer. A poset is StS_t-free if it contains no suborder isomorphic to the poset StS_t, and let \textscDomEnum\textsc{Dom-Enum} denote the problem of enumerating all minimal dominating sets of a graph.

The StS_t-free incomparability conjecture. For every tt, there is an output-polynomial time algorithm for \textscDomEnum\textsc{Dom-Enum} in incomparability graphs of StS_t-free posets.

The result would extend the paper's bounded-dimension algorithm to a broader class of posets. The proposed extension is not covered by the current proof, which relies crucially on a bounded-dimension representation; the conjecture remains open.

Sources & referencesView supporting material

Primary source

Marthe Bonamy, Oscar Defrain, Piotr Micek and Lhouari Nourine, “Enumerating minimal dominating sets in the (in)comparability graphs of bounded dimension posets”, arXiv:2004.07214 (2025).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.