Back to Search Start Over

Parameterized algorithms for Steiner tree and (connected) dominating set on path graphs.

Authors :
de Figueiredo, Celina M. H.
Lopes, Raul
de Melo, Alexsander A.
Silva, Ana
Source :
Networks; Sep2024, Vol. 84 Issue 2, p132-147, 16p
Publication Year :
2024

Abstract

Chordal graphs are the intersection graphs of subtrees of a tree, while interval graphs of subpaths of a path. Undirected path graphs, directed path graphs and rooted directed path graphs are intermediate graph classes, defined, respectively, as the intersection graphs of paths of a tree, of directed paths of an oriented tree, and of directed paths of an out branching. All of these path graphs have vertex leafage 2. DominatingSet, ConnectedDominatingSet, and Steinertree problems are W[2]$$ \mathrm{W}\left[2\right] $$‐hard parameterized by the size of the solution on chordal graphs, NP$$ \mathrm{NP} $$‐complete on undirected path graphs, and polynomial‐time solvable on rooted directed path graphs, and hence also on interval graphs. We further investigate the (parameterized) complexity of all these problems when constrained to chordal graphs, taking the vertex leafage and the aforementioned classes into consideration. We prove that DominatingSet, ConnectedDominatingSet, and Steinertree are FPT$$ \mathrm{FPT} $$ on chordal graphs when parameterized by the size of the solution plus the vertex leafage, and that WeightedConnectedDominatingSet is polynomial‐time solvable on strongly chordal graphs. We also introduce a new subclass of undirected path graphs, which we call in–out rooted directed path graphs, as the intersection graphs of directed paths of an in–out branching. We prove that DominatingSet, ConnectedDominatingSet, and Steinertree are solvable in polynomial time on this class, generalizing the polynomiality for rooted directed path graphs proved by Booth and Johnson (SIAM J. Comput. 11 (1982), 191‐199.) and by White et al. (Networks 15 (1985), 109‐124.). [ABSTRACT FROM AUTHOR]

Details

Language :
English
ISSN :
00283045
Volume :
84
Issue :
2
Database :
Complementary Index
Journal :
Networks
Publication Type :
Academic Journal
Accession number :
178784223
Full Text :
https://doi.org/10.1002/net.22220