5 votes
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 ...
pcpthm's user avatar
  • 2,348
5 votes
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 ...
nir shahar's user avatar
  • 11.5k
4 votes

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 ...
D.W.'s user avatar
  • 159k
4 votes

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 ...
Emil Jeřábek's user avatar
3 votes

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 ...
cody's user avatar
  • 8,204
3 votes
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 ...
Juho's user avatar
  • 22.6k
3 votes
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. ...
John L.'s user avatar
  • 39k
3 votes
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 ...
Giorgos Giapitzakis's user avatar
2 votes

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$. ...
John L.'s user avatar
  • 39k
2 votes
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$.
orlp's user avatar
  • 13.4k
2 votes

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 ...
Yuval Filmus's user avatar
2 votes

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" ...
Vincenzo's user avatar
  • 3,302
2 votes

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).
Yuval Filmus's user avatar
2 votes
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 &...
Nathaniel's user avatar
  • 15.5k
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
  • 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 ...
D.W.'s user avatar
  • 159k
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 ...
Yuval Filmus's user avatar
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 ...
nir shahar's user avatar
  • 11.5k
1 vote

Enumerate all connected components that could be created from removing k edges?

You might be optimizing on the wrong end. Finding connected components for a fixed graph can be done in $O(|V|+|E|)$ time. With the dynamic decremental algorithm you link to, you can reduce that to $O(...
kne's user avatar
  • 2,254
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.5k
1 vote
Accepted

find the strong component containing the vertex v

Since you are not trying to write an optimal algorithm, like this one or that one, I suggest you do not try to optimize space usage too much, especially if the optimization only diminish the ...
Nathaniel's user avatar
  • 15.5k
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.4k
1 vote

How can I examine the subnetworks of a nearly fully connected graph?

It sounds like you don't need to be talking about this as a "graph" data structure.. you have points in R3 and you want to partition them into clusters based on their distances (or their ...
JimN's user avatar
  • 837
1 vote

Finding connected components without building the graph first

Okay I'm writing another answer for the sake of tidiness. I suppose that the elements of your sets are integers. Otherwise one could just use pointers to the items. ...
plshelp's user avatar
  • 1,629
1 vote

Finding connected components without building the graph first

I have an idea for the algorithm that's slightly better than a simple dfs based on the fact that the relationship is transitive. From transitivity follows that $a \sim b \land b \sim c \Rightarrow a \...
plshelp's user avatar
  • 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:...
nir shahar's user avatar
  • 11.5k
1 vote
Accepted

Doubt regarding strong component in a graph

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: $...
Steven's user avatar
  • 29.4k
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 ...
John L.'s user avatar
  • 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 ...
DCTLib's user avatar
  • 2,742

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