2
I wonder if anyone knows if it is possible to eliminate all cycles of an undirected graph (n vertices) weightless, removing the smallest number of vertices, in time O(n²)?
Note: The graph can be complete at worst.
2
I wonder if anyone knows if it is possible to eliminate all cycles of an undirected graph (n vertices) weightless, removing the smallest number of vertices, in time O(n²)?
Note: The graph can be complete at worst.
0
First, you try to make a topological ordering graph. In a topological ordering, you define an order that tells which vertices come before or after which other vertices. In a graph with cycles, there is no topological ordering. I will copy the algorithm referenced in this link, but with some point modifications of mine to clarify better:
// Algoritmo de ordenação topológica, versão 1.
G ← grafo de entrada
L ← lista vazia que irá conter os vértices ordenados topologicamente
S ← conjunto de todos os vértices de G sem arestas de entrada
A ← conjunto de todas as arestas de G
enquanto S é não-vazio faça
remova um vértice N de S
insira N em L
para cada vértice M em G com uma aresta E de N até M faça
remova a aresta E de A
se M não tem mais arestas de entrada em A então
insira M em S
se o A é não-vazio então
retorne que o grafo G tem pelo menos um ciclo com arestas A
senão
retorne que L é uma ordenação topológica proposta
The part about computing the S
can be made like this:
// Algoritmo para computar as arestas sem entrada.
G ← grafo de entrada
S ← lista com todos os vértices de G
para cada aresta Y dentro de G faça
F ← vértice de destino da aresta Y
remova F de S (se já não tiver sido removido antes)
Compute S
, the complexity is of , because we have to build the list of vertices and scroll through the list of edges .
In the topological ordering algorithm, the complexity of the loop enquanto
is . Within the enquanto
, there’s a bond para
. Each iteration of para
removes an edge, so that in the worst case, all edges are removed, which gives .
One might think that the bond enquanto
runs the risk of being infinite by removing vertices of S
at the beginning and reintroduce vertices in S
within the se
that’s inside the para
. However, edges are progressively removed and vertices are only introduced when edges are removed. Therefore, the number of vertices entered cannot be greater than the number of edges, which ensures that the loop enquanto
is not infinite. Moreover, the vertices entered are not the same that are removed because S
contains only incoming edge-less vertices that are deleted, while those added there are just those that have just had all incoming edges removed.
The se
at the end and the construction of L
empty on first line have complexity . The construction of A
before the noose enquanto
cost . Therefore, this algorithm has total complexity of .
This algorithm attempts to form a topological ordering by removing edges and vertices from the graph (actually sets A
and S
) until at last it is empty. If he cannot remove all vertices and edges from these groups, then all that remain are part of some cycle.
So you can do this:
// Algoritmo de remoção do menor número de vértices de ciclos, versão 1.
G ← grafo de entrada
R ← lista que receberá os vértices a serem removidos
enquanto a ordenação topológica (versão 1) de H contém um ciclo de arestas A faça
G ← novo grafo com as arestas de A e os vértices correspondentes
C ← vértice de origem de alguma aresta qualquer de A
remova C de H junto com todas as arestas que entram ou saem de C
insira C em R
Create R
as an empty list has cost . The second and fourth instruction of the loop body enquanto
have complexity . In the worst case, ignoring the first instruction of the loop enquanto
, at the end of this algorithm, all vertices and all edges will be removed by the third statement of the loop enquanto
until the condition that the guard become false, then the total cost of that instruction (ignoring the cost of the first loop instruction enquanto
and adding up all loop iterations) is .
The problem now is to know how many times the topological ordering of H
will be tried in the loop enquanto
. In the worst case (a complete graph), if S
has all the edges of H
, every iteration of enquanto
, an edge of H
is removed. Therefore, the number of iterations of that loop in the worst case is . In each of these iterations, a topological ordering is done with the cost . Thus, the total cost of the loop in the worst case (still ignoring the creation of a new graph G
) is .
However, the worst case estimate is is exaggerated. If we take a closer look at the algorithm of removing the smallest number of vertices and the topological ordering together, we see that the enquanto
of topological ordering removes vertices and edges until only cycles remain, and the enquanto
the removal of the smallest number of vertices of the cycles removes the vertices that form cycles together with the edges that fall on them. as there is no form of the same vertex or edge being removed twice and no vertex or edge is seen without being removed, we conclude that the complexity is actually .
However, there are still two problems. The first is obviously that we ignore the cost of recreating G
, which greatly increases complexity by being a complex operation performed within the loop. The second is that nothing guarantees that the choice of the vertices removed in R
is minimal. For example, suppose I have a graph with two cycles that have a single vertex as an intersection (the graph is the figure of a number 8). If I remove the central vertex, with a removal I get the optimal result. But if the algorithm chooses another vertex to remove, two removals will be required to break all cycles. The solution to these two problems is to carry out this small modification in the first instruction of the loop body enquanto
:
// Algoritmo de remoção do menor número de vértices de ciclos, versão 2.
G ← grafo de entrada
R ← lista que receberá os vértices a serem removidos
H ← clone de G
enquanto a ordenação topológica (versão 1) de H contém um ciclo de arestas A faça
C ← vértice que aparece mais vezes nas arestas de A
remova C de H junto com todas as arestas que entram ou saem de C
insira C em R
By always removing the vertex that appears most often on the edges that form cycles, you ensure that as many cycles as possible are being broken by removing it.
However we have another problem: Count the number of times each vertex appears in each loop iteration enquanto
is costly and increases our degree of complexity (as well as recreating the graph). We can solve these problems by changing the topological ordering algorithm so that it accounts for the degree and removes unwanted vertices:
// Algoritmo de ordenação topológica destrutiva, versão 2.
G ← grafo de entrada
L ← lista vazia que irá conter os vértices ordenados topologicamente
S ← conjunto de todos os vértices de G sem arestas de entrada
A ← conjunto de todas as arestas de G
T ← mapeamento dos graus de cada vértice de G
enquanto S é não-vazio faça
remova um vértice N de S
remova N de G
insira N em L
coloque 0 em T na posição de N
para cada vértice M em G com uma aresta E de N até M faça
remova a aresta E de A e de G
subtraia 1 em T na posição de M
se M não tem mais arestas de entrada em A então
insira M em S
se o A é não-vazio então
C ← vértice com o maior número em T
retorne que:
o grafo G tem pelo menos um ciclo com arestas A e;
C é o vértice com mais incidências
senão
retorne que L é uma ordenação topológica proposta
Compute T
before the enquanto
cost . Compute C
cost . The other operations that have been put into the algorithm have cost ,
They also solve the problem of recreating the graph: instead of recreating it, I make destructive modifications to it. Therefore, the topological ordering algorithm remains .
And then, we have a third version of our vertex removal algorithm:
// Algoritmo de remoção do menor número de vértices de ciclos, versão 3.
G ← grafo de entrada
R ← lista que receberá os vértices a serem removidos
H ← clone de G // sofrerá modificações destrutivas,
// por isso queremos preservar o original.
enquanto a ordenação topológica destrutiva (versão 2) de H contém:
um ciclo A e;
um vértice C que aparece mais vezes
faça
remova C de H junto com todas as arestas que entram ou saem de C
insira C em R
The cost of creating the H
original as a clone of G
is . The cost in worst case loop enquanto
continues and this time without ignoring the part of rebuilding/modifying the fork. Despite this, you can still improve a little bit!
If you consider that the input graph does not contain parallel edges (i.e., two or more edges coming out of the same vertex A
and entering the same vertex B
), then there is no way the number of edges is more than the square of the number of vertices (ie, ), and therefore, in the worst case, we would have .
On the other hand, if your graph can have parallel edges, you can eliminate them like this: You create an array with boolean entries (adjacency matrix) so that each input corresponds to a possible input and output of the graph, that is, each one corresponds to a possible edge. This array is initialized with all positions with falso
. You then traverse all the edges and put verdadeiro
the ones you find. Then, you use the resulting array to reassemble the graph without the repeated edges and then try to remove the vertices from the cycle. The complexity of the process of eliminating repeated edges and reassembling the graph will be , but this will make the complexity of removing the vertices of the cycles go to . So the total complexity will be .
So we come to the latest version of our vertex removal algorithm:
// Algoritmo de remoção de arestas paralelas
G ← grafo de entrada
T ← número de vértices de G
Z ← matriz booleana com o T * T posições
para cada aresta W de G:
P ← número do vértice de entrada de W // primeira posição é zero
Q ← número do vértice de saída de W // primeira posição é zero
U ← P * T + Q
Z[U] ← verdadeiro
// Algoritmo de remoção do menor número de vértices de ciclos, versão 4.
G ← grafo de entrada
R ← lista que receberá os vértices a serem removidos
H ← clone de G // sofrerá modificações destrutivas,
// por isso queremos preservar o original.
remova as arestas paralelas de H.
enquanto a ordenação topológica destrutiva (versão 2) de H contém:
um ciclo A e;
um vértice C que aparece mais vezes
faça
remova C de H junto com todas as arestas que entram ou saem de C
insira C em R
Finally, we note that this very Boolean adjacency matrix can serve to represent the graph.
We already know that in the worst case, the complexity of the algorithm is . Since in order for this adjacency matrix to be constructed and also to be traversed in order to determine which are the vertices without inputs, it will be necessary that all cells of this matrix are accessed, as well as all parallel edges, then we have a lower limit of complexity . Since the lower and upper bound are equal, then the complexity of the algorithm is .
If the original graph is already represented in adjacency matrix form (with values 0 where there is no edge, 1 where there is an edge and 2 or more where there are parallel edges), the complexity will be because in that case, the algorithm to remove the parallel edges can simply traverse the adjacency matrix and exchange any numbers greater than or equal to 2 by 1.
Browser other questions tagged algorithm graph
You are not signed in. Login or sign up in order to post.
This matrix of booleans is called adjacency matrix
– Jefferson Quesado
@Jeffersonquesado Yes. However, since it rejects parallel edges it only has 0 and 1, while the conceptual definition of adjacency matrix would accept any integer values greater than or equal to zero where 2 or more would indicate the existence of parallel edges. In fact, this very Boolean adjacency matrix represents the graph.
– Victor Stafusa