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.

$\endgroup$
  • $\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 '18 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 '18 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 '18 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 '18 at 13:46

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.