Computer Science Graduate Seminar: About Treedepth and Related Notions

Friday, November 10, 2017, 12:00pm

Location: Computer Science Center, Geb. E3, Room 9U10 (2359|0.10)

Speaker: Dipl.-Inform. Fernando Sánchez Villaamil

Abstract:

In this thesis we present several results relating to treedepth. First, we provide the fastest linear-time fpt algorithm to compute the treedepth of a graph. It decides if a graph has treedepth d in time 2^O(d^2) * n. In the process we answer an open question by Nešetřil and Ossona de Mendez, which asked for a simple linear-time fpt algorithm. We then proceed to compare treewidth to treedepth. We give lower bounds for the running time and space consumption of any dynamic programming algorithm (for a reasonable definition of dynamic programming on tree/path/treedepth decompositions which we introduce) for the problems Vertex Cover, 3-Coloring and Dominating Set on either a tree, a path or a treedepth decomposition. These bounds match the best known running times for these problems to date. It is not difficult to see that there are linear-time fpt algorithms for Vertex Cover and 3-Coloring parameterized by a given treedepth decomposition of depth d with a space consumption bounded by poly(d) * log n$. We show the same is possible for Dominating Set. We analyze the random intersection graph model, which attempts to model real-world networks where the connections between actors represent underlying shared attributes. We show that this model, when configured such that it generates degenerate graphs, produces with high probability graphs which belong to a class of bounded expansion, otherwise the graphs are asymptotically almost surely somewhere dense. We then present an algorithm for motif/subgraph counting on bounded expansion graphs which exploits a characterization of bounded expansion graph classes via decompositions into parts of bounded treedepth. Finally, we present a heuristic to compute tree decompositions which starts by computing a treedepth decomposition and show that it is competitive against other known heuristics.

The computer science lecturers invite interested people to join.