On Polynomial Kernels for Traveling Salesperson Problem and Its Generalizations

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21240%2F22%3A00359294" target="_blank" >RIV/68407700:21240/22:00359294 - isvavai.cz</a>

Výsledek na webu

<a href="https://doi.org/10.4230/LIPIcs.ESA.2022.22" target="_blank" >https://doi.org/10.4230/LIPIcs.ESA.2022.22</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.4230/LIPIcs.ESA.2022.22" target="_blank" >10.4230/LIPIcs.ESA.2022.22</a>

Jazyk výsledku

angličtina

Název v původním jazyce

On Polynomial Kernels for Traveling Salesperson Problem and Its Generalizations

Popis výsledku v původním jazyce

For many problems, the important instances from practice possess certain structure that one should reflect in the design of specific algorithms. As data reduction is an important and inextricable part of today’s computation, we employ one of the most successful models of such precomputation - the kernelization. Within this framework, we focus on Traveling Salesperson Problem (TSP) and some of its generalizations. We provide a kernel for TSP with size polynomial in either the feedback edge set number or the size of a modulator to constant-sized components. For its generalizations, we also consider other structural parameters such as the vertex cover number and the size of a modulator to constant-sized paths. We complement our results from the negative side by showing that the existence of a polynomial-sized kernel with respect to the fractioning number, the combined parameter maximum degree and treewidth, and, in the case of {Subset TSP}, modulator to disjoint cycles (i.e., the treewidth two graphs) is unlikely.

Název v anglickém jazyce

On Polynomial Kernels for Traveling Salesperson Problem and Its Generalizations

Popis výsledku anglicky

For many problems, the important instances from practice possess certain structure that one should reflect in the design of specific algorithms. As data reduction is an important and inextricable part of today’s computation, we employ one of the most successful models of such precomputation - the kernelization. Within this framework, we focus on Traveling Salesperson Problem (TSP) and some of its generalizations. We provide a kernel for TSP with size polynomial in either the feedback edge set number or the size of a modulator to constant-sized components. For its generalizations, we also consider other structural parameters such as the vertex cover number and the size of a modulator to constant-sized paths. We complement our results from the negative side by showing that the existence of a polynomial-sized kernel with respect to the fractioning number, the combined parameter maximum degree and treewidth, and, in the case of {Subset TSP}, modulator to disjoint cycles (i.e., the treewidth two graphs) is unlikely.

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

<a href="/cs/project/EF16_019%2F0000765" target="_blank" >EF16_019/0000765: Výzkumné centrum informatiky</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>S - Specificky vyzkum na vysokych skolach

Rok uplatnění

2022

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

30th Annual European Symposium on Algorithms (ESA 2022)

ISBN

978-3-95977-247-1

ISSN

—

e-ISSN

1868-8969

Počet stran výsledku

16

Strana od-do

"22:1"-"22:16"

Název nakladatele

Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik

Místo vydání

Dagstuhl

Místo konání akce

Postdam

Datum konání akce

5. 9. 2022

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—