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 [...]

Read Full Post »

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 , called petals, each of cardinality at most l, such that all pairs of sets in the family have the same intersection, [...]

Read Full Post »

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 with non-negative costs for each edge , find a hamiltonian cycle of G with minimum cost. It is well-known that [...]

Read Full Post »