PPAD-complete problems on wikipedia

As requested by many of the readers of my blog, I added a wikipedia entry for PPAD-complete problems. It is called List of PPAD-complete problems. I added only the contents. I will try to add more content when I get time. Please feel free to edit and make it as informative (with definitions of problems, references, open problems etc) as possible.

A Compendium of PPAD-complete problems

Motivated by my recent paper (joint work with Laura J. Poplawski, Rajmohan Rajaraman, Ravi Sundaram, Shang-Hua Teng) and a suggestion of Noam Nisan, I created a compendium of PPAD-complete problems. Please let me know if you see any additions/corrections.

Dick Lipton's and Noam Nisan's Blogs

There are two new theory blogs.....

• Dick Lipton's Gödel’s Lost Letter and P=NP : This is an awesome blog. During my first semester at GeorgiaTech I took Dick's course on 'Open Problems in CS theory'. What an excellent course that was !! In every class, Dick proposed at least three open problems along with possible ways to attack them and required references. Since, it was my first semester at Gatech, some of these problems intimidated me. Nevertheless, I maintained a special notebook and scribbled each and every problem and references he mentioned, hoping to revisit them later. I am gald that all his open problems are being documented in his blog.
  

• Noam Nisan's Algorithmic game theory is very fresh. Just launcheded yesterday.

Troyis Game

I came across this game called Troyis. Being a theoretician, whenever I come across a new game, the first question that comes to my mind is "What is its complexity ?". Here is the decision version of Troyis :

• TROYIS : Given an instance of Troyis, can you paint all the white cells in <= k clicks ?

Here is a puzzle : Prove (or disprove) that TROYIS is NP-complete.

Open Problem Garden !!

Let me point you to this great site on open problems in mathematics, graph theory and theoretical computer science.

• Open Problem Garden

I found this through Computational Complexity blog.

Network flow : integer vs real values

Integer values are assumed in the analysis of most of the algorithms based on network flow. The reason for this is as follows.....

If the capacities on all the edges are integral then there always exists an integral flow.

If the capacities are rational numbers we can take the LCM and apply the same network flow algorithm (ford-fulkerson) by choosing augmenting paths arbitrarily.

If the capacities are real numbers, ford-fulkerson algorithm runs in polynomial time if augmenting paths are chosen via BFS. The algorithm might not terminate if the augmenting paths are chosen arbitrarily.

Assuming integer values makes the analysis much simpler, without worrying about how the augmenting paths are chosen. As said earlier, real-values can be handled efficiently using BFS.

A recent paper [1] analyzes the DFS approach of choosing augmenting paths.

[1] Finite Termination of "Augmenting Path" Algorithms in the Presence of Irrational Problem Data Brian C Dean, Michel X. Goemans, Nicole Immorlica. To appear in the proceedings of the 14th annual European Symposium on Algorithms (ESA), 2006.

CRICKET is NP-Complete

How do we decide the order of batsmen to maximize the cumulative runs made by them in 50 overs ? Here is my perspective......

Let's say we have the following statistics of batsmen based on their past performances.

• average time spent by a batsman on the field.
• average runs per over made (during past partnerships) for each pair of batsmen.

Given this data, we would like to decide the order of batsmen to maximize their runs (assuming they don't deviate much from their average past performance).

Formally speaking, we have a complete undirected weighted (vertex-weighted and edge-weighted) graph on n vertices. The vertices represent the batsmen and the weights on the vertices indicate the average time spent by the batsman on the field. The weight w on the edge (u,v) represents the average runs per over made (during past partnerships) by (u,v). That is, if u and v are playing on the field, they can together contribute at the rate of w runs per over. Having a bad partner hurts you, even if you are a high-scorer.

For example, the input graph can be as shown below...




The best schedule for m (=50) overs can be as shown below....



In the above figure, we have two rows representing the two batsmen on the field at any given time. The number of runs for the above schedule is derived by adding the length-of-overlap*edge-weight for each pair of players.

Theorem : Given the input graph G(V,E), finding the optimum (maximizing runs) schedule is NP-Complete.

I will post the proof at a later time in a later post. In the menwhile, you can try your own approaches to prove it. The next obvious question is about the approximability.

This model might not be pratical (due to noise, does not take other factors (like the skills of bowlers and bowler's schedule) into account) in real-life, but serves as a good mathematical puzzle.

P.S. Beginners can read the rules of cricket here. World Cup 2007 Schedule is here. Add this cool countdown to world cup to your google personalized homepage.

Transactions Minimization Problem

In April 2000, I visited Agra with one of my friends (Amit) and his roommates (X,Y,Z) . At the end of the tour we ended up owing money to each other, due to the transactions during the trip (Eg : Amit paid for my taxi, I paid for X's food, Y paid for Amit's photo's at taj mahal etc etc.,). At the end of the trip we have to decide "who owes whom how much".

Normal human-beings might solve this problem in a step by step fashion through multiple transactions. Since we are computer sceintists, we will add some "constraints" and solve this problem "efficiently"'.

Formally speaking, we have a weighted directed graph G(V,E) where the vertices represent the people and a directed edge (u,v) with weight w means that u owes w-dollars to v.

For example, the following graph shows that a owes $10 to b, and b owes $20 to c.



There are two ways to perform the transactions.

First way :

• a withdraws $10 from ATM
• b withdraws $20 from ATM
• a pays $10 to b
• b pays $20 to c

Second way : reduce G to G' as shown below :

• a withdraws $10 from ATM
• b withdraws only $10 from ATM
• a pays $10 to c
• b pays $10 to c

Second way is better in the following sense :

• b has withdrawn just as much money as required.
• there are smaller (less money involved) transactions.
• often there are lesser transactions (you can construct a complicated example to see this)
• The transactions are still parallelizable !! (i.e., all the payments can occur simultaneously).

Formally, we want to reduce the graph G(V,E) to G'(V',E') such that,

1. Net amount (payed/received) is preserved for each person. (I am too lazy to write down the equations)
2. |E'| is as small as possible (or)
   
3. The sum of the weights of the edges in G' is minimized (or)
   
4. The maximum weight of an edge in G' is minimized.
   

Question : Design an efficient algorithm to reduce G to G'

I will stop here and let you solve this problem on your own.....