Skip to main content
14 votes
Accepted

How to find a "short" walk that visits all vertices of a strongly connected directed graph

The answer is no. For any $n\geq 3$ consider an oriented cycle $C_n$ and let $u\to v$ be adjacent in the $C_n$. Create $n$ vertices $x_1...x_n$ and add edges $u\to x_i$ and $x_i \to v$. Now any walk ...
Michal Dvořák's user avatar
11 votes

Structural equivalence of self-referential structures

Since your types both reference each other, these are not inductive types, but coinductive types.$^{1}$ That's because, if you expand out T1 and T2 (as you have done partially in the question), you ...
Caleb Stanford's user avatar
6 votes
Accepted

Linear-time algorithm for determining the presence of incomparable pairs in a directed acyclic graph (DAG)

Here is a linear-time algorithm that decides whether a DAG contains at least one incomparable pair of nodes. Do a topological sorting with a linear algorithm. (Yes, topological sorting is very ...
John L.'s user avatar
  • 39.1k
5 votes
Accepted

Prove finding k disjoint paths from n given paths in a directed graph is NP-complete

Membership of your problem in $\mathsf{NP}$ is trivial. To prove that it is also $\mathsf{NP}$-hard consider an instance of (the decision version of) independent set consisting of a graph $G=(V, E)$ ...
Steven's user avatar
  • 29.5k
4 votes

Linear-time algorithm for determining the presence of incomparable pairs in a directed acyclic graph (DAG)

Observe that if there exists a vertex $u$ that is incomparable with another vertex $v$ in a DAG, then $u$'s order in a topological sort can be changed with respect to $v$. Equivalently, $u$'s position ...
Russel's user avatar
  • 2,780
4 votes

Linear-time algorithm for determining the presence of incomparable pairs in a directed acyclic graph (DAG)

Compute a topological ordering $(v_1, v_2, …, v_n)$ of the DAG. Now consider the recursive following algorithm: if $n = 1$, then there are no incomparable pairs of vertices; if $(v_1, v_2)\notin E$, ...
Nathaniel's user avatar
  • 15.8k
3 votes
Accepted

Maximum number of distinct nodes that can be visited on a single walk

The problem you have is the following: You have a directed graph and you are allowed to visit the same vertices and edges many times over. You want to find a walk starting in a vertex $s$ that ...
Pål GD's user avatar
  • 16.7k
2 votes
Accepted

Does every DAG have at most one "universal source"?

Suppose towards a contradiction that a DAG $G=(V,E)$ on $n$ vertices has more than one universal source and let $u,v \in V$ be two distinct universal sources of $G$. Since $\mbox{out-deg}(u)=n-1$, and ...
Steven's user avatar
  • 29.5k
2 votes
Accepted

Given an undirected graph, find an orientation such that every vertex has out-degree at least 3

Given $G=(V,E)$, create a directed bipartite graph $H=(V+E, F)$ where there is an edge $(v,e) \in F$ iff $v \in V$ is an endpoint of $e \in E$. All these edges have capacity $1$. Augment $H$ as ...
Steven's user avatar
  • 29.5k
2 votes

How to find long trails in a multidigraph

Here's a suggestion for a simple greedy heuristic to apply to the big SCC. It's based on the observation that a cycle of edges can be traversed a number of times equal to the minimum multiplicity of ...
j_random_hacker's user avatar
2 votes

Find palindrome in directed Graph where edges are either blue or red

Here's a possible algorithm. Construct a graph $G'$ with $|V|^2$ vertices where each vertex is labeled with the pair $(a, b)$ with $a, b$ being vertices in $G$. Then, construct all possible edges $(a, ...
orlp's user avatar
  • 13.6k
2 votes
Accepted

Connectivity in Directed Graph

The problem that you stated is known as the Graph Reachability Query problem. You may want to check this paper: An Efficient Algorithm for Answering Graph Reachability Queries, and the references ...
Inuyasha Yagami's user avatar
2 votes
Accepted

(Directed) Graphs: Minimal Vertices Subset With No Outgoing Edges

There is no wonder you end up feeling stuck. Assume $G$ has at least one vertex. The second case, "there is no such SCC with an out-degree of zero" does not exist. Recall if each strongly ...
John L.'s user avatar
  • 39.1k
2 votes
Accepted

Directed graph of bank balances and transactions, how to process transactions?

Depending on your rules, here's a greedy algorithm: Maintain a priority queue of all nodes where the value in the queue is how many debts they are able to pay down. Let the debt for each player be ...
Pål GD's user avatar
  • 16.7k
2 votes
Accepted

Find the directed subgraph with least edges that preserves connectivity

"In mathematics and computer science, connectivity is one of the basic concepts of graph theory: it asks for the minimum number of elements (nodes or edges) that need to be removed to separate ...
John L.'s user avatar
  • 39.1k
1 vote
Accepted

Balanced Directed Graph Realization

This is an instance of the directed graph realization problem. The problem can be solved in polynomial time; see Wikipedia for links to algorithms.
D.W.'s user avatar
  • 161k
1 vote
Accepted

Is the first distance that gets assigned to a node in BFS always the shortest distance?

Yes. You can imagine that instead of pop one node at a time, you can pop all nodes. Then enqueue all unvisited nodes that connected from one of the popped nodes. This imagination does not change the ...
John L.'s user avatar
  • 39.1k
1 vote
Accepted

Shortest walk with alternating colors in a directed graph

Let $G=(V, R \cup G \cup Y)$, where $R$, $G$, and $Y$ are the sets of red, green, and yellow edges, respectively. I assume you want to find the shortest walk between a pair of given vertices. Let ...
Steven's user avatar
  • 29.5k
1 vote

Turning an undirected graph into a directed graph such that in-degree of all nodes is at most 1 or show it is not possible

Your algorithm works. The main concept here are tree and cycle. it is possible iff no cycles or one cycle Claim: Let $G$ be an undirected connected graph. $G$ can be turned into a directed graph with ...
John L.'s user avatar
  • 39.1k
1 vote
Accepted

Which algorithm solves the single-pair shortest path in a weighted directed cyclic graph?

Since all distances are between $0$ and $n-1$, Dijkstra's algorithm with a suitable priority queue takes time $O(n+m)$, where $n$ and $m$ are the number of edges and vertices of the graph, ...
Steven's user avatar
  • 29.5k
1 vote
Accepted

Algorithm for finding a path in a directed graph that visits each node in a given subset

Instead of "path", Let us use "walk" for a sequence of edges which joins a sequence of vertices (that can revisit vertices and edges). We will reserve "path" for its ...
John L.'s user avatar
  • 39.1k
1 vote

Algorithm for finding a path in a directed graph that visits each node in a given subset

Hint: If that's not enough, here's a bigger hint:
D.W.'s user avatar
  • 161k
1 vote
Accepted

Find a simple path from S to T in a directed graph so that the product of its weights is maximum

The problem is NP-hard by a reduction from the Hamiltonian-path problem. If all edge weights are set to some constant $c>1$ and $P$ is a simple path from $s$ to $t$ that maximizes the product of ...
Steven's user avatar
  • 29.5k
1 vote

Find all nodes in directed graph from starting node that complete a loop

You should use the BFS algorithm to find the path from the source node to any other node (and it even produces the shortest path). For the converse, run the BFS on the transposed graph (swap the ...
nir shahar's user avatar
  • 11.6k
1 vote
Accepted

Find most vertices in a directed tree where no path of length less than 3 connects any pair

Yes, the greedy algorithm (you described) works. Given a directed graph, call a subset of its vertices "a 3-separated set" if there isn't a path of length less than 3 between any pair of ...
John L.'s user avatar
  • 39.1k
1 vote
Accepted

Minimal cut of a directed graph such that disjoint elements are strongly connected

There is a fast algorithm for this problem: (assuming you meant that $S$ is the set of edges being removed from $G$) Compute the strongly connected components of $G$, with an algorithm of your choice....
nir shahar's user avatar
  • 11.6k
1 vote
Accepted

DAG: When adding an edge that would normally result in a cycle, is there an algorithm to split the graph instead?

I think one possibility is do the naive thing, and whenever you find a backedge $u \to v$ (i.e., where $v$ is an ancestor of $u$ in the search tree), duplicate the subtree rooted at $v$, one duplicate ...
D.W.'s user avatar
  • 161k
1 vote

DAG: When adding an edge that would normally result in a cycle, is there an algorithm to split the graph instead?

Any graph of this type can be represented using this simplified model (left): where M1, M2, and M3 are metanodes that can represent 0 or more nodes, and edges involving M1, M2, and M3 can represent 0 ...
OmnipotentEntity's user avatar
1 vote
Accepted

Longest path in a strongly connected component

You won't be able to find any efficient algorithm for your problem, unless $\mathsf{P}=\mathsf{NP}$. Consider an instance of Hamiltonian path: given a graph $H=(V,E)$ on $n$ vertices decide whether it ...
Steven's user avatar
  • 29.5k

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