<p>The paper in question: 
<em>M.R. Garey, R.L. Graham and D.S. Johnson</em>. <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.308.8190&amp;rep=rep1&amp;type=pdf" rel="nofollow noreferrer">Some NP-complete geometric problems </a>. </p>

<p>This paper proofs the NP-completeness of some well-known problems, such as the <em>Steiner Tree Problem</em>, by reducing Exact Set Cover by 3-sets to these problems. </p>

<p>On page 3 (labeled page 12), right above Equation (2.2), it is stated that the number of crossovers is <span class="math-container">$q &lt; 3nt$</span>. In the example figure (Fig. 6) on page 4 however, this is clearly not true, as the number of crossovers <span class="math-container">$q=26$</span>, whereas <span class="math-container">$3nt=18$</span> (as the number of subsets <span class="math-container">$t=3$</span>, and the size of the set to cover <span class="math-container">$3n=6$</span>).<br>
I would understand if <span class="math-container">$q&lt;3(3nt)$</span>, is this an error?</p>

<p>PS: even if it's an error, it would likely not change the NP-completeness proof(s). I only ask to better understand the reasoning behind them.</p>

CC BY-SA 4.0
2018-09-04T00:55:44.597Z
Why do you think that "the size of the set to cover $3n=6$"? Is it *by definition* of X3C that the union of the $3$-element sets of the collection equal to the set $U$?
zdm
CC BY-SA 4.0
2018-09-04T08:58:06.117Z
@zdm on the second page of the paper, when defining X3C, it is stated that $U = \{1,2,3,...,3n\}$. On the third page, directly below the section 2 title, it is stated $\cup_{i=1}^t F_i = \{1,2,...,3n\}$.   
To answer your question, yes, by these arguments the union of the 3-element sets of the collection equals the set $U$.
J. Schmidt
CC BY-SA 4.0
2018-09-04T21:08:03.993Z
Anyway, I see that the authors use the inequality $q<3nt$ in the proof of Claim 2.3.
zdm
CC BY-SA 4.0
2018-09-05T13:46:49.897Z
@zdm They do. It would make the proof for Claim 2.3 incorrect if it's actually $q<3(3nt)$.
J. Schmidt
<np-complete><set-cover><complexity><tsp>
Error in paper "Some NP-complete geometric problems"?
J. Schmidt
# Error in paper "Some NP-complete geometric problems"?

(Asked by: username_0 on 2018-08-23)

The paper in question:
*M.R. Garey, R.L. Graham and D.S. Johnson*. [Some NP-complete geometric problems](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.308.8190&rep=rep1&type=pdf) .

This paper proofs the NP-completeness of some well-known problems, such as the *Steiner Tree Problem*, by reducing Exact Set Cover by 3-sets to these problems.

On page 3 (labeled page 12), right above Equation (2.2), it is stated that the number of crossovers is $q < 3nt$. In the example figure (Fig. 6) on page 4 however, this is clearly not true, as the number of crossovers $q=26$, whereas $3nt=18$ (as the number of subsets $t=3$, and the size of the set to cover $3n=6$).  
I would understand if $q<3(3nt)$, is this an error?

PS: even if it's an error, it would likely not change the NP-completeness proof(s). I only ask to better understand the reasoning behind them.

**Tags:** np-complete, set-cover, complexity, tsp
> **Comments:**
> **username_1**: Why do you think that "the size of the set to cover $3n=6$"? Is it *by definition* of X3C that the union of the $3$-element sets of the collection equal to the set $U$?  
> **username_0**: @zdm on the second page of the paper, when defining X3C, it is stated that $U = \{1,2,3,...,3n\}$. On the third page, directly below the section 2 title, it is stated $\cup_{i=1}^t F_i = \{1,2,...,3n\}$.    To answer your question, yes, by these arguments the union of the 3-element sets of the collection equals the set $U$.  
> **username_1**: Anyway, I see that the authors use the inequality $q<3nt$ in the proof of Claim 2.3.  
> **username_0**: @zdm They do. It would make the proof for Claim 2.3 incorrect if it's actually $q<3(3nt)$.  

---

## 0 answers

