Exploiting bounded signal flow for graph orientation based on cause–effect pairs

We take the viewpoint of parameterized algorithmics and examine several parameters related to the maximum signal flow over vertices or edges. We provide several fixed-parameter tractability results, and in one case a sharp complexity dichotomy between a linear-time solvable case and a slightly more general NP-hard case. We examine the value of these parameters for several real-world network instances.Several biologically relevant special cases of the NP-hard problem can be solved to optimality. In this way, parameterized analysis yields both deeper insight into the computational complexity and practical solving strategies.Current technologies [1] like two-hybrid screening can find protein interactions, leading to protein-protein interaction (PPI) networks, but cannot decide the direction of the interaction. This can be complemented by gene knock-out experiments which constitute a way to determine causal relations in these networks, thus providing additional information on possible directions of information flow in them [2]. Given a list of so-called cause–effect pairs, the challenge consists in deducing an orientation of the PPI network which takes into account the causal relations of as many of these pairs as possible. Medvedovsky et al. [3] formalize this in terms of a graph theoretical problem as follows.Let G = (V, E) be an undirected graph. An orientation G → of G is a directed graph G → = (V, E → ) obtained from G by replacing every undirected edge {u, v} ∈ E by a directed one, i. e., either by (u, v) ∈ E → or by (v, u) ∈ E → . Let P ？ V × V be a set of ordered source–target pairs, which we sometimes refer to as "signals". In order to distinguish pairs from edges or arcs, we use the notation [a, b] ∈ P to denote the pair starting in a and ending in b. We say that a pair [a, b] ∈ P is satisfied by a given orientation G → if there exists a directed path from a to b in G → . The central problem considered in this work is to find an ori