On the fractionality of the path packing problem

摘要

Given an undirected graph G=(N,E), a subset T of its nodes and an undirected graph (T,S), G and (T,S) together are often called a network. A collection of paths in G whose end-pairs lie in S is called an integer multiflow. When these paths are allowed to have fractional weight, under the constraint that the total weight of the paths traversing a single edge does not exceed 1, we have a fractional multiflow in G. The problems of finding the maximum weight of paths with end-pairs in S over all fractional multiflows in G is called the fractional path packing problem.