Finding edge-disjoint subgraphs in graphs

Attila Bernáth, Zoltán Király


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}

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