Algorithms and complexity for weighted hypergraph embedding in a cycle

摘要

The problem of weighted hypergraph embedding in a cycle (WHEC) is to embed the weighted hyperedges of a hypergraph as the paths in a cycle, such that the maximum congestion of any physical link in the cycle is minimized. A simpler version of this problem is the weighted graph embedding in a cycle (WGEC) that embeds the weighted edges of a normal graph as the paths in a cycle. The WHEC and WGEC problems have applications in design automation, parallel computing and computer communication. In this paper we first show that both WHEC and WGEC problems are NP-Complete. Afterwards we formulate the WHEC problem as an integer linear programming (ILP). Therefore, an approximation solution can be obtained by using LP-relaxation and rounding heuristic. Our LP-approximation algorithm generates an embedding with congestion at most two times the optimal solution. Finally, to guarantee the efficiency, we develop a linear-time approximation algorithm that also provides a solution with the same worst case approximation bound as the LP-approximation.