jeudi 5 mars 2026

par BUTEL Nathalie

Florian Hörsch, chercheur postdoctoral au CISPA, Saarbrücken, Germany, donnera un séminaire, en visioconférence, le jeudi 5 mars 2026 à 10h30 au Centre Inria d'Université Côte d'Azur dans la salle Euler Violet.

 

TITLE : 

Maximum Reachability Orientation of Mixed Graphs 

ABSTRACT : 

We aim to find orientations of mixed graphs optimizing the total reachability, a problem that has applications in causality and biology. For given a digraph D, we use P(D) for the set of ordered pairs of distinct vertices in V(D) and we define $\kappa_D:P(D)\rightarrow \{0,1\}$ by $\kappa_D(u,v)=1$ if v is reachable from u in D, and $\kappa_D(u,v)=0$, otherwise. We use $R(D)=\sum_{(u,v)\in P(D)}\kappa_D(u,v)$. Now, given a mixed graph G, we aim to find an orientation $\vec{G}$ of G that maximizes $R(\vec{G})$. We show that this problem is NP-hard and APX-hard, answering a question Hakimi, Schmeichel and Young. The problem being polynomial time solvable in undirected graphs, we consider the parameterized complexity of the problem with respect to the number k of preoriented arcs of G. We show that the problem can be solved in time $n^{O(k)}$ and that a $(1-\epsilon)$-approximation can be computed in time $f(k,\epsilon)n^{O(1)}$ for any $\epsilon > 0$.