Hot answers tagged

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 ...


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 ...


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 ...


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_\...


2

This is the classical problem of chain decomposition of partially ordered set (poset), in the sense that they can be reduced to each other very easily. Any directed acyclic graph (DAG) $G(V,E)$ defines a poset $P(V, \preceq)$ naturally by $u\preceq v$ for any pair of vertices $(u,v)$ such that there is a path from $u$ to $v$ in $G$. A path (which is named ...


2

When you get a question about a DAG, the first thing to do is a topological sort. Now, go through all vertexes in order. For each vertex $v$, keep all the possible costs of a path from $s$ to $v$; there will be no more than $3V$ distinct costs. For each edge $e(v,u)$, add to $u$ the costs of $v$ + the weight of $e$.


2

Yes it exists and the existence of a linear ordering not only shows the existence of the topological oredering over the vertices but also that this ordering is unique. It is not hard to prove that the graph represents a linear ordering using the facts that the graph is complete and acyclic. That should be a good exercise for you (proving a relation is a ...


1

I guess this optimality depends on how you define "the least replacement solution". I'm taking it to mean minimum insertions / deletions. If you prefer minimum number of swaps necessary, take a look at step 4.1 and 4.2 and you may be able to optimize it for such, though I don't show it here. If it is ensured that no additional $x_k$ and its partial ...


1

Your proposed approach doesn't work. For some directed graphs there is no single vertex you can split to turn it into a DAG. An algorithm only qualifies as a solution to the Hamiltonian Cycle problem if it solves the problem for all graphs. It's not enough to solve the problem for a subset of "easy" graphs.


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