A. G. Klyuchikov, M. N. Vyalyi, “A win-win algorithm for the $(k+1)$-LST/$k$-pathwidth problem”, Diskretn. Anal. Issled. Oper., 2021, Volume 28, Issue 4,Pages 117

A win-win algorithm for the $(k+1)$-LST/$k$-pathwidth problem

A. G. Klyuchikov^a, M. N. Vyalyi^abc

^a Moscow Institute of Physics and Technology, 9 Institutskii Lane, 141701 Dolgoprudnyi, Russia
^b Federal Research Center “Computer Science and Control” RAS 44 Bld. 2 Vavilov Street, 119333 Moscow, Russia
^c HSE University, 11 Pokrovskii Boulevard, 109028 Moscow, Russia

Abstract: We describe a win-win algorithm that produces in polynomial of size of a graph $G$ and given parameter $k$ time either a spanning tree with al least $k+1$ leaves or a path decomposition with width at most $k$. This algorithm is optimal due to the path decomposition theorem [1]. Bibliogr. 5.

Keywords: path decomposition, spanning tree, $k$-LST problem, win-win algorithm, FPT.

UDC: 519.178

Received: 12.04.2021
Revised: 02.08.2021
Accepted: 03.08.2021

DOI: 10.33048/daio.2021.28.710