Cohen, Sarel; Kamma, Lior; Niklanovits, Aikaterini A New Approach for Approximating Directed Rooted Networks50th International Workshop on Graph-Theoretic Concepts in Computer Science 2024
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.
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
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.
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
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.