ترغب بنشر مسار تعليمي؟ اضغط هنا

A Tight Lower Bound for Counting Hamiltonian Cycles via Matrix Rank

236   0   0.0 ( 0 )
 نشر من قبل Radu Curticapean
 تاريخ النشر 2017
  مجال البحث الهندسة المعلوماتية
والبحث باللغة English




اسأل ChatGPT حول البحث

For even $k$, the matchings connectivity matrix $mathbf{M}_k$ encodes which pairs of perfect matchings on $k$ vertices form a single cycle. Cygan et al. (STOC 2013) showed that the rank of $mathbf{M}_k$ over $mathbb{Z}_2$ is $Theta(sqrt 2^k)$ and used this to give an $O^*((2+sqrt{2})^{mathsf{pw}})$ time algorithm for counting Hamiltonian cycles modulo $2$ on graphs of pathwidth $mathsf{pw}$. The same authors complemented their algorithm by an essentially tight lower bound under the Strong Exponential Time Hypothesis (SETH). This bound crucially relied on a large permutation submatrix within $mathbf{M}_k$, which enabled a pattern propagation commonly used in previous related lower bounds, as initiated by Lokshtanov et al. (SODA 2011). We present a new technique for a similar pattern propagation when only a black-box lower bound on the asymptotic rank of $mathbf{M}_k$ is given; no stronger structural insights such as the existence of large permutation submatrices in $mathbf{M}_k$ are needed. Given appropriate rank bounds, our technique yields lower bounds for counting Hamiltonian cycles (also modulo fixed primes $p$) parameterized by pathwidth. To apply this technique, we prove that the rank of $mathbf{M}_k$ over the rationals is $4^k / mathrm{poly}(k)$. We also show that the rank of $mathbf{M}_k$ over $mathbb{Z}_p$ is $Omega(1.97^k)$ for any prime $p eq 2$ and even $Omega(2.15^k)$ for some primes. As a consequence, we obtain that Hamiltonian cycles cannot be counted in time $O^*((6-epsilon)^{mathsf{pw}})$ for any $epsilon>0$ unless SETH fails. This bound is tight due to a $O^*(6^{mathsf{pw}})$ time algorithm by Bodlaender et al. (ICALP 2013). Under SETH, we also obtain that Hamiltonian cycles cannot be counted modulo primes $p eq 2$ in time $O^*(3.97^mathsf{pw})$, indicating that the modulus can affect the complexity in intricate ways.



قيم البحث

اقرأ أيضاً

The Index Erasure problem asks a quantum computer to prepare a uniform superposition over the image of an injective function given by an oracle. We prove a tight $Omega(sqrt{n})$ lower bound on the quantum query complexity of the non-coherent case of the problem, where, in addition to preparing the required superposition, the algorithm is allowed to leave the ancillary memory in an arbitrary function-dependent state. This resolves an open question of Ambainis, Magnin, Roetteler, and Roland (CCC 2011), who gave a tight bound for the coherent case, the case where the ancillary memory must return to its initial state. The proof is based on evaluating certain Krein parameters of a symmetric association scheme defined over partial permutations. The study of this association scheme may be of independent interest.
Given two strings $S$ and $P$, the Episode Matching problem is to compute the length of the shortest substring of $S$ that contains $P$ as a subsequence. The best known upper bound for this problem is $tilde O(nm)$ by Das et al. (1997), where $n,m$ a re the lengths of $S$ and $P$, respectively. Although the problem is well studied and has many applications in data mining, this bound has never been improved. In this paper we show why this is the case by proving that an $O((nm)^{1-epsilon})$ algorithm (even for binary strings) would refute the popular Strong Exponential Time Hypothesis (SETH). The proof is based on a simple reduction from Orthogonal Vectors.
93 - Sepehr Assadi 2021
We prove a lower bound on the space complexity of two-pass semi-streaming algorithms that approximate the maximum matching problem. The lower bound is parameterized by the density of Ruzsa-Szemeredi graphs: * Any two-pass semi-streaming algorithm f or maximum matching has approximation ratio at least $(1- Omega(frac{log{RS(n)}}{log{n}}))$, where $RS(n)$ denotes the maximum number of induced matchings of size $Theta(n)$ in any $n$-vertex graph, i.e., the largest density of a Ruzsa-Szemeredi graph. Currently, it is known that $n^{Omega(1/!loglog{n})} leq RS(n) leq frac{n}{2^{O(log^*{!(n)})}}$ and closing this (large) gap between upper and lower bounds has remained a notoriously difficult problem in combinatorics. Under the plausible hypothesis that $RS(n) = n^{Omega(1)}$, our lower bound is the first to rule out small-constant approximation two-pass semi-streaming algorithms for the maximum matching problem, making progress on a longstanding open question in the graph streaming literature.
We prove tight lower bounds for the following variant of the counting problem considered by Aaronson et al. The task is to distinguish whether an input set $xsubseteq [n]$ has size either $k$ or $k=(1+epsilon)k$. We assume the algorithm has access to * the membership oracle, which, for each $iin [n]$, can answer whether $iin x$, or not; and * the uniform superposition $|psi_xrangle = sum_{iin x} |irangle/sqrt{|x|}$ over the elements of $x$. Moreover, we consider three different ways how the algorithm can access this state: ** the algorithm can have copies of the state $|psi_xrangle$; ** the algorithm can execute the reflecting oracle which reflects about the state $|psi_xrangle$; ** the algorithm can execute the state-generating oracle (or its inverse) which performs the transformation $|0ranglemapsto |psi_xrangle$. Without the second type of resources (related to $|psi_xrangle$), the problem is well-understood, see Brassard et al. The study of the problem with the second type of resources was recently initiated by Aaronson et al. We completely resolve the problem for all values of $1/k le epsilonle 1$, giving tight trade-offs between all types of resources available to the algorithm. Thus, we close the main open problems from Aaronson et al. The lower bounds are proven using variants of the adversary bound by Belovs and employing analysis closely related to the Johnson association scheme.
An assignment of colours to the vertices of a graph is stable if any two vertices of the same colour have identically coloured neighbourhoods. The goal of colour refinement is to find a stable colouring that uses a minimum number of colours. This is a widely used subroutine for graph isomorphism testing algorithms, since any automorphism needs to be colour preserving. We give an $O((m+n)log n)$ algorithm for finding a canonical version of such a stable colouring, on graphs with $n$ vertices and $m$ edges. We show that no faster algorithm is possible, under some modest assumptions about the type of algorithm, which captures all known colour refinement algorithms.
التعليقات
جاري جلب التعليقات جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
mircosoft-partner

هل ترغب بارسال اشعارات عن اخر التحديثات في شمرا-اكاديميا