Complexity of Finding and Enumerating Interconnection Trees

No\'e Demange; Yann Strozecki

arxiv: 2605.18125 · v1 · pith:MRZOWSSNnew · submitted 2026-05-18 · 💻 cs.CC · cs.DS

Complexity of Finding and Enumerating Interconnection Trees

No\'e Demange , Yann Strozecki This is my paper

Pith reviewed 2026-05-20 00:06 UTC · model grok-4.3

classification 💻 cs.CC cs.DS

keywords interconnection treesmultipartite graphsNP-completenessfixed-parameter tractabilityenumeration algorithmsmatchingsspanning treeschemoinformatics

0 comments

The pith

Finding interconnection trees is NP-complete in general multipartite graphs but fixed-parameter tractable by the number of parts and polynomial-time on complete ones.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper studies interconnection trees, which are matchings in a multipartite graph such that contracting each part to a single vertex yields a spanning tree on the resulting quotient graph. It proves that deciding whether an interconnection tree using at most a given number of edges exists is NP-complete. The problem becomes fixed-parameter tractable when parameterized by the number of parts, and it admits polynomial-time or linear-time algorithms when the multipartite graph is complete, quasi-complete, or t-quasi-complete. These complexity results are motivated by applications in chemoinformatics that require minimal connecting structures under a matching constraint between molecular parts.

Core claim

Interconnection trees are defined as matchings whose projections onto the quotient graph form a spanning tree. The decision problem of finding such a tree with a bounded number of edges is NP-complete. It is fixed-parameter tractable parameterized by the number of parts. Polynomial and linear-time algorithms exist on complete, quasi-complete, and t-quasi-complete multipartite graphs. Efficient flashlight-search enumeration algorithms with optimal delay are given for complete multipartite graphs, along with a weight-guided heuristic that performs well in practice.

What carries the argument

Interconnection tree: a matching in the multipartite graph whose edges, when each part is contracted to a vertex, produce a spanning tree on the quotient graph.

If this is right

When the number of parts is treated as a fixed parameter, algorithms exist that run efficiently even on large graphs.
On complete multipartite graphs, all interconnection trees can be enumerated with optimal delay.
The same structural restrictions that make the decision problem easy also make counting and enumeration tractable.
Weight-guided search heuristics can be used in practice to find low-cost interconnection trees quickly.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The parameterized approach could be extended to other connectivity problems that combine matching constraints with global tree structure.
Similar quotient-graph techniques might apply to hypergraph versions or to directed interconnection problems.
In chemoinformatics the linear-time results on complete multipartite graphs suggest that certain molecular scaffolds can be screened in linear time once the part partition is known.

Load-bearing premise

The definition of interconnection trees as matchings whose projections form spanning trees on the quotient graph transfers complexity results from ordinary spanning-tree and matching problems.

What would settle it

An explicit polynomial-time algorithm that decides the existence of an interconnection tree with at most k edges on arbitrary multipartite graphs would disprove the NP-completeness claim.

read the original abstract

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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

This paper defines interconnection trees via matchings projecting to spanning trees and gives NP-completeness plus FPT and poly-time results on multipartite graphs, but the chemoinformatics link stays thin.

read the letter

The main thing to take from this paper is that interconnection trees are NP-complete to find in general multipartite graphs, yet become fixed-parameter tractable when parameterized by the number of parts and admit polynomial or linear-time algorithms on complete, quasi-complete, and t-quasi-complete multipartite graphs. The authors also give enumeration algorithms with flashlight search for optimal delay in the complete case and a weight-guided heuristic that they say works well in practice. The definition is straightforward and lets standard reductions and dynamic programming carry over without much extra machinery, which keeps the arguments clean. The FPT result and the structured-graph algorithms are the parts that actually add something concrete; they identify new tractable islands for a problem that combines matching constraints with cross-part connectivity. The enumeration work is systematic and the practical heuristic is at least presented as an improvement over naive search. The chemoinformatics motivation is stated up front but the paper does not include any real molecular instances or comparisons to existing tools in that domain, so the application story remains mostly aspirational. The reductions for hardness are standard and internally consistent with the projection definition, but they do not appear to introduce surprising new techniques. The t-quasi-complete class is narrow enough that its relevance outside this specific setting is limited. This work is for people who already care about parameterized algorithms on multipartite graphs or enumeration with structural constraints. A reader working on FPT for connectivity problems with extra matching rules would find the parameterized and restricted-class results worth looking at. It is not broad enough to interest most graph theorists or complexity people outside that niche. The paper shows clear, honest engagement with the relevant literature and the claims line up with the definition they chose. I would send it to peer review rather than desk-reject it; the results are grounded enough to deserve referee time even if revisions will be needed on the application side and on tightening the enumeration experiments.

Referee Report

2 major / 3 minor

Summary. The paper defines interconnection trees in multipartite graphs as matchings whose projections onto the quotient graph form a spanning tree. It proves that the minimum interconnection tree decision problem is NP-complete in general multipartite graphs. It further shows fixed-parameter tractability parameterized by the number of parts, polynomial-time algorithms on quasi-complete multipartite graphs, and linear-time algorithms on complete and t-quasi-complete multipartite graphs. Enumeration algorithms with optimal delay via flashlight search are given for complete multipartite graphs, along with a weight-guided heuristic.

Significance. If the claims hold, the work establishes a complexity dichotomy for interconnection trees by transferring standard spanning-tree and matching results through the projection definition. This is useful for chemoinformatics applications and contributes concrete FPT and linear-time algorithms on structured graph classes. The optimal-delay enumeration result and practical heuristic add value for enumeration variants.

major comments (2)

[Reduction section] The NP-completeness proof (likely in the section presenting the reduction) must explicitly verify that the constructed instance preserves the multipartite structure and that the projection step does not introduce additional edges that would alter the spanning-tree condition on the quotient graph.
[FPT algorithm section] For the FPT algorithm parameterized by the number of parts, the dynamic-programming recurrence should be checked to confirm that the state depends only on the part count and not on hidden factors such as maximum part size.

minor comments (3)

[Introduction] Define 't-quasi-complete multipartite graph' at first use in the introduction rather than deferring to a later section.
[Algorithm for complete graphs] Clarify the input representation for complete multipartite graphs to ensure the claimed linear-time bound accounts for reading the part sizes.
[Enumeration] The enumeration section should include a brief comparison of the flashlight-search delay to known optimal delays for spanning-tree enumeration.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their thorough review and constructive comments, as well as the recommendation for minor revision. We address each major comment point by point below.

read point-by-point responses

Referee: [Reduction section] The NP-completeness proof (likely in the section presenting the reduction) must explicitly verify that the constructed instance preserves the multipartite structure and that the projection step does not introduce additional edges that would alter the spanning-tree condition on the quotient graph.

Authors: We agree that an explicit verification strengthens the presentation. In the revised manuscript we will add a dedicated paragraph immediately following the reduction construction. This paragraph will confirm that the instance is built on the same vertex partition into parts as the source problem, that no intra-part edges are added, and that the quotient graph is formed precisely by the standard contraction (one supervertex per part, with an edge between supervertices iff at least one cross-edge exists in the multipartite graph). Consequently the projection of any matching onto the quotient cannot create or remove edges beyond those already present in the original multipartite structure, preserving the spanning-tree condition exactly. revision: yes
Referee: [FPT algorithm section] For the FPT algorithm parameterized by the number of parts, the dynamic-programming recurrence should be checked to confirm that the state depends only on the part count and not on hidden factors such as maximum part size.

Authors: We have re-verified the recurrence. The DP table is indexed exclusively by subsets S of the k parts (2^k states) together with a constant-size interface recording the unmatched vertices on the boundary of the current tree; transitions correspond to adding a single cross-edge between two parts in S and its complement. Because the state never enumerates or depends on the cardinalities of the individual parts, the running time remains FPT in k alone (specifically O(2^k · n^2) after standard matching bookkeeping). We will insert a short clarifying sentence in the FPT section stating this independence from part sizes. revision: yes

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The paper defines interconnection trees via a new but explicit construction (matchings whose projections onto the quotient graph form a spanning tree) and then transfers standard NP-completeness, FPT, and enumeration results from classical spanning-tree and matching problems using ordinary reductions and dynamic programming. No equation or claim reduces to a fitted parameter, self-citation, or ansatz that is itself defined by the target result; the derivation chain remains independent of the conclusions it reaches.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The results rest on the new definition of interconnection trees and standard assumptions from complexity theory such as the validity of reductions for NP-completeness. No free parameters or invented physical entities are introduced.

axioms (1)

standard math Standard model of computation and graph theory definitions apply to multipartite graphs and matchings.
Invoked implicitly when defining the quotient graph and spanning tree projections.

pith-pipeline@v0.9.0 · 5667 in / 1254 out tokens · 43651 ms · 2026-05-20T00:06:44.944964+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Foundation/RealityFromDistinction.lean reality_from_one_distinction unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

We introduce interconnection trees, defined as matchings whose projections onto the quotient graph form a spanning tree.
IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

We show that the decision problem is NP-complete... flashlight-search based algorithms with optimal delay

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

13 extracted references · 13 canonical work pages · 1 internal anchor

[1]

Ziegler.Cayley’s formula for the number of trees, pages 235–240

1 Martin Aigner and Günter M. Ziegler.Cayley’s formula for the number of trees, pages 235–240. Springer Berlin Heidelberg, Berlin, Heidelberg, 2018.doi:10.1007/978-3-662-57265-8_33. 2 David Avis and Komei Fukuda. Reverse search for enumeration.Discrete applied mathematics, 65(1-3):21–46,

work page doi:10.1007/978-3-662-57265-8_33 2018
[2]

Adrian Bondy and Uppaluri S

3 J. Adrian Bondy and Uppaluri S. R. Murty.Graph Theory with Applications. Macmillan Education UK, 1976.doi:10.1007/978-1-349-03521-2. 4 Endre Boros, Khaled Elbassioni, Vladimir Gurvich, and Kazuhisa Makino. Generating vertices of polyhedra and related problems of monotone generation.Proceedings of the Centre de Recherches Mathématiques at the Université ...

work page doi:10.1007/978-1-349-03521-2 1976
[3]

From amortized to worst case delay in enumeration algorithms.arXiv preprint arXiv:2108.10208,

7 Florent Capelli and Yann Strozecki. From amortized to worst case delay in enumeration algorithms.arXiv preprint arXiv:2108.10208,

work page arXiv
[4]

Computational Generation of Substrate-Specific Molecular Cages

8 The Cambridge Crystallographic Data Centre. Cambridge structural database. http://www.ccdc.cam.ac.uk/. 9 Noé Demange, Yann Strozecki, and Sandrine Vial. Computational generation of substrate- specific molecular cages.arXiv preprint arXiv:2604.11060,

work page internal anchor Pith review Pith/arXiv arXiv
[5]

A survey of adaptive sorting algorithms.ACM Comput

12 Vladimir Estivill-Castro and Derick Wood. A survey of adaptive sorting algorithms.ACM Comput. Surv., 24(4):441–476, 1992.doi:10.1145/146370.146381. 13 Philippe Flajolet and Robert Sedgewick.Analytic combinatorics. cambridge University press,

work page doi:10.1145/146370.146381 1992
[6]

Hopcroft and Richard M

16 John E. Hopcroft and Richard M. Karp. A nˆ5/2 algorithm for maximum matchings in bipartite graphs. In12th Annual Symposium on Switching and Automata Theory, East Lansing, Michigan, USA, October 13-15, 1971, pages 122–125. IEEE Computer Society,

work page 1971
[7]

17 David S Johnson, Mihalis Yannakakis, and Christos H Papadimitriou

doi:10.1109/SWAT.1971.1. 17 David S Johnson, Mihalis Yannakakis, and Christos H Papadimitriou. On generating all maximal independent sets.Information Processing Letters, 27(3):119–123,

work page doi:10.1109/swat.1971.1 1971
[8]

20 Richard M. Karp. Reducibility among combinatorial problems. In Raymond E. Miller and James W. Thatcher, editors,Proceedings of a symposium on the Complexity of Computer Computations, held March 20-22, 1972, at the IBM Thomas J. Watson Research Center, Yorktown Heights, New York, USA, The IBM Research Symposia Series, pages 85–103. Plenum Press, New Yor...

work page doi:10.1007/978-1-4684-2001-2 1972
[9]

Generating pivot gray codes for spanning trees of complete graphs in constant amortized time

23 Bowie Liu, Dennis Wong, Chan-Tong Lam, and Sio-Kei Im. Generating pivot gray codes for spanning trees of complete graphs in constant amortized time. InProceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 833–870. SIAM,

work page 2026
[10]

All your bases are belong to us: listing all bases of a matroid by greedy exchanges

25 Arturo Merino, Torsten Mutze, and Aaron Williams. All your bases are belong to us: listing all bases of a matroid by greedy exchanges. In11th International Conference on Fun with Algorithms (FUN 2022), volume 226, page

work page 2022
[11]

Papadimitriou

28 Christos H. Papadimitriou. The euclidean traveling salesman problem is np-complete.Theor. Comput. Sci., 4(3):237–244, 1977.doi:10.1016/0304-3975(77)90012-3. 29 Robert C. Prim. Shortest connection networks and some generalizations.Bell System Technical Journal, 36(6):1389–1401,

work page doi:10.1016/0304-3975(77)90012-3 1977
[12]

Enumeration complexity: Incremental time, delay and space (habilitation thesis).arXiv preprint arXiv:2309.17042,

31 Yann Strozecki. Enumeration complexity: Incremental time, delay and space (habilitation thesis).arXiv preprint arXiv:2309.17042,

work page arXiv
[13]

The complexity of enumeration and reliability problems.siam Journal on Computing, 8(3):410–421, 1979

35 Leslie G Valiant. The complexity of enumeration and reliability problems.siam Journal on Computing, 8(3):410–421, 1979

work page 1979

[1] [1]

Ziegler.Cayley’s formula for the number of trees, pages 235–240

1 Martin Aigner and Günter M. Ziegler.Cayley’s formula for the number of trees, pages 235–240. Springer Berlin Heidelberg, Berlin, Heidelberg, 2018.doi:10.1007/978-3-662-57265-8_33. 2 David Avis and Komei Fukuda. Reverse search for enumeration.Discrete applied mathematics, 65(1-3):21–46,

work page doi:10.1007/978-3-662-57265-8_33 2018

[2] [2]

Adrian Bondy and Uppaluri S

3 J. Adrian Bondy and Uppaluri S. R. Murty.Graph Theory with Applications. Macmillan Education UK, 1976.doi:10.1007/978-1-349-03521-2. 4 Endre Boros, Khaled Elbassioni, Vladimir Gurvich, and Kazuhisa Makino. Generating vertices of polyhedra and related problems of monotone generation.Proceedings of the Centre de Recherches Mathématiques at the Université ...

work page doi:10.1007/978-1-349-03521-2 1976

[3] [3]

From amortized to worst case delay in enumeration algorithms.arXiv preprint arXiv:2108.10208,

7 Florent Capelli and Yann Strozecki. From amortized to worst case delay in enumeration algorithms.arXiv preprint arXiv:2108.10208,

work page arXiv

[4] [4]

Computational Generation of Substrate-Specific Molecular Cages

8 The Cambridge Crystallographic Data Centre. Cambridge structural database. http://www.ccdc.cam.ac.uk/. 9 Noé Demange, Yann Strozecki, and Sandrine Vial. Computational generation of substrate- specific molecular cages.arXiv preprint arXiv:2604.11060,

work page internal anchor Pith review Pith/arXiv arXiv

[5] [5]

A survey of adaptive sorting algorithms.ACM Comput

12 Vladimir Estivill-Castro and Derick Wood. A survey of adaptive sorting algorithms.ACM Comput. Surv., 24(4):441–476, 1992.doi:10.1145/146370.146381. 13 Philippe Flajolet and Robert Sedgewick.Analytic combinatorics. cambridge University press,

work page doi:10.1145/146370.146381 1992

[6] [6]

Hopcroft and Richard M

16 John E. Hopcroft and Richard M. Karp. A nˆ5/2 algorithm for maximum matchings in bipartite graphs. In12th Annual Symposium on Switching and Automata Theory, East Lansing, Michigan, USA, October 13-15, 1971, pages 122–125. IEEE Computer Society,

work page 1971

[7] [7]

17 David S Johnson, Mihalis Yannakakis, and Christos H Papadimitriou

doi:10.1109/SWAT.1971.1. 17 David S Johnson, Mihalis Yannakakis, and Christos H Papadimitriou. On generating all maximal independent sets.Information Processing Letters, 27(3):119–123,

work page doi:10.1109/swat.1971.1 1971

[8] [8]

20 Richard M. Karp. Reducibility among combinatorial problems. In Raymond E. Miller and James W. Thatcher, editors,Proceedings of a symposium on the Complexity of Computer Computations, held March 20-22, 1972, at the IBM Thomas J. Watson Research Center, Yorktown Heights, New York, USA, The IBM Research Symposia Series, pages 85–103. Plenum Press, New Yor...

work page doi:10.1007/978-1-4684-2001-2 1972

[9] [9]

Generating pivot gray codes for spanning trees of complete graphs in constant amortized time

23 Bowie Liu, Dennis Wong, Chan-Tong Lam, and Sio-Kei Im. Generating pivot gray codes for spanning trees of complete graphs in constant amortized time. InProceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 833–870. SIAM,

work page 2026

[10] [10]

All your bases are belong to us: listing all bases of a matroid by greedy exchanges

25 Arturo Merino, Torsten Mutze, and Aaron Williams. All your bases are belong to us: listing all bases of a matroid by greedy exchanges. In11th International Conference on Fun with Algorithms (FUN 2022), volume 226, page

work page 2022

[11] [11]

Papadimitriou

28 Christos H. Papadimitriou. The euclidean traveling salesman problem is np-complete.Theor. Comput. Sci., 4(3):237–244, 1977.doi:10.1016/0304-3975(77)90012-3. 29 Robert C. Prim. Shortest connection networks and some generalizations.Bell System Technical Journal, 36(6):1389–1401,

work page doi:10.1016/0304-3975(77)90012-3 1977

[12] [12]

Enumeration complexity: Incremental time, delay and space (habilitation thesis).arXiv preprint arXiv:2309.17042,

31 Yann Strozecki. Enumeration complexity: Incremental time, delay and space (habilitation thesis).arXiv preprint arXiv:2309.17042,

work page arXiv

[13] [13]

The complexity of enumeration and reliability problems.siam Journal on Computing, 8(3):410–421, 1979

35 Leslie G Valiant. The complexity of enumeration and reliability problems.siam Journal on Computing, 8(3):410–421, 1979

work page 1979