The exact distance t -power of a graph G , G [ ♯ t ] , is a graph which has the same vertex set as G , with two vertices adjacent in G [ ♯ t ] if and only if they are at distance exactly t in the original graph G . We study the clique number of this graph, also known as the t -equidistant number. We show that it is NP-hard to determine the t -equidistant number of a graph, and that in fact, it is NP-hard to approximate it within a constant factor. We also investigate how the t -equidistant number relates to another distance-based graph parameter; the t -independence number. In particular, we show how large the gap between both parameters can be. The hardness results motivate deriving eigenvalue bounds, which compare well against a known general bound. In addition, the tightness of the proposed eigenvalue bounds is studied.

Flexible network design deals with building a network that guarantees some connectivity requirements between its vertices, even when some of its elements (like vertices or edges) fail. In particular, the set of edges (resp. vertices) of a given graph are here partitioned into safe and unsafe. The goal is to identify a minimum size subgraph that is 2-edge-connected (resp. 2-vertex-connected), and stay so whenever any of the unsafe elements gets removed. In this paper, we provide improved approximation algorithms for flexible network design problems, considering both edge-connectivity and vertex-connectivity, as well as connectivity values higher than 2. For the vertex-connectivity variant, in particular, our algorithm is the first with approximation factor strictly better than 2.

The 2-Vertex-Connected Spanning Subgraph problem (2VCSS) is among the most basic NP-hard (Survivable) Network Design problems: we are given an (unweighted) undirected graph G. Our goal is to find a subgraph S of G with the minimum number of edges which is 2-vertex-connected, namely S remains connected after the deletion of an arbitrary node. 2VCSS is well-studied in terms of approximation algorithms, and the current best (polynomial-time) approximation factor is 10/7 by Heeger and Vygen [SIDMA'17] (improving on earlier results by Khuller and Vishkin [STOC'92] and Garg, Vempala and Singla [SODA'93]). Here we present an improved 4/3 approximation. Our main technical ingredient is an approximation preserving reduction to a conveniently structured subset of instances which are "almost" 3-vertex-connected. The latter reduction might be helpful in future work.

This paper addresses a graph optimization problem, called the Witness Tree problem, which seeks a spanning tree of a graph minimizing a certain non-linear objective function. This problem is of interest because it plays a crucial role in the analysis of the best approximation algorithms for two fundamental network design problems: Steiner Tree and Node-Tree Augmentation. We will show how a wiser choice of witness trees leads to an improved approximation for Node-Tree Augmentation, and for Steiner Tree in special classes of graphs.

The basic goal of survivable network design is to construct low-cost networks which preserve a sufficient level of connectivity despite the failure or removal of a few nodes or edges. One of the most basic problems in this area is the 2-Edge-Connected Spanning Subgraph problem (2-ECSS): given an undirected graph G, find a 2-edge-connected spanning subgraph H of G with the minimum number of edges (in particular, H remains connected after the removal of one arbitrary edge). 2-ECSS is NP-hard and the best-known (polynomial-time) approximation factor for this problem is 4/3. Interestingly, this factor was achieved with drastically different techniques by [Hunkenschröder, Vempala and Vetta '00,'19] and [Sebö and Vygen, '14]. In this paper we present an improved approximation for 2-ECSS. The key ingredient in our approach (which might also be helpful in future work) is a reduction to a special type of structured graphs: our reduction preserves approximation factors up to 6/5. While reducing to 2-vertex-connected graphs is trivial (and heavily used in prior work), our structured graphs are “almost” 3-vertex-connected: more precisely, given any 2-vertex-cut {u, v} of a structured graph G = (V, E), G[V \ {u, v}] has exactly 2 connected components, one of which contains exactly one node of degree 2 in G. * Partially supported by the SNSF Excellence Grant 200020B 182865/1 and the SNSF Grant 200021 200731/1.

Abstract. The basic goal of survivable network design is to build a cheap network that maintains the connectivity between given sets of nodes despite the failure of a few edges/nodes. The connectivity augmentation problem ([Formula: see text]) is arguably one of the most basic problems in this area: given a [Formula: see text](-edge)-connected graph [Formula: see text] and a set of extra edges ( links), select a minimum cardinality subset [Formula: see text] of links such that adding [Formula: see text] to [Formula: see text] increases its edge connectivity to [Formula: see text]. Intuitively, one wants to make an existing network more reliable by augmenting it with extra edges. The best known approximation factor for this NP-hard problem is 2, and this can be achieved with multiple approaches (the first such result is in [G. N. Frederickson and Jájá, SIAM J. Comput., 10 (1981), pp. 270–283]. It is known [E. A. Dinitz, A. V. Karzanov, and M. V. Lomonosov, Studies in Discrete Optimization, Nauka, Moscow, 1976, pp. 290–306] that [Formula: see text] can be reduced to the case [Formula: see text], also known as the t ree augmentation problem ([Formula: see text]) for odd [Formula: see text], and to the case [Formula: see text], also known as the c actus augmentation problem ([Formula: see text]) for even [Formula: see text]. Prior to the conference version of this paper [J. Byrka, F. Grandoni, and A. Jabal Ameli, STOC’20, ACM, New York, 2020, pp. 815–825], several better than 2 approximation algorithms were known for [Formula: see text], culminating with a recent [Formula: see text] approximation [F. Grandoni, C. Kalaitzis, and R. Zenklusen, STOC’18, ACM, New York, 1918, pp. 632–645]. However, for [Formula: see text] the best known approximation was 2. In this paper we breach the 2 approximation barrier for [Formula: see text], hence, for [Formula: see text], by presenting a polynomial-time [Formula: see text] approximation. From a technical point of view, our approach deviates quite substantially from previous work. In particular, the better-than-2 approximation algorithms for [Formula: see text] either exploit greedy-style algorithms or are based on rounding carefully designed LPs. We instead use a reduction to the Steiner tree problem which was previously used in parameterized algorithms [Basavaraju et al., ICALP ’14, Springer, Berlin, 2014, pp. 800–811]. This reduction is not approximation preserving, and using the current best approximation factor for a Steiner tree [Byrka et al., J. ACM, 60 (2013), 6] as a black box would not be good enough to improve on 2. To achieve the latter goal, we “open the box” and exploit the specific properties of the instances of a Steiner tree arising from [Formula: see text]. In our opinion this connection between approximation algorithms for survivable network design and Steiner-type problems is interesting, and might lead to other results in the area.

The basic goal of survivable network design is to build cheap networks that guarantee the connectivity of certain pairs of nodes despite the failure of a few edges or nodes. A celebrated result by Jain [Combinatorica'01] provides a 2-approximation for a wide class of these problems. However nothing better is known even for very basic special cases, raising the natural question whether any improved approximation factor is possible at all.

In the Demand Strip Packing problem (DSP), we are given a time interval and a collection of tasks, each characterized by a processing time and a demand for a given resource (such as electricity, computational power, etc.). A feasible solution consists of a schedule of the tasks within the mentioned time interval. Our goal is to minimize the peak resource consumption, i.e. the maximum total demand of tasks executed at any point in time. It is known that DSP is NP-hard to approximate below a factor 3/2, and standard techniques for related problems imply a (polynomial-time) 2-approximation. Our main result is a (5/3+eps)-approximation algorithm for any constant eps>0. We also achieve best-possible approximation factors for some relevant special cases.

Abstract In the k-Connectivity Augmentation Problem we are given a k-edge-connected graph and a set of additional edges called links. Our goal is to find a set of links of minimum size whose addition to the graph makes it (k + 1)-edge-connected. There is an approximation preserving reduction from the mentioned problem to the case k = 1 (a.k.a. the Tree Augmentation Problem or TAP) or k = 2 (a.k.a. the Cactus Augmentation Problem or CacAP). While several better-than-2 approximation algorithms are known for TAP, for CacAP only recently this barrier was breached (hence for k-Connectivity Augmentation in general). As a first step towards better approximation algorithms for CacAP, we consider the special case where the input cactus consists of a single cycle, the Cycle Augmentation Problem (CycAP). This apparently simple special case retains part of the hardness of the general case. In particular, we are able to show that it is APX-hard. In this paper we present a combinatorial $\left (\frac {3}{2}+\varepsilon \right )$ 3 2 + ε -approximation for CycAP, for any constant ε > 0. We also present an LP formulation with a matching integrality gap: this might be useful to address the general case of the problem.

In the Strip Packing problem, we are given a vertical half-strip [0,W]× [0,+∞) and a collection of open rectangles of width at most W. Our goal is to find an axis-aligned (non-overlapping) packing of such rectangles into the strip such that the maximum height OPT spanned by the packing is as small as possible. Strip Packing generalizes classical well-studied problems such as Makespan Minimization on identical machines (when rectangle widths are identical) and Bin Packing (when rectangle heights are identical). It has applications in manufacturing, scheduling and energy consumption in smart grids among others. It is NP-hard to approximate this problem within a factor (3/2-ε) for any constant ε > 0 by a simple reduction from the Partition problem. The current best approximation factor for Strip Packing is (5/3+ε) by Harren et al. [Computational Geometry '14], and it is achieved with a fairly complex algorithm and analysis. It seems plausible that Strip Packing admits a (3/2+ε)-approximation. We make progress in that direction by achieving such tight approximation guarantees for a special family of instances, which we call skewed instances. As standard in the area, for a given constant parameter δ > 0, we call large the rectangles with width at least δ W and height at least δ OPT, and skewed the remaining rectangles. If all the rectangles in the input are large, then one can easily compute the optimal packing in polynomial time (since the input can contain only a constant number of rectangles). We consider the complementary case where all the rectangles are skewed. This second case retains a large part of the complexity of the original problem; in particular, it is NP-hard to approximate within a factor (3/2-ε) and we provide an (almost) tight (3/2+ε)-approximation algorithm.

The basic goal of survivable network design is to build a cheap network that maintains the connectivity between given sets of nodes despite the failure of a few edges/nodes. The Connectivity Augmentation Problem (CAP) is arguably one of the most basic problems in this area: given a k(-edge)-connected graph G and a set of extra edges (links), select a minimum cardinality subset A of links such that adding A to G increases its edge connectivity to k+1. Intuitively, one wants to make an existing network more reliable by augmenting it with extra edges. The best known approximation factor for this NP-hard problem is 2, and this can be achieved with multiple approaches (the first such result is in [Frederickson and Jájá’81]).