Fine-Grained Complexity of Computing Degree-Constrained Spanning TreesOberseminar Discrete Optimization

by Phuc Hung Hong (Technische Universität Wien)

Monday Mar 24, 2025, 6:15 PM → 7:15 PM Europe/Berlin

Arithmeum, Lennéstr., 2 - Seminarraum (Arithmeum / Research Institute for Discrete Mathematics)

This talk is concerned with the computation of minimum-cost spanning trees satisfying prescribed vertex degree constraints: Given a graph G and a constraint function D, we ask for a (minimum-cost) spanning tree T such that for each vertex v, the degree of v in T is in a set D(v) of admissible degrees. We obtain an almost-complete overview of the fine-grained complexity of these problems taking into account the most classical graph parameters of the input graph G.

In particular, we show SETH-tight upper and lower bounds when parameterized by the pathwidth and cutwidth, an ETH-tight algorithm parameterized by the cliquewidth, and a nearly SETH-tight algorithm parameterized by treewidth.

Joint work with Narek Bojikian, Alexander Firbas, Robert Ganian and Krisztina Szilagyi.

 

The Oberseminar takes place in the Seminarraum, 1^st floor. Participants are invited to have coffee or tea in the lounge before.