Humboldt-Universität zu Berlin - Mathematisch-Naturwissenschaftliche Fakultät - Institut für Informatik

Vortragssprache ist Englisch. Geplant sind etwa 45 Minuten Vortrag und bis zu 30 Minuten für Fragen.

Eine Zoom-Einladung erhalten Sie auf Anfrage.

Abstract:

We study the fine-grained parameterized complexity of graph problems parameterized by clique-width (cw). The central theme of this dissertation is that representations of partial solutions can compress the dynamic-programming state space, yielding optimal algorithms under fine-grained complexity hypotheses.

Specifically, we develop three main representation techniques for graph problems parameterized by clique-width:
First, we introduce connectivity and acyclicity representations that result in SETH-optimal single-exponential FPT algorithms for Steiner Tree in time $O^*(3^{cw})$, Connected Odd Cycle Transversal in time $O^*(12^{cw})$, Feedback Vertex Set in time $O^*(6^{cw})$, and Connected Feedback Vertex Set in time $O^*(18^{cw})$, as well as SETH-tight algorithms for Parity Feedback Vertex Set relative to both treewidth ($O^*(3^{tw})$) and clique-width ($O^*(6^{cw})$). These algorithms are complemented by matching SETH-based lower bounds.

Second, we provide a degree-representation technique that results in ETH-tight single-exponential XP algorithms for two degree-constrained spanning tree problems: Degree-Constrained Spanning Tree and Exact Leaf Spanning Tree.

Finally, we show the limits of representation by proving that a straightforward dynamic programming algorithm for the d-Clique Packing problem running in time $n^{O(cw^{d-1})}$ is ETH-optimal for every fixed d >= 3, by providing a lower bound that excludes any algorithm running in time $n^{o(cw^{d-1})}$ under ETH.