# Tag Info

8

We can solve this problem just by doing DFS from each vertex. For each vertex $u \in G$, start the DFS from each vertex $v$ such that $v$ is the direct descendant of $u$, ie. $(u,v)$ is an edge. For each vertex $v'$ reachable by the DFS from $v$, remove the edge $(u, v')$. The overall complexity of the above is the complexity of running $N$ DFS', which ...

6

Here is a dynamic programming algorithm. Given a graph $G = (V, E)$ and two vertices $u, v \in V$. We define the recursive function $C:V\rightarrow \mathbb{N}$, such that $C(w)$ is the number of paths from $w$ to $v$. Note that we are looking for the value of $C(u)$. We set $C(v) = 1$ and $C(w)=0$ for each vertex $w \neq v$ with out-degree equal to zeroo. ...

5

The acronym DAG stands for directed acyclic graph. In other words, a DAG is a (finite) digraph without directed cycles. A digraph is a DAG if and only if it has a topological ordering. In your example you have a labeled DAG. The labels do not constitute a topological ordering of the DAG, but the underlying digraph is still a DAG.

5

Dec. 14, 2018 Standard approach and a heuristic alternative Standard approach -- use graph and distance product We note that transitive reduction is reduceable to transitive closure and vice versa both in additional time in $O(n ^ 2)$. Then, we know that if we can solve transitive closure in $O(n ^ 2 \cdot \textrm{polylog}(n))$ time, then we can also ...

4

Consider the following graph $G = (V, E)$ where $$V = \{1, 2, 3\}, E = \{(1, 3), (2, 3)\}.$$ If your example started at $1$, it will add $3$ to the list and then it will add $1$. In the next step the algorithm will choose $2$ as an unvisited vertex, which has an edge to a visited vertex $3$. Hence, It will conclude that the graph is not a DAG. However, the ...

4

Asympotically, you'll need $\Theta(n^2 \log n)$ comparisons. Suppose $x_{(1)},\dots,x_{(n)}$ denotes the elements in sorted order. Then if you don't see a comparison between $x_{(1)}$ and $x_{(2)}$, you will have no way to tell which order they should appear in. The same is true of every pair of adjacent element. So, there are $n-1$ coupons (one per ...

4

Kind of. But we're going to use the usual computer sciency way of describing this, using the language of binary relations. You're probably already familiar with binary relations, like equality $=$, less-than-or-equal-to $\le$, subset $\subseteq$, and so on. In general, a binary relation $R$ over a set $X$ is a subset $R \subseteq X \times X$. If $(x,y) \in ... 4 Hint: find a topological ordering, and for each vertex$v$, in the topological ordering, compute (the score of) the path with the highest score that ends at$v$. 3 First, remove all vertices whose degree is greater than 2 (i.e., their degree was greater than 2 in the original graph). The result is a smaller DAG. This can be done in linear time. Now, find the longest path in the resulting DAG. This can be done in linear time, too; see https://en.wikipedia.org/wiki/Longest_path_problem. 3 Not what you are looking for. But just for the purpose sharing knowledge, you can do that with$O(|E|)$messages if you assume that each vertex to act as a processor. Note each vertex has a comparable value. Therefore, there exists some vertices such that they are larger than all their neighbors. These vertices do the following: Let$u$be the maximum ... 3 Any algorithm for your problem will have to take exponential time in the worst case. However, if you're willing to live with this, there is a straightforward recursive algorithm to solve your problem. Details below. Generalizing a little bit, your problem is essentially the following: Input: a dag$G=(V,E)$, three sets$S_0,S_1,S_2 \subseteq V$of ... 3 Your problem is equivalent to counting the number of satisfying assignments for a monotone Boolean circuit. The restricted version in which the circuit is of the form$(x_{i_1} \lor x_{j_1}) \land \cdots \land (x_{i_m} \lor x_{j_m})$(where indices can repeat) is known as #Monotone-2SAT and is known to be #P-complete. This means that there is probably no ... 3 I'm not aware of any standard term. The graphs that you describe are subgraphs of the transitive closure of a tree, if that's of any help to you, but one wouldn't want to use that phrase twenty times in a paper. But... as Pål GD alludes to in a comment, every DAG on$n$vertices is a subgraph of the transitive closure of the$n$-vertex directed path. ... 3 This answer does not have a suggestion as to what existing names we might have. Rather, it is about what names are not appropriate. To be clear, the OP talks about a graph that is a rooted tree with possibly extra edges from some nodes to its descendants. Let us call this kind of graph "Clement directed acycle graph" or, in short, "Clement DAG" for the lack ... 3 I do not know about their algorithm, but the problem is easy to solve in$\mathcal{O}(V \cdot e)$time. The idea is to just do a DFS from every node to find vertices that can reach it. Normally this takes$\mathcal{O}(E)$time, but we can use the irreducible kernel we have already built to do it in$\mathcal{O}(e)$time. First note that$e \geq n-1$if the ... 2 I know of no convention; the right result depends entirely on what you want to do with the result. As an example, if you're trying to use strongly connected components to find satisfying assignments for 2SAT instances, then you likely want all the singleton cycles returned along with the larger components. But if you're just trying to find out if a graph ... 2 As far as I know, it is an open problem whether one can do significantly better (in an asymptotic sense). This is known as the reachability query problem for DAGs. You want to do some precomputation, after which you can answer queries of the form Reachable$(u,v)$(which should return true if$v$is reachable via some path from$u$, i.e., if$u$is an ... 2 This is sometimes known as a level structure, and they come up in e.g., certain algorithmic applications. 2 A DAG (or poset) is ranked or graded if it is possible to assign nodes a rank function$r$such that if$(x,y)$is a directed edge,$r(y) = r(x)+1$. We usually choose$r$so that$\min r = 0$. See for example the Wikipedia article on graded poset. 2 This doesn't hold if we flip both outgoing and incoming edges as shown by @Yuval Filmus. Here is my try of a proof by contradiction for only flipping outgoing of incoming edges (sorry if it's too informal): After flipping all incoming(outgoing) edges from vertex v in a DAG G, we get another graph that is not a DAG (it has a cycle). Since we only changed ... 2 Construct a new graph whose vertex set is the strongly connected components. Now go over all edge in the original graph, and if they connect two different strongly connected components, add the corresponding edge to the new graph if it's not already there. 2 You can compute a topological ordering of the vertices in linear time. 2$G=(V,E)$is the graph we work on. Problem 2:$\Diamond_F(reverse(G))=\Diamond_J(G)$, where$reverse(G)$reverses all the edges of G. Problem 3: This can be solved in$O(nm)$time. For each vertex$s$, find all the pairs$(s,v)\in \Diamond$in$O(m)$time. To do this and split every outgoing edge$(s,v)$with a new vertex$v'$. Namely, delete edge$(s,v)$, ... 2 Your algorithm is correct, provided that the following is a formal definition of your problem: Given a DAG$D = (V, A)$, find a minimum set$C \subseteq V$such that for every vertex$v \in V$, either$v \in C$or there exists a vertex$c \in C$such that$v$is reachable from$c$. Let's call a vertex with indegree 0 a source and any vertex set that ... 2 First, notice that your topological sort comment isn't quite right, because other nodes can be sinks than the last node in a topological sort. To your original question: Consider some path in a DAG that is not from a source to a sink. Can you show that this path can be made longer? (This implies that the longest path must be from a source to a sink.) For ... 2 Your strategy is close, but probably needs some clarification. This is essentially equivalent to finding the longest path in DAGs, which can be done easily in a few ways easiest of which, similar to what you describe: Negating edge weights and running a DAG-Shortest-Path algorithm. In your case we could implement it similar to the following (transcribed ... 2 Instead of seting a 'mark' flag; node.Marked = true; You can maintain a set of marked nodes in a hashtable or similar; hashTable[node] = true; You now have to pass the hash table around, but it's O(n) for space and O(1) to check if a node is marked. 2 Let$V_P(n)$represent the value of the optimal solution to a problem$P$with size$n$. According to Bellman equations, this value is computed from the value of the optimal solutions of its subproblems$P'$:$V_P(n) = \oplus \{v_{P'} + V_{P'}(n')\}$where$\oplus$is an operator such as$\max$,$\min$, +, ...$v_{P'}$is an operator which steps from$P$to ... 2 I think you can solve this problem by reducing it to a minimum-cost circulation problem. Let$G$be your graph. Replace each vertex$v$with two vertices$v_\text{in},v_\text{out}$; replace each edge$u \to v$into$v$with an edge$u \to v_\text{in}$and each edge$v \to w$out of$v$with an edge$v_\text{out} \to w$, and add the edge$v_\text{in} \to v_\...

Only top voted, non community-wiki answers of a minimum length are eligible