My latest preprint, arXiv:2101.09918 with Sid Gupta and Elham Havvaei, has a mouthful of a title: “Parameterized complexity of finding subgraphs with hereditary properties on hereditary graph classes”. It’s about finding large induced subgraphs with a given property within a larger graph, such as in an earlier paper I wrote on finding large planar induced subgraphs.

Since we’re looking for induced subgraphs, it makes sense to restrict attention to properties that behave nicely under induced subgraphs; these are called hereditary properties. And if there’s no restriction on what kind of graph the larger graph can be, then the parameterized complexity of this induced subgraph problem (parameterized by the number of vertices in the subgraph) is completely settled by a paper by Khot and Raman, “Parameterized complexity of finding subgraphs with hereditary properties” (Theor. Comput. Sci. 2002). The result depends only on whether the subgraphs you’re looking for include arbitrary large cliques or arbitrarily large independent sets. If both, then the answer to “is there a \(k\)-vertex induced subgraph with the property” is (for all sufficiently large inputs) yes, by Ramsey’s theorem, so the algorithmic problem is easy. If neither, then again Ramsey’s theorem says that (for all sufficiently large \(k\)) the answer is no, so again the problem is easy. And in all remaining cases, when the property includes large cliques but not large independent sets or vice versa, Khot and Raman show that the problem is hard for parameterized computation.

But what if the input is not allowed to be an arbitrary graph, but is restricted to another hereditary class of graphs? An example we consider is the problem of finding large planar induced subgraphs in unit disk graphs. Planar graphs fall into the hard side of Khot and Raman’s dichotomy, but their hardness proof uses graphs that might not be unit disk graphs. Our results involve more case analysis based on cliques and independent sets, but for the input graph class as well as for the target subgraph class, so there are many more cases to consider. Again, Ramsey theory clears away many of them, either by saying that all sufficiently large inputs contain big subgraphs in the target class, or by limiting the number of subgraphs we need to consider to a finite set.

The case analysis from our paper focuses attention on one remaining case, where Ramsey-like arguments do not prevail. This is the case where the target subgraph class is one of the types that is hard for Khot and Raman’s dichotomy (such as finding induced planar subgraphs), and where the input subgraph class can contain both large cliques and large independent sets (as is true for the unit disk graphs). It would be nice to say that in this case everything is hard, providing a nice clean dichotomy, but some problems like this are not hard. For instance, when the input is a cluster graph, a disjoint union of cliques, the largest induced planar subgraph is obtained by taking at most four vertices from each clique, and many other induced subgraph problems on cluster graphs are equally easy. We were at least able to find a couple of general hardness reductions that apply in many cases, including in the planar-in-unit-disk case. But the question of whether all problems in this case are either easy (fixed-parameter tractable) or hard, and if so whether there is an easy way of determining which side of the dichotomy any particular subgraph-searching problem falls into, remains open.

(Discuss on Mastodon)