Relation to integer linear programming and polynomial time solvability

For the simplest case, since there is a single attribute and the FOV events are ignored, we can represent the number of targets in a shadow with a single unknown quantity. Let the set of shadows be $\{s_i\}$ ; we denote the set of corresponding unknowns as $\{x_i\}$ . We can write the initial condition for each shadow at $t = t_0$ as two constraints

$$l_i \le x_i \le u_i.$$ (2)

For each event in the sequence of component events, we then obtain one extra constraint of the following form:

$$\begin{array}{ll} \textrm{Appear or disappear:} & x_i = a_i \textrm{Split or merge:} & x_i = x_j + x_k. \end{array}$$ (3)

Here we allow that as an appear event happens, $a_i$ targets may hide in $s_i$ at the same time. This is more general than letting $a_i = 0$ . To unify notation, we write these in the same way as the initial conditions by letting $l_i = u_i = a_i$ . The same applies to the disappear events. Additionally, we have for each shadow $s_i$ , the constraint

$$x_i \ge 0.$$ (4)

Finally, the task becomes finding the lower and upper bounds of targets for a set of shadows at time $t = t_f$ indexed by $\mathcal I$ . For the upper bound, we can write the problem as maximizing the sum of the set of unknowns

$$\textrm{maximize } \displaystyle\sum_{i \in \mathcal I} x_i.$$ (5)

Finding the lower bound then becomes maximizing the set of unknowns not indexed by $\mathcal I$ because the total number of targets are preserved. We have obtained a standard integer linear programming (ILP) problem described by (2),(3),(4), and (5). We may group the constraints in (2),(3), and (4) and express the problem as (each equality constraint becomes two inequality constraint)

$$\textrm{maximize } \displaystyle\sum_{i \in \mathcal I} x_i, \quad \textrm{ subject to } Ax \le b.$$ (6)

It is well known that the class of ILP problems is NP-complete in general. It turns out, however, that our ILP problem is not only feasible, but also efficiently solvable.

Proposition 3   A polynomial time algorithm exists for the system described by (6).

As a first step in proving the proposition, we establish the following lemma:

Lemma 4   The constraint matrix $A$ in (6) is totally unimodular.

PROOF. We use induction over the size of square submatrices of $A$ to prove that all such submatrices must have determinant 0 or $\pm 1$ . As the base case, every element of $A$ is 0 or $\pm 1$ . Suppose that all square submatrices of order $n$ have determinant $0, \pm 1$ . Denote these matrices $\mathcal M_n$ . Suppose there is a square submatrix $M$ of $A$ of order $(n+1)$ with determinant not in $\{0, \pm 1\}$ . Every constraint arising from (2), (3), and (4) except $x_i = x_j + x_k$ introduces rows in $A$ with a single $\pm 1$ in them; the rest of the row contains only 0 s. If $M$ contains a row arising from these types of constraint then $M$ must have determinant $0, \pm 1$ by induction. Suppose not. In this case, all rows of $M$ are introduced by constraint of type $x_i = x_j + x_k$ . Each such constraint brings in two rows of $A$ with opposite signs and therefore cannot both appear in $M$ . We can assume that $M$ 's first row have coefficients coming from one of the rows introduced by a split event, $x_i = x_j + x_k$ . As a first case, let the $i, j, k$ th columns of $A$ correspond to $i', j', k'$ th columns of $M$ , respectively. To make $M$ 's determinant not in $\{0, \pm 1\}$ , there needs to be another row in $M$ that contains exactly two non zero elements among $i', j', k'$ th columns. This is only possible if $s_j$ and $s_k$ merge again, giving a constraint of the form $x_j + x_k = x_l$ . We may let this row be the second row in $M$ . This suggests that $j', k'$ th column of $M$ are all zeros after the second row; but this gives us that $M$ has determinant 0 . The second case is that $M$ includes only two columns of $A$ 's $i, j, k$ th columns. It can be checked similarly that $M$ must have determinant 0 . 

PROOF OF PROPOSITION 3. When the constraint matrix $A$ is totally unimodular and $b$ is a vector of integers, then the minimal faces of the constraint polytope must assume integer coordinates, making the solution of the relaxed linear programming (LP) problem also the solution to the original ILP problem [32]. It is clear that $b$ in (6) is integer. Lemma 4 gives us that $A$ is totally unimodular. Therefore, a polynomial time algorithm such as interior point method can be applied to solve (6).