![]() |
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:
| AUTHOR | = | {Bern{\'a}th, Attila and Kir{\'a}ly, Zolt{\'a}n}, |
| TITLE | = | {Finding edge-disjoint subgraphs in graphs}, |
| NOTE | = | {{\tt egres.elte.hu}}, |
| INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
| YEAR | = | {2010}, |
| NUMBER | = | {QP-2010-04} |