|
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.
Bibtex entry:
| AUTHOR | = | {Bern{\'a}th, Attila and Kaminski, Marcin}, |
| TITLE | = | {Nonseparating cycles in planar and Eulerian graphs}, |
| NOTE | = | {{\tt egres.elte.hu}}, |
| INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
| YEAR | = | {2014}, |
| NUMBER | = | {TR-2014-05} |