Month: July 2009

by

Finding a Second Hamilton Circuit

De
Given an undirected graph does it have a Hamilton circuit ? It is well-known that this is an NP-complete problem. Consider the following problem :
ANOTHER HAMILTON CIRCUIT : Given a Hamilton circuit in a graph find another hamilton circuit.
It is easy to see that ANOTHER HAMILTON CIRCUIT is FNP-complete. What if we are given a Hamilton graph which is guaranteed to have a second Hamilton circuit. Following is a simple exercise :
Exercise : Prove that if a cubic graph has a hamilton circuit then it must have a second one
The above exercise is called Smith’s Theorem. Now consider the following computational poblem :
SMITH : Given a Hamilton circuit in a 3-regular graph, find a second Hamilton circuit.
Since the second hamilton circuit is guaranteed to exist, SMITH belongs to complexity class TFNP. Note that TFNP is a semantic class. In a beautiful paper [1] Papadimitriou defined several syntactic classes (e.g., PPA, PPAD, PPP) in TFNP. Papadimitriou proved that SMITH is in the complexity class PPA [1]. Here is an open problem mentioned in [1].
Open Problem : Find a polynomial time algorithm for SMITH (or) Prove that SMITH is PPA-complete.
[1] 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)

Deciding if an undirected graph has a Hamilton circuit is a well-known NP-complete problem. Let’s consider the following problem :

ANOTHER HAMILTON CIRCUIT : Given a Hamilton circuit in a graph find another hamilton circuit.

It is easy to see that ANOTHER HAMILTON CIRCUIT is FNP-complete. What if we are given a Hamilton graph which is guaranteed to have a second Hamilton circuit. Following is a simple exercise :

Smith’s Theorem : Prove that if a cubic graph has a hamilton circuit then it must have a second one

Now consider the following computational poblem :

SMITH : Given a Hamilton circuit in a 3-regular graph, find a second Hamilton circuit.

Thomason’s proof [Thomason’78] of Smith’s theorem yields an algorithm that given one Hamiltonian cycle in a cubic graph, computes another one. Since the second hamilton circuit is guaranteed to exist, SMITH belongs to complexity class TFNP. Note that TFNP is a semantic class. In a beautiful paper [Papadimitriou’94] Papadimitriou defined several syntactic classes (e.g., PPA, PPAD, PPP) in TFNP. Infact one can convert Thomason’s proof  into a PPA-membership proof of SMITH. Simply put, PPA is the undirected version of the complexity class PPAD. Krawczyk showed that [Krawczyk’99] the “PPA-graph” of SMITH can have exponentially long paths, thus proving that Thomason’s algorithm is exponential in the worst case.

Open Problems

  • Find a polynomial time algorithm for SMITH (or) Prove that SMITH is PPA-complete.
  • Are there special cases of SMITH solvable in polynomial-time ?

References :

  • [Krawczyk’99] Adam Krawczyk: The Complexity of Finding a Second Hmiltonian Cycle in Cubic Graphs. J. Comput. Syst. Sci. 58(3): 641-647 (1999)
  • [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)
  • [Thomason’78] A. G. Thomason, Hamiltonian cycles and uniquely edge colourable graphs, Ann. Discrete. Math. 3 (1978), 259-268.
by

The Sunflower Lemma

Today’s post is about the Sunflower Lemma (a.k.a the Erdos-Rado Lemma). I learnt about Sunflower Lemma while reading Razborov’s Theorem from Papadimitriou’s computational complexity book.

A sunflower is a family of p sets \{P_1,P_2,\dots,P_p\}, called petals, each of cardinality at most l, such that all pairs of sets in the family have the same intersection, called the core of the sunflower.

The Sunflower Lemma : Let Z be a family of more than M=(p-1)^{l}l! nonempty sets, each of cardinality l or less. Then Z must contain a sunflower.

Exercise : Prove the Sunflower Lemma

The best known lower bound on M is (p-1)^l.

Exercise : Construct a family of  (p-1)^l nonempty sets that does not have a sunflower.

We develop counterparts
of the Sunflower Lemma for distributive lattices, graphic matroids, and matroids
representable over a xed nite eld.

Sunflower lemma plays a crucial role in Razborov’s theorem [Razborov’85]. [McKenna’05] generalized the Sunflower Lemma for distributive lattices, graphic matroids, and matroids representable over a fi xed fi nite fi eld.

I am not aware of other applications of Sunflower Lemma. If you know any, please leave a comment.

Open problems :

  • Improve the upper/lower bound on M.
  • Erdos and Rado conjectured that “For every fixed p there is a constant C = C(p) such that a family of more than C^{l} nonempty sets, each of cardinality l or less has a sunflower”. This conjecture is still open. It is open even for p=3.

References :

  • [Razborov’85] A. A. Razborov, Some lower bounds for the monotone complexity of some Boolean functions, Soviet Math. Dokl. 31 (1985), 354-357.
  • [McKenna’05] Geoffrey McKenna, Sunflowers in Lattices, The Electronic Journal of Combinatorics Vol.12 2005 [pdf]
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