Minimizing External Vertices in Hypergraph Orientations

We introduce the problem of assigning a direction to the hyperedges of a hypergraph such that the number of source and sink vertices is minimized. We consider hypergraphs whose hyperedges are partitioned in two disjoint subsets of vertices, which will become the tail and the head of the hyperedge when oriented. We prove that the problem is NP-hard even when restricted to hypergraphs where each vertex belongs to exactly two hyperedges, and that it becomes polynomial-time solvable on graphs. We give a compact ILP formulation for the general problem, and apply it to the biochemical reactions stored in the KEGG database by representing compounds as vertices, reactions as hyperedges, and metabolic pathways and networks as hypergraphs. We provide experimental results showing that metabolic pathways and networks with thousands of compounds and reactions can be oriented in a few seconds on a personal computer.