Open problems

This page lists a few open problems I'm interested in. It should be seen as a personal page I don't mind making public, because I will not take the time here to explain the full details of everything I mention. However, I have sometimes provided a few references I know about on the subject, which you can access by clicking the corresponding "bib" link. For further information, my publications may also help. If you have ideas, don't hesitate to get in touch: I'm always up for teamwork, and I'd really like to have more coauthors. Updated stuff will be in red and/or brought back on top of the list.

• Maximum common subgraph: given a graph and a tree, both of which are partially vertex-labelled, find their maximum common subgraph. The problem is NP-hard, but how fast can we solve it?
• "Warmuth's conjecture": does every concept class of finite VC dimension d have a compression scheme of size d?
• The following problems have been solved (submitted paper):
• Edge-partitioning graphs:
  • join the discussion on MathOverflow or on Stack Exchange TCS
• Partitions:
  • join the discussion on MathOverflow or on Stack Exchange TCS
• Minimum common supergraphs of partially labelled graphs: (there are some results in my Ph. D. thesis)
  • complexity of the problem on two and more trees;
  • other tractable cases than restricted graphs?
• Sorting by transpositions: bib
  • determine the complexity of the problem; this seems to have been settled (not by me): see the preprint
  • determine the transposition diameter;
• Burnt pancake flipping: my latest paper with Josef Cibulka features a new tight lower bound on the prefix signed reversal distance, and we are able to sort simple permutations in polynomial time; future work could include:
  • tightening the lower bound for arbitrary permutations;
  • designing improved approximation algorithms based on that lower bound;
  • and of course, settling the complexity of the problem; note that the unburnt variant is now known to be NP-hard
• Path-dependent shortest path problems: given an edge-weighted digraph, find a least-cost path from vertex s to vertex t. The catch: path cost depends not only on edge weights, but also on which path you've taken.
  • the general problem is NP-hard; in which case can we prove polynomial time solvability?
  • the "suffix-k" variant (path cost can be altered by at most k edges) can be solved in O(|V|^k|E|) time; can we do better than that?
• Gift wrapping: currently researching the literature (if you can help me, please drop me a line! I don't even know if the name is accurate), but the problem I'm interested in is the following:
  • given a polyhedron and a sheet of paper, how can you wrap the polyhedron using as few paper as possible?
• Sorting by prefix transpositions: bib
  • determine the complexity of the problem;
  • determine the prefix transposition diameter (lies between (3n+1)/4 and n-1);
• Pancake flipping:
  • can the current best approximation ratio (2) by Fischer and Ginzinger be outperformed?
• Edit distances in general: my ESA 2008 paper introduces a simple and generic way to obtain lower bounds on edit distances on permutations. It spawns a number of interesting questions, for instance:
  • can we generalise the model to other structures (e.g. signed permutations, strings, ...)?
  • can we extend the model to derive upper bounds rather than lower bounds?
• Universal graphs:
  • bounds for the number of edges in a universal graph for spanning trees?
  • can we characterise "optimal" universal graphs?

Other problems that have been giving brilliant minds a hard time can be found through these links:

• The Open Problem Garden is a collection of open problems in mathematics and theoretical computer science
• The Open Problems Project focuses on computational geometry
• If you need money or are looking for something really serious, check out the Millenium Problems