Input: Planar graph $G$ and its embedding in sphere $\Pi$, edges $e, f \in E(G)$ and integer $k$.

Output: A shortest closed walk (one among possibly many, if exists) in $G$ using $e$ and $f$ which contains exactly $k$ faces of $G$.

A walk $w = v_1,e_1,v_2,...,e_i,v_i$ (where $v_j \in V(G), e_j \in E(G)$ for $1 \le j \le i$) uses an edge $e$, if $e = e_j$ for some $1 \le j \le i$. Also a walk $w$ contains the face $g$ if in the embedding of $G$ on sphere when we consider $w$ and $g$ as closed $2$-dimensional polytopes, then $g \subseteq w$. A walk is allowed to have repeated vertices/edges.

Can this problem be solved in polynomial time?

  • 1
    $\begingroup$ 3. Regardless of how you obtained $G$, I still wonder whether it might be fruitful to consider $G^*$ (the dual graph of $G$) and try to reformulate the problem in terms of $G^*$, and see if that leads to a clean formulation. 4. It might be useful to edit the question to clear up all of these. $\endgroup$ – D.W. Jan 4 '16 at 23:25
  • $\begingroup$ Related (but not a duplicate): cs.stackexchange.com/q/19137/9550 $\endgroup$ – David Richerby Jan 5 '16 at 15:31

Your Answer

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

Browse other questions tagged or ask your own question.