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

Output: The set of closed walks in $G$ using $e$ and $f$ which contains $k$ faces of $G$. In other words the set of close walks in $G$ via $e$ and $f$ which each one partition $\Pi$ into two set of faces which one is of size $k$.

I'm wondering if this problem is solvable in poly-time!


1 Answer 1


It's not, since there can be exponentially many such walks.

The $((2 \cdot n)+1)$ by $((2 \cdot n)+1)$ grid graph will have at least $2^n$ such paths for $​k = (2\cdot n \cdot n)+(4 \cdot n)+1$, since paths can go along two sides of the grid, in from both ends of that, then connect both ends of that in a way which encloses exactly two squares of each of the $n$ non-overlapping 2-by-2 blocks on the diagonal between those ends.

However, there are at least 8 weaker versions of what you're asking about.

  1. Enumerating them in poly(input_size, number_of_such_paths) time.

  2. Enumerating them in ​poly(input_size) $\cdot$ number_of_such_paths time.

  3. Enumerating them with polynomial delay.

  4. Doing one of the previous three while using only poly(input_size) space.

  5. Computing number_of_such_paths and a bijection from {0,1,2,3,...,number_of_such_paths-1} to the set of such paths.

  6. Doing the previous thing and computing the inverse of the bijection.

I don't know anything about whether or not any of those are doable in polynomial time.

  • $\begingroup$ What if we change the question to finding a closed walk with minimum length containing k faces? $\endgroup$
    – Saaber
    Jan 4, 2016 at 21:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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