Minimizing External Vertices in Hypergraph Orientations

GABRIEL VALIENTE; G. NASINI; ALBERTO FERRARI; VALERIA LEONI

LECTURE NOTES IN COMPUTER SCIENCE

Springer

Año: 2024

0302-9743

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.