Wish you all a Very Happy New Year. Here is a list of my 10 favorite open problems for 2014. They belong to several research areas inside discrete mathematics and theoretical computer science. Some of them are baby steps towards resolving much bigger open problems. May this new year shed new light on these open problems.
- 1. Combinatorics : Prove that trees with diameter 6 are graceful. (see earlier posts graceful tree conjecture, graceful diameter-6 trees).
- 2. Optimization :Improve the approximation factor for the undirected graphic TSP. The best known bound is 7/5 by Sebo and Vygen.
- 3. Algorithms :Prove that the tree-width of a planar graph can be computed in polynomial time (or) is NP-complete.
- 4. Fixed-parameter tractability : Treewidth and Pathwidth are known to be fixed-parameter tractable. Are directed treewidth/DAG-width/Kelly-width (generalizations of treewidth) and directed pathwidth (a generalization of pathwidth) fixed-parameter tractable ?
View original post 358 more words