Prospectous for Embedding Hypergraph in a Cycle
Guojun Li · Journal of Liaocheng University · 2008
We consider the problem of embedding hyperedges of a hypergraph as paths in a cycle such that the maximum congestion,the maximum number of paths that use any single edge in a cycle,is minimized.The Minimum Congestion Hypergraph Embedding in a Cycle problem is known to be NP-hard and its graph version,the Minimum Congestion Graph Embedding in a Cycle,is solvable in polynomial time.Furthermore,for the graph problem,a polynomial time approxima-tion scheme for the weighted version is known.For the hypergraphmodel,several approximation algorithms with a ratio of two have been previously published.A recent works on this problem reduced the approximation ratio to 1.5.We present a polynomial time approximation scheme in this paper,settling the debate regarding if the problem is polynomial time approximable