Approximation and Parameterized Algorithms for Graph Connectivity Problems

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.

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].

In the general case of weighted graphs, partitioning a graph into connected subgraphs of balanced weights has applications in several problems such as parallel processing, road network decomposition, image processing, cluster analysis, operating systems and robotics [2, 3, 4, 5].

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.

To find bounded separators, i.e. to remove vertices such that the arising components have weight of at most some given parameter, is more popular for the unweighted (unit-weight) case. There are different names to denote this problem such \(\alpha\)-separator problem, \(W\)-size separator problem, or component order connectivity problem. For the following technical terms, we refer to the famous parametrized complexity book by Cygan et al. [8]. In particular, we are interested in kernelization algorithms. Roughly, a kernelization of a problem instance is to find reduction rules, such that in the end, an estimation of the instance size is possible through the considered parameters without influencing the optimization problem. For more background in kernelization algorithms, we recommend the kernelization book from Fomin et al. [9]. Let \(k\) be the solution size and \(W\) the demanded weight-bound for the arising components after removing the \(k\) separator vertices from the graph. We consider \(k\) and \(W\) as the instance parameters and our goal is it to find a kernelization algorithm for it. To find \(k\) vertex separators, such that the arising connected components weigh less than \(W\) is W[1]-hard or Para-NP-hard if we consider \(k\) and \(W\) individually as parameters, respectively. The problem becomes fixed parameter tractable if \(k\) and \(W\) are considered as parameters.

Towards improving the best known kernelization result for the bounded vertex-separator problem we develope a graph structural theorem, called balanced crown decomposition [13], which enables improvements as well as solves open questions for a variety of problems including the bounded vertex separator problem.

• Decomposition of the vertices into three sets H (head), C (crown) and R (royal body), such that H separates C from R.
• The size of the connected components Q induced by C are smaller than λ and the vertices in R are partitionable into size bounded connected components R w.r.t. \(\lambda\).
• There is a function f that maps elements of Q to vertices H, such that the inverse image of each element h \(\in\) H forms a lower bounded connected vertex set w.r.t. \(\lambda\), which includes the vertex h itself.

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.

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 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)

• 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

[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