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