<p>Here's an argument that falls a bit short of NP-hardness, but gives strong evidence that we shouldn't expect a polynomial time algorithm, even in the case when the graph is a star.</p>
<p>Theorem 1: If there's a polynomial time algorithm for deciding if at most <span class="math-container">$3$</span> orientations suffice, then there's a polynomial time algorithm that, given a graph <span class="math-container">$G$</span>, correctly concludes either <span class="math-container">$\chi(G) &gt; 3$</span> or <span class="math-container">$\chi(G) \le 6$</span>, where <span class="math-container">$\chi(G)$</span> is the chromatic number of <span class="math-container">$G$</span>.</p>
<p>Before going to the proof of Theorem 1, let me note that such an approximate <span class="math-container">$3$</span>-coloring algorithm would violate the &quot;<span class="math-container">$d$</span>-to-<span class="math-container">$1$</span>-conjecture&quot; in the literature of approximation algorithms (see <a href="https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.62" rel="noreferrer">https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.62</a>).</p>
<p>Proof of Theorem 1: First, let's define &quot;Directed edge <span class="math-container">$3$</span>-coloring&quot; as the problem where we are given a directed graph, and we wish to color its edges with at most three colors, so that there is no vertex with an incoming and an outgoing edge of the same color. It is quite straightforward to observe that the original problem, in the case when the graph is a star and we ask if at most <span class="math-container">$3$</span> orientations suffice, is equivalent to Directed edge <span class="math-container">$3$</span>-coloring: The leaves of the star correspond to the vertices of the directed graph, and the demand pairs correspond to the edges of the directed graph. Therefore, assuming a polynomial time algorithm for deciding if <span class="math-container">$3$</span> orientations suffice, we get a polynomial time algorithm for Directed edge <span class="math-container">$3$</span>-coloring.</p>
<p>Now, let's use this algorithm to construct our approximate <span class="math-container">$3$</span>-coloring algorithm. Our reduction is simple: Given an undirected graph <span class="math-container">$G = (V,E)$</span>, we turn it into a directed graph <span class="math-container">$D = (V,F)$</span> by adding for each edge directed edges in both directions.</p>
<p>Claim 1: If <span class="math-container">$\chi(G) \le 3$</span>, then <span class="math-container">$D$</span> has a directed edge <span class="math-container">$3$</span>-coloring.</p>
<p>Proof of Claim 1: Given a <span class="math-container">$3$</span>-coloring of <span class="math-container">$G$</span>, for each color class <span class="math-container">$i$</span>, color the edges of <span class="math-container">$D$</span> leaving the vertices of <span class="math-container">$i$</span> with the the color <span class="math-container">$i$</span>.</p>
<p>Claim 2: If <span class="math-container">$D$</span> has a directed edge <span class="math-container">$3$</span>-coloring, then <span class="math-container">$\chi(G) \le 6$</span>.</p>
<p>Proof of Claim 2: Consider a directed edge <span class="math-container">$3$</span>-coloring of <span class="math-container">$D$</span>. It must be that for every vertex <span class="math-container">$v$</span>, either all outgoing edges are colored with the same color, or all incoming edges are colored with the same color. This is because if both outgoing and incoming edges would have at least two different colors, there would be a color with both incoming and outgoing edges, which was not allowed. Now we can classify vertices into <span class="math-container">$6$</span> types: For each color <span class="math-container">$i$</span>, we have the types of &quot;all incoming edges are color <span class="math-container">$i$</span>&quot; and &quot;all outgoing edges are color <span class="math-container">$i$</span>&quot; (if a vertex satisfies multiple of these, pick one arbitrarily). We then observe that the vertices of each type must form an independent set, so the types form a <span class="math-container">$6$</span>-coloring of <span class="math-container">$G$</span>.</p>
<p>Now Claims 1 and 2 imply that if there's a directed edge <span class="math-container">$3$</span>-coloring of <span class="math-container">$D$</span>, we may return <span class="math-container">$\chi(G) \le 6$</span>, and if not, we may return <span class="math-container">$\chi(G) &gt; 3$</span>. This finishes the proof of Theorem 1.</p>
<p>I would conjecture that in fact, directed edge <span class="math-container">$3$</span>-coloring would be NP-hard, and hope that this approach with a bit more clever analysis would be able to prove it.</p>

CC BY-SA 4.0
2024-08-19T20:44:16.703Z
2024-08-19T20:44:16.703Z
Laakeri
<p>This problem is belongs to a family of problems referred to as Maximum (Undirected) Graph Orientation problem or similarly.
It was described for example by Medvedovsky et al. [1]
who also observed that the general case is reducible to trees.</p>
<p>Medvedovsky et al. [1] thus focused on the tree case, defined as follows.</p>
<p><strong>Maximum Tree Orientation</strong></p>
<p><strong>Input:</strong> An undirected tree <span class="math-container">$T=(V,E)$</span> and a set <span class="math-container">$P$</span> of ordered pairs of vertices.</p>
<p><strong>Task:</strong> Find an orientation of <span class="math-container">$T$</span> that maximizes the number of pairs in <span class="math-container">$P$</span> that are satisfied, where a pair <span class="math-container">$(u,v)$</span> is satisfied by an orientation if the orientation contains a <span class="math-container">$(u,v)$</span>-path.</p>
<p>Medvedovsky et al. showed that the problem is NP-hard on trees and polynomial-time solvable on paths.</p>
<p>Further work showed that the problem can be solved</p>
<ul>
<li>in polynomial time if <span class="math-container">$P$</span> contains all possible vertex pairs, that is, <span class="math-container">$P=V\times V$</span> [2],</li>
<li>in <span class="math-container">$1.28^k+n^{O(1)}$</span> time when we ask for an orientation that satisfies at least <span class="math-container">$|P|-k$</span> pairs (via reduction to <strong>Vertex Cover</strong>) [3],</li>
<li>in <span class="math-container">$O(2^{mv} \cdot |P | + n^4)$</span> time on an
<span class="math-container">$n$</span>-vertex tree, where <span class="math-container">$mv$</span> denotes the maximum number of input vertex pairs over any tree vertex [3].</li>
</ul>
<p>On the practical side, Silverbush et al. [4] describe an ILP formulation and Dorn et al. [2] have an extended discussion about practical algorithms for the problem, in particular those that use reduction to <strong>Vertex Cover</strong>.</p>
<p>[1] Alexander Medvedovsky, Vineet Bafna, Uri Zwick, Roded Sharan:
An Algorithm for Orienting Graphs Based on Cause-Effect Pairs and Its Applications to Orienting Protein Networks. WABI 2008: 222-232</p>
<p>[2] S. Louis Hakimi, Edward F. Schmeichel, Neal E. Young:
Orienting Graphs to Optimize Reachability. Inf. Process. Lett. 63(5): 229-235 (1997)</p>
<p>[3] Britta Dorn, Falk Hüffner, Dominikus Krüger, Rolf Niedermeier, Johannes Uhlmann: Exploiting bounded signal flow for graph orientation based on cause-effect pairs. Algorithms Mol. Biol. 6: 21 (2011)</p>
<p>[4] Dana Silverbush, Michael Elberfeld, Roded Sharan:
Optimally Orienting Physical Networks. J. Comput. Biol. 18(11): 1437-1448 (2011)</p>

CC BY-SA 4.0
2024-08-14T13:28:01.670Z
[1] cleanly answers the maximization question. Shows APX-hardness and also gives an $O(\log n)$ approximation. However, they do not rule out obtaining an $O(1)$-approximation. An $\alpha$-approximation for the maximization problem easily implies an $O(\alpha \log n)$-approximation for the coloring problem that the OP asked. The coloring question is likely to be NP-Hard but a formal proof is required. And whether one can obtain a better than $O(\log^2 n)$-approximation is also interesting.
Chandra Chekuri
CC BY-SA 4.0
2024-08-14T12:32:54.917Z
2024-08-17T22:26:17.940Z
2024-08-17T22:26:17.940Z
Christian Komusiewicz
<p>I would like to ask about an approach to find the min. number of edge orientations to ensure that a specific subset of nodes (between which demand exists) in a weighted undirected graph is eventually connected.</p>
<p>In the example, I have an undirected graph with 5 nodes and assume there is demand between (A, E), (B, C) and (E, A). The minimum number of edge orientations would be 2 in this case.</p>
<p>I can solve this with ILP by first generating a set of k-shortest paths for each node pair (where demand is not 0) and then minimising routing cost and the number of edge orientations. The constraints ensure that paths do not conflict. I was wondering if there is a better approach.
Thanks for any resources!</p>
<p><a href="https://i.sstatic.net/DdKGiLS4.png" rel="noreferrer"><img src="https://i.sstatic.net/DdKGiLS4.png" alt="enter image description here" /></a></p>

CC BY-SA 4.0
2024-08-11T13:54:13.387Z
The description of the problem is not complete. Please edit for clarity and precision, and if possible, also provide examples and motivation.
Chandra Chekuri
CC BY-SA 4.0
2024-08-11T19:53:47.230Z
Thank you for the answer. I edited my post.
L. Wallet
CC BY-SA 4.0
2024-08-11T21:55:23.613Z
Note that it suffices to solve the problem for trees: if your graph is not a tree, you can find bi-connected components, and you can always orient edges in bi-connected components to make them strongly-connected component. After condensing the bi-connected components, you are left with a tree. That said, it's not clear how to handle trees, and I suspect that it might be NP-hard even for a star graph.
Dmitry
CC BY-SA 4.0
2024-08-11T23:11:31.797Z
I still don't understand the problem.
Chandra Chekuri
CC BY-SA 4.0
2024-08-12T02:25:20.947Z
Here's a guess at OP's problem.  Given an undirected graph $G=(V, E)$ and a collection $P$ of ordered pairs of vertices, find a minimum number of orientations of $G$ such that, for every pair $(u, w)\in P$, at least one of the orientations has a directed path from $u$ to $w$.  Here an *orientation* of $G$ is any directed graph that can be obtained from $G$ by assigning a direction to each edge.
Neal Young
CC BY-SA 4.0
2024-08-12T07:31:02.227Z
That's it. Thank you very much for formulating it.
L. Wallet
CC BY-SA 4.0
2024-08-12T15:46:15.537Z
Ok, got the problem now. As Dmitry noted, it seems reducible to trees. A related question may be useful to think about. On a tree, what is an orientation that maximizes the number of pairs that are "connected" in that orientation. Is it solvable efficiently? This would give a heuristic for the number of orientations needed and seems independently interesting.
Chandra Chekuri
CC BY-SA 4.0
2024-08-16T18:04:52.857Z
My intuition tells me that distinguishing between case when the min is 1 and cases where the min is 2 is already NP hard
ULechine
CC BY-SA 4.0
2024-08-17T22:35:31.750Z
Distinguishing 1 vs 2 is easy. Once we reduce to a tree there is a unique path for each demand so we just connect along that path orienting the edges along the right direction. If there are no conflicts on any edge (that is, an edge needs to be oriented in opposite directions due to different demands) then 1 suffices, otherwise we need at least 2.
Chandra Chekuri
<graph-algorithms>
Orientations of an undirected graph
L. Wallet
# Orientations of an undirected graph

(Asked by: username_0 on 2024-08-11)

I would like to ask about an approach to find the min. number of edge orientations to ensure that a specific subset of nodes (between which demand exists) in a weighted undirected graph is eventually connected.

In the example, I have an undirected graph with 5 nodes and assume there is demand between (A, E), (B, C) and (E, A). The minimum number of edge orientations would be 2 in this case.

I can solve this with ILP by first generating a set of k-shortest paths for each node pair (where demand is not 0) and then minimising routing cost and the number of edge orientations. The constraints ensure that paths do not conflict. I was wondering if there is a better approach.
Thanks for any resources!

[![enter image description here](https://i.sstatic.net/DdKGiLS4.png)](https://i.sstatic.net/DdKGiLS4.png)

**Tags:** graph-algorithms

> **Comments:**
> **username_1**: The description of the problem is not complete. Please edit for clarity and precision, and if possible, also provide examples and motivation.  
> **username_0**: Thank you for the answer. I edited my post.  
> **username_2**: Note that it suffices to solve the problem for trees: if your graph is not a tree, you can find bi-connected components, and you can always orient edges in bi-connected components to make them strongly-connected component. After condensing the bi-connected components, you are left with a tree. That said, it's not clear how to handle trees, and I suspect that it might be NP-hard even for a star graph.  
> **username_1**: I still don't understand the problem.  
> **username_3**: Here's a guess at OP's problem.  Given an undirected graph $G=(V, E)$ and a collection $P$ of ordered pairs of vertices, find a minimum number of orientations of $G$ such that, for every pair $(u, w)\in P$, at least one of the orientations has a directed path from $u$ to $w$.  Here an *orientation* of $G$ is any directed graph that can be obtained from $G$ by assigning a direction to each edge.  
> **username_0**: That's it. Thank you very much for formulating it.  
> **username_1**: Ok, got the problem now. As username_2 noted, it seems reducible to trees. A related question may be useful to think about. On a tree, what is an orientation that maximizes the number of pairs that are "connected" in that orientation. Is it solvable efficiently? This would give a heuristic for the number of orientations needed and seems independently interesting.  
> **username_4**: My intuition tells me that distinguishing between case when the min is 1 and cases where the min is 2 is already NP hard  
> **username_1**: Distinguishing 1 vs 2 is easy. Once we reduce to a tree there is a unique path for each demand so we just connect along that path orienting the edges along the right direction. If there are no conflicts on any edge (that is, an edge needs to be oriented in opposite directions due to different demands) then 1 suffices, otherwise we need at least 2.  

---

## 2 answers

### Answer by username_6 on 2024-08-14. Score: 9 | Accepted answer

This problem is belongs to a family of problems referred to as Maximum (Undirected) Graph Orientation problem or similarly.
It was described for example by Medvedovsky et al. [1]
who also observed that the general case is reducible to trees.

Medvedovsky et al. [1] thus focused on the tree case, defined as follows.

**Maximum Tree Orientation**

**Input:** An undirected tree $T=(V,E)$ and a set $P$ of ordered pairs of vertices.

**Task:** Find an orientation of $T$ that maximizes the number of pairs in $P$ that are satisfied, where a pair $(u,v)$ is satisfied by an orientation if the orientation contains a $(u,v)$-path.

Medvedovsky et al. showed that the problem is NP-hard on trees and polynomial-time solvable on paths.

Further work showed that the problem can be solved

* in polynomial time if $P$ contains all possible vertex pairs, that is, $P=V\times V$ [2],
* in $1.28^k+n^{O(1)}$ time when we ask for an orientation that satisfies at least $|P|-k$ pairs (via reduction to **Vertex Cover**) [3],
* in $O(2^{mv} \cdot |P | + n^4)$ time on an
  $n$-vertex tree, where $mv$ denotes the maximum number of input vertex pairs over any tree vertex [3].

On the practical side, Silverbush et al. [4] describe an ILP formulation and Dorn et al. [2] have an extended discussion about practical algorithms for the problem, in particular those that use reduction to **Vertex Cover**.

[1] Alexander Medvedovsky, Vineet Bafna, Uri Zwick, Roded Sharan:
An Algorithm for Orienting Graphs Based on Cause-Effect Pairs and Its Applications to Orienting Protein Networks. WABI 2008: 222-232

[2] S. Louis Hakimi, Edward F. Schmeichel, Neal E. Young:
Orienting Graphs to Optimize Reachability. Inf. Process. Lett. 63(5): 229-235 (1997)

[3] Britta Dorn, Falk Hüffner, Dominikus Krüger, Rolf Niedermeier, Johannes Uhlmann: Exploiting bounded signal flow for graph orientation based on cause-effect pairs. Algorithms Mol. Biol. 6: 21 (2011)

[4] Dana Silverbush, Michael Elberfeld, Roded Sharan:
Optimally Orienting Physical Networks. J. Comput. Biol. 18(11): 1437-1448 (2011)

> **Comments:**
> **username_1**: [1] cleanly answers the maximization question. Shows APX-hardness and also gives an $O(\log n)$ approximation. However, they do not rule out obtaining an $O(1)$-approximation. An $\alpha$-approximation for the maximization problem easily implies an $O(\alpha \log n)$-approximation for the coloring problem that the OP asked. The coloring question is likely to be NP-Hard but a formal proof is required. And whether one can obtain a better than $O(\log^2 n)$-approximation is also interesting.  

---

### Answer by username_5 on 2024-08-19. Score: 6

Here's an argument that falls a bit short of NP-hardness, but gives strong evidence that we shouldn't expect a polynomial time algorithm, even in the case when the graph is a star.

Theorem 1: If there's a polynomial time algorithm for deciding if at most $3$ orientations suffice, then there's a polynomial time algorithm that, given a graph $G$, correctly concludes either $\chi(G) > 3$ or $\chi(G) \le 6$, where $\chi(G)$ is the chromatic number of $G$.

Before going to the proof of Theorem 1, let me note that such an approximate $3$-coloring algorithm would violate the "$d$-to-$1$-conjecture" in the literature of approximation algorithms (see <https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.62>).

Proof of Theorem 1: First, let's define "Directed edge $3$-coloring" as the problem where we are given a directed graph, and we wish to color its edges with at most three colors, so that there is no vertex with an incoming and an outgoing edge of the same color. It is quite straightforward to observe that the original problem, in the case when the graph is a star and we ask if at most $3$ orientations suffice, is equivalent to Directed edge $3$-coloring: The leaves of the star correspond to the vertices of the directed graph, and the demand pairs correspond to the edges of the directed graph. Therefore, assuming a polynomial time algorithm for deciding if $3$ orientations suffice, we get a polynomial time algorithm for Directed edge $3$-coloring.

Now, let's use this algorithm to construct our approximate $3$-coloring algorithm. Our reduction is simple: Given an undirected graph $G = (V,E)$, we turn it into a directed graph $D = (V,F)$ by adding for each edge directed edges in both directions.

Claim 1: If $\chi(G) \le 3$, then $D$ has a directed edge $3$-coloring.

Proof of Claim 1: Given a $3$-coloring of $G$, for each color class $i$, color the edges of $D$ leaving the vertices of $i$ with the the color $i$.

Claim 2: If $D$ has a directed edge $3$-coloring, then $\chi(G) \le 6$.

Proof of Claim 2: Consider a directed edge $3$-coloring of $D$. It must be that for every vertex $v$, either all outgoing edges are colored with the same color, or all incoming edges are colored with the same color. This is because if both outgoing and incoming edges would have at least two different colors, there would be a color with both incoming and outgoing edges, which was not allowed. Now we can classify vertices into $6$ types: For each color $i$, we have the types of "all incoming edges are color $i$" and "all outgoing edges are color $i$" (if a vertex satisfies multiple of these, pick one arbitrarily). We then observe that the vertices of each type must form an independent set, so the types form a $6$-coloring of $G$.

Now Claims 1 and 2 imply that if there's a directed edge $3$-coloring of $D$, we may return $\chi(G) \le 6$, and if not, we may return $\chi(G) > 3$. This finishes the proof of Theorem 1.

I would conjecture that in fact, directed edge $3$-coloring would be NP-hard, and hope that this approach with a bit more clever analysis would be able to prove it.


---

