Approximation and Parameterized Algorithms for Graph Connectivity Problems

The above problem domains become combinatorial optimization problems when we add an objective function that we want to minimize or maximize. In the following, we give an overview of the problems 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.

The problems considered have many practical and modular applications. For example, partitioning a graph into bounded components by removing nodes or edges has proven useful for developing divide and conquer and parallel algorithms for various graph problems. Other practical applications of this problem are finding guard points in traffic networks for toll control or, in the case of an epidemic, limiting the number of infections by exploiting 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 the partitioning of the set of vertices of a vertex-weighted graph into balanced connected subgraphs. The weight of a subgraph is defined as the sum of the weights of its vertices. Classical objectives to achieve the desired partition are to minimize the weight of the maximum weighted subgraph (min-max) or to maximize the weight of the minimum weighted subgraph (max-min) in the corresponding subgraph partition. The problem has been studied since the 1980s, and an open question for balanced partitioning is to find a constant approximation algorithm for general graphs, where, on the other hand, several approximation results have been obtained for special classes of graphs. Recently, we provided a first constant approximation (more precisely, a 3-approximation) for both variants of the balanced partitioning problem for general graphs by using the structural properties of the balanced crown decomposition [13]. Of course, it is an open question whether these results can be surpassed.

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 algorithms that provide the desired subgraph partition. Towards solving this problem we design algorithms which outputs \(k\)-subgraph partitions, where 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]. We extended our research by also considering special graph classes for this problem and provided efficient algorithms for chordal and almost chordal graphs [18]. Next steps could be finding exact algorithms for other graph classes, or to find connected \(k\)-subgraph partitions, such that each subgraph is both bounded by a constant times the demanded sizes. 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.

Our studies basically focus on the relationship between these gap guarantees regarding multiflows and multicuts with respect to the treewidth of the given graph. For instance, the following picture illustrates that the integral multiflow-multicut gap is in order of at least \(\Omega(r)\), where \(r\) is the treewidth of the input graph. 

If we send a unit of flow through a source-sink pair \((s_j,t_j)\), then any other flow path is blocked. On the other hand, we need at least \(k\) edges to separate each commidity. 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 \(\Omega(k)\). This shows that the integral multiflow-multicut gap of \(\Omega(r)\) is tight, where \(r\) denotes the treewidth. So far, we have proved 2 different approximate max-multiflow min-multicut theorems for graphs with bounded treewidth. The first result is for graphs with treewidth 2, which are also characterized by serially parallel graphs. Here we provide a multiflow multicut gap of 80 [16]. The other result is more general and gives a multiflow multicut gap of \(\mathcal{O}(\ln(r))\) for general graphs with bounded treewidth r [17]. It is known that the multiflow-multicut gap on an expander graph with \(r\)-vertex (constant degree) can be \(\Omega(\ln(r))\), and hence our result is tight up to constant factors.

• 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)
• Teaching assistant for the Mathe 2 (B.Sc) lecture (summer term 2022)

• Friedrich, Tobias and Issac, Davis and Kumar, Nikhil and Mallek, Nadym and Zeif, Ziena; Approximation Algorithms for Combinatorial Optimization Problems (APPROX); 2022
• Baguley, Samuel and Friedrich, Tobias and Timo, Kötzing and Li, Xiaoyue and Pappik, Marcus and Zeif, Ziena; Analysis of a Gray-Box Operator for Vertex Cover; Genetic and Evolutionary Computation Conference (GECCO); 2022.
• Casel, Katrin; Friedrich, Tobias; Issac, Davis; Niklanovits, Aikaterini; Zeif, Ziena; Balanced Crown Decomposition for Connectivity Constraints; European Symposium on Algorithms (ESA); 2021.

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

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

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

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

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

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

[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.; On the Independent Spanning Tree Conjectures and Related Problems (Doctoral dissertation, Georgia Institute of Technology); 2019.

[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.; Kernelization: theory of parameterized preprocessing. Cambridge University Press; 2019.

[10] Mithilesh Kumar and Daniel Lokshtanov; A 2lk Kernel for l-Component Order Connectivity}; International Symposium on Parameterized and Exact Computation (IPEC); 2016.

[11] Mingyu Xiao; Linear kernels for separating a graph into components of bounded size; In: Journal of Computer and System Sciences 88; 2017.

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

[14] Euiwoong Lee; Partitioning a Graph into Small Pieces with Applications to Path Transversal; Symposium on Discrete Algorithms (Soda); 2017.

[15] Baguley, Samuel and Friedrich, Tobias and Timo, Kötzing and Li, Xiaoyue and Pappik, Marcus and Zeif, Ziena; Analysis of a Gray-Box Operator for Vertex Cover; Genetic and Evolutionary Computation Conference (GECCO); 2022.

[16] Friedrich, Tobias and Issac, Davis and Kumar, Nikhil and Mallek, Nadym and Zeif, Ziena; Approximation Algorithms for Combinatorial Optimization Problems (APPROX); 2022

[17] Friedrich, Tobias and Issac, Davis and Kumar, Nikhil and Mallek, Nadym and Zeif, Ziena; Approximate Max-Flow Min-Multicut Theorem for Graphs of Bounded Treewidth; arXiv preprint arXiv:2211.06267; 2022

[18] Casel, Katrin and Friedrich, Tobias and Issac, Davis and Niklanovits, Aikaterini and Zeif, Ziena; Efficient Constructions for the Gyori-Lovasz Theorem on Almost Chordal Graphs; arXiv preprint arXiv:2207.09262; 2022