# Tag Info

Accepted

### Efficiently determine which nodes should leave a graph while maintaining connectedness

The problem is equivalent to the node-weighted version of the Steiner tree problem. Happy nodes correspond to terminals, and non-removed unhappy nodes correspond to Steiner vertices. This problem is ...
• 2,872
Accepted

### What is the relation between Topological Sort and Strongly Connected Components?

One connection could be the following: Given a graph $G$, construct the graph $G'$ in which every connected component of $G$ is a node, and two nodes in $G'$ have a (directed) edge if there is an edge ...
• 11.6k

### Implementing Tarjan's strongly connected components algorithm in a language without exceptions or undefined behavior

There will always be situations where we can see there is a complex invariant but the compiler cannot derive it. Type systems are sound but not complete: not all invariants can be expressed in the ...
• 163k

### Tseitin formula on 2-connected graph

Clearly, whether a formula is minimally unsatisfiable depends on the exact details of how it is formulated, so let me give a specific definition of Tseitin formulas. Given a graph $G=(V,E)$ and a ...
• 1,361

### Implementing Tarjan's strongly connected components algorithm in a language without exceptions or undefined behavior

By a happy coincidence, people (Ran Chen, Cyril Cohen, Jean-Jacques Levy, Stephan Merz and Laurent Thery) have completed formally verified implementations of Tarjan's algorithm in various formal ...
• 8,252

### O(m) time algorithm to check for a strongly connected graph

As mentioned by others, we can assume $n \le m$ otherwise the answer is NO. Perform a visit (say, a DFS) from node 1 along the digraph; and then, a visit from node 1 along the "reverse" ...
• 3,397
Accepted

### Efficiently check if removing an edge splits a strongly connected component

An arc is said to be a bridge if its removal increases the number of connected components of the graph. Further, an arc is a strong bridge if its removal increases the number of strongly connected ...
• 22.7k
Accepted

### Is a simple graph connected, if every node has at least one adjacent edge and $|E|\ge |V|-1$?

If $|V|=n, |E|\ge n-1$ and every node has at least one adjacent edge , then $G$ is connected. No, it is not true. Here is an counterexample. Graph made at https://graphonline.ru/en/ Exercise. ...
• 39k
Accepted

### Infinite Graph with Finite Degree

The lattice $\mathbb{Z}^2$ gives an example. Take $u=(0,0)$ and $v=(0,1)$. For every $n$ we can construct the path $u = (0,0) \to (n, 0) \to (n, 1) \to (0, 1)=v$ of length $2n+1$. Each of these paths ...

### How to generate random adjacency matrix with given number of components in graph

What you need is to take advantage of disjoint set, a very efficient data structure. Here is the simple algorithm to generate a random graph of $n$ vertices and $m$ component. MakeSet of size $n$. ...
• 39k
Accepted

### Fast algorithm for finding the size of each connected component in a graph of 2D points

You can do it in $O(n \log n)$ time by forming an Euclidean minimum spanning tree, and then dropping any edge with length greater than $t$.
• 13.8k

### Minimum vertices to remove from a graph so that no path exists between two given vertices anymore

Your problem is known as minimum vertex cut or minimum vertex separator. There is a simple reduction from this problem to the directed minimum edge cut, adopted from notes by Locke. The new graph ...
• 278k

### Deciding if a graph is "Single Connected"

Is your graph directed or undirected? If your graph is undirected then the condition you mention is equivalent to your graph being a forest (every connected component is a tree).
• 278k
Accepted

### A graph is strongly connected iff every non-trivial cut contains an edge

You can prove the existence of a path between any $u$ and $v$ vertices using the following process: set $S = \{u\}$; while $S \neq V$ do for each $(x, y)\in \delta(S)$, add $y$ to $S$ The property &...
• 15.9k
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 ...
• 39k
1 vote

### Find connected components in a graph of computer network with parallel pairwise tests

The best you can do is about $N$ steps. You can do it in about $N$ steps, by just testing $N/2$ new pairs in each step, until you've tested all pairs. Then once you have tested all pairs, you can use ...
• 163k
1 vote
Accepted

### Make maze connected by removing internal walls

You can use a graph traversal algorithm such as BFS/DFS to detect the connected components, and to construct a graph in which the vertices are connected components and the edges are walls adjacent to ...
• 278k
1 vote

### Algorithm for Getting Largest Connected Component From List of Touching Pairs

Create a graph only from nodes that appear in the output, and add an edge for each tuple in the output. Then find the connected components in this graph using DFS + union find (or your other favorite ...
• 11.6k
1 vote

• 1,629
1 vote

### Doubt regarding strong component in a graph

A strong component in a graph $G$, is a group of vertices $V_s$ such that $\forall v_1,v_2\in V_s:\exists u_1,...,u_n\in V_s:v_1=u_1\rightarrow u_2\rightarrow...\rightarrow u_n=v_2$. In simpler terms:...
• 11.6k
1 vote
Accepted

Your question is a bit too broad. There can be a lot of properties $P$ such that if $H$ is a subgraph of $G$ and $P(H)$ holds then all vertices of $H$ are in the same strong component. For example: $... • 29.6k 1 vote Accepted ### On the complexity analysis of quick-union in Algorithms by Sedgewick and Wayne Yes, you are correct! You have identified a typo in that book, Algorithms, the fourth edition by Robert Sedgewick and Kevin Wayne. Please check the errata for the first printing (March 2011) of the ... • 39k 1 vote Accepted ### Equivalence of states between two "quasi-deterministic" strongly connected Büchi automata accepting the same$\omega$-language Your property does not hold. Consider the following languages over$\Sigma = \{a,b\}$: There are infinitely many$a$s at even positions in a word There are infinitely many$a\$s at odd positions in a ...
• 2,797

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