Generating Faster Algorithms for d-Path Vertex Cover

Result code in 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>

Result on the web

<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>

Result language

angličtina

Original language name

Generating Faster Algorithms for d-Path Vertex Cover

Original language description

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.

Czech name

—

Czech description

—

Type

D - Article in proceedings

CEP classification

—

OECD FORD branch

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

Project

<a href="/en/project/EF16_019%2F0000765" target="_blank" >EF16_019/0000765: Research Center for Informatics</a><br>

Continuities

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

Publication year

2023

Confidentiality

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

Article name in the collection

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

Number of pages

15

Pages from-to

157-171

Publisher name

Springer

Place of publication

Cham

Event location

Fribourg

Event date

Jun 28, 2023

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

—