AG 1   Info

AG Audience

English

30 Minutes

Saarbrücken

We investigate 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, T achieves a degree specified by D(v). Specifically, we consider three kinds of constraint functions ordered by their generality -- D may either assign each vertex to a list of admissible degrees, an upper bound on the degrees, or a specific degree. Using a combination of novel techniques and state-of-the-art machinery, 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 present SETH-tight upper and lower bounds for these problems when parameterized by the pathwidth and

cutwidth, an ETH-tight algorithm parameterized by the cliquewidth, and a nearly SETH-tight algorithm parameterized by treewidth. This is joint work with Narek Bojikian, Alexander Firbas, Robert Ganian and Hung P. Hoang.

Nidhi Rathi

+49 681 9325 1134

--email hidden

Zoom

897 027 2575

passcode not visible

logged in users only