

![0_image_0.png](0_image_0.png)

Proof. Assume C = (x1, z1, . . . , xk, zk, t) is a certifying path for x1 in F. Property (1) follows from condition C1 of a certifying path, property (2) follows from condition C5 and Lemma 4. Property (3) follows from conditions C2 and C3.

To see the reverse assume that C satisfies properties (1)–(3). Condition C1 follows from property (1). Conditions C3, C4 and C5 follow from property (2) and the assumption that F is bipartite. Condition C2 follows from property (3). Hence C is a certifying path for x1 in F.

Indeed, consider the certifying path C of Example 7 which gives rise to the sequence of values v5, v4, v2, v1.

This sequence is a directed path in H
−v5 F, however v4, v2, v1 is not a directed path in H
−v4 F, v2, v1 is not a directed path in H
−v2 F, and v1 is not a directed path in H
−v1 F.

Lemma 5 suggests a simple strategy for finding a certifying path for x1 in F, if one exists. For each value v we search for a directed path vk**, . . . , v**1 from v = vk to v1 = η(x1) in H
−v F. If we find such a path vk**, . . . , v**1, we check for each subsequence vi, . . . , v1, 1 ≤ **i < k**, whether it is a directed path in H
−vi F. If the answer is NO for all i, then vk**, . . . , v**1 satisfies the conditions of Lemma 5. Hence the sequence of arguments in X whose values form P is a certifying path for x1 in F. If, however, the answer is YES for some **i < k**, we take the smallest i for which the answer is YES. Now the sequence vi**, . . . , v**1 satisfies the conditions of Lemma 5 and so gives rise to a certifying path for x1 in F. On the other hand, if there is no value v such that H
−v Fcontains a directed path from v to v1, then there is no certifying path for x1 in F. The pseudo code for this algorithm is given in Figure 6. Proposition 1. *The algorithm* DETECT CERTIFYING PATH *correctly returns a certifying path for* x1 in F =
(**X, A, V, η**) *if one exists and returns NO otherwise in time* O(|V | 2· (|X| + |A| + |V |)).

Proof. The correctness of DETECT CERTIFYING PATH follows from Lemma 5. For v ∈ V , building H
−v Fand finding a shortest directed path from v to v1 = η(x1), if one exists, takes linear time in the input size of F (which we estimate by the term O(|X| + |A| + |V |)). As we iterate over all vertices of V , and we check for at most |V | subsequences vi**, . . . , v**1 whether it is a directed path in H
−vi F, the claimed running time follows.

We are now ready to combine the above results to a proof of Theorem 2. Statement (A) of the theorem follows from Lemma 1 and Proposition 1. Statement (B) follows from Statement (A) and Lemma 2.