Finding Shortest Contractible and Shortest Separating Cycles in Embedded Graphs
We give a polynomial-time algorithm to find a shortest contractible cycle (i.e., a closed walk without repeated vertices) in a graph embedded in a surface. This answers a question posed by Hutchinson. In contrast, we show that finding a shortest contractible cycle through a given vertex is NP-hard. We also show that finding a shortest separating cycle in an embedded graph is NP-hard. This answers a question posed by Mohar and Thomassen.
algorithms theory 3-path condition forbidden pairs graphs on surfaces topological graph theory