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

Zugangsdaten für Zoom  teilt Prof. Kratsch auf Anfrage mit.

Abstract:

Dynamic-programming algorithms on tree decompositions form a well-established tool for solving NP-hard problems. However, they suffer from at least two drawbacks we address in this work. First, graphs of bounded treewidth are sparse, so such algorithms cannot handle even the simplest dense graphs like cliques or bicliques. One parameter that generalizes treewidth, overcomes these issues, and still often allows for efficient dynamic-programming algorithms is clique-width. There are graph classes, though, for which clique-width is exponential in treewidth. So the algorithms for clique-width do not necessarily yield algorithms with the same running time for treewidth; some exponential blow-up might occur. Martin Fürer [LATIN 2014, ITCS 2017] introduced two generalizations of clique-width called fusion-width and multi-clique-width, each upper-bounded by both treewidth and clique-width (plus a constant), thus overcoming the limitations mentioned so far. We study algorithmic applications and structural properties of those two parameters and establish a relation between them.

The second limitation of dynamic-programming algorithms for treewidth is that they require exponential space. Unlike exponential time complexity, which can be tolerated for small parameters by letting the algorithm run long enough, the exponential space complexity is prohibitive as the available space is usually limited. Further, conditional results by Allender et al. [Theory Comput. 2014] and Pilipczuk and Wrochna [ACM Trans. Comput. Theory 2018] suggest that decreasing the space complexity of such algorithms requires an increase in the running time. On the positive side, the works by Fürer and Yu [Theory Comput. Syst. 2017], Pilipczuk and Wrochna [ACM Trans. Comput. Theory 2018], Hegerfeld and Kratsch [STACS 2020], and Nederlof et al. [WG 2020] show that if one replaces treewidth by a larger parameter, treedepth, then one can obtain algorithms with essentially the same running time and only polynomial space complexity. We show that this is true for a much broader class of problems, namely the problems captured by what we call a NEO2[FRec]+ACK logic.

Finally, we consider the interplay between these two concepts by studying a bounded-depth analogue of clique-width, called shrubdepth. We establish that for certain standard graph problems, bounding the depth of clique-expressions allows for recursive algorithms with polynomial space complexity.