QP-2010-04

Finding edge-disjoint subgraphs in graphs

Attila Bernáth, Zoltán Király



Abstract

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}
}


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