ABSTRACT
In Network Design problems, the goal is to select a “cheap” graph that satisfies some property 𝒢, meaning that the graph belongs to a family 𝒢 of subgraphs of a given graph G. Many fundamental properties can be characterized by degree demands (existence of a given number of edges incident to a node) or pairwise connectivity demands (existence of a given number of disjoint paths between node pairs). Traditionally, “cheap” means that the edges of the input graph G = (V, E)have costs c = {ce : e ∈ E}, and the cost of a subgraph of G is the sum of the costs of its edges. Some classic examples of “low demands” problems are Edge-Cover, st-Path, Spanning Tree, Steiner Tree, Steiner Forest, Out-Arborescence, and others. Examples of “high demands” problems are Edge-Multi-Cover, k Disjoint Paths, k-Out-Connected Subgraph, k-Connected Subgraph, and others. Refer to, for example, References 1 and 2, for polynomial time solvable problems of this type. Here we discuss Activation Network Design problems, in which we seek an assignment a = {av ≥ 0: v ∈ V} to the nodes, such that the activated graph G a = (V, E a ) satisfies a given property, and the value a ( V ) = ∑ v ∈ V a v https://s3-euw1-ap-pe-df-pch-content-public-u.s3.eu-west-1.amazonaws.com/9781351235426/021cf6c0-a3fa-48d9-836a-fa4830c7d2d0/content/equ_0874.tif"/> of the assignment is minimized. We now give three examples of such problems.
