Posts Tagged ‘graph theory’

Minimum Spanning Tree

December 7, 2010


The other day I came across this problem and ramprasad gave a brilliant solution to it.

Problem : Given a connected weighted graph G, find a minimum spanning tree. But wait, before you jump to any conclusion. The weights of the edges are not real numbers, but a quadratic function of time. So given a time interval [t1,t2] find out the minimum spanning tree T. That is T attains the minimum at time tm.  \forall t \in [t1,t2], \forall TR \in {Spanning Tree of G}, W(T_{tm}) \leq W(TR_t). Now, find out the minimum spanning tree and the time instant tm at which it attains that minimum value.

Solution : Well, the first solution that popped up in my mind was a brute force approach. Consider all spanning trees. As the weights of edges are quadratic functions, the weights of spanning trees would also be quadratic functions. Now differentiate these functions to find the minima. Now find out the absolute minimum of all these. But apparently, the number of spanning tree of a graph could be as high as n^{n-1}  thanks to Kirchoff. So obviously, it does not fit into our perception of “efficient algorithm”.

Ramprasad gave a nice solution which is definitely polynomial time. Not sure whether there are better solutions or not. Note that, prim’s algorithm or kruskal’s algorithm takes into account the order of weights of edge and does not really care about what these actual weights are.  So as long as the order of the weights remains unchanged, you can apply one of these algorithm. Given the time interval [t1,t2] it can give rise to infinitely many instances of the weighted graph. As the weight function of edges are quadratic ( parabola ) there are at most O({|E| \choose 2}) many intersection points. That is, parabola corresponding to two edges intersect at atmost 2 points.  And these intersection points are the points in time where weight of one edge goes beyond the weight of another edge.

So, sort these intersection points by time co-ordinate. Note, that between two consecutive intersection points, the order of the weights remain unchanged and hence one of the standard algorithm can be applied. So we need to run Prim’s or Kruskal’s algorithm (O(|E| log |V|)) for each such interval giving rise to O(|E|^3 log |V|) algorithm overall. Clearly, a major improvement over the brute force method.
Ramprasad and I are not sure whether this can be improved or not. Please leave a comment if you have some improvements in mind.


Shortest Path

December 3, 2010


I am sure most of you must be aware of dijkstra’s shortest path algorithm. Now here is a bit interesting version of it.

Problem : You are given a weighted connected graph with all edges having positive weights. Some of the cities ( nodes ) have petrol pump whereas some don’t. You have a car with the tank capacity of C. That is, with full tank, the car can travel for C units of distance. At any city with the petrol pump the car can fill its tank to full. Find out the shortest distance from a given source vertex to a given destination vertex with these constraints. Find out the shortest path between the given source and destination. Find out the shortest paths and distances from the source to all vertices.

Solution : Actually, this time, I am being a bit lazy. But I have this simple idea which certainly is a solution. Probably with a scope to improve it. Given the graph, take a vertex v without a petrol pump.  Remove this vertex and all edges incident on it. Now, for all neighbours u1,..,uk of it, add/update edges between (ui,uj). These edges can now store the shortest path between (ui,uj). Once the graph is converted in this manner, the standard algorithm can be applied. The conversion of this graph can be done in O(n^3) or O(n^4) depending upon whether we need the paths or just distances. I know I have omitted many details. But all in all, this trick can give rise to a O(n^4) algorithm ( probably O(n^3) not sure 😉 ) which does the job. Let me know if you can do better 🙂

Tournament graph and Hamiltonian Path

November 11, 2010


Those of you who are unaware of tournament graph and hamiltonian path, you can look here and here. Ramprasad gave me the following interesting problem to think about.

Problem : Given a tournament ( I will omit the suffix “graph” as it is obvious in the context of graph theory ), construct a hamiltonian path in polynomial time.

Solution : When I first heard the problem, I was even wondering how to prove first that all tournament indeed always have an hamiltonian path. And that too, we need to find it in polynomial time..Phew! But I believe that if you comeup with an algorithm, that itself gives you a proof!!

He gave me a hint : given that you already have explored some path v_1,\dots,v_k how can you extend it for a given vertex v? That is, of course, if the path has not covered every vertex :-).

If there is a directed edge from v_k to v there is a natural extension. You just append v to the path. If not, find out two consecutive vertices v_i, v_{i+1} in the path such that the tournament have edges (v_i,v) and (v,v_{i+1}) in which case the modified path will be v_1,\dots , v_i, v ,v_{i+1},\dots, v_k.

Suppose no such pair exists!!!! Let’s try to see why this can’t be true. Look at, v_1,v_2. It has to be the case that either tournament contains edges (v_1,v),(v_2,v) or (v,v_1),(v_2,v). If it is the second case, that v can be just added as a prefix to the path. If it is the first case, than note that tournament must contain (v_3,v) because other wise we can have \dots, v_2,v,v_3,\dots. Similarly, we can argue for v_4,\dots giving us the contradiction as we had assumed that edge (v_k,v) is absent from the tournament.

Hence, we can always extend the path as long as there is some vertex we have not yet covered.
Ramprasad gave a simple proof of why a pair v_i,v_{i+1} must exist such that we can extend the path to contain v_i,v,v_{i+1}. If we can not add v as a prefix or a suffix to the path. Then look at the vertex with the least index j such that (v,v_j) is an edge. By the definition of the tournament, one of the two edge (v_{j-1},v) , (v,v_{j-1}) must be there. But, because j is the least index having an incoming edge in the path, the second edge can not be there. hence we can extend the path to contain v_{j-1},v,v_j.

Easy to see that algorithm runs in O(n^2) time as we need to search O(n) vertex to extend the path and repeat it till we  have covered all vertices.

–Saurabh Joshi

A problem in graph theory

January 19, 2009


It’s been a long time on this blog and I can feel it through reduced traffic. But anyways, let me not worry about it and lets get to the point.

The problem was brought to me by manoj for which saket gave a very elegant and simple solution. Me and satyam made some good observtions but not the one which matterred the most :-).

Problem : Let G be any undirected graph. Let I be the maximum independent set and C be the minimum vertex cover for this graph.  Prove that

|I| + |C| = |V| where V denote the set of vertices of G.

Solution : A very important observation to make is this.

Claim 1 : Let VC be any vertex cover ( not necessarily minimum ) then the set V-VC will form an independent set and vice versa.

Proof :   Let VC be a vertex cover. If V-VC does not form an independent set then there must be two vertices u,v \in V-VC such that (u,v) \in E. But in that case VC can’t be a vertex cover as it did not cover (u,v).

For the other direction, let IS be an independent set. So V-IS must form a vertex cover. If not then there must be an edge,  for which none of the incident vertex belong to V-IS. Then they must be in IS.  It is a contradiction then that IS is an independent set.

Having established claim 1, it is easy to prove the original stated theorem. Let C be a minimum vertex cover ( for a graph, minimum vertex cover or maximum independent set need not be unique ). V-C must form an indepedent set. If V-C is not the maximum independent set then let I be the maximum independent set such that |IS| > |V-C|.  From claim one there exist a vertex cover V-IS such that |V-IS| < |C| . But C was a minimum vertex cover and we found a smaller vertex cover V-IS. A contradiction! So the theorem holds :-).

–Saurabh Joshi

Job scheduling problem

December 29, 2008


This problem was written on whiteboard by manoj for others to solve and finally arpita solved it for the most part with me chipping in at the end.

Problem : There are n jobs to be done and 2 processor available.  Each job take the same amount of time ( so for simplicity one can assume it takes unit time ). Both processor have the same capabilities.  A job may depend on other jobs, for example if job A is dependent on B and C then A can not be scheduled before B and C both  are finished.  Dependancies amogst jobs are given.  Give an algorithm to find the optimum schedule ( in terms of time to finish all jobs ).

Solution ; Because dependacies are given, one can generate a dependacy graph. This graph is a DAG ( Directed Acyclic Graph ). Because if there is a cycle then all jobs which participate in the cycle can never be scheduled. Now, compute the transitive closure, in a sense that if there are edges A -> B and B -> C, then add an edge A -> C.

This way we have obtained all dependencies, direct as well as indirect, in this graph G. Forget about the direction of the edges for a moment and compute a complement graph G’. It is easy to see two jobs can be scheduled in parallel if and only if there is an edge between them in G’. Find a maximum matching ( 1-factor ) of G’.  Minimum time taken would

# of edges in G’ + # of unmatched nodes in G’.

Of course, the ordering is still needs to be decided.

Let’s get back to G now.  We will merge nodes which were matched in G’, that will give us another DAG.  Topological sort on this DAG would give us the order in which we should schedule the jobs.

Though I am not fully confident, I believe that this method would give us the optimum schedule. One more point to ponder is that whether this can be generalized for k-processors.

— Saurabh Joshi