Shortest paths algorithms

elective monographs

Algorithms and data structures 1000-213bASD

(in Polish) W niektórych częściach materiału pomocna będzie podstawowa wiedza z algebry

liniowej, rachunku prawdopodobieństwa i przedmiotu Algorytmika (1000-2N00ALG).

The course is devoted to theoretical aspects of computing shortest paths in graphs, beyond the scope of basic algorithmic courses. We will discuss some of the most important theoretical developments of the last decades in this area: scaling algorithms for negative weights, distance oracles, dynamic and parallel algorithms, conditional lower bounds. We will also be looking at their applications and relationships with other fundamental algorithmic problems on graphs.

1. Variants of the problem and models of computation. Basic algorithms: Dijkstra, Bellman-Ford, their generalizations, weight scaling.

2. Classical scaling algorithms for single-source shortest paths (SSSP) with negative weights: Goldberg, Gabow-Tarjan.

3. Conditional lower bounds: equivalence of all-pairs shortest paths (APSP), negative triangle detection, and related problems.

4. Dynamic data structures maintaining shortest paths (a selection).

5. Algebraic algorithms: APSP in directed and undirected graphs; distance oracles.

6. Spanners. Approximate distance oracles in undirected graphs.

7. Low-diameter decomposition (LDD) in undirected and directed graphs and applications.

8. SSSP with negative weights in almost linear time.

9. Parallel algorithms: the classical, reducing exact integer SSSP to an approximate variant, parallel LDD.

10. Basic techniques for planar and minor-free graphs.

11. Shortest paths in real-life graphs: highway dimension.

Notes and research articles provided or indicated by the lecturer.

Knowledge: the student:

1. knows and can motivate the most important settings which fundamental path problems in graphs are studied in,

2. understands the importance of model of computation's choice for determining the computational complexity of algorithmic problems,

3. has advanced knowledge on designing algorithms solving (polynomial) graph problems and proving their (conditional) lower bounds.

Skills: the student:

1. can apply the learned techniques to construct efficient algorithms for graph problems or to prove their hardness,

2. can formally prove the correctness and determine the time complexity of algorithms in the studied settings: static, dynamic, and parallel.

Competences: the student:

1. knows the limitations of their own knowledge and the need of further study, and in particular the necessity of obtaining knowledge from outside the field,

2. the student understands the need to systematically read scientific articles to broaden and expand his/her knowledge.

The final grade will depend on the results of the homeworks (theoretical; about 70%) and the oral exam (about 30%).

The oral exam will be in one of two forms (to be chosen by each student):

1. a test of knowledge of the lecture material covered, or

2. a discussion about a single related scientific article not covered in class, to be read independently by the student. A list of possible articles will be provided. It is allowed to choose an article from outside the list, but such an article will have to be approved be the lecturer beforehand.

In the case of doctoral students, only the second form of oral examination is allowed.