Category Archives: polyhedral combinatorics

by

TrueShelf 1.0

One year back (on 6/6/12) I announced a beta version of TrueShelf, a social-network for sharing exercises and puzzles especially in mathematics and computer science. After an year of testing and adding new features, now I can say that TrueShelf is out of beta.

TrueShelf turned out to be a very useful website. When students ask me for practice problems (or books) on a particular topic, I simply point them to trueshelf and tell them the tags related to that topic. When I am advising students on research projects, I first tell them to solve all related problems (in the first couple of weeks) to prepare them to read research papers.

Here are the features in TrueShelf 1.0.

  • Post an exercise (or) multiple-choice question (or) video (or) notes.
  • Solve any multiple-choice question directly on the website.
  • Add topic and tags to any post
  • Add source or level (high-school/undergraduate/graduate/research).
  • Show text-books related to a post
  • Show related posts for every post.
  • View printable version (or) LaTex version of any post.
  • Email / Tweet / share on facebook (or) Google+ any post directly from the post.
  • Add any post to your Favorites
  • Like (a.k.a upvote) any post.

Feel free to explore TrueShelf, contribute new exercises and let me know if you have any feedback (or) new features you want to see. You can also follow TrueShelf on facebook, twitter and google+. Here is a screenshot highlighting the important features.

trueshelf

by

Open Problems from Lovasz and Plummer’s Matching Theory Book

I always have exactly one bed-time mathematical book to read (for an hour) before going to sleep. It helps me learn new concepts and hopefully stumble upon interesting open problems. Matching Theory by Laszlo Lovasz and Michael D. Plummer has been my bed-time book for the last six months. I bought this book 3 years back (during my PhD days) but never got a chance to read it. This book often disappears from Amazon’s stock. I guess they are printing it on-demand.

If you are interested in learning the algorithmic and combinatorial foundations of Matching Theory (with a historic perspective), then this book is a must read. Today’s post is about the open problems mentioned in Matching Theory book. If you know the status (or progress) of these problems, please leave a comment.

—————————————————————————-

1 . Consistent Labeling and Maximum Flow 

Conjecture (Fulkerson) : Any consistent labelling procedure results in a maximum flow in polynomial number of steps.

—————————————————————————-

2. Toughness and Hamiltonicity

The toughness of a graph G, t(G) is defined to be +\infty, if G = K_n and to be min(|S|/c(G-S)), if G \neq K_n. Here c(G-S) is the number of components of G-S.

Conjecture (Chvatal 1973) : There exists a positive real number t_0 such that for every graph G, t(G) \geq t_0 implies G is Hamiltonian.

—————————————————————————-

3. Perfect Matchings and Bipartite Graphs

Theorem : Let X be a set, X_1, \dots, X_t \subseteq X and suppose that |X_i| \leq r for i = 1, \dots, t. Let G be a bipartite graph such that

a) X \subseteq V(G),

b) G - X_i has a perfect matching , and

c) if any edge of G is deleted, property (b) fails to hold in the resulting graph.

Then, the number of vertices in G with degree \geq 3 is at most r^3 {t \choose 3}.

Conjecture : The conclusion of the above theorem holds for non-bipartite graphs as well.

—————————————————————————-

4. Number of Perfect Matchings

Conjecture (Schrijver and W.G.Valiant 1980) : Let \Phi(n,k) denote the minimum number of perfect matchings a k-regular bipartite graph on 2n points can have. Then, \lim_{n \to \infty} (\Phi(n,k))^{\frac{1}{n}} = \frac{(k-1)^{k-1}}{k^{k-2}}.

—————————————————————————-

5. Elementary Graphs

Conjecture : For k \geq 3 there exist constants c_1(k) > 1 and c_2(k) > 0 such that every k-regular elementary graph on 2n vertices, without forbidden edges , contains at least c_2(k){\cdot}c_1(k)^n perfect matchings. Furthermore c_1(k) \to \infty as k \to \infty.

—————————————————————————-

6. Number of colorations

Conjecture (Schrijver’83) : Let G be a k-regular bipartite graph on 2n vertices. Then the number of colorings of the edges of G with k given colors is at least (\frac{(k!)^2}{k^k})^n.

—————————————————————————-

7. The Strong Perfect Graph Conjecture (resolved)

Theorem : A graph is perfect if and only if it does not contain, as an induced subgraph, an odd hole or an odd antihole.

—————————————————————————-

by

TrueShelf

I have been teaching (courses related to algorithms and complexity) for the past six years (five years as a PhD student at GeorgiaTech, and the past one year at Princeton). One of the most challenging and interesting part of teaching is creating new exercises to help teach the important concepts in an efficient way. We often need lots of problems to include in homeworks, midterms, final exams and also to create practice problem sets.

We do not get enough time to teach all the concepts in class because the number of hours/week is bounded. I personally like to teach only the main concepts in class and design good problem sets so that students can learn the generalizations or extensions of the concepts by solving problems hands-on. This helps them develop their own intuitions about the concepts.

Whenever I need a new exercise I hardly open a physical textbook. I usually search on internet and find exercises from a course website (or) “extract” an exercise from a research paper. There are hundreds of exercises “hidden” in pdf files across several course homepages. Instructors often spend lots of time designing them. If these exercises can reach all the instructors and students across the world in an efficiently-indexed form, that will help everybody. Instructors will be happy that the exercises they designed are not confined to just one course. Students will have an excellent supply of exercises to hone their problem-solving skills.

During 2008, half-way through my PhD, I started collected the exercises I like in a private blog. At the same time I registered the domain trueshelf.com to make these exercises public. In 2011, towards the end of my PhD, I started using the trueshelf.com domain and made a public blog so that anybody can post an exercise. [ Notice that I did not use the trueshelf.com domain for three years. During these three years I got several offers ranging upto $5000 to sell the domain. So I knew I got the right name :) ] Soon, I realized that wordpress is somewhat “static” in nature and does not have enough “social” features I wanted. A screenshot of the old website is shown below.

The new version of TrueShelf is a social website enabling “crowd-sourcing” of exercises in any area. Here is the new logo, I am excited about :)

The goal of TrueShelf is to aid both the instructors and students by presenting quality exercises with tag-based indexing. Read the TrueShelf FAQ for more details. Note that we DO NOT allow users to post solutions. Each user may add his own “private” solution and notes to any exercise. I am planning to add more features soon.

In the long-run, I see TrueShelf becoming a ”Youtube for exercises”. Users will be able to create their own playlists of exercises (a.k.a problem sets) and will be recommended relevant exercises. Test-preparation agencies will be able to create their own channels to create sample tests.

Feel free to explore TrueShelf, contribute new exercises and let me know if you have any feedback (or) new features you want to see. You can also follow TrueShelf on facebook, twitter and google+.

Let’s see how TrueShelf evolves.

by

Linear Complementarity Problem

Linear Complementarity Problem (LCP) is a generalization of Linear Programming and a special case of quadratic programming. I stumbled upon LCP theory due to my interest in complexity problems in game theory and PPAD-completeness. As we will see these concepts are very closely related.

Let M be a n \times n square matrix and q an n dimensional vector. Let LCP(q,M) be the following problem : Find two vectors w and z satisfying

LCP

LCP(q,M) consists of linear constraints and complementary conditions. Since w{\geq}0, z{\geq}0 the complementary conditions {w_i}{z_i}=0 is equivalent to {w^T}{z}=0. There is an obvious exponential time algorithm to solve LCP. For every i, set either w_i=0 or z_i=0 and solve the resulting system of linear equations. If one of these linear systems has a solution then the corresponding LCP is solvable. Deciding if a given LCP has a solution is NP-complete. The following exercise shows that LCP is a generalization of LP.

Exercise : Every LP can solved by solving a corresponding LCP, representing the complementary slackness of the LP.

LCP can also be expressed in the following equivalent form :

LCPobj

Lemke’s algorithm is a “path-following” algorithm (similar to simplex algorithm) to solve LCP. Unfortunately, Lemke’s algorithm can sometimes fail to produce a solution even if one exists !! There are many special instances of LCP on which Lemke’s algorithm always produces a solution or a certificate that no solution exists.

As mentioned earlier, solving an LCP is NP-complete. What about special cases ? i.e., when the input matrix M is special.

  • If M is a Positive Semi-Definite matrix, then LCP(q,M) can be solved in polynomial time. In fact, every LCP with a PSD matrix is a convex quadratic program and every convex quadratic program can be expressed as an LCP with a PSD matrix.
  • If M is a Z-matrix, Chandrasekaran’s algorithm solves LCP(q,M) in polynomial time [Chandrasekaran'70].
  • If M is a triangular P-matrix, LCP(q,M) can be solved in polynomial time by using a back substitution method.
  • If M is a P-matrix, LCP(q,M) has a unique solution for every q.

Following is one of the coolest applications of LCP.

Exercise : Finding a Nash Equilibrium in a bimatrix game can be expressed as an LCP.

Lemke-Howson’s algorithm [Lemke,Howson'64] to solve a bimatrix game is known to take exponential number of steps in the worst case [Savani, vonStengel'04]. It is also known that finding Nash equilibrium in a bimatrix game is PPAD-complete [Chen,Deng'09].

Open Problems :

  • The complexity of solving LCP with a P-matrix (P-LCP) is open for more than two decades !! P-LCP is known to be in PPAD [Papadimitriou'94]. Note that recognizing Z-matrices and PSD-matrices can be done in polynomial-time but recognizing P-matrices is coNP-complete [Coxson'94].
  • Are there other interesting classes of matrices M for which LCP(q,M) is solvable in polynomial time ?
  • Savani and von Stengel’s instance of bimatrix game has “full support mixed equilibrium”, which can easily solved using linear programming techniques. It is an open problem to construct an instance of a bimatrix game that does not have full-support mixed equilibrium and the Lemke-Howson algorithm takes exponential number of steps on this instance.
    Savani and von Stengel’s instance of bimatrix game has full support.
    It is open problem to construct an instance of bimatrix game that
    does not have full-support mixed equilibrium and the Lemke-Howson algorithm
    takes exponential number of steps.

References :

  • [Chandrasekaran'70] R. Chandrasekaran. “A Special Case of the Complementary Pivot Problem“, Opsearch, 7(1970) 263 268.
  • [Coxson'94] G. E. Coxson. The P-matrix problem is co-NP-complete. Math. Programming, 64(2):173–178, 1994.
  • [Chen,Deng'09] Xi Chen, Xiaotie Deng, Shang-Hua Teng: Settling the complexity of computing two-player Nash equilibria. J. ACM 56(3): (2009)
  • [Savani, vonStengel'04] Rahul Savani, Bernhard von Stengel: Exponentially Many Steps for Finding a Nash Equilibrium in a Bimatrix Game. FOCS 2004: 258-267
  • [Lemke,Howson'64] Lemke, C. E. and J. T. Howson, Jr. (1964), Equilibrium points of bimatrix games. Journal of the Society for Industrial and Applied Mathematics 12, 413–423.
  • [Papadimitriou'94] Christos H. Papadimitriou: On the Complexity of the Parity Argument and Other Inefficient Proofs of Existence. J. Comput. Syst. Sci. 48(3): 498-532 (1994)
by

Held Karp Relaxation

The Traveling Salesman Problem (TSP) is undoubtedly the most important and well-studied problem in Combinatorial Optimization. Today’s post is a quick overview of the Held-Karp Relaxation of TSP.

TSP : Given a complete undirected graph G(V,E) with non-negative costs c_e for each edge e \in E, find a hamiltonian cycle of G with minimum cost. It is well-known that this problem is NP-Complete.

Exercise : There is no \alpha-approximation algorithm for TSP (for any \alpha \geq 1) unless P=NP.

Metric TSP : In Metric-TSP, the edge costs satisfy triangle inequality i.e., for all u,v,w \in V, c(u,w) \leq c(u,v) + c(v,w). Metric-TSP is also NP-complete. Henceforth, we shall focus on metric TSP.

Symmetric TSP (STSP) : In STSP, the edge costs are symmetric i.e., c(u,v) = c(v,u). Approximation algorithms with factor 2 (find a minimum spanning tree (MST) of G and use shortcuts to obtain a tour) and factor 3/2 (find an MST, find a perfect matching on the odd degree nodes of  the MST to get a eulerian graph and obtain a tour) are well-known. The factor 3/2 algorithm, known as Christofides Algorithm [Christofides'76], is the best known approximation factor for STSP. No improvement in the last three decades !!

Following is the Held-Karp Relaxation for STSP with the cut constraints and the degree constraints. The variables are x_e, one for each edge e \in E. For a subset S \subset V, \delta(S) denotes the edges incident to S. Let x(\delta(S)) denote the sum of values of x_e of the edges with exactly one endpoint in S. For more details of Held-Karp relaxation see [HK'70, HK'71]

hk-stsp

Exercise : In the following instance of STSP the cost between vertices u and v is the length of the shortest path between u and v. The three long paths are of length k. Prove that this instance achieves an integrality ratio arbitrarily close to 4/3 (as k is increased).

stsp

Asymmetric TSP (ATSP) : In ATSP, the edge costs are not necessarily symmetric i.e., the underlying graph is directed. The Held-Karp relaxation for ATSP is as follows :

hk-atsp

Charikar, Goemans and Karloff [CGK'04] showed that the integrality of Held-Karp relaxation for ATSP is at least 2-\epsilon. Frieze, Galbiati and Maffioli [FGM'82] gave a simple O({\log}_2{n})-approximation algorithm for ATSP in 1982, where n is the number of vertices. In the last eight years, this was improved to a guarantee of 0.999 {\log}_2{n} by Blaser [Blaser'02], and to \frac{4}{3}{\log}_3{n} Kaplan et al [KLSS'03] and to \frac{2}{3}{\log}_2{n} by Feige and Singh [FS'07]. So we have an approximation factor better than {\ln}n !!

Open Problems :

  • The long-standing open problem is to determine the exact integrality gap of Held-Karp relaxation. Many researchers conjecture that the integrality gap of Held-Karp relaxation for STSP is 4/3 and for ATSP it is bounded by a constant. The best known upper bounds are 3/2 and O(logn) respectively.
  • The size of the integrality gap instance of ATSP (constructed by [CGK'04]) is exponential in 1/\epsilon to achieve an integrality gap of 2-\epsilon. Is there a polynomial-sized (in 1/\epsilon) instance achieving an integrality gap of 2-\epsilon ?

References :

Nicos Christofides, Worst-case analysis of a new heuristic for the travelling salesman problem, Report 388, Graduate School of Industrial Administration, CMU, 1976.

  • [HK'70] Micheal Held and Richard M. Karp, The Traveling Salesman Problem and Minimum Spanning Trees, Operations Research 18, 1970, 1138–1162.
  • [HK'71] Michael Held and Richard Karp, The Traveling-Salesman Problem and Minimum Spanning Trees: Part II, Mathematical Programming 1, 1971, 6–25.
  • [Christofides'76] Nicos Christofides, Worst-case analysis of a new heuristic for the travelling salesman problem, Report 388, Graduate School of Industrial Administration, CMU, 1976.
  • [FGM'82] A. M. Frieze, G. Galbiati and M. Maffioli, On the Worst-Case Performance of Some Algorithms for the Asymmetric Traveling Salesman Problem, Networks 12, 1982, 23–39.
  • [Blaser'02] M. Blaser, A New Approximation Algorithm for the Asymmetric TSP with Triangle Inequality, Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms, 2002, 638–645.
  • [KLSS'03] H. Kaplan, M. Lewenstein, N. Shafir and M. Sviridenko, Approximation Algorithms for Asymmetric TSP by Decomposing Directed Regular Multidigraphs, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, 2003, 56–67.
  • [CGK'04] Moses Charikar, Michel X. Goemans, Howard J. Karloff: On the Integrality Ratio for Asymmetric TSP. FOCS 2004: 101-107
  • [FS'07] Uriel Feige, Mohit Singh: Improved Approximation Ratios for Traveling Salesperson Tours and Paths in Directed Graphs. APPROX-RANDOM 2007: 104-118

by

Scarf’s Lemma

Proof and Applications of Scarf’s Lemma…….

Today’s post is about Scarf’s Lemma, my recent obsession. I learnt about Scarf’s Lemma while reading Haxell & Wilfong’s paper [HW'08] on Fractional Stable Paths Problem (FSPP). I will write about FSPP in a future post. Today’s post is about the elegant proof of Scarf’s Lemma and its wonderful applications.

Scarf’s Lemma : Let m < n and let B be an m \times n real matrix such that b_{ij} = \delta_{ij} for 1 \leqslant i, j \leqslant m. Let b be a non-negative vector in {\mathbb{R}}^m,  such that the set \{\alpha\in{\mathbb{R}}_{+}^n : B{\alpha}=b\} is bounded. Let C be an m \times n matrix such that c_{ii} \leqslant c_{ik} \leqslant c_{ij} whenever i,j \leqslant m, i \neq j and k > m. Then there exists a subset J of size m of [n] such that

  • (feasible) : B{\alpha}=b for some \alpha\in{\mathbb{R}}_{+}^n such that \alpha_j=0 whenever j\notin{J}.
  • (subordinating) : For every k \in [n] there exists i \in [m] such that c_{ik} \leqslant c_{ij} for all j \in J.

Proof of Scarf’s Lemma :

We want an \alpha\in{\mathbb{R}}_{+}^n which is simultaneously feasible for B and subordinating for C. Note that it is easy to find a feasible x and a subordinating y that are “almost same”. Choose x = [m]. Choose y = (2,3,....,m,j) where j is selected from all of the columns k > n so as to maximize c_{1k}. Now x and y have m-1 columns in common. To find the required \alpha we shall apply the following (feasible and ordinal) pivot steps. Throughout we shall maintain this relationship of having at least m-1 common columns. This elegant and powerful idea was first introduced in the Lemke-Howson Algorithm. I will talk about Lemke-Howson algorithm it in a future post.

Assuming non-degeneracy for matrices B and C the following lemmas hold. (C is said to be non-degenerate if no two elements in the same row are equal).

(i) Feasible Pivot Step : Let J be a feasible basis for (B, b), and k\in[n]\setminus{J}. Then there exists a unique j \in J such that J+k-j (i.e., J\cup\{k\}{\setminus}\{j\}) is a feasible basis.

(ii) Ordinal Pivot Step : Let K be a subordinating set for C of size m-1. Then there are precisely two elements j \in [n]{\setminus}K such that K+j is subordinating for C, unless K\subseteq[m], in which case there exists precisely one such j.

Proof of (i) is well-known. For Proof of (ii), refer to [Schrijver's Book]. To prove Scarf’s lemma we construct a bipartite graph \mathcal{G} with partitions A (the set of all feasible bases containing 1) and B (the set of all subordinating sets of size m not containing 1. A vertex a \in A is joined to a vertex b \in B if a\setminus b = \{1\}.

Exercise : Prove that every node (except [m] and the required solution \alpha) in \mathcal{G} have degree two.

Since [m] is not subordinating, the required solution \alpha which is both feasible and subordinating must exist. Note that this proof gives a PPA membership of the computational version of Scarf’s lemma. For PPAD-membership and PPAD-completeness of Scarf’s lemma and its applications (mentioned below) see [KPRST'09].

Applications of Scarf’s Lemma :

Scarf’s lemma provides an elegant proof for a number of “fractional stability type” problems. Here is the list, starting with Scarf’s original paper that introduced the Scarf’s lemma.

Theorem (Scarf’67) : Every balanced game with non-transferable utilities has a non-empty core.

Theorem (AH’98) : Every clique-acyclic digraph has a strong fractional kernel.

Theorem (AF’03) : Every hypergraphic preference system has a fractional stable solution.

Theorem (HW’08) : Every instance of Stable Paths Problem has a fractional stable solution.

Open Problems : Are there other unexplored applications of Scarf’s lemma ? It is known [Scarf'67] that Scarf’s lemma provides a combinatorial proof of Brower’s fixed point theorem. Can we use Scarf’s lemma to prove other fixed-point theorems, for example, geometric stability theorems from topology. The above mentioned applications are all PPAD-complete [KPRST'09]. Are there interesting applications of Scarf’s lemma that are polynomial time solvable ?

References :

  • [Scarf'67] Herbert E. Scarf : The Core of an N Person Game. Econometrica, Vol 69, 35-50 (1967)
  • [AH'98] Ron Aharoni, Ron Holzman : Fractional Kernels in Digraphs. J. Comb. Theory, Ser. B 73(1): 1-6 (1998)
  • [AF'03] Ron Aharoni, Tamás Fleiner : On a lemma of Scarf. J. Comb. Theory, Ser. B 87(1): 72-80 (2003)
  • [HW'08] Penny E. Haxell, Gordon T. Wilfong : A fractional model of the border gateway protocol (BGP). SODA 2008: 193-199
  • [KPRST'09] Shiva Kintali, Laura J. Poplawski, Rajmohan Rajaraman, Ravi Sundaram, Shang-Hua Teng Reducibility Among Fractional Stability Problems Electronic Colloquium on Computational Complexity (ECCC) TR09-041 (2009) [pdf]
  • [Schijver's Book] Alexander Schrijver : Combinatorial Optimization, Polyhdera and Efficiency, Volume B Springer-Verlag Berlin Heidelberg, (2003)