Tag Info

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

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 ...
• 7,088
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 ...
• 39.1k
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)$ ...
• 29.5k

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 ...
• 2,780

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$, ...
• 15.8k
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 ...
• 16.7k
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 ...
• 29.5k
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 ...
• 29.5k