Saturday, August 19th

 Special Edges in a Minimum Cost Spanning Tree

Given a graph represented as a weighted edgeless, find critical and pseudo-critical edges in the Minimum Cost Spanning Tree (MST) of a graph.  A critical edge is an edge whose deletion would increase the cost of the MST, while a pseudo-critical edge is an edge that may appear in some MSTs.

The Tokyo subway network courtesy of Yveltal via Wikipedia.  Distributed under the Creative Commons Attribution-Share Alike 4.0 International license.  Not exactly a minimum cost spanning tree, but illustrates related network problems

We assume the reader is familiar with graph theory, including the Minimum Cost Spanning Tree.

Since we are dealing with questions of connectivity, Kruskal's algorithm for MST seems like a good approach.  In order to properly use it, we convert the graph to a Union-Find Data Structure

We keep a global variable vector of parents, and initiate it by setting the size equal to the number of nodes in the graph

    vector<int>parent;

void disjoint(int size){

parent.resize(size);

for(int i=0;i<size;i++)

parent[i]=i;

}

Next, we implement the find method, which recursively calls itself until the condition is met that a node is its own parent in the data structure.

    int find(int u){

if(u!=parent[u]) {

parent[u]=find(parent[u]);

}

return parent[u];

}

The last method for the Union-Find data structure, merge(), is implemented by finding the parents of 2 disconnected subgraphs and combining them into the same parent

void merge(int u,int v){

int ua = find(u);

int ub = find(v);

parent[ua] = ub;

}

With the Union-Find data structure ready, we take a look at Kruskal's and try to see how we can use it to solve the problem

Vanilla Kruskal's is below.  Since the problem here deals with MST weights, we have Kruskal's only returning the weight of the MST, not the edges of the MST

The algorithm works by first sorting the edges according to weight, then beginning with the smallest-weighted edge, iterating through the edgelist while selecting edges that connect new nodes.  

To test for that connection, we use the find function for the Union-Find data structure, and if the nodes of an edge reside in different components, then we call merge.  

At the end, if the structure contains n-1 edges, we know we have an MST.

    int k(vector<vector<int>>& e, int n){

disjoint(n);

vector<pair<int,pair<int,int>>>v;

for(int i=0;i<e.size();i++){

v.push_back({e[i][2],{e[i][0],e[i][1]}});

}

sort(v.begin(),v.end());

int mst_weight = 0;

int edges = 0;

for(int i=0;i<v.size();i++){

auto x = v[i];

int u = find(x.second.first);

int v = find(x.second.second);

if(u!=v){

edges++;

mst_weight += x.first;

merge(u,v);

}

}

if(edges!=n-1)return INT_MAX;

return mst_weight;

}

We modify Kruskal's in 2 ways to help solve the problem.  In 1 version, we take an additional input parameter j, which identifies the index of an edge.  Then add the following line of code inside the for loop that creates the vector of weighted edges:

int k1(vector<vector<int>>& e,int j,int n){

//disjoint(n+1);

disjoint(n);

vector<pair<int,pair<int,int>>>v;

for(int i=0;i<e.size();i++){

if(i==j)continue;

v.push_back({e[i][2],{e[i][0],e[i][1]}});

    }

        ...

    }

The addition of the edge parameter allows us to create an MST without the edge in question.  To find an MST without edge of index 2, we call

int mst_sans2 = k1(e,2,n);

We can use the same function to perform ordinary Kruskal's by including the index of an edge that doesn't exist

int mst_k = k1(e,-1,n);

The above function, for finding a MST weight while omitting an edge, will be used for testing whether an edge is critical or not.  If k1() is called with a given edge omitted, if the the MST weight increases, then we know the edge in question is critical.

A second modification allows us to look for pseudo critical edges

In addition to including the exclusion line like in k1(), we add a line forcing the MST to use a given edge.  Below, while an inputted edge is omitted in the for loop, it is forced into the MST by explicitly merging the endpoints

    int k2(vector<vector<int>>& e,int j,int n){

disjoint(n);

int mst_weight = e[j][2];

merge(e[j][1],e[j][0]);

vector<pair<int,pair<int,int>>>v;

for(int i=0;i<e.size();i++){

if(i==j)continue;

v.push_back({e[i][2],{e[i][0],e[i][1]}});

}

        ...

    }

Forcing an edge to be in the MST helps finding the pseudo-critical edges.  By forcing an edge into an MST, we can compare MST weights.  If the weight with a given edge is equal to the vanilla MST, then we can say an edge is pseudo-critical.

Finally, we craft our main program to incorporate the k1() and k2() functions to answer the problem

    vector<vector<int>> findCriticalAndPseudoCriticalEdges(int n, vector<vector<int>>& e) {

        ...

    }

First we initialize our Union-Find data structure, then compute the base MST weight

disjoint(n);

int mst_weight = help1(e,-1,n);

Then we create our solution vectors: a vector to hold the critical edges, a vector for psuedo-critical edges, and the answer vector to hold both edge vectors

vector<vector<int>>ans;

vector<int>v1,v2;

Next we iterate through the edgeless.  

    for(int i=0;i<e.size();i++){

        ...

    }

For each edge, we compute the MST when it is omitted.  If the MST increases in weight, then we have a critical edge

    int wk1 = k1(e,i,n);

if(wk1 > mst_weight){

v1.push_back(i);

}

For each edge, we also compute when the MST is forced to include the edge.  If the MST weight remains the same, we have a pseudo edge

    int wk2 = k2(e,i,n);

else if(wk2 == mst_weight){

v2.push_back(i);

}

Finally, combine both vectors into the final solution vector and return it

ans.push_back(v1);

ans.push_back(v2);

return ans;

Definitely a hard problem, but knowing the Union-Find data structure and having a comfortable knowledge of Kruskal's, the problem isn't too complicated

Thanks to CHIIKUU for the very sensible implementation