Parameterized Complexity of Finding a Maximum Common Vertex Subgraph Without Isolated Vertices
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866913068735266816 |
|---|---|
| author | Dey, Palash Dhar, Anubhav Hota, Ashlesha Kolay, Sudeshna Mitra, Aritra |
| author_facet | Dey, Palash Dhar, Anubhav Hota, Ashlesha Kolay, Sudeshna Mitra, Aritra |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_10948 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Parameterized Complexity of Finding a Maximum Common Vertex Subgraph Without Isolated Vertices Dey, Palash Dhar, Anubhav Hota, Ashlesha Kolay, Sudeshna Mitra, Aritra Computational Complexity Data Structures and Algorithms 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. |
| title | Parameterized Complexity of Finding a Maximum Common Vertex Subgraph Without Isolated Vertices |
| topic | Computational Complexity Data Structures and Algorithms |
| url | https://arxiv.org/abs/2602.10948 |