How do I convert a simple weighted graph to a hypergraph?

Question

I have found a partitioning algorithm that works on hypergraphs and its name is hMETIS, but my input is in the form of a simple weighted graph. Is there any technique that maps a graph to a hypergraph?

Answer 1

In general: No.

A graph contains information on binary interactions between two vertices, and there is no way to extract the information about the higher order interactions.

In short, if I give you a hypergraph I can use (multiple methods) to turn it into a graph, but that graph could be the result of multiple hypergraphs.

There are a few exceptions to this, notably if you have more information about the vertices outside of the graph, or if the graph is bipartite.

Answer 2

As a graph is a particular hypergraph, I would say there is no need for such a mapping.

Answer 3

A hypergraph is a set of elements called vertices, together with a set of sets of elements, each of which is an edge.

An r-uniform hypergraph is a hypergraph where the edges are sets of exactly r vertices.

A 2-uniform hypergraph is a graph.

You should be able to format your graph as the hypergraph file format hmetis expects.

See section 3.4: Format of hypergraph input file: https://course.ece.cmu.edu/~ee760/760docs/hMetisManual.pdf

Quoted here in case the link fails: The primary input of hMETIS is the hypergraph to be partitioned. This hypergraph is stored in a file and is supplied to hMETIS as one of the command line parameters. A hypergraph H = (V, Eh ) with V vertices and Eh hyperedges is stored in a plain text file that contains |Eh| + 1 lines, if there are no weights on the vertices and |Eh|+|V | + 1 lines if there are weights on the vertices. Any line that starts with ‘%’ is a comment line and is skipped. The first line contains either two or three integers. The first integer is the number of hyperedges (|Eh|), the second is the number of vertices (|V|), and the third integer (fmt) contains information about the type of the hypergraph. In particular, depending on the value of fmt, the hypergraph H can have weights on either the hyperedges, the vertices, or both. In the case that H is unweighted (i.e., all the hyperedges and vertices have the same weight), fmt is omitted. 10 After this first line, the remaining |Eh| lines store the vertices contained in each hyperedge–one line per hyperedge. In particular, the ith line (excluding comment lines) contains the vertices that are included in the (i −1)th hyperedge. This format is illustrated in Figure 5(a). Weighted hyperedges are specified as shown in Figure 5(b). The first integer in each line contains the weight of the respective hyperedge. Note, hyperedge weights are integer quantities. Furthermore, note that the fmt parameter is equal to 1, indicating the fact that H has weights on the hyperedges. Finally, weights on the vertices are also allowed, as illustrated in Figure 5(c). In this case, |V| lines are appended to the input file containing the weight of the |V| vertices. Note that the value of fmt is equal to 10. As was the case with hyperedge weights, vertex weights are integer quantities. Figure 5(d) shows the case when both the hyperedges and the vertices are weighted. fmt in this case is equal to 11. Figure 5 shows the HGraphFile expected by hMETIS for the example hypergraphs shown in the figure. It shows the four cases in which the hypergraph is unweighted, has weighted hyperedges, has weighted vertices and has both hyperedges and vertices weighted. The hypergraph shown in Figure 5(a) has four unweighted hyperedges a, b, c, and d. Number of vertices in the hypergraph is 7. When the hypergraph is unweighted, first line of the HGraphFile contains two integers denoting the number of hyperedges and the number of the vertices in the hypergraph. After that, each line corresponds to a hyperedge containing an entry for each vertex in the hyperedge. Hypergraph shown in Figure 5(b) has hyperedge weights equal to 2, 3, 7, and 8 on each of the hyperedge a, b, c, and d respectively. For this weighted hyperedges first line of the HGraphFile consists of three integers. Third integer specify that the hyperedges are weighted and is equal to 1. Each line corresponding to each hyperedge, has first entry equal to its weight. The following entries corresponds to the vertices in the respective hyperedge. The case when both the vertices are weighted fmt is equal to 10, and 7 lines corresponding to the 7 vertices are appended to the input file each containing weight of the respective vertex. This is shown in Figure 5(c). Figure 5(d) shows the case when both the hyperedges and the vertices are weighted.