Finding a Maximum Common (Induced) Subgraph: Structural Parameters Revisited
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866917131002576896 |
|---|---|
| author | Hanaka, Tesshu Okada, Yuto Otachi, Yota Volk, Lena |
| author_facet | Hanaka, Tesshu Okada, Yuto Otachi, Yota Volk, Lena |
| contents | We study the parameterized complexity of the problems of finding a maximum common (induced) subgraph of two given graphs. Since these problems generalize several NP-complete problems, they are intractable even when parameterized by strongly restricted structural parameters. Our contribution in this paper is to sharply complement the hardness of the problems by showing fixed-parameter tractable cases: both induced and non-induced problems parameterized by max-leaf number and by neighborhood diversity, and the induced problem parameterized by twin cover number. These results almost completely determine the complexity of the problems with respect to well-studied structural parameters. Also, the result on the twin cover number presents a rather rare example where the induced and non-induced cases have different complexity. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_06383 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Finding a Maximum Common (Induced) Subgraph: Structural Parameters Revisited Hanaka, Tesshu Okada, Yuto Otachi, Yota Volk, Lena Data Structures and Algorithms We study the parameterized complexity of the problems of finding a maximum common (induced) subgraph of two given graphs. Since these problems generalize several NP-complete problems, they are intractable even when parameterized by strongly restricted structural parameters. Our contribution in this paper is to sharply complement the hardness of the problems by showing fixed-parameter tractable cases: both induced and non-induced problems parameterized by max-leaf number and by neighborhood diversity, and the induced problem parameterized by twin cover number. These results almost completely determine the complexity of the problems with respect to well-studied structural parameters. Also, the result on the twin cover number presents a rather rare example where the induced and non-induced cases have different complexity. |
| title | Finding a Maximum Common (Induced) Subgraph: Structural Parameters Revisited |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2512.06383 |