Graph partitioning in restricted graph classes

2024 [ nach oben ]

Cohen, Sarel; Kamma, Lior; Niklanovits, Aikaterini A New Approach for Approximating Directed Rooted Networks50th International Workshop on Graph-Theoretic Concepts in Computer Science 2024
[ Abstract ] [ BibTeX ] [ Download ]
 
We consider the k-outconnected directed Steiner tree problem (k-DST). Given a directed edge-weighted graph G=(V,E,w), where \(V = \r\} \cup S \cup T\), and an integer k, the goal is to find a minimum cost subgraph of \($G$\) in which there are k edge-disjoint rt-paths for every terminal \(t \in T\). The problem is known to be NP-Hard. Furthermore,the question on whether a polynomial time, subpolynomial approximation algorithm exists for k-DST was answered negatively by Grandoni etal (2018), by proving an approximation hardness of \(\Omega(|T|/\log |T|)\) under NP\(\neq\)ZPP. Inspired by modern day applications, we focus on developing efficient algorithms for k-DST in graphs where terminals have out-degree 0, and furthermore constitute the vast majority in the graph. We provide the first approximation algorithm for k-DST on such graphs, in which the approximation ratio depends (primarily) on the size of S. We present a randomized algorithm that finds a solution of weight at most \(O(k|S| \log|T|)\) times the optimal weight, and with high probability runs in polynomial time.
@inproceedings{cohen2024approach, abstract = {We consider the k-outconnected directed Steiner tree problem (k-DST). Given a directed edge-weighted graph G=(V,E,w), where \(V = \{r\} \cup S \cup T\), and an integer k, the goal is to find a minimum cost subgraph of $G$ in which there are k edge-disjoint rt-paths for every terminal \(t \in T\). The problem is known to be NP-Hard. Furthermore,the question on whether a polynomial time, subpolynomial approximation algorithm exists for k-DST was answered negatively by Grandoni \etal (2018), by proving an approximation hardness of \(\Omega(|T|/\log |T|)\) under NP\(\neq\)ZPP. Inspired by modern day applications, we focus on developing efficient algorithms for k-DST in graphs where terminals have out-degree 0, and furthermore constitute the vast majority in the graph. We provide the first approximation algorithm for k-DST on such graphs, in which the approximation ratio depends (primarily) on the size of S. We present a randomized algorithm that finds a solution of weight at most \(O(k|S| \log|T|)\) times the optimal weight, and with high probability runs in polynomial time.}, author = {Cohen, Sarel and Kamma, Lior and Niklanovits, Aikaterini}, editor = {"Kráľ, Daniel" and "Milanič, Martin"}, journal = {50th International Workshop on Graph-Theoretic Concepts in Computer Science}, keywords = {sarelcohen sys:relevantfor:ae aikaterininiklanovits year2024 DirectedSteinerTree wg}, title = {A New Approach for Approximating Directed Rooted Networks}, year = 2024 }

Horev, Yinon; Shay, Shiraz; Cohen, Sarel; Friedrich, Tobias; Issac, Davis; Kamma, Lior; Niklanovits, Aikaterini; Simonov, Kirill A Contraction Tree SAT Encoding for Computing Twin-WidthAdvances in Knowledge Discovery and Data Mining 2024
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
Twin-width is a structural width parameter and matrix invariant introduced by Bonnet et al. [FOCS 2020], that has been gaining attention due to its various fields of applications. In this paper, inspired by the SAT approach of Schidler and Szeider [ALENEX 2022], we provide a new SAT encoding for computing twin-width. The encoding aims to encode the contraction sequence as a binary tree. The asymptotic size of the formula under our encoding is smaller than in the state-of-the-art relative encoding of Schidler and Szeider. We also conduct an experimental study, comparing the performance of the new encoding and the relative encoding.
@inproceedings{horev2024contraction, abstract = {Twin-width is a structural width parameter and matrix invariant introduced by Bonnet et al. [FOCS 2020], that has been gaining attention due to its various fields of applications. In this paper, inspired by the SAT approach of Schidler and Szeider [ALENEX 2022], we provide a new SAT encoding for computing twin-width. The encoding aims to encode the contraction sequence as a binary tree. The asymptotic size of the formula under our encoding is smaller than in the state-of-the-art relative encoding of Schidler and Szeider. We also conduct an experimental study, comparing the performance of the new encoding and the relative encoding.}, author = {Horev, Yinon and Shay, Shiraz and Cohen, Sarel and Friedrich, Tobias and Issac, Davis and Kamma, Lior and Niklanovits, Aikaterini and Simonov, Kirill}, booktitle = {Advances in Knowledge Discovery and Data Mining}, keywords = {sarelcohen yinonhorev davisissac kirillsimonov aikaterininiklanovits tobiasfriedrich year2024 shirazshay liorkamma pakdd}, month = {April 2024}, publisher = {Springer, Singapore}, title = {A Contraction Tree SAT Encoding for Computing Twin-Width}, volume = 14646, year = 2024 }

Casel, Katrin; Friedrich, Tobias; Niklanovits, Aikaterini; Simonov, Kirill; Zeif, Ziena Combining Crown Structures for Vulnerability MeasuresInternational Symposium on Parameterized and Exact Computation (IPEC) 2024
Best Paper Award
[ Abstract ] [ BibTeX ]
 
Over the past decades, various metrics have emerged in graph theory to grasp the complex nature of network vulnerability. In this paper, we study two specific measures: (weighted) vertex integrity (wVI) and (weighted) component order connectivity (wCOC). These measures not only evaluate the number of vertices required to decompose a graph into fragments, but also take into account the size of the largest remaining component. The main focus of our paper is on kernelization algorithms tailored to both measures. We capitalize on the structural attributes inherent in different crown decompositions, strategically combining them to introduce novel kernelization algorithms that advance the current state of the field. In particular, we extend the scope of the balanced crown decomposition provided by Casel et al.~\cite{DBLP:conf/esa/Casel0INZ21 and expand the applicability of crown decomposition techniques. In summary, we improve the vertex kernel of VI from \(p^3\) to \(p^2\), and of wVI from \(p^3\) to \(3(p^2 + p^1.5 p_{\ell})\), where \(p_{\ell} < p\) represents the weight of the heaviest component after removing a solution. For wCOC we improve the vertex kernel from \(\mathcal{O(k^2W + kW^2)\) to \(3\mu(k + \sqrt{\mu}W)\), where \(mu = \max(k,W)\). We also give a combinatorial algorithm that provides a \(2kW\) vertex kernel in fixed-parameter tractable time when parameterized by \(r\), where \(r \leq k\) is the size of a maximum \((W+1)\)-packing. We further show that the algorithm computing the \(2kW\) vertex kernel for COC can be transformed into a polynomial algorithm for two special cases, namely when \(W=1\), which corresponds to the well-known vertex cover problem, and for claw-free graphs. In particular, we show a new way to obtain a \($2k$\) vertex kernel (or to obtain a 2-approximation) for the vertex cover problem by only using crown structures.
@inproceedings{casel2024combining, abstract = {Over the past decades, various metrics have emerged in graph theory to grasp the complex nature of network vulnerability. In this paper, we study two specific measures: (weighted) vertex integrity (wVI) and (weighted) component order connectivity (wCOC). These measures not only evaluate the number of vertices required to decompose a graph into fragments, but also take into account the size of the largest remaining component. The main focus of our paper is on kernelization algorithms tailored to both measures. We capitalize on the structural attributes inherent in different crown decompositions, strategically combining them to introduce novel kernelization algorithms that advance the current state of the field. In particular, we extend the scope of the balanced crown decomposition provided by Casel et al.&nbsp;\cite{DBLP:conf/esa/Casel0INZ21} and expand the applicability of crown decomposition techniques. In summary, we improve the vertex kernel of VI from \(p^3\) to \(p^2\), and of wVI from \(p^3\) to \(3(p^2 + {p}^{1.5} p_{\ell})\), where \(p_{\ell} < p\) represents the weight of the heaviest component after removing a solution. For wCOC we improve the vertex kernel from \(\mathcal{O}(k^2W + kW^2)\) to \(3\mu(k + \sqrt{\mu}W)\), where \(\mu = \max(k,W)\). We also give a combinatorial algorithm that provides a \(2kW\) vertex kernel in fixed-parameter tractable time when parameterized by \(r\), where \(r \leq k\) is the size of a maximum \((W+1)\)-packing. We further show that the algorithm computing the \(2kW\) vertex kernel for COC can be transformed into a polynomial algorithm for two special cases, namely when \(W=1\), which corresponds to the well-known vertex cover problem, and for claw-free graphs. In particular, we show a new way to obtain a $2k$ vertex kernel (or to obtain a 2-approximation) for the vertex cover problem by only using crown structures.}, author = {Casel, Katrin and Friedrich, Tobias and Niklanovits, Aikaterini and Simonov, Kirill and Zeif, Ziena}, booktitle = {International Symposium on Parameterized and Exact Computation (IPEC)}, keywords = {zienazeif ipec katrincasel kirillsimonov aikaterininiklanovits tobiasfriedrich year2024}, note = {Best Paper Award}, title = {Combining Crown Structures for Vulnerability Measures}, year = 2024 }

2023 [ nach oben ]

Casel, Katrin; Friedrich, Tobias; Issac, Davis; Niklanovits, Aikaterini; Zeif, Ziena Efficient Constructions for the Gyori-Lovasz Theorem on Almost Chordal GraphsWorkshop Graph-Theoretic Concepts in Computer Science (WG) 2023: 143–156
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
In the 1970s, GyHo}ri and Lovász showed that for a \(k\)-connected \(n\)-vertex graph, a given set of terminal vertices \(t_1, \dots, t_k\) and natural numbers \(n_1, \dots, n_k\) satisfying \(\sum_{i=1^k n_i = n\), a connected vertex partition \(S_1, \dots, S_k\) satisfying \(t_i \in S_i\) and \(|S_i| = n_i\) exists. However, polynomial algorithms to actually compute such partitions are known so far only for \(k \leq 4\). This motivates us to take a new approach and constrain this problem to particular graph classes instead of restricting the values of \(k\). More precisely, we consider \(k\)-connected chordal graphs and a broader class of graphs related to them. For the first class, we give an algorithm with \(\mathcal{O(n^2)\) running time that solves the problem exactly, and for the second, an algorithm with \(\mathcal{O(n^4)\) running time that deviates on at most one vertex from the required vertex partition sizes.
@inproceedings{casel2023efficient, abstract = {In the 1970s, Gy\H{o}ri and Lov{á}sz showed that for a \(k\)-connected \(n\)-vertex graph, a given set of terminal vertices \(t_1, \dots, t_k\) and natural numbers \(n_1, \dots, n_k\) satisfying \(\sum_{i=1}^{k} n_i = n\), a connected vertex partition \(S_1, \dots, S_k\) satisfying \(t_i \in S_i\) and \(|S_i| = n_i\) exists. However, polynomial algorithms to actually compute such partitions are known so far only for \(k \leq 4\). This motivates us to take a new approach and constrain this problem to particular graph classes instead of restricting the values of \(k\). More precisely, we consider \(k\)-connected chordal graphs and a broader class of graphs related to them. For the first class, we give an algorithm with \(\mathcal{O}(n^2)\) running time that solves the problem exactly, and for the second, an algorithm with \(\mathcal{O}(n^4)\) running time that deviates on at most one vertex from the required vertex partition sizes.}, author = {Casel, Katrin and Friedrich, Tobias and Issac, Davis and Niklanovits, Aikaterini and Zeif, Ziena}, booktitle = {Workshop Graph-Theoretic Concepts in Computer Science (WG)}, keywords = {sys:relevantfor:ae zienazeif katrincasel davisissac aikaterininiklanovits tobiasfriedrich year2023 wg}, pages = {143&ndash;156}, title = {Efficient Constructions for the Gyori-Lovasz Theorem on Almost Chordal Graphs}, year = 2023 }

2021 [ nach oben ]

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
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
A connected partition is a partition of the vertices of a graph into sets that induce connected subgraphs. Such partitions naturally occur in many application areas such as road networks, and image processing. In these settings, it is often desirable to partition into a fixed number of parts of roughly of the same size or weight. The resulting computational problem is called Balanced Connected Partition (BCP). The two classical objectives for BCP are to maximize the weight of the smallest, or minimize the weight of the largest component. We study BCP on \(c\)-claw-free graphs, the class of graphs that do not have \(K_{1,c}\) as an induced subgraph, and present efficient \((c-1)\)-approximation algorithms for both objectives. In particular, for \(3\)-claw-free graphs, also simply known as claw-free graphs, we obtain a \(2\)-approximation. Due to the claw-freeness of line graphs, this also implies a \(2\)-approximation for the edge-partition version of BCP in general graphs. A harder connected partition problem arises from demanding a connected partition into k parts that have (possibly) heterogeneous target weights \(w_1, \dots, w_k\). In the 1970s Győri and Lovász showed that if \(G\) is \(k\)-connected and the target weights sum to the total size of \(G\), such a partition exists. However, to this day no polynomial algorithm to compute such partitions exists for \(k > 4\). Towards finding such a partition \(T_1, \dots, T_k\) in \(k\)-connected graphs for general \(k\), we show how to efficiently compute connected partitions that at least approximately meet the target weights, subject to the mild assumption that each \(w_i\) is greater than the weight of the heaviest vertex. In particular, we give a \(3\)-approximation for both the lower and the upper bounded version i.e. we guarantee that each \(T_i\) has weight at least \(\frac{w_i}{3}\) or that each \(T_i\) has weight most \(3 w_i\), respectively. Also, we present a both-side bounded version that produces a connected partition where each \(T_i\) has size at least \(\frac{w_i}{3}\) and at most \(\max(\{r, 3\}) w_i \), where \(r \geq 1\) is the ratio between the largest and smallest value in \(w_1, \dots, w_k\). In particular for the balanced version, i.e. \(w_1 = w_2 =, \dots , = w k\), this gives a partition with \(\frac{w_i3 leq w(T_i) \leq 3 w_i\).
@inproceedings{borndorfer2021connected, abstract = {A connected partition is a partition of the vertices of a graph into sets that induce connected subgraphs. Such partitions naturally occur in many application areas such as road networks, and image processing. In these settings, it is often desirable to partition into a fixed number of parts of roughly of the same size or weight. The resulting computational problem is called Balanced Connected Partition (BCP). The two classical objectives for BCP are to maximize the weight of the smallest, or minimize the weight of the largest component. We study BCP on \(c\)-claw-free graphs, the class of graphs that do not have \(K_{1,c}\) as an induced subgraph, and present efficient \((c-1)\)-approximation algorithms for both objectives. In particular, for \(3\)-claw-free graphs, also simply known as claw-free graphs, we obtain a \(2\)-approximation. Due to the claw-freeness of line graphs, this also implies a \(2\)-approximation for the edge-partition version of BCP in general graphs. A harder connected partition problem arises from demanding a connected partition into k parts that have (possibly) heterogeneous target weights \(w_1, \dots, w_k\). In the 1970s Győri and Lovász showed that if \(G\) is \(k\)-connected and the target weights sum to the total size of \(G\), such a partition exists. However, to this day no polynomial algorithm to compute such partitions exists for \(k > 4\). Towards finding such a partition \(T_1, \dots, T_k\) in \(k\)-connected graphs for general \(k\), we show how to efficiently compute connected partitions that at least approximately meet the target weights, subject to the mild assumption that each \(w_i\) is greater than the weight of the heaviest vertex. In particular, we give a \(3\)-approximation for both the lower and the upper bounded version i.e. we guarantee that each \(T_i\) has weight at least \(\frac{w_i}{3}\) or that each \(T_i\) has weight most \(3 w_i\), respectively. Also, we present a both-side bounded version that produces a connected partition where each \(T_i\) has size at least \(\frac{w_i}{3}\) and at most \(\max(\{r, 3\}) w_i \), where \(r \geq 1\) is the ratio between the largest and smallest value in \(w_1, \dots, w_k\). In particular for the balanced version, i.e. \(w_1 = w_2 =, \dots , = w k\), this gives a partition with \(\frac{w_i}{3} \leq w(T_i) \leq 3 w_i\).}, author = {Borndörfer, Ralf and Casel, Katrin and Issac, Davis and Niklanovits, Aikaterini and Schwartz, Stephan and Zeif, Ziena}, booktitle = {Approximation Algorithms for Combinatorial Optimization Problems (APPROX)}, keywords = {sys:relevantfor:ae zienazeif katrincasel davisissac aikaterininiklanovits approx year2021 ralfborndörfer stephanschwartz}, pages = {27:1-27:14}, title = {Connected k-Partition of k-Connected Graphs and c-Claw-Free Graphs}, year = 2021 }

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
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
We introduce the balanced crown decomposition that captures the structure imposed on graphs by their connected induced subgraphs of a given size. Such subgraphs are a popular modeling tool in various application areas, where the non-local nature of the connectivity condition usually results in very challenging algorithmic tasks. The balanced crown decomposition is a combination of a crown decomposition and a balanced partition which makes it applicable to graph editing as well as graph packing and partitioning problems. We illustrate this by deriving improved approximation algorithms and kernelization for a variety of such problems. In particular, through this structure, we obtain the first constant-factor approximation for the Balanced Connected Partition (BCP) problem, where the task is to partition a vertex-weighted graph into k connected components of approximately equal weight. We derive a \(3\)-approximation for the two most commonly used objectives of maximizing the weight of the lightest component or minimizing the weight of the heaviest component.
@inproceedings{casel2021balanced, abstract = {We introduce the balanced crown decomposition that captures the structure imposed on graphs by their connected induced subgraphs of a given size. Such subgraphs are a popular modeling tool in various application areas, where the non-local nature of the connectivity condition usually results in very challenging algorithmic tasks. The balanced crown decomposition is a combination of a crown decomposition and a balanced partition which makes it applicable to graph editing as well as graph packing and partitioning problems. We illustrate this by deriving improved approximation algorithms and kernelization for a variety of such problems. In particular, through this structure, we obtain the first constant-factor approximation for the Balanced Connected Partition (BCP) problem, where the task is to partition a vertex-weighted graph into k connected components of approximately equal weight. We derive a \(3\)-approximation for the two most commonly used objectives of maximizing the weight of the lightest component or minimizing the weight of the heaviest component.}, author = {Casel, Katrin and Friedrich, Tobias and Issac, Davis and Niklanovits, Aikaterini and Zeif, Ziena}, booktitle = {European Symposium on Algorithms (ESA)}, keywords = {sys:relevantfor:ae zienazeif esa katrincasel davisissac aikaterininiklanovits tobiasfriedrich year2021}, pages = {26:1&ndash;26:15}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title = {Balanced Crown Decomposition for Connectivity Constraints}, volume = 204, year = 2021 }