Realizing symmetric set functions as hypergraph cut capacity

In this paper, we focus on the case of undirected hypergraphs, which was not dealt with in the previous work of Fujishige and Patkar. For this case, Grishuhin (1989) had given a set of hyperedges forming a basis of the cut realization of symmetric set functions. By using the Möbius inversion formula together with Grishuhin's basis, we extend a result of Fujishige and Patkar for the case of undirected graphs to hypergraphs. We also clarify the kernel of the cut realization, which leads to other interesting bases and an alternative proof of Grishuhin's result. In addition, we provide a new necessary condition for the cut realization by undirected hypergraphs with nonnegative capacity.