Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2604.16308 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910204332867584 |
|---|---|
| author | Yi, Yongming |
| author_facet | Yi, Yongming |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_16308 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | $\#$W[1] = $\text{FPT}$: Fixed-Parameter Tractable Exact Algorithms for the $\#k$-Matching Problem Yi, Yongming Computational Complexity 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. |
| title | $\#$W[1] = $\text{FPT}$: Fixed-Parameter Tractable Exact Algorithms for the $\#k$-Matching Problem |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/2604.16308 |