Simple Undirected Two-Commodity Integral Flow with a Unitary Demand

Even, Itai and Shamir (1976) proved that the simple two-commodity integral flow problem is NP-complete both in the directed and undirected cases. They showed the NP-completeness of the directed case even if the demand of one commodity is unitary. However, the complexity of the undirected case when one commodity has a demand bounded by a constant remained unknown since then. In this paper, we show the NP-completeness of Simple undirected two-commodity integral flow when the demand of one commodity is unitary, closing a forty-year complexity gap. Furthermore, we also prove the NP-completeness of a related problem, called k+1vertex-disjoint paths, which aims to determine whether an undirected graph admits k+1 vertex disjoint paths where k of those paths are between a given pair of vertices and one path is between another given pair of vertices.