Hasso-Plattner-InstitutSDG am HPI
Hasso-Plattner-InstitutDSG am HPI
Login
 

Approximation and Parameterized Algorithms for Graph Connectivity Problems

Chair for Algorithm Engineering
Hasso Plattner Institute

Office: A-1.13
Tel.: +49 331 5509-3933
Email: Ziena.Zeif(at)hpi.de
Links: Homepage, Publications

Supervisor: Prof. Dr. Tobias Friedrich

A network graph is a mathematical model consisting of vertices and pairs of vertices, called edges, that can describe structures in nature and technology. For instance social structures, road networks, computer networks, electrical circuits, supply networks, chemical components, and so on. Weights often arise naturally in network graphs on the edges or vertices, which gives the motivation to research vertex-weighted or/and edge-weighted graphs. Our investigations are focused on classical graph problems like to partition, cover or pack a graph into subgraphs, multicommodity flows and multicuts, as well as graph separations via vertices or edges.

Problem Overview

The field of problems from above become to be combinatorial optimization problems when we add an objective function that we wish to minimize or maximize, respectively. In the following we give an overview about the problems that we consider:

  • Bounded Graph Separation: Given a (weighted) network graph and a positive number \(W\). The task is to find a minimal number of vertices or edges such that its removal leads to connected components of size (weight) less than \(W\).
  • Connected Graph Partitioning, Packing, Covering: Given a weighted network graph and a positive integer \(k\). The task is to find a set of \(k\) connected subgraphs of approximately equal weight. Thereby, we distinguish between partitioning, covering or packing the vertex set.
  • Multicommodity Flows and Multicuts: Given a network graph with edge capacities and \(k\) source-sink pairs, the maximum multicommodity flow problem asks for the maximum amount of flow that can be routed between the source-sink pairs. A natural dual to the maximum multicommodity flow problem is the minimum multicut problem, where we search for a set of edges whose removal disconnects all the source-sink pairs and has minimal costs w.r.t. its capacities.

Practical Applications

Finding bounded vertex separators, multicommodity flows and multicuts and connected balanced vertex or edge partitions in graphs are classical problems in graph theory with many practical applications. Separating a graph into bounded components by removing vertices or edges has been proven useful in designing divide-and-conquer algorithms and parallel algorithms for various graph problems. Practical applications of these problems include finding guard points in traffic networks for the toll control or in case of epidemics, restricting the number of infections by taking advantage of cuts and separators in graph networks [1].

All problems that we consider are NP-complete and even hard to approximate arbitrarily close by a polynomial algorithm. In technical terms, there exists no PTAS (polynomial-time approximation scheme) for them. This gives the motivation to consider these problems regarding parameterized complexity or to find approximation algorithms. In the following is a rough explanation of these terms:

  • Parameterized Complexity: Parameterized Complexity considers certain parameters concerning the given instance of a problem and can analyze how hard this problem is regarding these parameters. In particular, it allows a finer subdivision of the problem class NP.
  • Approximation Algorithm: An approximation algorithm for a given optimization problem is a polynomial time algorithm that provides for every instance a solution with a gap guaranty to the optimial objective value.

Connected Subgraph Partitioning, Packing and Covering

One of our most interesting results/investigations is to partition the vertex set of a vertex-weighted graph into balanced connected subgraphs. The weight of a subgraph is defined as the sum of its vertex weights. Classical objectives to achieve the desired partition are to minimize the weight of the maximal weighted subgraph (Min-Max) or to maximize the weight of the minimum weighted subgraph (Max-Min) in the corresponding subgraph partition, respectively. Since the eighties, the problem is investigated and until 2021 no constant approximation algorithm was known for general graphs, but there are several results for special graph classes. Recently, through the balanced crown decomposition we obtained a first constant approximation (precisely a 3-approximation) algorithm for both variants of the balanced partitioning problem. Naturally, it is a open question to beat these results.

Nowadays, data volumes are getting bigger and bigger which motivates us to design efficient approximation algorithms. We provide very efficient (\(c-1\))-approximation algorithms for \(c\)-claw free graphs [6]. A \(c\)-claw free graph is a graph which has no \(K_{1,c}\) (a star-graph with \(c\) leaves) as induced subgraph. If we ignore the running time, then we have only an improvement when we consider \(3\)-claw free graphs, known as claw-free graphs. There are lot of interesting graph classes that are claw-free. For instance line graphs which implies that we obtain a 2-approximation for the edge balanced partition case.

Another interesting research project regarding graph partitions is to partition \(k\)-connected graphs into \(k\) connected subgraphs for \(k \geq 2\). The connectivity of a \(k\)-connected graph can only drop if at least \(k\) vertices are removed. Gyori and Lovasz proved independently from each other that every \(k\)-connected graph can partition into connected subgraphs of size \(n_i \in  \mathbb{N}\) such that \(n_1 + \dots + n_k = n \), where \(n\) is the number of vertices in the  \(k\)-connected graph. It is even possible that \(k\) terminal vertices will determine before, such that each of them are in different subgraphs. The existence of such subgraph partitions in \(k\)-connected graphs has been proven, but polynomial algorithms exist only for \(k \leq 4 \) [7]. The challenge here is to find a suitable algorithm that provides desired subgraph partitions. Towards solving this problem we provide \(k\)-subgraph partitions that either each subgraph has size at least \(n_i/3\), or at most \(n_i \cdot 3\) [6]. W.r.t. to the ratio \( r = \max_i n_i /  \min_i n_i\) we even realize a both bounded partition, such that each subgraph has size between \(n_i/3\) and \(n_i \cdot   \max \{3,r\}\) [6]. Next steps could be finding connected \(k\)-subgraph partitions, such that each subgraph is both bounded by a constant times the demanded sizes, or to find approximate solutions w.r.t. to certain \(k\) terminal vertices. Moreover, exact polynomial time algorithms for \(k > 4\) would also be nice results.

If we wish to pack the vertex set into \(k\) connected subgraphs, then we damand that the subgraphs are only vertex disjoint. That is, we do not need to partition the whole vertex set. Given here is a network graph and a positive integer \(W\). The challenge is to find a maximal number of connected subgraphs each of size at least \(W\). It turns out that the balanced crown decomposition is also usefule for this problem, where we provide the first constant approximation, and improve the \(\mathcal{O}(kW^3)\) vertex size kernel to \(\mathcal{O}(kW)\) ( precisely a \(3kW\) vertex size kernel) [6], where \(k\) is the solution size. Improving the factors of the approximation as well as kernelization guarantee could be furher research directions.

As the name suggests in the covering case we wish to cover the vertex sets by connected \(k\)-subgraphs. Hence, overlappings of vertices are now allowed. Due to this relaxation there is reason to think that a better approximation guarantee than 3 is realizable through the techniques finding a 3-approximation for the Min-Max \(k\)-partition.

Multicommodity Flows and Multicuts

Multicommodity flows and multicuts are one of the most popular topics in combinatorial optimization since it has an impact to decode structural properties in graphs and supports finding solutions in related problems. Our investigations are focused on the relationship between the integral gap guarantee between multiflows and multicuts w.r.t. the treewidth of the given problem instance. Note that because of the duality of these problems a result would immediately provide approximation results for each problem, i.e. for the multiflow and multicut problem. The following picture illustrates that the gap guarantee is in order of at least \(\mathcal{O}(r)\). 

If we send a unit of flow through a source-sink pair \((s_j,t_j)\), then any other flow path is blocked. Hence, the integral multiflow-multicut gap is \(1/k\). On the other hand the wall graph from above has a \(k \times k\) grid as minor and therefore a treewidth of \(\mathcal{O}(k)\). This shows that the integral multiflow-multicut gap of \(\mathcal{O}(r)\) is tight, where \(r\) denotes the treewidth. Currently you are able to guarantee a \(\mathcal{O}(r^4)\) multiflow-multicut gap by combining two results which uses linear programming methods. Our goal is to find a fully combinatorial algorithm that in the best case beats the best known bound of \(\mathcal{O}(r^4)\).

Teaching

  • Teaching assistant for the Algorithmic Problem Solving (B.Sc) lecture (winter term 2019/2020)
  • Teaching assistant for the Wahrscheinlichkeitstheorie (B.Sc) lecture (summer term 2020)
  • Teaching assistant for the Algorithmic Problem Solving (B.Sc) lecture (winter term 2020/2021)
  • Teaching assistant for the Algorithmic Problem Solving (B.Sc) lecture (winter term 2020/2021)
  • Teaching assistant for the Uncovering Chains of Infection/Inferring Infection Chains (M.Sc) seminar (winter term 2020/2021
  • Teaching assistant for the Wahrscheinlichkeitstheorie (B.Sc) lecture (summer term 2021)

Publications

  • Casel, Katrin; Friedrich, Tobias; Issac, Davis; Niklanovits, Aikaterini; Zeif, Ziena; Balanced Crown Decomposition for Connectivity Constraints; European Symposium on Algorithms (ESA) 2021: 26:1–26:15
  • Borndörfer, Ralf; Casel, Katrin; Issac, Davis; Niklanovits, Aikaterini; Schwartz, Stephan; Zeif, Ziena Connected k-Partition of k-Connected Graphs and c-Claw-Free Graphs Approximation Algorithms for Combinatorial Optimization Problems (APPROX) 2021

  •  

    Borndörfer, Ralf; Arslan, Oytun; Elijazyfer, Ziena; Güler, Hakan; Renken, Malte; Şahin, Güvenç; Schlechte, ThomasLine Planning on Path Networks with Application to the Istanbul Metrobüs German Operations Research Society (GOR) 2016: 235–241

References

[1] Jessica Enright and Kitty Meeks. “Deleting edges to restrict the size of an epi- demic: a new application for treewidth”. In: Algorithmica 80.6 (2018), pp. 1857-1889.

[2] Aydın Buluç, Henning Meyerhenke, Ilya Safro, Peter Sanders, and Christian Schulz. “Recent advances in graph partitioning”. In: Algorithm Engineering. Springer, 2016, pp. 117-158.

[3] Mario Lucertini, Yehoshua Perl, and Bruno Simeone. “Most uniform path partitioning and its use in image processing”. In: Discrete Applied Mathematics 42.2-3 (1993), pp. 227-256.

[4] Rolf H Möhring, Heiko Schilling, Birk Schütz, Dorothea Wagner, and Thomas Willhalm. “Partitioning graphs to speedup Dijkstra’s algorithm”. In: Journal of Experimental Algorithmics (JEA) 11 (2007), pp. 2-8.

[5] Xing Zhou, Huaimin Wang, Bo Ding, Tianjiang Hu, and Suning Shang. “Balanced connected task allocations for multi-robot systems: An exact flow-based integer program and an approximate tree-based genetic algorithm”. In: Expert Systems with Applications 116 (2019), pp. 10-20.

[6] Borndörfer, Ralf; Casel, Katrin; Issac, Davis; Niklanovits, Aikaterini; Schwartz, Stephan; Zeif, Ziena Connected k-Partition of k-Connected Graphs and c-Claw-Free Graphs Approximation Algorithms for Combinatorial Optimization Problems (APPROX) 2021

[7] Hoyer, A. (2019). On the Independent Spanning Tree Conjectures and Related Problems (Doctoral dissertation, Georgia Institute of Technology).

[8] Marek Cygan, Fedor V Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Micha l Pilipczuk, and Saket Saurabh. Parameterized algorithms. Vol. 4. 8. Springer, 2015.

[9] Fomin, F. V., Lokshtanov, D., Saurabh, S., & Zehavi, M. (2019). Kernelization: theory of parameterized preprocessing. Cambridge University Press.

[10] Mithilesh Kumar and Daniel Lokshtanov. “A 2kp Kernel for "Component Order
Connectivity”. In: arXiv preprint arXiv:1610.04711 (2016).

[11] Mingyu Xiao. “Linear kernels for separating a graph into components of bounded
size”. In: Journal of Computer and System Sciences 88 (2017), pp. 260-270.

[12] https://brilliant.org/wiki/max-flow-min-cut-algorithm/

[13] Casel, Katrin; Friedrich, Tobias; Issac, Davis; Niklanovits, Aikaterini; Zeif, Ziena; Balanced Crown Decomposition for Connectivity Constraints; European Symposium on Algorithms (ESA) 2021: 26:1–26:15