A 2-Approximation Algorithm for Weighted Directed Hypergraph Embedding in a cycle

The problem of weighted directed hypergraph embedding in a cycle (denoted by WDHEC for short) is to embed the weighted directed hyperedges of a hypergraph as the weighted directed paths around a cycle such that maximal congestion-the sum of weight of the paths that use any physical link in the cycle-is minimized. In this paper we show that the WDHEC problem is NP-complete even when each hyperedge contains exactly two vertices. A linear-time algorithm with performance ratio two is presented by a greedy algorithm.