0
$\begingroup$

Given a graph $G=<E,V>$ where $E$ is the set of edges and $V$ is the set of nodes in acyclic directed graph $G$. What is the smallest set of nodes that can reach all other nodes?

Lemma 1: If there are no source nodes in the graph, then the graph contains at least one cycle.

Approach#1: source nodes that has no incoming edges can reach all nodes in the graph. Now, this is rough claim that I want to prove myself. I found that this indeed works as we only need to start with all source nodes in order to visit all other nodes and that would indeed give us the minimum set of vertices that answer the question.

Proof of Lemma 1:

Assume there are no source nodes in the graph. This implies that every node in the graph has at least one incoming edge (in-degree > 0).

Let's perform a depth-first search (DFS) on the graph starting from any node v.

During the DFS traversal, we visit each adjacent node u of v.

  • Case 1: If u has already been visited in the current DFS traversal, then there exists a back edge from u to v, which forms a cycle.

    Case 2: If u has not been visited in the current DFS traversal, we recursively continue the DFS traversal from u.

Since the graph is acyclic, the DFS traversal cannot enter an already visited node, so Case 1 will always be encountered. Therefore, we can conclude that there is at least one cycle in the graph.

Lemma 2: If we select all the source nodes in the graph, we can reach all other nodes in the graph without creating a cycle.

Proof of Lemma 2:

Assume we select all the source nodes in the graph.

Since the source nodes have 0 incoming edges, we can start traversing the graph from each source node.

During the traversal, we move from one node to another using directed edges.

Since the graph is acyclic, there is no way to encounter a cycle during the traversal because there are no back edges or cycles in the graph.

Therefore, by starting from the source nodes and traversing the graph using directed edges, we can reach all other nodes without creating a cycle.

Theorem: The smallest set of vertices that can reach all vertices in the graph are the source nodes (nodes with 0 incoming degrees).

Proof of Theorem:

From Lemma 1, if there are no source nodes in the graph, then the graph contains at least one cycle.

From Lemma 2, if we select all the source nodes, we can reach all other nodes without creating a cycle.

Therefore, in order to have a graph without cycles, we must select the source nodes.

Additionally, since the source nodes are the nodes with 0 incoming degrees and form the smallest set of vertices, they are the optimal solution to the problem. Hence, the smallest set of vertices that can reach all vertices in the graph are the source nodes (nodes with 0 incoming degrees), and this completes the proof.

Question: I am trying to construct mathematical proof for it, but I guess the proof above is not formal, so if you can help me make it more formal.

$\endgroup$

1 Answer 1

1
$\begingroup$

Proof of Lemma 1: Assume there is no source node. Take any node $v_1$. Because it is not a source node, there is a node $v_2$ such that $v_1v_2 \in E$. As $v_2$ is not a source there exist $v_3$ such that (...). Repeat until $v_{|V|+1}$. By the pigeon hole principle, there must be $i< j$ such that $v_i = v_j$, thus $v_j\dots v_i$ is a cycle.

The current formulation of lemma 2 is unclear and I don't understand why you need it to prove the final result. Instead consider the following lemma:

Lemma 3: $\forall v \in V$, there exists $s$ a source and a path from $s$ to $v$. Proof: If $v$ is a source, nothing has to be done. Otherwise, consider any $v_1$ such that $v_1 v \in E$. If $v_1$ is a source, we are done. Otherwise, consider $v_2$ (...). Stop at $v_{|V|-1}$: it is necessarily a source, otherwise by lemma 1 the graph is not acyclic.

Proof of the theorem: let $k$ be the number of sources and $opt(G)$ our objective (aka we want to prove that $k=opt(G)$). Clearly $opt(G) \ge k$ as any set reaching all the vertices reach necessarily the sources. By lemma 3, selecting the sources allows us to reach all the nodes, thus $opt(G) \le k$.

$\endgroup$
5
  • $\begingroup$ Thank you. What do you mean by $v_{|V|+1}$? Also , can you please elaborate more what is meant by ," there must be $i< j$ such that $v_i = v_j$, thus $v_j\dots v_i$ is a cycle." For example, v1...v4 v5, then v4 = v5 means there have the same edge? $\endgroup$
    – Avv
    Commented Aug 4, 2023 at 13:08
  • $\begingroup$ 1. $|V|$ is the number of vertices. You stop doing this procedure at $v_{|V|+1}$ because you have enumerated enough vertices to make the argument (which is usually pigeon hole principle) $\endgroup$
    – Qise
    Commented Aug 4, 2023 at 17:18
  • $\begingroup$ 2. I suppose $v_4 = v_5$ would be impossible if you forbid self loops to exist. An other example: say you did the procedure up to $v_8$ and found out that $v_3 = v_8$. then $v_8 v_7 v_6 v_5 v_4 v_8$ is a cycle. $\endgroup$
    – Qise
    Commented Aug 4, 2023 at 17:21
  • $\begingroup$ v4=v5 means v4 is connected to v5 via an edge please? $\endgroup$
    – Avv
    Commented Aug 4, 2023 at 22:10
  • $\begingroup$ $v_4 = v_5$ means there's an edge from $v_4$ to $v_4$. $\endgroup$
    – Qise
    Commented Aug 5, 2023 at 14:14

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .