Generating Faster Algorithms for d-Path Vertex Cover

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21240%2F23%3A00371545" target="_blank" >RIV/68407700:21240/23:00371545 - isvavai.cz</a>

Výsledek na webu

<a href="https://doi.org/10.1007/978-3-031-43380-1_12" target="_blank" >https://doi.org/10.1007/978-3-031-43380-1_12</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/978-3-031-43380-1_12" target="_blank" >10.1007/978-3-031-43380-1_12</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Generating Faster Algorithms for d-Path Vertex Cover

Popis výsledku v původním jazyce

Many algorithms which exactly solve hard problems require branching on more or less complex structures in order to do their job. Those who design such algorithms often find themselves doing a meticulous analysis of numerous different cases in order to identify these structures and design suitable branching rules, all done by hand. This process tends to be error prone and often the resulting algorithm may be difficult to implement in practice. In this work, we aim to automate a part of this process and focus on the simplicity of the resulting implementation. We showcase our approach on the following problem. For a constant d, the d-Path Vertex Cover problem (d-PVC) is as follows: Given an undirected graph and an integer k, find a subset of at most k vertices of the graph, such that their deletion results in a graph not containing a path on d vertices as a subgraph. We develop a fully automated framework to generate parameterized branching algorithms for the problem and obtain algorithms outperforming those previously known for 3 < d < 8, e.g., we show that 5-PVC can be solved in O(2.7^kn^{O(1)}) time.

Název v anglickém jazyce

Generating Faster Algorithms for d-Path Vertex Cover

Popis výsledku anglicky

Many algorithms which exactly solve hard problems require branching on more or less complex structures in order to do their job. Those who design such algorithms often find themselves doing a meticulous analysis of numerous different cases in order to identify these structures and design suitable branching rules, all done by hand. This process tends to be error prone and often the resulting algorithm may be difficult to implement in practice. In this work, we aim to automate a part of this process and focus on the simplicity of the resulting implementation. We showcase our approach on the following problem. For a constant d, the d-Path Vertex Cover problem (d-PVC) is as follows: Given an undirected graph and an integer k, find a subset of at most k vertices of the graph, such that their deletion results in a graph not containing a path on d vertices as a subgraph. We develop a fully automated framework to generate parameterized branching algorithms for the problem and obtain algorithms outperforming those previously known for 3 < d < 8, e.g., we show that 5-PVC can be solved in O(2.7^kn^{O(1)}) time.

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í

2023

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

Proceedings of the 49th International Workshop on Graph-Theoretic Concepts in Computer Science

ISBN

978-3-031-43380-1

ISSN

0302-9743

e-ISSN

1611-3349

Počet stran výsledku

15

Strana od-do

157-171

Název nakladatele

Springer

Místo vydání

Cham

Místo konání akce

Fribourg

Datum konání akce

28. 6. 2023

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

WRD - Celosvětová akce

Kód UT WoS článku

—