Eliminate cycles in graph by removing fewer vertices

Question

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.

Answer 1

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.