|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'504'928
Articles rated: 2609
26 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
Parameterizing the Permanent: Genus, Apices, Minors, Evaluation mod 2^k | | Radu Curticapean
; Mingji Xia
; | | Date: |
7 Nov 2015 | | Abstract: | We identify and study relevant structural parameters for the problem
PerfMatch of counting perfect matchings in a given input graph $G$. These
generalize the well-known tractable planar case, and they include the genus of
$G$, its apex number (the minimum number of vertices whose removal renders $G$
planar), and its Hadwiger number (the size of a largest clique minor).
To study these parameters, we first introduce the notion of combined
matchgates, a general technique that bridges parameterized counting problems
and the theory of so-called Holants and matchgates: Using combined matchgates,
we can simulate certain non-existing gadgets $F$ as linear combinations of
$t=O(1)$ existing gadgets. If a graph $G$ features $k$ occurrences of $F$, we
can then reduce $G$ to $t^k$ graphs that feature only existing gadgets, thus
enabling parameterized reductions.
As applications of this technique, we simplify known $4^g n^{O(1)}$ time
algorithms for PerfMatch on graphs of genus $g$. Orthogonally to this, we show
#W[1]-hardness of the permanent on $k$-apex graphs, implying its #W[1]-hardness
under the Hadwiger number. Additionally, we rule out $n^{o(k/log k)}$ time
algorithms under the counting exponential-time hypothesis #ETH.
Finally, we use combined matchgates to prove parity-W[1]-hardness of
evaluating the permanent modulo $2^k$, complementing an $O(n^{4k-3})$ time
algorithm by Valiant and answering an open question of Bj"orklund. We also
obtain a lower bound of $n^{Omega(k/log k)}$ under the parity version of the
exponential-time hypothesis. | | Source: | arXiv, 1511.2321 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER