1
$\begingroup$

Garey proved that the Rectilinear Steiner Tree problem is (strongly) NP-hard. I wonder if it is still true when we retrict the points to have integral coordinates and lie on a square of side lenght n^O(1) where n denotes the number of points.

$\endgroup$
1
$\begingroup$

Yes.

I suspect that you have not read the paper The Rectilinear Steiner Tree Problem is NP-complete, by M. R. Garey and D. S. Johnson, SIAM Journal on Applied Mathematics, Vol. 32 (1977), pp. 826-834. Well, if you have, I am sorry. Well, if you have, please indicate that critical information in your question. In fact, whenever your question is based on one big theorem/one paper, it is always a good idea to inform readers here whether you have no access to or have read or are familiar with a proof or proofs of the theorem/that paper. People, or at least I, will then be able to exchange ideas with you more efficiently in a way that suit you better.

I just browsed through the proof by Garey and Johnson. It is clear that, in fact, they build their proof on the rectilinear stree problem with integral coordinates within a square of side length $n^{O(1)}$, where $n$ denotes the number of points.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.