11
$\begingroup$

The paper in question: M.R. Garey, R.L. Graham and D.S. Johnson. Some NP-complete geometric problems .

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.

Improve this question
$\endgroup$
4
  • $\begingroup$ 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$? $\endgroup$
    – zdm
    Sep 4, 2018 at 0:55
  • $\begingroup$ @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$. $\endgroup$
    – J. Schmidt
    Sep 4, 2018 at 8:58
  • $\begingroup$ Anyway, I see that the authors use the inequality $q<3nt$ in the proof of Claim 2.3. $\endgroup$
    – zdm
    Sep 4, 2018 at 21:08
  • $\begingroup$ @zdm They do. It would make the proof for Claim 2.3 incorrect if it's actually $q<3(3nt)$. $\endgroup$
    – J. Schmidt
    Sep 5, 2018 at 13:46

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.