TR-2014-05

Nonseparating cycles in planar and Eulerian graphs

Attila Bernáth, Marcin Kamiński



Abstract

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 Kamiński, 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}
}


Last modification: 15.9.2018. Please email your comments to Tamás Király!