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

Graph partitioning and tree-cut width

Aikaterini Niklanovits

Chair of Algorithm Engineering
Hasso Plattner Institute

Office: A-1.9
Tel.: +49 331 5509-3996
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.

In some partitioning problems, the condition of each component being connected does not exist, it is however proven to be optimal like the case of dense partition.

Dense Graph partitioning

The partitioning problem that I am currently working on is the dense graph partitioning, which is defined as follows: Given a graph \(G=(V,E)\) our goal is to partition \(V\) into components, \(P_1,\ldots, P_k\) such that the value \(\sum_{i=1}^k\frac{|E(P_i)|}{|V(P_i)|}\) is maximized. Note that unlike the variant of partitioning problems we described above,here \(k\) is not part of the input. Furthermore this notion can be also found in the image segmetation literature under the name ration association criterion [4],[5]. Darlay, Brauer and Moncel proved [1] that this problem is NP-complete on general graphs, when restricting it however on trees it can be solved in polynomial time. My current work consists of studying this problem on graphs with bounded tree-cut width, which is mentioned below.

 

Tree-cut width

Intuitively a tree-cut decomposition is a partition of the vertices of a graph into sets of bounded size in a way that each of its parts is connected with the rest of the graph by a bounded number of edges. Moreover the number of parts that are connected to the rest of the graph through more than 2 edges is also bounded. The width of a tree-cut decomposition is basically the number that bounds all these notions. The notion of tree-cut width was firstly introduced by Wollan [6] as follows:

Definition: A tree-cut decomposition of a graph \(G\) is a pair \(T,\mathcal X\) such that \(T\) is a tree and \(\mathcal X=\{X_t\subset V(G):t\in V(T)\}\) is a near partition of  \(V(G)\) indexed by the vertices of \(T\). For each edge \(e=uv\) in \(T\), \(T-uv\) has exactly two components \(T_u\) and \(T_v\) containing \(u\) and \(v\) respectively. The adhesion of the decomposition is \(\max_{uv\in E(T)}|\delta (\cup_{t\in V(T_v)}X_t|\), when \(T\) has at least one edge, and \(0\) otherwise and is denoted by \(\alpha\). The sets \(\{X_t:t\in V(T)\}\) are called bags of the decomposition. Let also \(H_t\) be the torso of \(T,\mathcal X\) at \(t\) and let \(\bar H_t\) be the 3-center of \((H_t,X_t)\). The width of the decomposition is \(\max[\{\alpha\}\cup\{|V(\bar H_t)|:t\in V(T)\}]\) and is denoted by \(tcw(G)\).

We do provide this, being the original definition of tree-cut width, for completness, but as you can see this definition seems quite complicated and hard to use. Since then, a simpler definition has been provided by Giannopoulou, Pilipczuk, Raymond, Thilikos and Wroncha [11].

This graph parameter has been proven useful to establishing FPT algorithms, that is of running time polynomial to the size of the input and exponential to a certain parameter, for a variety of hard combinatorial problems such as Capacitated Vertex Cover which is known to be hard when parametrized by treewidth. It has also strengthened some known \(W[1]\)-hardness results with respect to treewidth such as List Coloring. For more details  on these applications see [7].

 

 

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. Julien Darlay, Ndia Brauer, Julien Moncel. “Dense and sparse graph partition”. In: Discrete Applied Mathematics 2012
  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. Inderjit S. Dhillon, Yuqiang Guan, Brian Kulis. “Weighted Graph Cuts without Eigenvectors: A Multilevel Approach”. In: IEEE transactions on pattern analysis and machine intelligence 2007
  5. Jianbo Shi, Jitendra Malik. “Normalized cuts and Image Segmentation”. In: IEEE transactions on pattern analysis and machine intelligence 2000
  6. Paul Wollan. “The structure of graphs not admitting a fixed immersion”. In: Journal of Combinatorial Theory, Series B 2015
  7. Robert Ganian, Eun Jung Kim, Stefan Szeider. “Algorithmic applications of tree-cut width”. In: MFCS 2015
  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. Archontia C Giannopoulou, Michal Pilipczuk, Jean-Florent Raymond, Dimitrios M Thilikos, Marcin Wroncha. “Linear kernels for edge deletion problems to immersion-closed graph classes”. In: SIAM Journal on Discrete Mathematics, Volume 35.