network optimization engineers

Abstract: We study the sample complexity of testing $k$-colorability in the dense graph model. A graph is $\varepsilon$-far from being $k$-colorable if at least $\varepsilon n^2$ edge deletions are required to make it $k$-colorable. We prove that, for every integer $k\ge 2$, a uniformly random induced subgraph on \[ O\!\left(\frac{k\log k}{\varepsilon}\right) \] vertices is non-$k$-colorable with probability at least $2/3$ whenever the original graph is $\varepsilon$-far from $k$-colorable. The proof introduces a trial coloring process based on nested palette systems and iteratively selected pivots. This yields an upper bound of $O(k\log k/\varepsilon)$, which is no worse than the previous state of the art $O(k\log(1/\varepsilon)/\varepsilon)$ throughout the nonvacuous parameter range, and is an improvement whenever $1/\varepsilon$ is superpolynomial in $k$. Moreover, for every fixed $k$, our bound matches the known lower bound, thereby establishing the optimal $Θ(1/\varepsilon)$ dependence on $\varepsilon$ and, to the best of our knowledge, achieving this optimal dependence for the first time.

Abstract: First defined by Bouchitté and Todinca, Potential Maximal Cliques (PMC) are a well studied notion in graph theory due to its numerous applications. The PMCs of an undirected graph $G$ are defined as the maximal cliques of the minimal triangulations of $G$. Their number can be exponential in the size of the graph. PMCs were crucial in the design of a polynomial-time algorithm which solves Maximum Weight Independent Set on $P_6$-free graphs (Grzesik, Klimošová, Pilipczuk, Pilipczuk, 2020). They also play a central role in the proposal of a polynomial-time algorithm to solve Largest Induced Subgraph of treewidth $\le t$ (Fomin, Todinca, Villanger, 2013). Last but not least, certainly one of the main application of PMCs is the existence of an exact dynamic-programming algorithm to determine the treewidth of a graph (Fomin, Kratsch, Todinca, Villanger, 2008) which uses its list of PMCs as an input. In fact, the enumeration of PMCs stands as the bottleneck for the computation of treewidth with this method: the PMC-enumeration step takes output-quadratic time (Bouchitté, Todinca, 2002) while the dynamic-programming one takes a time linear in the number of PMCs. This two-step procedure was proven to be among the most performing approaches in practice to determine treewidth. Answering a longstanding open question, we propose an algorithm to enumerate PMCs in output-linear time, {\em i.e.} a running time linear in the number of PMCs. This offers nice perspectives not only from the theoretical viewpoint - better running time for the PMC-based methods determining treewidth, for Minimum Fill-In and Largest Induced Subgraph of treewidth $\le t$ - but also from the practical side, with the possibility to propose top-performance implementation.

Abstract: Braess paradox originates when latency at Wardrop equilibrium in traffic networks decreases because of removing edges. The graph-theoretic property of networks suffering from the Braess paradox was called vulnerability by Roughgarden in 2006; it was then characterized and algorithmically checked both for undirected and for directed nets. In this paper, we provide a decremental algorithm of linear amortized complexity to check vulnerability for dynamically evolving networks. The basic idea of our dynamic algorithm is to use a static algorithm that marks some edges as irrelevant for the vulnerability of the graph and ignore those edges for all subsequent runs of the decremental procedure. To get a linear amortized cost for every edge remotion, we also provide a new version of such a static algorithm that improves its complexity from O(n m^2) to O(m^2), that is in turn aligned with the cost of the best state-of-the-art static algorithm for vulnerability.

Abstract: In this work we consider the Maximal Independent Set (MIS) problem and the metric Steiner Forest problem in the sublinear time setting, under the adjacency/distance matrix query model. First, we give an algorithm that estimates the size of an MIS up to a multiplicative factor of $(1+\eps)$ using $\tO(n^{4/3}/\eps^2)$ queries. This improves the best previous algorithm by Mahabadi, Roghani, Tarnawski, and Vakilian (SODA 2026), which had a query complexity of $\tO(n^{3/2}/\eps^2)$. Via a reduction from that work, this would automatically imply the same improvement for the problem of estimating the metric Steiner Forest cost up to an $O(\log n)$ factor. However, as our second contribution, we consider the Steiner Forest problem directly and provide an algorithm with $\tO(n)$ query complexity that is very simple and does not proceed via MIS.

Abstract: We investigate decentralized nonsmooth nonconvex stochastic optimization over a network of $n$ nodes, with the goal of finding an $(δ,ε)$-Goldstein stationary point. The best existing algorithm achieves $O(δ^{-1}(ε^{-3}+dε^{-1}))$ sample complexity and $\widetilde{O}(γ^{-1/2}δ^{-1}(ε^{-3}+dε^{-1}))$ communication complexity, where $d$ is the problem dimension and $γ$ is the spectral gap of the communication matrix. However, the polynomial dependence on $d$ can be a major bottleneck in high-dimensional regimes. In this paper, we propose a novel algorithm that achieves $O(δ^{-1}ε^{-3})$ sample complexity and $\widetilde{O}(γ^{-1/2}δ^{-1}ε^{-3})$ communication complexity. The primary technique is an elegant decentralized online-to-nonconvex conversion that reduces the original problem to a decentralized online convex optimization (D-OCO) problem. A key property of our conversion is that its consensus requirements can be inherited directly from the consensus of the underlying D-OCO decisions. In particular, this property enables us to establish an explicit connection between the dimension dependence and the consensus error, which in turn shows that the polynomial dependence on $d$ can be removed with only logarithmic additional communication.