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$

$\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$ Jan 26 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$ Jan 26 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$ Jan 26 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$ Jan 26 at 17:07
  • $\begingroup$ I've an answer. $\endgroup$ Jan 26 at 17:38

1 Answer 1

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.