More Like this

1. On 2-fold graceful graphs

   Bunge, R; Cornett, M; El-Zanati, S; Jeffries, J; Rattin, E. (January 2020, Journal of Combinatorial Mathematics and Combinatorial Computing)

   null (Ed.)

   A long-standing conjecture by Kotzig, Ringel, and Rosa states that every tree admits a graceful labeling. That is, for any tree $$T$$ with $$n$$~edges, it is conjectured that there exists a labeling $$f\colon V(T) \to \{0,1,\ldots,n\}$$ such that the set of induced edge labels $$\bigl\{ |f(u)-f(v)| : \{u,v\}\in E(T) \bigr\}$$ is exactly $$\{1,2,\ldots,n\}$$. We extend this concept to allow for multigraphs with edge multiplicity at most~$$2$$. A \emph{2-fold graceful labeling} of a graph (or multigraph) $$G$$ with $$n$$~edges is a one-to-one function $$f\colon V(G) \to \{0,1,\ldots,n\}$$ such that the multiset of induced edge labels is comprised of two copies of each element in $$\bigl\{ 1,2,\ldots, \lfloor n/2 \rfloor \bigr\}$$ and, if $$n$$ is odd, one copy of $$\bigl\{ \lceil n/2 \rceil \bigr\}$$. When $$n$$ is even, this concept is similar to that of 2-equitable labelings which were introduced by Bloom and have been studied for several classes of graphs. We show that caterpillars, cycles of length $$n \not\equiv 1 \pmod{4}$$, and complete bipartite graphs admit 2-fold graceful labelings. We also show that under certain conditions, the join of a tree and an empty graph (i.e., a graph with vertices but no edges) is $$2$$-fold graceful. 

   more » « less
2. Relative Survivable Network Design

   Dinitz, Michael; Koranteng, Ama; Kortsarz, Guy (September 2022, Leibniz international proceedings in informatics)

   One of the most important and well-studied settings for network design is edge-connectivity requirements. This encompasses uniform demands such as the Minimum k-Edge-Connected Spanning Subgraph problem (k-ECSS), as well as nonuniform demands such as the Survivable Network Design problem. A weakness of these formulations, though, is that we are not able to ask for fault-tolerance larger than the connectivity. Taking inspiration from recent definitions and progress in graph spanners, we introduce and study new variants of these problems under a notion of relative fault-tolerance. Informally, we require not that two nodes are connected if there are a bounded number of faults (as in the classical setting), but that two nodes are connected if there are a bounded number of faults and the two nodes are connected in the underlying graph post-faults. That is, the subgraph we build must "behave" identically to the underlying graph with respect to connectivity after bounded faults. We define and introduce these problems, and provide the first approximation algorithms: a (1+4/k)-approximation for the unweighted relative version of k-ECSS, a 2-approximation for the weighted relative version of k-ECSS, and a 27/4-approximation for the special case of Relative Survivable Network Design with only a single demand with a connectivity requirement of 3. To obtain these results, we introduce a number of technical ideas that may of independent interest. First, we give a generalization of Jain’s iterative rounding analysis that works even when the cut-requirement function is not weakly supermodular, but instead satisfies a weaker definition we introduce and term local weak supermodularity. Second, we prove a structure theorem and design an approximation algorithm utilizing a new decomposition based on important separators, which are structures commonly used in fixed-parameter algorithms that have not commonly been used in approximation algorithms. 

   more » « less
3. Approximation Algorithms for Network Design in Non-Uniform Fault Models

   https://doi.org/10.4230/LIPIcs.ICALP.2023.36  

   Chekuri, Chandra; Jain, Rhea (January 2023, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Etessami, Kousha; Feige, Uriel; Puppis, Gabriele (Ed.)

   Classical network design models, such as the Survivable Network Design problem (SNDP), are (partly) motivated by robustness to faults under the assumption that any subset of edges upto a specific number can fail. We consider non-uniform fault models where the subset of edges that fail can be specified in different ways. Our primary interest is in the flexible graph connectivity model [Adjiashvili, 2013; Adjiashvili et al., 2020; Adjiashvili et al., 2022; Boyd et al., 2023], in which the edge set is partitioned into safe and unsafe edges. Given parameters p,q ≥ 1, the goal is to find a cheap subgraph that remains p-connected even after the failure of q unsafe edges. We also discuss the bulk-robust model [Adjiashvili et al., 2015; Adjiashvili, 2015] and the relative survivable network design model [Dinitz et al., 2022]. While SNDP admits a 2-approximation [K. Jain, 2001], the approximability of problems in these more complex models is much less understood even in special cases. We make two contributions. Our first set of results are in the flexible graph connectivity model. Motivated by a conjecture that a constant factor approximation is feasible when p and q are fixed, we consider two special cases. For the s-t case we obtain an approximation ratio that depends only on p,q whenever p+q > pq/2 which includes (p,2) and (2,q) for all p,q ≥ 1. For the global connectivity case we obtain an O(q) approximation for (2,q), and an O(p) approximation for (p,2) and (p,3) for any p ≥ 1, and for (p,4) when p is even. These are based on an augmentation framework and decomposing the families of cuts that need to be covered into a small number of uncrossable families. Our second result is a poly-logarithmic approximation for a generalization of the bulk-robust model when the "width" of the given instance (the maximum number of edges that can fail in any particular scenario) is fixed. Via this, we derive corresponding approximations for the flexible graph connectivity model and the relative survivable network design model. We utilize a recent framework due to Chen et al. [Chen et al., 2022] that was designed for handling group connectivity. 

   more » « less
4. Optimal Vertex Fault-Tolerant Spanners in Polynomial Time

   https://doi.org/10.1137/1.9781611976465.174  

   Bodwin, Greg; Dinitz, Michael; Robelle, Caleb (January 2021, Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA))

   null (Ed.)

   Recent work has pinned down the existentially optimal size bounds for vertex fault-tolerant spanners: for any positive integer k, every n-node graph has a (2k – 1)-spanner on O(f^{1–1/k} n^{1+1/k}) edges resilient to f vertex faults, and there are examples of input graphs on which this bound cannot be improved. However, these proofs work by analyzing the output spanner of a certain exponential-time greedy algorithm. In this work, we give the first algorithm that produces vertex fault tolerant spanners of optimal size and which runs in polynomial time. Specifically, we give a randomized algorithm which takes Õ(f^{1–1/k} n^{2+1/k} + mf2) time. We also derandomize our algorithm to give a deterministic algorithm with similar bounds. This reflects an exponential improvement in runtime over [Bodwin-Patel PODC '19], the only previously known algorithm for constructing optimal vertex fault-tolerant spanners. 

   more » « less
5. Maximal k-Edge-Connected Subgraphs in Almost-Linear Time for Small k

   https://doi.org/10.4230/LIPIcs.ESA.2023.92  

   Saranurak, Thatchaphol; Yuan, Wuwei (January 2023, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Gørtz, Inge Li; Farach-Colton, Martin; Puglisi, Simon J; Herman, Grzegorz (Ed.)

   We give the first almost-linear time algorithm for computing the maximal k-edge-connected subgraphs of an undirected unweighted graph for any constant k. More specifically, given an n-vertex m-edge graph G = (V,E) and a number k = log^o(1) n, we can deterministically compute in O(m+n^{1+o(1)}) time the unique vertex partition {V_1,… ,V_z} such that, for every i, V_i induces a k-edge-connected subgraph while every superset V'_i ⊃ V_{i} does not. Previous algorithms with linear time work only when k ≤ 2 [Tarjan SICOMP'72], otherwise they all require Ω(m+n√n) time even when k = 3 [Chechik et al. SODA'17; Forster et al. SODA'20]. Our algorithm also extends to the decremental graph setting; we can deterministically maintain the maximal k-edge-connected subgraphs of a graph undergoing edge deletions in m^{1+o(1)} total update time. Our key idea is a reduction to the dynamic algorithm supporting pairwise k-edge-connectivity queries [Jin and Sun FOCS'20]. 

   more » « less