Complexity of Finding and Enumerating Interconnection Trees
For researchers in chemoinformatics and graph theory, this paper provides complexity results and algorithms for a new combinatorial problem, though the results are largely theoretical and incremental.
The paper introduces interconnection trees and shows that the decision problem is NP-complete, but becomes tractable in structured settings such as complete or quasi-complete multipartite graphs, with fixed-parameter tractability in the number of parts. Efficient enumeration algorithms with optimal delay are provided for complete multipartite graphs.
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.