## Hauptseminar (Master): Advanced Graph Algorithms

### General Information

Course instructors: Andreas S. Schulz and Alexander Grosz

Dijkstra, Kruskal and Ford-Fulkerson are examples of well-established algorithms on graphs and networks - but there's much more to discover!

In this seminar we will discuss a broad range of other problems and algorithms on graphs.

### Schedule

- Session 1 (G, A), Thursday 2024-01-25 14:00.
- Session 2 (M, L), Thursday 2024-01-25 15:30.
- Session 3 (J, K), Friday 2024-01-26 10:30.
- Session 4 (F), Friday 2024-01-26 14:00.

### Topics

**A: Approximating Steiner Trees**

Karpinski & Zelikovsky,*New Approximation Algorithms for the Steiner Tree Problems,*1997 DOI

The authors achieve improved approximation ratios by employing the notion of relative gain.**B: Steiner Trees with bounded treewidth**

Chimani et al.,*Improved Steiner tree algorithms for bounded treewidth,*2012 DOI

A dynamic programming approach gives proves FPT with regards to the treewidth of the graph.**C: Tree-Decompositions**

Bodlaender,*A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth*, 1996 DOI

By distinguishing between high- and low-degree vertices, an efficient (wrt the treewidth) recursion scheme can be devised to compute the treewidth of a graph and the corresponding tree-decomposition.**D: Budgeted Prize Collecting TSP**

Paul et al.,*Budgeted Prize-Collecting Traveling Salesman and Minimum Spanning Tree Problems*, 2020 DOI

A primal-dual approach gives a 2-approximation for the rooted and unrooted budgeted prize-collecting TSP.**E: Graph Drawing**

Bannister et al.,*Parameterized Complexity of 1-Planarity*, 2013 DOI

Several parameters lead to FPT algorithms for the NP-hard problem of deciding/finding a 1-planar drawing. Other parameters are discussed for which the problem remains NP-complete when they are bounded.**F: Edge Coloring**

Adamaszek & Popa,*Approximation and Hardness Results for the Maximum Edge q-coloring Problem*, 2010 DOI

Variants of the edge-coloring problem are identified as being NP- and APX-hard. For perfect graphs, an approximation algorithm is given.**G: A Simple Min-Cut Algorithm**

Stoer & Wagner,*A simple min-cut algorithm*, 1997 DOI

Queyranne,*Minimizing symmetric submodular functions*, 1998 DOI

Stoer and Wagner present an algorithm to compute a minimum cut that is*not*based on flow computations (as compared to most previous results), but on an iterative construction of the graph instead. This approach has been generalized to the class of symmetric submodular functions by Queyranne.**H: Parametric Network Flow**

Gallo et al.,*A Fast Parametric Maximum Flow Algorithm and Applications*, 1989 DOI

The Goldberg and Tarjan algorithm (push-relabel) is extended to the case of*parametric*max-flow, in which the capacities are not fixed, but given as functions of a parameter.**I: Generalized Steiner Networks**

Jain,*A Factor 2 Approximation Algorithm for the Generalized Steiner Network Problem*, 2001 DOI

The author presents an iterative rounding scheme on an LP-formulation of the generalized Steiner network problem (or more precisely a generalization of it).**J: Minimum Bounded Degree Spanning Trees**

Goemans,*Minimum Bounded Degree Spanning Trees*, 2006 DOI

A different kind of approximation: Even though the problem of finding a minimum spanning tree with a given maximum degree is NP-hard, a tree with better or the same cost can be found efficiently when we allow the degree bound to be violated by at most 2.**K: Minimum Bounded Degree Spanning Trees revisited**

Singh & Lau,*Approximating Minimum Bounded Degree Spanning Trees to within One of Optimal*, 2015 DOI

A new method (extending the approach of Jain 2001) improves the result of Goemans to violating the degree bound by at most 1.**L: Randomized Min-Cut**

Karger & Stein,*A new approach to the minimum cut problem*, 1996 DOI

Yet another approach for solving the problem of finding a minimum cut in a graph. This efficient randomized algorithm finds an/all optimal solutions with high probability.**M: Approximating CVRP with Unsplittable Demands**

Friggstad et al.,*Improved Approximations for Capacitated Vehicle Routing with Unsplittable Client Demands,*2022 DOI

The unsplittable capacitated vehicle routing problem allows for different approximation methods, in this case either based on a subroutine for approximating the TSP or on LP rounding techniques.