Network Activation with Property $\Pi$

• INSTANCE: Graph $G=(V,E)$ , monotone activation functions $f_e\colon \mathbb{R}^+\times\mathbb{R}^+\to\{0,1\}$ for the edges $e\in E$ , monotone property $\Pi$ of subgraphs of $G$
• SOLUTION: Assignment $x=(x_v)_{v\in V}\in \mathbb{R}^{\vert V\vert}$ such that the subgraph induced by the activated edges $e=\{u,v\}$ (i.e. $f_e(x_u,x_v)=1$ ) is contained in $\Pi$
• COST FUNCTION: $\sum_{v\in V}x_v$
• OBJECTIVE: Minimize
• Approx.: If every inclusion minimal edge-set $F\subseteq E$ with $(V,F)\in \Pi$ has maximum degree at most $\Delta$ and the underlying Edge-Costs Network Design Problem with property $\Pi$ admits a $\theta$ -approximation algorithm, the problem is approximable within approximation ratio $\theta\Delta$ [92,51].