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.