Complexity of Finding and Enumerating Interconnection Trees
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2026
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866910232189337600 |
|---|---|
| author | Demange, Noé Strozecki, Yann |
| author_facet | Demange, Noé Strozecki, Yann |
| contents | We study the problem of connecting the parts of a multipartite graph using a minimum number of edges under a matching constraint. We introduce interconnection trees, defined as matchings whose projections onto the quotient graph form a spanning tree. Motivated by applications in chemoinformatics, we investigate the decision, counting, and enumeration variants of this problem.
We show that the decision problem is $NP$-complete. Nevertheless, it becomes tractable in several structured settings: it is fixed-parameter tractable in the number of parts, and admits polynomial or linear-time algorithms on complete, quasi-complete, and $t$-quasi-complete multipartite graphs. We also study enumeration, for which we design efficient flashlight-search based algorithms with optimal delay for complete multipartite graphs, and a weight-guided heuristic that prioritizes low-weight solutions and performs well in practice. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_18125 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Complexity of Finding and Enumerating Interconnection Trees Demange, Noé Strozecki, Yann Computational Complexity Data Structures and Algorithms F.2 We study the problem of connecting the parts of a multipartite graph using a minimum number of edges under a matching constraint. We introduce interconnection trees, defined as matchings whose projections onto the quotient graph form a spanning tree. Motivated by applications in chemoinformatics, we investigate the decision, counting, and enumeration variants of this problem. We show that the decision problem is $NP$-complete. Nevertheless, it becomes tractable in several structured settings: it is fixed-parameter tractable in the number of parts, and admits polynomial or linear-time algorithms on complete, quasi-complete, and $t$-quasi-complete multipartite graphs. We also study enumeration, for which we design efficient flashlight-search based algorithms with optimal delay for complete multipartite graphs, and a weight-guided heuristic that prioritizes low-weight solutions and performs well in practice. |
| title | Complexity of Finding and Enumerating Interconnection Trees |
| topic | Computational Complexity Data Structures and Algorithms F.2 |
| url | https://arxiv.org/abs/2605.18125 |