Corelab Seminar

Dimitris Chatzidimitriou (UoA)
Recognizing Subgraphs of Grids is NP-Complete

A graph H that can be obtained from a graph G by successively removing either one of its vertices or one of its edges is called a subgraph of G. Other relations between graphs such as the minor and the induced minor relationship are well studied and the corresponding problems of recognizing whether a graph is a minor of another is shown to be in P, while for induced minors is FPT. On the other hand, the subgraph relation seems to be more difficult to recognize since the corresponding general problem is in NP. In this talk we will show that the much more specific problem of recognizing whether a given graph is a subgraph of a (large enough) grid is also in NP.