A criticism often heard coming from scientists in other disciplines is that we put too much emphasis on worst-case analysis. But where else would we go? I have an interest in reconstruction problems, when the input is a noisy version of some hidden ground truth.
Recently I was looking at a paper by Magen and Moharrami about independent set in near-planar graphs, that is, planar graphs with o(n) extraneous edges.
Now, how about reconstructing a planar graph?
The problem would take as input a graph and remove the fewest edges to make it planar (minimum non-planar deletion). Think about Kleinberg's original small world networks: they consisted of a planar graph plus a moderate number of random "long" edges. So, such graphs have been considered. The problem is APX-hard. The complementary problem has a constant factor approximation (Calinescu, Fernandes, Finkler and Karloff). Here's the question. Consider a graph built as follows: first, pick an arbitrary planar graph -- the ground truth. Then, take a random graph G(n,p) where p=o(1)/n -- the noise. The superposition of those two graphs is the input. Given the input, is it possible to reconstruct the ground truth or at least a close approximation to it?
Why this may be a good open question:
- The broad area of reconstruction is exciting
- It is not inconceivable that a good algorithm might interest people outside Theory.
- The problem has not been studied that much, so there are not yet walls of impossibly hard questions in every direction.
- The probabilistic question feels doable. It has never been considered before.
- Little background is needed
- It is a chance to learn about: elementary random graph techniques and perhaps basic FPT techniques