14
$\begingroup$

Gilbert-Pollak conjecture on the Steiner ratio: Consider a set $P$ of $n$ points on the euclidean plane. A shortest network interconnecting $P$ must be a tree, which is called a Steiner minimum tree and denoted by $SMT(P)$. A $SMT(P)$ may contain vertices not in $P$. Such vertices are called Steiner points, while vertices in $P$ are called regular points. A spanning tree on $P$ is just a tree with vertex set $P$. A shortest spanning tree on $P$ is also called a minimum spanning tree on $P$, denoted by $MST(P)$. The Steiner ratio is defined to be $$\rho=\inf\{L_s(P)/L_m(P)|P\},$$ where $L_s(P)$ and $L_m(P)$ are lengths of $SMT(P)$ and $MST(P)$, respectively. Gilbert and Pollak conjectured that $p = \sqrt{3}/2$.

I find recently that the proof of the Gilbert-Pollak conjecture given by D. Z. Du and F. K. Hwang in 1990 is disproved by N. Innami etc. (The Steiner Ratio Conjecture of Gilbert-Pollak May Still Be Open and The Steiner Ratio Gilbert–Pollak Conjecture Is Still Open). When I check related comments about this case on the Internet, I find there seems to be few people that care about this (very few information).

Is this conjecture still open? Is there anyone trying to sovle this problem in other ways or to fix the proof of D. Z. Du and F. K. Hwang?

$\endgroup$
2
  • 2
    $\begingroup$ Also posted, with no notice at either site, to cstheory.stackexchange.com/questions/19285/… $\endgroup$ Oct 6, 2013 at 6:33
  • $\begingroup$ @Benjamin Thanks. Your information is very useful. Personally, I find this problem interesting. I don't understand why few people care about it, specifically when the only proof has been disproved. Maybe as it is not a problem big engough. $\endgroup$
    – zenos
    Oct 8, 2013 at 8:06

2 Answers 2

12
$\begingroup$

The answer is yes. The basic concept used in Du and Hwang approach to the problem is so-called characteristic area constructed for a Steiner tree. But this object needs to have mutually exclusive properties. We put a short note in arXiv concerning these problems, see http://arxiv.org/abs/1402.6079. Some questions related to Gilbert-Pollack conjecture are discussed in http://arxiv.org/abs/1101.0106.

$\endgroup$
7
$\begingroup$

[Since this question has not elicited any other responses over the past two months, I am now migrating my comments to serve as an answer.]

As far as I know, the answer is yes: it's still open. Pollak sent me a nice historical piece on Steiner Trees a few months ago; it is written by, among others, Ron Graham. The paper doesn't address - or even mention - the conjecture you ask about here, but it is enjoyable reading (and shows there are still some people who care about this subject!). The manuscript is:

Brazil, M., Graham, R.L., Thomas, D.A. et al. Arch. Hist. Exact Sci. (2014) 68: 327. doi:10.1007/s00407-013-0127-z. Link (no paywall).

Also, I did personally ask Pollak whether he knows about this problem being open or not. His response:

As Bob Prim, one of my bosses at Bell Labs, used to say, 'nobody ever tells me anything.' I did not know that the Du-Hwang proof had been questioned.

(So: He's not sure either.)

Apparently the textbook to look at for a "proof" is: Ivanov, A. A. O., & Tužilin, A. A. (1994). Minimal networks: the Steiner problem and its generalizations. CRC press. You will find it as Theorem 3.1 on page 167. Of course, a "disproof" evidently means there is an error somewhere in the text.

This now exhausts what I know of the problem and its current standing, but I hope anyone with further information will not hesitate to post it! (Edit: It seems Ivanov has also responded to the OP.)

$\endgroup$
0

Your Answer

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

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