Author Archives: admin

Topics for the first few lectures

The lectures were based on the following papers:
1. A data structure for dynamic trees by Sleator and Tarjan 1982,  https://www.cs.cmu.edu/~sleator/papers/dynamic-trees.pdf
2. Lecture on dynamic graph connectivity by Virginia V. Williams http://theory.stanford.edu/~virgi/cs267/lecture10.pdf
3. Data Structures for On-Line Updating of Minimum Spanning Trees, with Applications by Frederickson 1984, https://csclub.uwaterloo.ca/~gzsong/papers/Data%20Structures%20for%20On-Line%20Updating%20of%20Minimum%20Spanning%20Trees,%20with%20Applications.pdf
4. Dynamic Transtive Closure via Dynamic Matrix Inverse by Sankowski 2004, www.mimuw.edu.pl/~sank/pub/sankowski_focs04.ps
5. Subquadratic Algorithm for Dynamic Shortest Distances by Sankowski 2005, http:///chapter/10.1007%2F11533719_47
6. A New Approach to Dynamic All Pairs Shortest Paths by Demetrescu and Italiano 2003, www.dis.uniroma1.it/~demetres/docs/dapsp-full.pdf
7. Fully-Dynamic All-Pairs Shortest Paths: Faster and Allowing Negative Cycles by Thorup 2004, http://link.springer.com/chapter/10.1007%2F978-3-540-27810-8_33

Miniworkshop on 09.04.2015

logo FNPOn 09.04.2015 during our Foundation for Polish Science Algorithmic Miniworkshops we will host Mikkel Thorup from University of Copenhagen. He will give a talk on his recent result on “Deterministic Global Minimum Cut of a Simple Graph in Near-Linear Time”. The abstract is given below.

We plan to have a group discussion and joint pierogi lunch after his talk (sponsored by FNP).


 

Ken-ichi Kawarabayashi, National Institute of Informatics, Tokyo, Japan

Mikkel Thorup, University of Copenhagen, Denmark

Abstract

We present a deterministic near-linear time algorithm that computes the edge-connectivity and finds a minimum cut for a simple undirected unweighted graph G with n vertices and m edges. This is the first o(mn) time deterministic algorithm for the problem.  In near-linear time we can also construct the classic cactus representation of all minimum cuts.

The previous fastest deterministic algorithm by Gabow from STOC’91 took ~O(m+k^2 n), where k is the edge connectivity, but k could be Omega(n).

At STOC’96 Karger presented a randomized near linear time Monte Carlo algorithm for the minimum cut problem.  As he points out, there is no better way of certifying the minimality of the returned cut than to use Gabow’s slower deterministic algorithm and compare sizes.

Our main technical contribution is a near-linear time algorithm that contract vertex sets of a simple input graph G with minimum degree d, producing a multigraph with ~O(m/d) edges which preserves all minimum cuts of G with at least 2 vertices on each side.

In our deterministic near-linear time algorithm, we will decompose the problem via low-conductance cuts found using PageRank a la Brin and Page (1998), as analyzed by Andersson, Chung, and Lang at FOCS’06. Normally such algorithms for low-conductance cuts are randomized Monte Carlo algorithms, because they rely on guessing a good start vertex. However, in our case, we have so much structure that no guessing is needed.

Miniworkshop on 26.02.2015

On 26.02.2015 as a part of our logo FNPFoundation for Polish Science Algorithmic Miniworkshop series we will have a seminar by Archontia Giannopoulou. The title of the talk is “Uniform Kernelization Complexity of Hitting Forbidden Minors” and the abstract is given below.

We plan to have a group discussion and joint lunch after his talk.

Abstract:

The F-Minor-Free Deletion problem asks, for a fixed set F and an input consisting of a graph G and integer k, whether k vertices can be removed from G such that the resulting graph does not contain any member of F as a minor. It generalizes classic graph problems such as Vertex Cover and Feedback Vertex Set.  Fomin et al. (FOCS 2012) showed that the special case Planar-F-Minor-Free Deletion (when F contains at least one planar graph) has a kernel of polynomial size: instances (G,k) can efficiently be reduced to equivalent instances (G’,k) of size f(F)k^{g(F)} for some functions f and g. The degree g of the polynomial grows very quickly; it is not even known to be computable. Fomin et al. left open whether Planar-F-Minor-Free Deletion has kernels whose size is uniformly polynomial, i.e., of the form f(F) k^c$ for some universal constant c that does not depend on F.
In this talk we discuss to what extent provably effective and efficient preprocessing is possible for F-Minor-Free Deletion. In particular, we show that not all Planar-F-Minor-Free Deletion problems admit uniformly polynomial kernels but also that there exist problems that do admit uniformly polynomial kernels.

The Talk on Online Bipartite Matching in Offline Time

The talk on The Talk on Online Bipartite Matching in Offline Time.

The lecture on mechanism design.

[1] Giuseppe F. Italiano, Yahav Nussbaum, Piotr Sankowski, Christian Wulff-Nilsen: Improved algorithms for min cut and max flow in undirected planar graphs. STOC 2011: 313-322.
[2] Glencora Borradaile, Piotr Sankowski, Christian Wulff-Nilsen: Min st-cut Oracle for Planar Graphs with Near-Linear Preprocessing Time. FOCS 2010: 601-610.
[3] Jakub Lacki, Yahav Nussbaum, Piotr Sankowski, Christian Wulff-Nilsen: Single Source – All Sinks Max Flows in Planar Digraphs. FOCS 2012: 599-608.

Algorithmic Trends: Third Homework

The third homework is due on the 23rd of April.