Istnienie płaskiego zabezpieczenia odległości?

Niech G będzie n-węzłem niekierowanym grafem, a niech T będzie podzbiorem węzłów V (G) zwanym zaciskami . Zabezpieczenie odległości (G, T) jest wykresem H spełniającym tę właściwość

dla wszystkich węzłów u, v w T. (Należy zauważyć, że H niekoniecznie jest podrozdziałem G.)

Na przykład, niech G będzie poniższym wykresem (a), a T będzie węzłami na powierzchni zewnętrznej. Zatem wykres (b) jest zabezpieczeniem odległości dla (G, T).

Wiadomo, że istnieje konserwator odległości o różnych parametrach. Szczególnie interesuje mnie ta o następujących właściwościach:

1. G jest płaskie i nieważone (to znaczy wszystkie krawędzie G mają wagę jeden),
2. T ma rozmiar , a$O(n^{0.5})$
3. H ma rozmiar (liczbę węzłów i krawędzi) . (Byłoby miło, gdybyśmy mieli O ( $o(n)$.)$O(\frac{n}{\log\log n})$

Czy istnieje taki moduł zabezpieczający odległość?

Jeśli nie można spełnić powyższych właściwości, mile widziane są wszelkie formy relaksu.

Bibliografia:

• Rzadkie, jeśli chodzi o źródła i pary , obserwatory odległości , Don Coppersmith i Michael Elkin, SIDMA, 2006.
• Sparse Distance Preservers and Additive Spanners , Béla Bollobás, Don Coppersmith i Michael Elkin, SIDMA, 2005.
• Klucze i emulatory z sublinearnymi błędami odległości , Mikkel Thorup i Uri Zwick, SODA, 2006.
• Dolne granice dla kluczy przyrostowych, emulatorów i innych , David P. Woodruff, FOCS, 2006.

Zabezpieczenie odległości jest również znane jako emulator ; wiele pokrewnych prac można znaleźć w Internecie, wyszukując termin klucz , który wymaga, aby H był subgrafem G. Ale w moich aplikacjach możemy również używać innych wykresów, o ile H zachowuje odległości między T w G.

Wiele lat później wygląda na to, że OP w końcu odpowiedział na swoje własne pytanie: prawie optymalny emulator odległości dla grafów planarnych Hsien-Chiha Changa, Pawła Gawrychowskiego, Shay'a Mozesa i Orena Weimanna właśnie został opublikowany na arxivie.

$\widetilde{O}(\min\{t^2, \sqrt{tn}\})$$|T| =: t$$\widetilde{O}(n^{3/4})$$\widetilde{O}(n)$

(W mniej formalnej notatce uważam, że ten wynik jest naprawdę niesamowity. Gratulacje!)

warto przyjrzeć się płaskiemu kluczowi płaskiego podzestawu Kleina, który zachowuje odległości do współczynnika epsilon 1+.

Podzestaw klucza do grafów płaskich, z zastosowaniem do podzestawu TSP http://doi.acm.org/10.1145/1132516.1132620