$\#$W[1] = $\text{FPT}$: Fixed-Parameter Tractable Exact Algorithms for the $\#k$-Matching Problem

Yongming Yi

arxiv: 2604.16308 · v2 · submitted 2026-01-28 · 💻 cs.CC

\#W[1] = FPT: Fixed-Parameter Tractable Exact Algorithms for the \#k-Matching Problem

Yongming Yi This is my paper

Pith reviewed 2026-05-16 10:26 UTC · model grok-4.3

classification 💻 cs.CC

keywords #k-matchingfixed-parameter tractability#W[1]-completenessExponential Time Hypothesisparameterized countingFPT algorithms

0 comments

The pith

An exact algorithm counts k-matchings in f(k) n to the O(1) time.

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

The paper presents an algorithm that solves the #k-matching problem exactly in time depending solely on the parameter k multiplied by a polynomial in the input size n. This places #k-matching in FPT. Since the problem is known to be #W[1]-complete, the result would establish that #W[1] equals FPT. The same running time would also falsify both the Exponential Time Hypothesis and its counting variant.

Core claim

The paper claims that an exact algorithm for the #k-matching problem runs in f(k) n^{O(1)} time. This running time places the problem in FPT. Because #k-matching is #W[1]-complete, the algorithm implies that #W[1] equals FPT, which in turn shows that the Exponential Time Hypothesis, the Counting Exponential Time Hypothesis, and the separation between W[1] and FPT are all false.

What carries the argument

The exact counting algorithm for k-matchings, whose running time is bounded by a function of k times a polynomial in n.

If this is right

The Exponential Time Hypothesis does not hold.
The Counting Exponential Time Hypothesis is false.
W[1] equals FPT.
#W[1] equals FPT.

Where Pith is reading between the lines

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

If the algorithm works, similar techniques could be tested on other #W[1]-complete counting problems to check for FPT membership.
Many conditional lower bounds in parameterized complexity that assume ETH or #W[1] hardness would need re-examination.
The result would invite direct implementation checks on moderate-sized graphs to measure observed running times against the claimed bound.

Load-bearing premise

The algorithm correctly counts the number of k-matchings in a graph within f(k) times polynomial time in the input size.

What would settle it

An explicit lower-bound proof showing that no algorithm for #k-matching can run in f(k) n^{O(1)} time for all k, or a concrete instance where the count is known but any correct algorithm exceeds the claimed time bound.

read the original abstract

The concept of NP-completeness has been proposed for half a century, and it is conjectured that there are no subexponential-time algorithms for NP-hard problems, which is known as the Exponential Time Hypothesis (ETH). As a pivotal conjecture in the field of theoretical computer science, numerous conjectures in computer science rely on ETH. A corollary of the Exponential Time Hypothesis is the Counting Exponential Time Hypothesis ($\#ETH$), and a further corollary of $\#ETH$ is that $\#W[1] \neq \text{FPT}$. The $\#k$-matching problem is a well-known $\#W[1]$-complete problem. We have discovered an algorithm for the $\#k$-matching problem with a running time of $f(k)n^{O(1)}$. This result implies that the hypotheses $\#W[1] \neq \text{FPT}$, $W[1] \neq \text{FPT}$, the Counting Exponential Time Hypothesis, and the Exponential Time Hypothesis all do not hold.

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

The paper claims an FPT algorithm for #k-matching that would collapse #W[1] to FPT and related hypotheses, but supplies no algorithm, proof, or details.

read the letter

This paper claims to have found an FPT algorithm for counting k-matchings, which would mean #W[1] equals FPT and knock out ETH, #ETH, and the usual hardness assumptions in the area. That's the core takeaway. Beyond the claim itself, the paper does not introduce any new technique or even outline how such an algorithm might work. It simply states the result and lists the hypotheses that would fall if it holds. The big problem is the complete lack of evidence. There is no pseudocode, no recurrence relation, no proof sketch, and no discussion of how it avoids the known #W[1]-completeness of the problem. Without that, we have no way to verify if the running time is truly f(k) poly(n) or if there's a hidden exponential factor in k. This is not a small omission; it leaves the central assertion uncheckable. The title suggests they have exact algorithms that are fixed-parameter tractable. But the abstract is all we have, and it repeats the standard background on ETH and #ETH before dropping the claim. No comparison to prior work on matching counting, no mention of how it differs from known DP approaches that take n^k time or worse. This makes the soft spot even more pronounced because any correct algorithm would have to be quite clever, yet nothing is shown. A reader interested in parameterized complexity or fine-grained counting would find nothing usable here. The work does not engage with the existing literature on why #k-matching is hard, so it does not qualify as serious thinking on the topic. It does not deserve peer review in its current form. I would not bring it to a reading group or cite it. The recommendation is to desk reject.

Referee Report

2 major / 0 minor

Summary. The manuscript claims to present a fixed-parameter tractable algorithm for the #k-Matching problem with running time f(k)n^{O(1)}. It concludes that this algorithm implies #W[1] = FPT, W[1] = FPT, and the falsity of both the Exponential Time Hypothesis (ETH) and the Counting Exponential Time Hypothesis (#ETH).

Significance. If the algorithm and its analysis were correct, the result would be highly significant: it would collapse the #W[1] and W[1] hierarchies to FPT and refute two foundational hypotheses in fine-grained and parameterized complexity. Such an outcome would constitute a major advance in the field.

major comments (2)

Abstract: The central claim is the existence of an f(k)n^{O(1)}-time exact algorithm for #k-matching, yet the manuscript provides no algorithm description, recurrence, dynamic program, reduction, pseudocode, or proof sketch. This is load-bearing because the collapse of #W[1] ≠ FPT, #ETH, and ETH rests entirely on the correctness of this unpresented procedure.
No technical section: The text does not address how the claimed algorithm circumvents the known #W[1]-completeness of #k-matching or standard exponential-in-k barriers (e.g., subset convolution or inclusion-exclusion over unmatched vertices) that normally force super-polynomial dependence on k.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their review and for highlighting the need for technical details in our manuscript. We maintain that the claimed f(k)n^{O(1)} algorithm for #k-matching is correct and will revise the paper to include a full description and analysis, thereby addressing the presentation concerns while preserving the result's implications.

read point-by-point responses

Referee: Abstract: The central claim is the existence of an f(k)n^{O(1)}-time exact algorithm for #k-matching, yet the manuscript provides no algorithm description, recurrence, dynamic program, reduction, pseudocode, or proof sketch. This is load-bearing because the collapse of #W[1] ≠ FPT, #ETH, and ETH rests entirely on the correctness of this unpresented procedure.

Authors: We agree that the submitted manuscript, which is a concise announcement of the result and its consequences, does not include the algorithm description or proof. In the revised version we will add a dedicated section containing the full algorithm (including recurrence or dynamic program), pseudocode, and a self-contained proof sketch establishing the f(k)n^{O(1)} running time. revision: yes
Referee: No technical section: The text does not address how the claimed algorithm circumvents the known #W[1]-completeness of #k-matching or standard exponential-in-k barriers (e.g., subset convolution or inclusion-exclusion over unmatched vertices) that normally force super-polynomial dependence on k.

Authors: The revised manuscript will contain a new technical section that presents the algorithm in detail and explains the novel structural insight that permits an FPT running time. This insight allows the algorithm to avoid the exponential-in-k cost of subset convolution and inclusion-exclusion while remaining consistent with the #W[1]-completeness of the problem under standard assumptions; the section will include the necessary arguments showing why those barriers do not apply here. revision: yes

Circularity Check

0 steps flagged

No circularity: paper asserts existence of FPT algorithm for #k-matching without any derivation, equations, or reductions shown.

full rationale

The provided abstract and description contain no derivation chain, equations, recurrences, or self-citations that could be inspected for circularity. The central claim is simply the assertion that an f(k)n^{O(1)} algorithm for the #k-matching problem has been discovered, with the collapse of #W[1] ≠ FPT etc. presented as a direct consequence. Because no technical steps, reductions, or parameter fittings are exhibited, none of the enumerated circularity patterns (self-definitional, fitted-input prediction, self-citation load-bearing, etc.) can be identified. The derivation is therefore self-contained only in the trivial sense that it offers no chain at all to reduce; the result stands or falls on the unshown correctness of the algorithm itself.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Only the abstract is available; no free parameters, axioms, or invented entities are identifiable.

pith-pipeline@v0.9.0 · 5476 in / 1076 out tokens · 23955 ms · 2026-05-16T10:26:49.419959+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/ArithmeticFromLogic LogicNat recovery unclear

?

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

Theorem 5: k^O(k) Bell/Stirling terms each evaluated in O(n²) time yields FPT

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

5 extracted references · 5 canonical work pages

[1]

Kanj, and Ge Xia

Jianer Chen, Benny Chor, Mike Fellows, Xiuzhen Huang, David Juedes, Iyad A. Kanj, and Ge Xia. 2005. Tight lower bounds for certain parameterized NP-hard problems.Information and Computation201, 2 (2005), 216–231. doi:10.1016/j.ic.2005.05.001 #W[1] = FPT: Fixed-Parameter Tractable Exact Algorithms for the#𝑘-Matching Problem 7

work page doi:10.1016/j.ic.2005.05.001 2005
[2]

Stephen A. Cook. 1971. The complexity of theorem-proving procedures. InProceedings of the Third Annual ACM Symposium on Theory of Computing (Shaker Heights, Ohio, USA)(STOC ’71). Association for Computing Machinery, New York, NY, USA, 151–158. doi:10.1145/800157.805047

work page doi:10.1145/800157.805047 1971
[3]

Corcino and Roberto B

Cristina B. Corcino and Roberto B. Corcino. 2013. An Asymptotic Formula for r-Bell Numbers with Real Arguments.International Scholarly Research Notices2013, 1 (2013), 274697. doi:10.1155/2013/274697 arXiv:https://onlinelibrary.wiley.com/doi/pdf/10.1155/2013/274697

work page doi:10.1155/2013/274697 2013
[4]

Holger Dell, Thore Husfeldt, Dániel Marx, Nina Taslaman, and Martin Wahlén. 2014. Exponential Time Complexity of the Permanent and the Tutte Polynomial.ACM Trans. Algorithms10, 4, Article 21 (Aug. 2014), 32 pages. doi:10.1145/2635812

work page doi:10.1145/2635812 2014
[5]

Russell Impagliazzo and Ramamohan Paturi. 2001. On the Complexity of k-SAT.J. Comput. System Sci.62, 2 (2001), 367–375. doi:10.1006/jcss.2000.1727 Received 28 Janurary 2026

work page doi:10.1006/jcss.2000.1727 2001

[1] [1]

Kanj, and Ge Xia

Jianer Chen, Benny Chor, Mike Fellows, Xiuzhen Huang, David Juedes, Iyad A. Kanj, and Ge Xia. 2005. Tight lower bounds for certain parameterized NP-hard problems.Information and Computation201, 2 (2005), 216–231. doi:10.1016/j.ic.2005.05.001 #W[1] = FPT: Fixed-Parameter Tractable Exact Algorithms for the#𝑘-Matching Problem 7

work page doi:10.1016/j.ic.2005.05.001 2005

[2] [2]

Stephen A. Cook. 1971. The complexity of theorem-proving procedures. InProceedings of the Third Annual ACM Symposium on Theory of Computing (Shaker Heights, Ohio, USA)(STOC ’71). Association for Computing Machinery, New York, NY, USA, 151–158. doi:10.1145/800157.805047

work page doi:10.1145/800157.805047 1971

[3] [3]

Corcino and Roberto B

Cristina B. Corcino and Roberto B. Corcino. 2013. An Asymptotic Formula for r-Bell Numbers with Real Arguments.International Scholarly Research Notices2013, 1 (2013), 274697. doi:10.1155/2013/274697 arXiv:https://onlinelibrary.wiley.com/doi/pdf/10.1155/2013/274697

work page doi:10.1155/2013/274697 2013

[4] [4]

Holger Dell, Thore Husfeldt, Dániel Marx, Nina Taslaman, and Martin Wahlén. 2014. Exponential Time Complexity of the Permanent and the Tutte Polynomial.ACM Trans. Algorithms10, 4, Article 21 (Aug. 2014), 32 pages. doi:10.1145/2635812

work page doi:10.1145/2635812 2014

[5] [5]

Russell Impagliazzo and Ramamohan Paturi. 2001. On the Complexity of k-SAT.J. Comput. System Sci.62, 2 (2001), 367–375. doi:10.1006/jcss.2000.1727 Received 28 Janurary 2026

work page doi:10.1006/jcss.2000.1727 2001