MathB.in
New
Demo
Tutorial
About
Suppose we have an arbitrary bipartite graph on vertex sets $(U,V)$. Endow each vertex $v \in U \cup V$ with a positive integral weight $w(v)$. We define the potential function $\varphi : \mathcal{P}(V) \to \mathbb{Z}$ that maps every subset $X \subseteq V$ to an integer as follows: $$\varphi(X) = \sum_{v \in X} w(v) - \sum_{u \in U, \\ N(u) \subseteq X} w(u).$$ Here $N(u)$ denotes the set of neighbours of $u \in U$ in the graph. In words, $\varphi$ sums up the weights of vertices in $X$ and subtracts the weights of the vertices in $U$ covered by $X$. (A vertex $v$ is said to be covered by vertex set $S$ if $N(v) \subseteq S$.) The challenge: find an efficient algorithm to determine the smallest set $X$ that minimises $\varphi$.
ERROR: JavaScript must be enabled to render input!
Thu, 07 Oct 2021 11:45 GMT