contradiction with expanders and sat?
- From: perfectanimezephyr@xxxxxxxxx
- Date: Fri, 29 Aug 2008 21:56:16 -0700 (PDT)
I think I am reading a contradiction in a paper I am reading; Am I
wrong?
"The description of reduction $\tau$ uses special types of expander
graphs. The relevant property of these graphs is that for every
subset S of the vertices, the number of edges between S and its
complement $\overline{S}$ is at least $\min\{|S|,|\overline{S}|\}$.
[...] algorithm A constructs in poly(k) time a 14-regular graph $G_k$
on k vertices that is an expander. [...] One of these sets has size at
most $m_i/2$; say it is S. In the expander $G_{m_i}$, consider the
set of $|S|$ vertices corresponding to [elements] in S. Expansion
implies there are at least $|S|+1$ edges leaving this set."
Since $|S|\le m_i/2$ we know that in the graph $G_{m_i}$ the
cardinality of the complement of the $|S|$ vertices is at least $m_i/
2$. Therefore $|S|\le |\overline{S}|$. Therefore the number of edges
leaving the set of |S| vertices is at least $\min\{|S|,|\overline{S}|
\}=|S|$ in an expander graph. So why do the authors state that the
number of edges leaving the set of $|S|$ vertices is at least $|S|+1$?
Since $|S|\ne |S|+1$, I think this argument is contradictory.
in the same way that
$a=4 \wedge a>=5$ is unsatisfiable (contradictory).
Should I contact one of the authors, if I am right?
.
- Prev by Date: CFP/Bursary Awards- eCheminfo Community of Practice InterAction Meeting/India 08
- Next by Date: Verifying complexity empirically
- Previous by thread: CFP/Bursary Awards- eCheminfo Community of Practice InterAction Meeting/India 08
- Next by thread: Verifying complexity empirically
- Index(es):