Monday, October 24, 2016
Technische Universität Berlin
Institut für Mathematik
Straße des 17. Juni 136
10623 Berlin
room MA 041
Lecture - 14:15
Abstract:
We study the problem of searching for a hidden target in an environment that is modeled by an edge-weighted graph. A sequence of edges is chosen starting from a given root vertex such that each edge is adjacent to a previously chosen edge. This search paradigm, known as expanding search was recently introduced for modeling problems such as coal mining in which the cost of re-exploration is negligible. We define the search ratio of an expanding search as the maximum over all vertices of the ratio of the time taken to reach the vertex and the shortest-path cost to it from the root. Similar objectives have previously been studied in the context of conventional (pathwise) search.
In this talk we address algorithmic and computational issues of minimizing the search ratio over all expanding searches, for a variety of search environments, including general graphs, trees and star-like graphs. Our main results focus on the problem of finding the {\em randomized expanding search} with minimum expected search ratio, which is equivalent to solving a zero-sum game between a Searcher and a Hider. We solve these problems for certain classes of graphs, and obtain constant-factor approximations for others.
The talk is aimed at non specialists, and based on a joint work with Syros Angelopoulos and Thomas Lidbetter.
Colloquium - 16:00
Abstract:
Recently, several researchers have focused on vertex-deletion problems where the target graph classes have tree-like structures. A famous example is the Feedback Vertex Set problem which asks the existence of a set of at most k vertices in a given graph whose removal turns it into a forest. The existence of an FPT algorithm for the Feedback Vertex Set problem is generalized to a general problem called Treewidth-w Vertex Deletion; Fomin et al. (FOCS 2012) and Kim et al. (ACM Trans. Algorithms 2016) showed that Treewidth-w Vertex Deletion can be solved in single-exponential FPT time parameterized by the solution size, for every fixed w.
However, for such problems, the YES-instances should be sparse, as the target classes are already known to be sparse. A natural question is that when a given graph is very dense, can we efficiently turn this graph into some dense graph with some useful structure. Graphs of bounded rank-width or clique-width are one of the natural candidates for this question. Rank-width is one of the useful graph width parameters measuring how easy it is to decompose a graph into a certain tree-like structure based on the matrix rank function, and all complete graphs and complete bipartite graphs already have rank-width 1. In this talk, we survey recent progress on variants of deletion problems to graphs of bounded rank-width. Then we slightly focus on an interesting application of Mader's S-path Theorem, used to obtain a kernelization algorithm for Rankwidth-1 Vertex Deletion.