Bounded Vertex-Separators and Connected Subgraph-Partitions

Finding bounded separators or cuts, as well as bounded vertex or edge partitions in graphs are classical problems in graph theory, that also have 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].

To find bounded separators or to partition a graph into balanced connected components are NP-complete problems and even hard to approximate arbitrarily close by a polynomial algorithm. In technical terms, the problems are strongly NP-complete and 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. Roughly, 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. An approximation algorithm for a given optimization problem is a polynomial algorithm that provides for every instance a solution with a gap guaranty.

Another research project 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 challenge here is to find a suitable algorithm that provides the desired subgraph partition.

One of our most interesting topics is to partition the vertices 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 this goal 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 interesting and until now no constant approximation algorithm is known for general graphs. The best-known approximation ratio for these objectives is a \(\Delta\)-approximation [6], where \(\Delta\) is the maximal degree of an arbitrary spanning tree in the graph. One of our goals is to achieve a constant approximation ratio for these objectives.

The Gyori-Lovasz Theorem states that each \(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]. Our goal is to develop polynomial algorithms for \(k > 4\) or developing algorithms even if \(k\) is part of the input.

To find bounded separators, i.e. to remove vertices, such that the arising components have weight most some given parameter, is more popular for the unweighted case. There are different names to denote this problem such \(\alpha\)-separator problem, \(p\)-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]. Moreover, we are interested in kernelization algorithms. Roughly, a kernelization of a problem instance means to find reduction rules, such that in the end, an estimation of the instance size is possible. For more background in kernelization algorithms, we recommend the kernelization book by Fomin et al. [9]. Let \(k\) be the solution size and \(p\) the weight-bound for the arising components after removing the \(k\) separator vertices from the graph. For the unweighted case, the weight of a subgraph corresponds to the number of vertices within itself. To find \(k\) vertex separators, such that the arising connected components weight most \(p\) is \(W[1]\)-hard if the solution size \(k\) is considered as a parameter and Para-NP-hard with parameter \(p\). The problem becomes fixed parameter tractable if \(k\) and \(p\) are considered as parameters. The best-known vertex kernel is a \(2kp\) vertex kernel [10] obtaining in time \(\mathcal{O}(n^p)\), where \(n\) is the number of vertices in the considered instance graph. Thus, not polynomial if \(p\) is part of the input. The best-known vertex kernel, even if \(p\) is part of the input, is a \(9kp\) vertex kernel. Our goal is to improve the \(9kp\) vertex kernel with \(p\) seen as input. Furthermore, we try to generalize the results to the vertex-weighted case. Finally, we try to find an approximation algorithm for this problem. The best known is a trivial \(p\)-approximation algorithm. 

[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] Ralf Borndörfer, Ziena Elijazyfer, and Stephan Schwartz. “Approximating balanced graph partitions”. In: (2019).

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