#StackBounty: #cc.complexity-theory #graph-theory #sat #counting-complexity #planar-graphs Disproving $oplus$ETH by reducing $oplus k…

Bounty: 100

In this question and its answer, they discuss about reducing CNF-SAT with $n$ variables and $m$ clauses to a (problem on) planar graph $G=(V,E)$ with $|V|$ as small as possible. It is said that the best known reduction has $|V| = m^2$, and that if a better reduction with $|V| in o(m^2)$ is found, that would refute ETH.

There is a reduction from $oplus k$-SAT with $n$ variables and $m$ clauses to $oplus$VERTEX COVER where the output graph $G=(V,E)$ is planar and has $|V| = 51(k+1)nm$. Such reduction clearly meets the $|V| in o(m^2)$ requirement when $k$ is a constant and $m$ is superlinear in $n$.

Can the same line of reasoning made within the linked question be applied here in order to refute $oplus$ETH, or am I missing some important detail?

Get this bounty!!!

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.