A cycle $C \subseteq E$ in a graph $G=(V,E)$ is nonseparating if $G - C$ is
connected (note that we only delete the edges of the cycle). We study the algorithmic
problem of deciding whether a graph contains a nonseparating cycle.
This problem was shown to be
NP-complete in [Bernáth and Király, 2011]. We prove a lemma about this problem in
planar graphs and we show that it is NP-complete in Eulerian
graphs. The former problem was an open problem raised in [Bernáth and Király, 2011]; the
latter is a natural question in the context of greedy improvements of
feasible solutions to the graphic TSP Problem.
Previous version can be found here.
Bibtex entry:
@techreport{egres-14-05,
AUTHOR | = | {Bern{\'a}th, Attila and Kaminski, Marcin}, |
TITLE | = | {Nonseparating cycles in planar and Eulerian graphs}, |
NOTE | = | {{\tt www.cs.elte.hu/egres}}, |
INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
YEAR | = | {2014}, |
NUMBER | = | {TR-2014-05} |