Maximum Non-Blocker Problem

computation graph-theory

Definition

Maximum Non-Blocker Problem

Let $G=(V,E,c)$ be a weighted graph with edge weights $c:E\to {\mathbb{R}}_{\ge 0}$ and let $k\in \mathbb{N}$ be part of the input. The maximum non-blocker problem is a decision problem asking whether there exists a non-blocker $N\subseteq E$ of $G$ — a subset of edges whose removal leaves $G$ connected — such that

$$\sum _{e\in N}{c}_e\ge k.$$

Reading

A non-blocker $N$ is a set of edges that $G$ does not need to stay connected: $G-N=(V,E\setminus N)$ is still connected. The problem asks whether the redundant edges can be chosen heavy enough to clear a given threshold $k$. Equivalently, it asks whether the heaviest non-blocker of $G$ has total weight at least $k$. The “maximum” refers to this weight threshold, not to a cardinality constraint on $N$ itself.

The optimisation variant maximises ${\sum }_{e\in N}{c}_e$ subject to $N$ being a non-blocker; the question above is its decision version, parameterised by the target $k$.