Parameterized Complexity of Finding a Maximum Common Vertex Subgraph Without Isolated Vertices
This work advances the theoretical understanding of a variant of the Maximum Common Subgraph problem, which has applications in computational social choice, by characterizing its parameterized complexity across multiple structural parameters.
The paper studies the Maximum Common Vertex Subgraph problem without isolated vertices, proving it is NP-hard and providing an FPT algorithm parameterized by h. It also establishes a complete parameterized complexity dichotomy with respect to structural parameters like vertex cover number, treewidth, and treedepth.
In this paper, we study the Maximum Common Vertex Subgraph problem: Given two input graphs $G_1,G_2$ and a non-negative integer $h$, is there a common subgraph $H$ on at least $h$ vertices such that there is no isolated vertex in $H$. In other words, each connected component of $H$ has at least $2$ vertices. This problem naturally arises in graph theory along with other variants of the well-studied Maximum Common Subgraph problem and also has applications in computational social choice. We show that this problem is NP-hard and provide an FPT algorithm when parameterized by $h$. Next, we conduct a study of the problem on common structural parameters like vertex cover number, maximum degree, treedepth, pathwidth and treewidth of one or both input graphs. We derive a complete dichotomy of parameterized results for our problem with respect to individual parameterizations as well as combinations of parameterizations from the above structural parameters. This provides us with a deep insight into the complexity theoretic and parameterized landscape of this problem.