Editorial Board
Publishing Ethics
Author Guide
Submission Prepare Your ManuscriptPeer review
Archive
Volume 28, No 4, 2021, P. 117-124
UDC 519.178
A. G. Klyuchikov and M. N. Vyalyi
A win-win algorithm for the $(k + 1)-LST/k$-pathwidth problem
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.
DOI: 10.33048/daio.2021.28.710
Artyom G. Klyuchikov 1
Artyom G. Klyuchikov 1,2,3
1. Moscow Institute of Physics and Technology,
9 Institutskii Lane, 141701 Dolgoprudnyi, Russia
2. Moscow Institute of Physics and Technology,
9 Institutskii Lane, 141701 Dolgoprudnyi, Russia
3. HSE University,
11 Pokrovskii Boulevard, 109028 Moscow, Russia
e-mail: klyuchikov@phystech.edu, vyalyi@gmail.com
Received April 12, 2021
Revised August 2, 2021
Accepted August 3, 2021
References
[1] D. Bienstock, N. Robertson, P. D. Seymour, and R. Thomas, Quickly excluding a forest, J. Comb. Theory, Ser. B., 52, 274–283 (1991).[2] R. J. Douglas, NP-completeness and degree restricted spanning trees, Discrete Math. 105 (1–3), 41–47 (1992).
[3] T. Kashiwabara and T. Fujisawa, NP-completeness of the problem of finding a minimum-clique-number interval graph containing a given graph as a subgraph, in Proc. 1979 Int. Symp. Circuits and Systems, Tokyo, Japan, July 17–19, 1979 (IEEE, New York, 1979), pp. 657–660.
[4] H. L. Bodlaender, E. D. Demaine, M. R. Fellows [et al.], Open problems in parameterized and exact computation — IWPEC 2008, Technical Report UU– CS–2008–017, (Utrecht Univ., Utrecht, 2008). Available at http://www.cs.uu. nl/research/techreps/repo/CS-2008/2008-017.pdf (accessed Aug. 3, 2021).
[5] R. Diestel, Graph minors I: A short proof of the path-width theorem, Comb. Prob. Comput. 4 (1), 27–30 (1995).
