I (k, r)-Center får vi en (eventuellt kantviktad) graf och uppmanas att välja som mest k hörn (centra), så att alla andra hörn är på avstånd som mest r från ett centrum. I detta dokument ger vi ett antal snäva finkorniga gränser på komplexiteten av detta problem med avseende på olika standard graf parametrar. Specifikt: • För varje r ≥ 1, visar vi en algoritm som löser problemet i O * ((3r + 1) cw ) tid, där cw är klique-bredden i inmatningskurvan, samt en tight SETH lägre bundet matchar denna algoritms prestanda. Som en följd, för r = 1, detta minskar gapet som tidigare existerade på komplexiteten av Dominating Set parameterized av cw. • Vi stärker tidigare kända FPT nedre gränser, genom att visa att (k, r)-Center är W[1]-hård parameteriserad av indatagrafens vertex omslag (om kantvikter är tillåtna), eller feedback vertex set, även om k är en ytterligare parameter. Våra minskningar innebär snäva ETH-baserade nedre gränser. Slutligen, vi utformar en algoritm parameteriserad av vertex täcka för oviktade grafer. • Vi visar att komplexiteten i problemet parameteriseras av träddjup är 2  på (td 2 ) genom att visa en algoritm av denna komplexitet och en tight ETH-baserad nedre gräns. Vi kompletterar dessa mestadels negativa resultat genom att tillhandahålla FPT approximationssystem parameteriserade av klickbredd eller trädbredd som fungerar effektivt oberoende av värdena för k, r. I synnerhet ger vi algoritmer som, för alla > 0, kör i tiden O * ((tw/ ) O( tw) ), O * ((cw/ ) O(cw) ) och returnera en (k, (1 + )r)-center, om en (k, r)-center finns, vilket kringgår problemets W-hårdhet.
Även för träddjupet är k-Center FPT REF.
Structural Parameters, Tight Bounds, and Approximation for (k,r)-Center
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}