<p>I have a DAG like this</p>

<p>$G_1 = \lbrace A \to B \to C \rbrace$</p>

<p>My algorithm modify $G_1$ so it will be like this</p>

<p>$ G_2 = \lbrace A \to C, B \to C \rbrace $</p>

<p>I now that $G_2$ is not a transitive reduction of $G_1$. How it is called this operation?</p>

<p>Thanks in advance</p>

<p><strong>EDIT</strong>: basically, $G_2$ contains the edge $(a, b)$ of $G_1$ if and only if $b$ is a sink node and exist a path between $a$ and $b$.</p>

CC BY-SA 3.0
2015-01-26T09:55:49.923Z
You need to define the operation more formally. For example, what happens if I apply it on $A\to B\to C\to D?$. Do you wish to create a graph with no paths on 3 vertices?
R B
CC BY-SA 3.0
2015-01-26T10:34:49.450Z
Thanks for the reply, look at my edit. I hope is more clear now. In your examples, the result graph will be $\lbrace A \to D, B \to D, C \to D \rbrace$.
Alberto
CC BY-SA 3.0
2015-01-26T10:38:13.610Z
So, basically, $G_2$ is a set of sinks and a set of vertices that points to them, without any 3-path in the graph. I don't think this has a standard name, but I think the question is better suited for [math.se](http://math.stackexchange.com/).
R B
<graph-theory><graph-algorithms>
DAG reduce edges by transitivity
Alberto
# DAG reduce edges by transitivity

(Asked by: username_0 on 2015-01-26)

I have a DAG like this

$G\_1 = \lbrace A \to B \to C \rbrace$

My algorithm modify $G\_1$ so it will be like this

$ G\_2 = \lbrace A \to C, B \to C \rbrace $

I now that $G\_2$ is not a transitive reduction of $G\_1$. How it is called this operation?

Thanks in advance

**EDIT**: basically, $G\_2$ contains the edge $(a, b)$ of $G\_1$ if and only if $b$ is a sink node and exist a path between $a$ and $b$.

**Tags:** graph-theory, graph-algorithms
> **Comments:**
> **username_1**: You need to define the operation more formally. For example, what happens if I apply it on $A\to B\to C\to D?$. Do you wish to create a graph with no paths on 3 vertices?  
> **username_0**: Thanks for the reply, look at my edit. I hope is more clear now. In your examples, the result graph will be $\lbrace A \to D, B \to D, C \to D \rbrace$.  
> **username_1**: So, basically, $G_2$ is a set of sinks and a set of vertices that points to them, without any 3-path in the graph. I don't think this has a standard name, but I think the question is better suited for [math.se](http://math.stackexchange.com/).  

---

## 0 answers

