In this note we show the hardness of many natural edge-disjoint subgraphs problems in undirected graphs. For example, given an undirected graph $G=(V,E)$ and two nodes $s,t\in V$, it is NP-complete to decide whether there exists an $s-t$-path $P\subseteq E$ such that $G-P=(V; E-P)$ is connected.
Bibtex entry:
@techreport{egresqp-10-04,
AUTHOR | = | {Bern{\'a}th, Attila and Kir{\'a}ly, Zolt{\'a}n}, |
TITLE | = | {Finding edge-disjoint subgraphs in graphs}, |
NOTE | = | {{\tt www.cs.elte.hu/egres}}, |
INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
YEAR | = | {2010}, |
NUMBER | = | {QP-2010-04} |