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

Graph partitioning in restricted graph classes

Aikaterini Niklanovits

Chair of Algorithm Engineering
Hasso Plattner Institute

Office: K-2.19
Email: Aikaterini.Niklanovits(at)hpi.de

Supervisor: Prof. Dr. Tobias Friedrich
 

Graph Partitioning

A graph \(G\) is a mathematical structure used to define pairwise relations between objects. These objects are denoted by a set of nodes or vertices \(V\) and a set of edges \(E\), each consisting of two nodes who have the relation expressed by the edge in \(E\). Each node might represent for example a person, while a connection of two nodes denotes that these two people meet at least once per week. Separating such a structure into two or more such substructures have been proven useful to effectively derive infromation regarding the described relations. This procedure is known as graph partition and is formally defined as follows:

Definition: Given a graph \(G=(V,E)\) we say that \(\mathcal P=(P_1,\ldots,P_k)\) is a partition of \(G\) to \(k\) parts if \(\cup_{i=1}^lP_i=V\) and \(P_i\cap P_j=\emptyset\) \(\forall i,j\in[k]\) such that \(i\neq j\).

Partitioning the vertices of a graph under certain contstraints such as the size, the connectivity or the density of each component has found various applications. For example, partitioning a graph into \(k\) components of roughly equal size such that each induced graph is connected has found applications in areas such as parallel processing, road network decomposition, image processing, districting problems and can also be used to design efficient divide and conquer algorithms [8],[9],[10]. In the context of parallel computing for example, such a partition can lead to a decomposition of the given tasks and each component of a partition can be mapped to a processor of a multiprocessor.

Balanced Graph Partitioning

As mentioned above a usual restriction, apart from the components being connected, required in some applications is demanding these components to have approximately the same size. The two most commonly used objectives of this problem are minimizing the size of the largest component and maximizing the size of the smallest one, while when we work on weighted graphs the size of one component is the sum of the weight of its vertices. In order to tackle these problems we defined the Balanced Crown Decomposition structure (on weighted graphs), through which a \(3\)-approximation algorithm for each of these objectives was obtained [2]. Moreover, since this problem is known to be NP-hard on general graphs, another approach one could follow is restricting it to special graph classes. One such a class is \(K_{1,c}\)-free graphs for which we were able to derive a \((c-1)\)-approximation algorithm [3]. This algorithm can also be used to obtain a 2-approximation for the respective edge partition problem since line graphs are an already known \(K_{1,3}\)-free graph class.

Another view of the balanced partitioning objective is to define the size of each connecetd subgraph. This, together with a condition regarding the connectivity of a graph is captured through the Gyori-Lovasz theorem.

Gyori-Lovasz Theorem

In theory as well as in many applications, one is interested in a connected partition that has a given number of subgraphs of chosen respective sizes. With the simple example of a star-graph, it is observed that not every graph admits a connected partition for any choice of subgraph sizes. More generally speaking, if there exists a small set of \(t\) vertices whose removal disconnects a graph (separator), then any connected partition into \(k>t\) subgraphs has limited choice of subgraph sizes. Graphs that do not contain  such a separator of size less than \(k\) are called \(k\)-connected.

Gyori [1] and Lovasz [4] independently showed that \(k\)-connectivity is not just necessary but also sufficient to enable a connected partitioning into \(k\) subgraphs of required sizes, formally stated by the following result:

Theorem: Let \(k\geq 2\) be an integer, \(G=(V,E)\) a \(k\)-connected graph, \(t_1,\ldots, t_k\in V\) distinct vertices and \(n_1,\ldots,n_k\in \mathbb N\) such that \(\sum_{i=1}^kn_i= |V|\). Then \(G\) has disjoint connected subgraphs \(G_1, \ldots G_k\) such that \(|V(G_i)|=n_i\)  and \(t_i\in V(G_i)\) for all \(i\in [k]\).

The caveat of this famous result is that the constructive proof of it yields an exponential time algorithm. Despite this result being known since 1976, to this day we only know polynomial constructions for restricted values of \(k\). Specifically, in 1990 Suzuki et al. [7] provided such an algorithm for \(k=2\) and also for \(k=3\) [11]. Moreover, in 1994 Wada et al. [6] also provided an extended result for \(k=3\).
For the case of \(k=4\) in 2016 Hoyer and Thomas [5] provided a polynomial time algorithm for the case of \(k=4\). And so far, this is where the list ends, thus for \(k\geq 5\) it remains open whether there even exists a polynomial time construction.

Towards developing efficient algorithms for the general \(k\) I believe that the approach of restricting the graphs into certain classes defined through forbidden induced subgraphs instead of restricting the values of \(k\) is promising. In particular we have obtain such results for chordal graphs, that is graphs that do not contain any cycle of length more than 3 as an induced subgraph. We have also extended this algorithm for the class of graphs where induced cycles of length 4 are also allowed with the restriction that each pair of them share at most one vertex in common.

Teaching

During my Ph.D. studies, I wasTeaching Assistant for the following courses:

Publications

[ 2021 ]

2021 [ nach oben ]

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

References

  1. Ervin Gyori. “On division of graphs to connecetd subgraphs, combinatorics”. In: Colloq. Math. Soc. Janos Bolyai 1976, 1976
  2. Katrin Casel, Tobias Friedrich, Davis Issac, Aikaterini Niklanovits, Ziena Zeif. “Balanced Crown Decomposition for Connectivity Constraints”. In: Proc. of ESA 2021
  3. Ralf Borndörfer, Katrin Casel, Davis Issac, Aikaterini Niklanovits, Stephan Schwartz, Ziena Zeif. “Connected k-partition of k-connected graphs and c-claw-free graphs”. In: Proc. of APPROX 2021
  4. Laszlo Lovasz. “A homology theory for spanning trees of a graph”. In: Acta Mathematica Hungarica, 30, 1977
  5. Alexander Hoyer. “On the independent spanning tree conjecture”. PhD thesis, Georgia Institute of Technology, 2019
  6. H Suzuki, N Takahashi, T Nishizeki, H Miyano, S Ueno. “An algorithm for tripartitioning 3-connected graphs”. In: Journal of Information Processing Society of Japan, 1990
  7. Hitoshi Suzuki, Naomi Takahashi, Takao Nishizeki. “A linear algorithm for bipartition of biconnected graphs”. In: Inf. Process. Lett., 1990
  8. Mario Lucertini, Yehoshua Perl, Bruno Simeone. “Most uniform path partitioning and its use in image processing”. In: Discrete Applied Mathematics 1993
  9. Rolf H Möhring, Heiko Schilling, Birk Schütz, Dorothea Wagner, Thomas Willhalm. “Partitioning to speedup dijkstra's algorithm”. In: JEA 2007
  10. Xing Zhou, Huaimin Wang, Bo Ding, Tianjiang Hu, 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 2019
  11. Koichi Wada, Kimio Kawaguchi. “Efficient algorithms for tripartitioning triconnected graphs and 3-edge connnected graphs”. In: Graph Theoretic Concepts in Computer science, 19th International Workshop, WG 1993