On the Parameterized Complexity of Computing $st$-Orientations with Few Transitive Edges

Carla Binucci, Giuseppe Liotta, Fabrizio Montecchiani +2

Orienting the edges of an undirected graph such that the resulting digraph satisfies some given constraints is a classical problem in graph theory, with multiple algorithmic applic…