Maximum Reachability Orientation of Mixed Graphs
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915507610845184 |
|---|---|
| author | Hörsch, Florian |
| author_facet | Hörsch, Florian |
| contents | 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 $κ_D:P(D)\rightarrow \{0,1\}$ by $κ_D(u,v)=1$ if $v$ is reachable from $u$ in $D$, and $κ_D(u,v)=0$, otherwise. We use $R(D)=\sum_{(u,v)\in P(D)}κ_D(u,v)$.
Now, given a mixed graph $G$, we aim to find an orientation $\vec{G}$ of $G$ that maximizes $R(\vec{G})$. Hakimi, Schmeichel, and Young proved that the problem can be solved in polynomial time when restricted to undirected inputs. They inquired about the complexity in mixed graphs.
We answer this question by showing that this problem is NP-hard, and, moreover, APX-hard.
We then develop a finer understanding of how quickly the problem becomes difficult when going from undirected to mixed graphs. To this end, we consider the parameterized complexity of the problem with respect to the number $k$ of preoriented arcs of $G$, a poorly understood form of parameterization.
We show that the problem can be solved in time $n^{O(k)}$ and that a $(1-ε)$-approximation can be computed in time $f(k,ε)n^{O(1)}$ for any $ε> 0$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_16171 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Maximum Reachability Orientation of Mixed Graphs Hörsch, Florian Computational Complexity Discrete Mathematics 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 $κ_D:P(D)\rightarrow \{0,1\}$ by $κ_D(u,v)=1$ if $v$ is reachable from $u$ in $D$, and $κ_D(u,v)=0$, otherwise. We use $R(D)=\sum_{(u,v)\in P(D)}κ_D(u,v)$. Now, given a mixed graph $G$, we aim to find an orientation $\vec{G}$ of $G$ that maximizes $R(\vec{G})$. Hakimi, Schmeichel, and Young proved that the problem can be solved in polynomial time when restricted to undirected inputs. They inquired about the complexity in mixed graphs. We answer this question by showing that this problem is NP-hard, and, moreover, APX-hard. We then develop a finer understanding of how quickly the problem becomes difficult when going from undirected to mixed graphs. To this end, we consider the parameterized complexity of the problem with respect to the number $k$ of preoriented arcs of $G$, a poorly understood form of parameterization. We show that the problem can be solved in time $n^{O(k)}$ and that a $(1-ε)$-approximation can be computed in time $f(k,ε)n^{O(1)}$ for any $ε> 0$. |
| title | Maximum Reachability Orientation of Mixed Graphs |
| topic | Computational Complexity Discrete Mathematics |
| url | https://arxiv.org/abs/2506.16171 |