1
$\begingroup$

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$.

Question
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?

Improve this question
$\endgroup$
7
  • 2
    $\begingroup$ What is $\oplus$ETH? $\endgroup$
    – Emil Jeřábek
    Aug 8, 2020 at 10:59
  • $\begingroup$ @EmilJeřábek: In the paper arxiv.org/pdf/1112.2275.pdf, $\oplus$SETH is mentioned. From page 3: "Formally, $\oplus$SETH asserts that, for all $\epsilon$ < 1, there exists a (large) integer $k$ such that $\oplus k$-SAT cannot be computed in time $O(2^{\epsilon n})$". Unless I'm wrong, such definition is to $\oplus k$-SAT as the SETH is to $k$-SAT. Then, I've imagined that if $\oplus$SETH was introduced, then so was $\oplus$ETH... Is it the case that, while $\oplus$SETH exists as a conjecture, there is no such thing as $\oplus$ETH? $\endgroup$
    – Giorgio Camerani
    Aug 8, 2020 at 12:12
  • 1
    $\begingroup$ I didn’t say that it didn’t exist. I simply asked what it was. “Exists” can mean anything between “someone mentioned it in passing in one obscure paper”, and “it is widely known in the field”. $\endgroup$
    – Emil Jeřábek
    Aug 8, 2020 at 13:19
  • $\begingroup$ Why do you assume that $n = o(m)$? To my understanding, for the purposes of ETH (not sure about $\oplus ETH$) we should assume that $m = \Theta(n)$. $\endgroup$
    – Laakeri
    Aug 12, 2020 at 14:30
  • $\begingroup$ @Laakeri: Maybe you're right, but then why in the linked question and its answer there is no such limitation? They pose no constraints on $m$. I imagine they implicitly refer to the Sparsification Lemma, but even in such case there is something unclear to me: suppose they take a CNF with unbounded $m$ and reduce it to a subexponential number of CNFs having $m' = \Theta(n)$, then they turn each of such CNFs into a planar graph to take profit of its sublinear treewidth. Even if this is their reasoning, why they write $|V| \in o(m^2)$, being $m$ the number of clauses of the original formula? ... $\endgroup$
    – Giorgio Camerani
    Aug 13, 2020 at 11:06

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy