In this paper, we study a variant of set packing, in which a set P of paths in a graph G = (V, E) is given, the goal is to find a maximum number of edge-disjoint paths of P. We show that the problem is iVP-hard even if each path in P contains at most three edges, while it is hard to approximate within O(|E|~(1/2-∈)) for the general case unless NP = ZPP. In the positive aspect, a parameterized algorithm relying on the maximum degree and the tree-width of G is derived. For tree networks, we present a polynomial time optimal algorithm.
展开▼
机译：在本文中，我们研究了集装箱的一种变体，其中给出了图形G =（V，E）中的一组路径P，目标是找到最大数量的边不相交路径P。即使P中的每个路径最多包含三个边，问题也是iVP难以解决的，而除非NP = ZPP，否则一般情况下很难在O（| E |〜（1 /2-∈））内近似。在积极方面，推导了依赖于最大程度和G的树宽的参数化算法。对于树形网络，我们提出了多项式时间最优算法。
展开▼
