A cycle in a connected graph $G$ is called dominating if its complement is an independent set. H.J. Veldman proved in 1983 (Disc. Math. v.43, 281-96) a general result that in particular implies that a connected $2K_2$-free $G$ (i.e. $G$ does not contain a induced subgraph which is the disjoint union of two edges) admits such a cycle, unless $G$ is a tree (in the latter case the cycle collapses to a vertex or to an edge). His proof is not algorithmic.

In fact, it's not hard to give an efficient algorithm for finding such a cycle in a connected $2K_2$-free $G$. Is this known? (It could be an exercise in a book, if you ask me). Also, I wonder if more general statements from [loc.cit.] are known to allow efficient algorithmic versions.

A cycle $C$ in a connected graph $G$ is called dominating if its complement $V(G)-V(C)$ is an independent set. H.J. Veldman proved in 1983 (Disc. Math. v.43, 281-96) a general result that in particular implies that a connected $2K_2$-free $G$ (i.e. $G$ does not contain a induced subgraph which is the disjoint union of two edges) admits such a cycle, unless $G$ is a tree (in the latter case the cycle collapses to a vertex or to an edge). His proof is not algorithmic.

In fact, it's not hard to give an efficient algorithm for finding such a cycle in a connected $2K_2$-free $G$. Is this known? (It could be an exercise in a book, if you ask me). Also, I wonder if more general statements from [loc.cit.] are known to allow efficient algorithmic versions.

A cycle in a graph $G$ is called dominating if its complement is an independent set. H.J. Veldman proved in 1983 (Disc. Math. v.43, 281-96) a general result that in particular implies that a connected $2K_2$-free $G$ (i.e. $G$ does not contain a induced subgraph which is the disjoint union of two edges) admits such a cycle, unless $G$ is a tree (in the latter case the cycle collapses to a vertex or to an edge). His proof is not algorithmic.

In fact, it's not hard to give an efficient algorithm for finding such a cycle in a connected $2K_2$-free $G$. Is this known? (It could be an exercise in a book, if you ask me). Also, I wonder if more general statements from [loc.cit.] are known to allow efficient algorithmic versions.

A cycle in a connected graph $G$ is called dominating if its complement is an independent set. H.J. Veldman proved in 1983 (Disc. Math. v.43, 281-96) a general result that in particular implies that a connected $2K_2$-free $G$ (i.e. $G$ does not contain a induced subgraph which is the disjoint union of two edges) admits such a cycle, unless $G$ is a tree (in the latter case the cycle collapses to a vertex or to an edge). His proof is not algorithmic.

In fact, it's not hard to give an efficient algorithm for finding such a cycle in a connected $2K_2$-free $G$. Is this known? (It could be an exercise in a book, if you ask me). Also, I wonder if more general statements from [loc.cit.] are known to allow efficient algorithmic versions.