{"ID":2832232,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2512.06383","arxiv_id":"2512.06383","title":"Finding a Maximum Common (Induced) Subgraph: Structural Parameters Revisited","abstract":"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.","short_abstract":"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...","url_abs":"https://arxiv.org/abs/2512.06383","url_pdf":"https://arxiv.org/pdf/2512.06383v1","authors":"[\"Tesshu Hanaka\",\"Yuto Okada\",\"Yota Otachi\",\"Lena Volk\"]","published":"2025-12-06T10:27:45Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}