Editing Open Problems:42
Warning: You are not logged in. Your IP address will be publicly visible if you make any edits. If you log in or create an account, your edits will be attributed to your username, along with other benefits.
The edit can be undone.
Please check the comparison below to verify that this is what you want to do, and then save the changes below to finish undoing the edit.
Latest revision | Your text | ||
Line 27: | Line 27: | ||
currently known. | currently known. | ||
β | |||
β | Partial progress has been made | + | '''Update:''' Partial progress has been made in [http://drops.dagstuhl.de/opus/volltexte/2015/5336/ FPS15] where it is proved that if all $k$-discs in $G$ are trees (i.e., $G$ has girth greater than $2k+1$), then $|V(H)| \leq \frac{10^{10^{50}}}{\epsilon}$. The result generalizes to arbitrary degree bound $d$ and $k \geq 0$, and $H$ can be constructed in constant time at the cost of roughly an additional factor $\epsilon^{-1}$. It was sketched by the same authors at the [http://math.ucsd.edu/~sbuss/SPB_Workshops/AlgCPTC_1.html Workshop on Algorithms in Communication Complexity, Property Testing and Combinatorics in Moscow in 2016] that one can also construct $H$ if $G$ is planar by using the planar separator theorem. In this case, $|V(H)| \in O(\epsilon^{-4})$. |