A Fast Algorithm for Path 2-Packing Problem.

Let G = (VG, EG) be an undirected graph, $\mathcal{T} = \{T_1, \ldots, T_k\}$ be a collection of disjoint subsets of nodes. Nodes in T1 ∪ ... ∪ Tk are called terminals, other nodes are called inner. By a $\mathcal{T}$-path P we mean an undirected path such that P connects terminals from distinct sets in $\mathcal{T}$ and all internal nodes of P are inner. We study the problem of finding a maximum cardinality collection $\mathcal{P}$ of $\mathcal{T}$-paths such that at most two paths in $\mathcal{P}$ pass through any node v ∈ VG. Our algorithm is purely combinatorial and achieves the time bound of O(mn2), where n : = <INNOPIPE>VG<INNOPIPE>, m : = <INNOPIPE>EG<INNOPIPE>. [ABSTRACT FROM AUTHOR]