# Closed Walk in Planar Graphs

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!

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.

• What if we change the question to finding a closed walk with minimum length containing k faces? – Saaber Jan 4 '16 at 21:40