New answers tagged randomized-algorithms
3
Although I agree with Yuval, I'll try to get you started on the connection to their longest path approach. The goal is, given a graph $G$, to define a polynomial $P_G$ which is nonzero iff $G$ has $k$ disjoint triangles. If you could evaluate $P_G$ on an arbitrary point in the underlying field $\mathbb{F}$ in time $2^{3k}n^{O(1)}$ then Schwartz-Zippel gives ...
2
Koutis gives an $O^*(2^{3k})$ algorithm for the more general problem of $3$-set $k$-packing in his paper Faster algebraic algorithms for path and packing problems. This was improved by Björklund, Husfeldt, Kaski, and Koivisto in their work Narrow sieves for parameterized paths and packings to $O^*(1.493^{3k})$. I don't know what is the state of the art on ...
2
Color the vertices in $V \setminus X$ with $2k$ colors at random. With probability $e^{-2k}$, the $V \setminus X$ vertices of your $k$ disjoint triangles will be highlighted.
Suppose without loss of generality that $X = [m]$.
Using dynamic programming, determine for each subset $S \subseteq [2k]$ and $i \in [m]$ whether there exist $|S|/2$ disjoint triangles ...
4
The point is that instead of checking what happens for all possible random strings, you can reduce the search to the output of the generator.
Let $M(x,r)$ be some RP machine for a language $L$, i.e. if $x\in L$ at least two thirds of the $r$'s lead to acceptance, and if $x\notin L$ there is no $r$ for which $M(x,r)$ accepts. Now, Given input $x$, construct a ...
Top 50 recent answers are included
