Help Privacy Policy Disclaimer
  Advanced SearchBrowse





Domination and Cut Problems on Chordal Graphs with Bounded Leafage


Sharma,  Roohani
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource
No external resources are shared
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)

(Preprint), 548KB

Supplementary Material (public)
There is no public supplementary material available

Galby, E., Marx, D., Schepper, P., Sharma, R., & Tale, P. (2022). Domination and Cut Problems on Chordal Graphs with Bounded Leafage. Retrieved from https://arxiv.org/abs/2208.02850.

Cite as: https://hdl.handle.net/21.11116/0000-000C-1DF6-F
The leafage of a chordal graph G is the minimum integer l such that G can be
realized as an intersection graph of subtrees of a tree with l leaves. We
consider structural parameterization by the leafage of classical domination and
cut problems on chordal graphs. Fomin, Golovach, and Raymond [ESA 2018,
Algorithmica 2020] proved, among other things, that Dominating Set on chordal
graphs admits an algorithm running in time $2^{O(l^2)} n^{O(1)}$. We present a
conceptually much simpler algorithm that runs in time $2^{O(l)} n^{O(1)}$. We
extend our approach to obtain similar results for Connected Dominating Set and
Steiner Tree. We then consider the two classical cut problems MultiCut with
Undeletable Terminals and Multiway Cut with Undeletable Terminals. We prove
that the former is W[1]-hard when parameterized by the leafage and complement
this result by presenting a simple $n^{O(l)}$-time algorithm. To our surprise,
we find that Multiway Cut with Undeletable Terminals on chordal graphs can be
solved, in contrast, in $n^{O(1)}$-time.