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
The paper
ReplyDeleteKen-ichi Kawarabayashi, Bruce A. Reed: Computing crossing number in linear time. STOC 2007: 382-390
shows that computing the min number k of edges whose removal makes a graph planar is fpt wrt to k.
Thank you Anonymous. Do you have any idea if that paper contains ideas that might help for reconstruction?
ReplyDeleteIt seems that the Kawarabayashi-Reed algorithm explicitly finds the obstruction to planarity, so it should be enough for reconstruction. Problem is that in KR k is constant, but when you add a random graph that might not be the case. I wonder - given a planar graph, add an edge randomly - what is the probability that you increased the crossing number?
ReplyDeleteNote that you do not necessarily get "the ground truth" (and can't really hope for it...) but rather some planar graph contained in the input.
Yes, you do not necessarily get the "ground truth". You you really want is the max likelihood planar graph that can lead to the input.
ReplyDeleteA random edge almost surely increases the crossing number. Take the grid of triangles, add a random edge: most likely, its endpoints are far from one another in the grid, and then the edge increases the crossing number.
One would hope that even if the noise added n/100 such edges, they would still be easy to spot and to remove...