Fast exact algorithms via the Matrix Tree Theorem
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866908701825171456 |
|---|---|
| author | Arvind, V. Chakraborty, Srijan Datta, Samir Khan, Asif |
| author_facet | Arvind, V. Chakraborty, Srijan Datta, Samir Khan, Asif |
| contents | Fast exact algorithms are known for Hamiltonian paths in undirected and directed bipartite graphs through elegant though involved algorithms that are quite different from each other. We devise algorithms that are simple and similar to each other while having the same upper bounds. The common features of these algorithms is the use of the Matrix-Tree theorem and sieving using roots of unity.
Next, we use the framework to provide alternative algorithms to count perfect matchings in bipartite graphs on $n$ vertices, i.e., computing the $\{0,1\}$-permanent of a square $n/2 \times n/2$ matrix which runs in a time similar to Ryser.
We demonstrate the flexibility of our method by counting the number of ways to vertex partition the graph into $k$-stars (a $k$-star consist of a tree with a root having $k-1$ children that are all leaves). Interestingly, our running time improves to $O^*((1+ε_k)^n)$ with $ε_k \rightarrow 0$ as $k \rightarrow \infty$.
As an aside, making use of Björklund's algorithm for exact counting perfect matchings in general graphs, we show that the count of maximum matchings can be computed in time $O^*(2^ν)$ where $ν$ is the size of a maximum matching. The crucial ingredient here is the famous Gallai-Edmonds decomposition theorem.
All our algorithms run in polynomial space. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_08600 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Fast exact algorithms via the Matrix Tree Theorem Arvind, V. Chakraborty, Srijan Datta, Samir Khan, Asif Data Structures and Algorithms Fast exact algorithms are known for Hamiltonian paths in undirected and directed bipartite graphs through elegant though involved algorithms that are quite different from each other. We devise algorithms that are simple and similar to each other while having the same upper bounds. The common features of these algorithms is the use of the Matrix-Tree theorem and sieving using roots of unity. Next, we use the framework to provide alternative algorithms to count perfect matchings in bipartite graphs on $n$ vertices, i.e., computing the $\{0,1\}$-permanent of a square $n/2 \times n/2$ matrix which runs in a time similar to Ryser. We demonstrate the flexibility of our method by counting the number of ways to vertex partition the graph into $k$-stars (a $k$-star consist of a tree with a root having $k-1$ children that are all leaves). Interestingly, our running time improves to $O^*((1+ε_k)^n)$ with $ε_k \rightarrow 0$ as $k \rightarrow \infty$. As an aside, making use of Björklund's algorithm for exact counting perfect matchings in general graphs, we show that the count of maximum matchings can be computed in time $O^*(2^ν)$ where $ν$ is the size of a maximum matching. The crucial ingredient here is the famous Gallai-Edmonds decomposition theorem. All our algorithms run in polynomial space. |
| title | Fast exact algorithms via the Matrix Tree Theorem |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2512.08600 |