0
$\begingroup$

Let $G(V,E)$ be a symmetric graph with $n$ vertices and $m$ edges that has a $2\text{-factor}$ with edge set $F$, i.e. $F$ are the edges of an undirected vertex-disjoint cycle cover of $G$.

Question:
given only $F$ represented as an unordered sequence $\big( (u_1,v_1),\,\dots,\,(u_n,v_n)\big)$, what is the complexity of determining a permutation of the $n$ vertices that has the same cycles as $F$, i.e. storing the vertices in an array $\boldsymbol{a}$ such that $(i,\boldsymbol{a}[i])\in F$

Improve this question
$\endgroup$
5
  • $\begingroup$ If I got the problem correctly, it amounts to construction of an Eulerian cycle in the graph formed by $F$, which is rather straightforward. $\endgroup$
    – Max Alekseyev
    Commented Jan 26, 2022 at 15:18
  • $\begingroup$ @MaxAlekseyev no, it is not an Eulerian cycle; it is spanning graph, in which every vertex has degree 2; but there may be several disconnected cycles in $F$. The challenge is that you cannot assume that edges are oriented in any consistent way, i.e. you may have $(a,b),(a,x),(b,y).\dots$ in the given sequence and the task amounts to finding a "consistent" orientation for the edges.. $\endgroup$
    – Manfred Weis
    Commented Jan 26, 2022 at 15:44
  • $\begingroup$ It's still an Eulerian graph (every vertex has an even degree) as I understand. Then an Eulerian cycle can be found in each connected component. Such cycles will provide edges with consistent orientation. $\endgroup$
    – Max Alekseyev
    Commented Jan 26, 2022 at 15:54
  • $\begingroup$ @MaxAlekseyev so how would you find these cycles in the unordered set of edges? You must sort the edges in some way and eventually reverse the direction of cycle fragments whose directions do no not comply. A naive implementation would thus be $O(n^2)$ $\endgroup$
    – Manfred Weis
    Commented Jan 26, 2022 at 17:07
  • $\begingroup$ I've an answer. $\endgroup$
    – Max Alekseyev
    Commented Jan 26, 2022 at 17:38

1 Answer 1

Reset to default
2
$\begingroup$

Construct an undirected graph on the edge set $F$. This graph has each vertex with even degree, i.e. it's an Eulerian graph. Construct an Eulerian cycle in each connected component, e.g. following the Hierholzer's algorithm, which takes linear time in $|F|$. Fix any orientation of these cycles, and impose it on the edges from $F$.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .