2024 [ nach oben ]

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 = {aikaterininiklanovits ipec katrincasel kirillsimonov tobiasfriedrich year2024 zienazeif}, note = {Best Paper Award}, title = {Combining Crown Structures for Vulnerability Measures}, year = 2024 }

2023 [ nach oben ]

Bläsius, Thomas; Friedrich, Tobias; Katzmann, Maximilian; Ruff, Janosch; Zeif, Ziena On the Giant Component of Geometric Inhomogeneous Random GraphsEuropean Symposium on Algorithms (ESA) 2023: 20:1–20:13
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
In this paper we study the threshold model of geometric inhomogeneous random graphs (GIRGs); a generative random graph model that is closely related to hyperbolic random graphs (HRGs). These models have been observed to capture complex real-world networks well with respect to the structural and algorithmic properties. Following comprehensive studies regarding their connectivity, i.e., which parts of the graphs are connected, we have a good understanding under which circumstances a giant component (containing a constant fraction of the graph) emerges. While previous results are rather technical and challenging to work with, the goal of this paper is to provide more accessible proofs. At the same time we significantly improve the previously known probabilistic guarantees, showing that GIRGs contain a giant component with probability \( 1 - exp(-\Omega (n^{(3-\tau )/2})) \) for graph size \(n\) and a degree distribution with power-law exponent \(\tau \in (2, 3)\). Based on that we additionally derive insights about the connectivity of certain induced subgraphs of GIRGs.
@inproceedings{blasius2023giant, abstract = {In this paper we study the threshold model of geometric inhomogeneous random graphs (GIRGs); a generative random graph model that is closely related to hyperbolic random graphs (HRGs). These models have been observed to capture complex real-world networks well with respect to the structural and algorithmic properties. Following comprehensive studies regarding their connectivity, i.e., which parts of the graphs are connected, we have a good understanding under which circumstances a giant component (containing a constant fraction of the graph) emerges. While previous results are rather technical and challenging to work with, the goal of this paper is to provide more accessible proofs. At the same time we significantly improve the previously known probabilistic guarantees, showing that GIRGs contain a giant component with probability \( 1 - exp(-\Omega (n^{(3-\tau )/2})) \) for graph size \(n\) and a degree distribution with power-law exponent \(\tau \in (2, 3)\). Based on that we additionally derive insights about the connectivity of certain induced subgraphs of GIRGs.}, author = {Bläsius, Thomas and Friedrich, Tobias and Katzmann, Maximilian and Ruff, Janosch and Zeif, Ziena}, booktitle = {European Symposium on Algorithms (ESA)}, keywords = {esa janoschruff maximiliankatzmann thomasblaesius tobiasfriedrich year2023 zienazeif}, pages = {20:1&ndash;20:13}, title = {On the Giant Component of Geometric Inhomogeneous Random Graphs}, year = 2023 }

Baguley, Samuel; Friedrich, Tobias; Neumann, Aneta; Neumann, Frank; Pappik, Marcus; Zeif, Ziena Fixed Parameter Multi-Objective Evolutionary Algorithms for the W-Separator ProblemGenetic and Evolutionary Computation Conference (GECCO) 2023
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
Parameterized analysis provides powerful mechanisms for obtaining fine-grained insights into different types of algorithms. In this work, we combine this field with evolutionary algorithms and provide parameterized complexity analysis of evolutionary multi-objective algorithms for the W-separator problem, which is a natural generalization of the vertex cover problem. The goal is to remove the minimum number of vertices such that each connected component in the resulting graph has at most W vertices. We provide different multi-objective formulations involving two or three objectives that provably lead to fixed-parameter evolutionary algorithms with respect to the value of an optimal solution OPT and W. Of particular interest are kernelizations and the reducible structures used for them. We show that in expectation the algorithms make incremental progress in finding such structures and beyond. The current best known kernelization of the W-separator uses linear programming methods and requires a non-trivial post-process to extract the reducible structures. We provide additional structural features to show that evolutionary algorithms with appropriate objectives are also capable of extracting them. Our results show that evolutionary algorithms with different objectives guide the search and admit fixed parameterized runtimes to solve or approximate (even arbitrarily close) the W-separator problem.
@inproceedings{baguley2023fixed, abstract = {Parameterized analysis provides powerful mechanisms for obtaining fine-grained insights into different types of algorithms. In this work, we combine this field with evolutionary algorithms and provide parameterized complexity analysis of evolutionary multi-objective algorithms for the W-separator problem, which is a natural generalization of the vertex cover problem. The goal is to remove the minimum number of vertices such that each connected component in the resulting graph has at most W vertices. We provide different multi-objective formulations involving two or three objectives that provably lead to fixed-parameter evolutionary algorithms with respect to the value of an optimal solution OPT and W. Of particular interest are kernelizations and the reducible structures used for them. We show that in expectation the algorithms make incremental progress in finding such structures and beyond. The current best known kernelization of the W-separator uses linear programming methods and requires a non-trivial post-process to extract the reducible structures. We provide additional structural features to show that evolutionary algorithms with appropriate objectives are also capable of extracting them. Our results show that evolutionary algorithms with different objectives guide the search and admit fixed parameterized runtimes to solve or approximate (even arbitrarily close) the W-separator problem.}, author = {Baguley, Samuel and Friedrich, Tobias and Neumann, Aneta and Neumann, Frank and Pappik, Marcus and Zeif, Ziena}, booktitle = {Genetic and Evolutionary Computation Conference (GECCO)}, keywords = {sys:relevantfor:ae anetaneumann frankneumann gecco marcuspappik samuelbaguley tobiasfriedrich year2023 zienazeif}, title = {Fixed Parameter Multi-Objective Evolutionary Algorithms for the W-Separator Problem}, year = 2023 }

Friedrich, Tobias; Issac, Davis; Kumar, Nikhil; Mallek, Nadym; Zeif, Ziena Approximate Max-Flow Min-Multicut Theorem for Graphs of Bounded TreewidthSymposium Theory of Computing (STOC) 2023: 1325–1334
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
We prove an approximate max-multiflow min-multicut theorem for bounded treewidth graphs. In particular, we show the following: Given a treewidth-\(r\) graph, there exists a (fractional) multicommodity flow of value \(f\), and a multicut of capacity \(c\) such that \(f \leq c \leq \mathcal{O}(\ln(r + 1)) \cdot f \) . It is well known that the multiflow-multicut gap on an \(r\)-vertex (constant degree) expander graph can be \(\Omega(ln r)\), and hence our result is tight up to constant factors. Our proof is constructive, and we also obtain a polynomial time \( \mathcal{O}(ln(r + 1))\)-approximation algorithm for the minimum multicut problem on treewidth-r graphs. Our algorithm proceeds by rounding the optimal fractional solution to the natural linear programming relaxation of the multicut problem. We introduce novel modifications to the well-known region growing algorithm to facilitate the rounding while guaranteeing at most a logarithmic factor loss in the treewidth.
@inproceedings{friedrich2023approximate, abstract = {We prove an approximate max-multiflow min-multicut theorem for bounded treewidth graphs. In particular, we show the following: Given a treewidth-\(r\) graph, there exists a (fractional) multicommodity flow of value \(f\), and a multicut of capacity \(c\) such that \(f \leq c \leq \mathcal{O}(\ln(r + 1)) \cdot f \) . It is well known that the multiflow-multicut gap on an \(r\)-vertex (constant degree) expander graph can be \(\Omega(ln r)\), and hence our result is tight up to constant factors. Our proof is constructive, and we also obtain a polynomial time \( \mathcal{O}(ln(r + 1))\)-approximation algorithm for the minimum multicut problem on treewidth-r graphs. Our algorithm proceeds by rounding the optimal fractional solution to the natural linear programming relaxation of the multicut problem. We introduce novel modifications to the well-known region growing algorithm to facilitate the rounding while guaranteeing at most a logarithmic factor loss in the treewidth.}, author = {Friedrich, Tobias and Issac, Davis and Kumar, Nikhil and Mallek, Nadym and Zeif, Ziena}, booktitle = {Symposium Theory of Computing (STOC)}, keywords = {davisissac nadymmallek nikhilkumar stoc tobiasfriedrich year2023 zienazeif}, pages = {1325&ndash;1334}, title = {Approximate Max-Flow Min-Multicut Theorem for Graphs of Bounded Treewidth}, year = 2023 }

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, 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.
@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 aikaterininiklanovits davisissac katrincasel tobiasfriedrich wg year2023 zienazeif}, pages = {143&ndash;156}, title = {Efficient Constructions for the Gyori-Lovasz Theorem on Almost Chordal Graphs}, year = 2023 }

2022 [ nach oben ]

Friedrich, Tobias; Issac, Davis; Kumar, Nikhil; Mallek, Nadym; Zeif, Ziena A Primal-Dual Algorithm for Multicommodity Flows and Multicuts in Treewidth-2 GraphsApproximation Algorithms for Combinatorial Optimization Problems (APPROX) 2022: 55:1–55:18
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
We study the problem of multicommodity flow and multicut in treewidth-2 graphs and prove bounds on the multiflow-multicut gap. In particular, we give a primal-dual algorithm for computing multicommodity flow and multicut in treewidth-2 graphs and prove the following approximate max-flow min-cut theorem: given a treewidth-2 graph, there exists a multicommodity flow of value \(f\) with congestion \(4\), and a multicut of capacity \(c\) such that \(c \leq 20f \) . This implies a multiflow-multicut gap of \(80\) and improves upon the previous best known bounds for such graphs. Our algorithm runs in polynomial time when all the edges have capacity one. Our algorithm is completely combinatorial and builds upon the primal-dual algorithm of Garg, Vazirani and Yannakakis for multicut in trees and the augmenting paths framework of Ford and Fulkerson.
@inproceedings{friedrich2022primaldual, abstract = {We study the problem of multicommodity flow and multicut in treewidth-2 graphs and prove bounds on the multiflow-multicut gap. In particular, we give a primal-dual algorithm for computing multicommodity flow and multicut in treewidth-2 graphs and prove the following approximate max-flow min-cut theorem: given a treewidth-2 graph, there exists a multicommodity flow of value \(f\) with congestion \(4\), and a multicut of capacity \(c\) such that \(c \leq 20f \) . This implies a multiflow-multicut gap of \(80\) and improves upon the previous best known bounds for such graphs. Our algorithm runs in polynomial time when all the edges have capacity one. Our algorithm is completely combinatorial and builds upon the primal-dual algorithm of Garg, Vazirani and Yannakakis for multicut in trees and the augmenting paths framework of Ford and Fulkerson.}, author = {Friedrich, Tobias and Issac, Davis and Kumar, Nikhil and Mallek, Nadym and Zeif, Ziena}, booktitle = {Approximation Algorithms for Combinatorial Optimization Problems (APPROX)}, keywords = {approx davisissac nadymmallek nikhilkumar tobiasfriedrich year2022 zienazeif}, pages = {55:1&ndash;55:18}, title = {A Primal-Dual Algorithm for Multicommodity Flows and Multicuts in Treewidth-2 Graphs}, year = 2022 }

Baguley, Samuel; Friedrich, Tobias; Timo, Kötzing; Li, Xiaoyue; Pappik, Marcus; Zeif, Ziena Analysis of a Gray-Box Operator for Vertex CoverGenetic and Evolutionary Computation Conference (GECCO) 2022: 1363–1371
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
Combinatorial optimization problems are a prominent application area of evolutionary algorithms, where the (1+1) EA is one of the most investigated. We extend this algorithm by introducing some problem knowledge with a specialized mutation operator which works under the assumption that the number of 1s of a solution is critical, as frequently happens in combinatorial optimization. This slight modification increases the chance to correct wrongly placed bits while preserving the simplicity and problem independence of the (1+1) EA. As an application of our algorithm we examine the vertex cover problem on certain instances, where we show that it leads to asymptotically better runtimes and even finds with higher probability optimal solutions in comparison with the usual (1+1) EA. Precisely, we compare the performance of both algorithms on paths and on complete bipartite graphs of size \(n\). Regarding the path we prove that, for a particular initial configuration, the (1+1) EA takes in expectation \(\Theta(n^4)\) iterations while the modification reduces this to \(\Theta(n^3)\), and present experimental evidence that such a configuration is reached. Concerning the complete bipartite graph our modification finds the optimum in polynomial time with probability \(1-1/2^{\Omega(n^\xi)}\) for every positive constant \(\xi < 1\), which improves the known probability of \(1-1/\)poly\((n)\) for the (1+1) EA.
@inproceedings{baguley2022analysis, abstract = {Combinatorial optimization problems are a prominent application area of evolutionary algorithms, where the (1+1) EA is one of the most investigated. We extend this algorithm by introducing some problem knowledge with a specialized mutation operator which works under the assumption that the number of 1s of a solution is critical, as frequently happens in combinatorial optimization. This slight modification increases the chance to correct wrongly placed bits while preserving the simplicity and problem independence of the (1+1) EA. As an application of our algorithm we examine the vertex cover problem on certain instances, where we show that it leads to asymptotically better runtimes and even finds with higher probability optimal solutions in comparison with the usual (1+1) EA. Precisely, we compare the performance of both algorithms on paths and on complete bipartite graphs of size \(n\). Regarding the path we prove that, for a particular initial configuration, the (1+1) EA takes in expectation \(\Theta(n^4)\) iterations while the modification reduces this to \(\Theta(n^3)\), and present experimental evidence that such a configuration is reached. Concerning the complete bipartite graph our modification finds the optimum in polynomial time with probability \(1-1/2^{\Omega(n^\xi)}\) for every positive constant \(\xi < 1\), which improves the known probability of \(1-1/\)poly\((n)\) for the (1+1) EA.}, author = {Baguley, Samuel and Friedrich, Tobias and Timo, Kötzing and Li, Xiaoyue and Pappik, Marcus and Zeif, Ziena}, booktitle = {Genetic and Evolutionary Computation Conference (GECCO)}, keywords = {sys:relevantfor:ae gecco marcuspappik samuelbaguley timokoetzing tobiasfriedrich xiaoyueli year2022 zienazeif}, pages = {1363&ndash;1371}, title = {Analysis of a Gray-Box Operator for Vertex Cover}, year = 2022 }

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_i}{3} \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 aikaterininiklanovits approx davisissac katrincasel ralfborndörfer stephanschwartz year2021 zienazeif}, 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 aikaterininiklanovits davisissac esa katrincasel tobiasfriedrich year2021 zienazeif}, 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 }

2016 [ nach oben ]

Borndörfer, Ralf; Arslan, Oytun; Elijazyfer, Ziena; Güler, Hakan; Renken, Malte; Şahin, Güvenç; Schlechte, Thomas Line Planning on Path Networks with Application to the Istanbul MetrobüsGerman Operations Research Society (GOR) 2016: 235–241
[ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
@inproceedings{DBLP:conf/or/BorndorferAEGRS16, author = {Borndörfer, Ralf and Arslan, Oytun and Elijazyfer, Ziena and Güler, Hakan and Renken, Malte and Şahin, Güvenç and Schlechte, Thomas}, booktitle = {German Operations Research Society (GOR)}, crossref = {DBLP:conf/or/2016}, keywords = {sys:relevantfor:ae guevencsahin hakangueler malterenken or oytunarslan ralfborndoerfer thomasschlechte year2016 zienaelijazyfer zienazeif}, pages = {235-241}, title = {Line Planning on Path Networks with Application to the Istanbul Metrobüs}, year = 2016 }