Vi studerar låg-förvrängning inbäddning av metriska utrymmen in i linjen, och mer allmänt, in i den kortaste vägen metrisk av träd, från parameteriserade komplexitet perspektiv. Låt M = M (G) vara den kortaste vägen metrisk för en kant viktad graf G, med vertex set V (G) och kanten set E(G), på n hörn. Vi ger den första fasta parametern dragbar algoritm som för en oviktad graf metrisk M och heltal d antingen konstruerar en inbäddning av M i raden med distorsion som mest d, eller drar slutsatsen att ingen sådan inbäddning finns. Vår algoritm kräver O(nd 4 (2d + 1) 2d ) tid som är en betydande förbättring jämfört med den bästa tidigare algoritm som körs i tid O(n 4d+2 d O(1) ). På grund av sin uppenbara likhet med den notoriskt hårda Bandbredd Minimering problem, finner vi det förvånande att detta problem visar sig vara fast parameter kantbar. Vi utökar våra resultat på att inbädda oviktad graf i linjen på två sätt. Först ger vi en algoritm för att konstruera små distorsion inbäddningar av viktade grafmått. Löptiden för vår algoritm är O(n(dW ) 4 (2d + 1) 2dW ), där W är den största kantvikten för indatagrafen. För att komplettera detta resultat visar vi att det exponentiella beroendet av maximal kantvikt är oundvikligt. I synnerhet visar vi att avgöra om en viktad graf metriska M (G) med maximal vikt W <  och V (G) kan inbäddas i linjen med distorsion som mest d är NP-komplett för varje fast rationell d ≥ 2. Detta utesluter alla möjligheter till en algoritm med körtid O(nW ) h(d) ) där h är en funktion av d ensam. För det andra anser vi att det finns mer allmänna värdvärden för motsvarande resultat. I synnerhet, Vi bevisar att för alla träd T med maximal grad, inbädda M i en kortaste väg metriska av T är fast parameter dragbar, Parameterized av ( ska, d).
Parameteriserad komplexitet av låg-snedvridning inbäddningar övervägdes av Fellows et al. REF, som gav en fast parameter dragbar (FPT) algoritm för att hitta en inbäddning av en oviktad graf metriska i raden med distorsion som mest c, eller drar slutsatsen att ingen sådan inbäddning finns, som fungerar i tiden O (nc 4 (2c + 1) 2c ).
Distortion Is Fixed Parameter Tractable
{'venue': 'ICALP', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}