The hypergraph orientation problem with vertex constraints

In computational biology and bioinformatics, hypergraphs model metabolic pathways and networks representing compounds as vertices and reactions as hyperedges. In a previous work we considered the problem of assigning a direction to the hyperedges of a hypergraph minimizing the number of source and sink vertices. We proved that this problem is NP-hard and that it is polynomial-time solvable on graphs. In a more general setting, a compound can be a source or a sink in a particular metabolic pathway but, in the context of a metabolic network, it may become both a sink of one pathway and a source of another pathway (an internal vertex). Therefore, in the present work we address a more general form of the hypergraph orientation problem in which some vertices are constrained to be a source, a sink, or an internal vertex. We prove that it remains polynomial-time solvable on graphs by giving a linear-time algorithm. We propose a polynomial-size ILP formulation of the problem, which, applied to the biochemical reactions stored in the Kyoto Encyclopedia of Genes and Genomes (KEGG) database, shows that metabolic pathways and networks, and random hypergraphs with thousands of vertices and hyperedges, can be oriented in a few seconds on a personal computer.