Example 6. Consider again the value-based system F of Example 2. The proponent wants to prove that argument a is subjectively accepted in F and asserts a with her first move. Now, it is the opponent's turn. He has no other choice but to assert b (the only argument different from a with the same value as a). Now, it is again the proponent's turn. She must assert an argument x /∈ {**a, b**} that attacks b but does not attack a. Argument d satisfies this property (it happens that this is the only choice). Next, the opponent asserts c, and the proponent asserts f, and it is again the opponent's turn. The only argument with the same value as f is argument e, but e does not attack any of the arguments in {**a, d, f**}. Hence, the proponent wins. The sequence of arguments (**a, b, d, c, f**) produced by this play is indeed a certifying path for a in F. Hence a is subjectively accepted.

## 3.4 Polynomial-Time Algorithm For Bipartite Value-Based Systems Of Value-Width 2

In this subsection we prove Theorem 2. Throughout this section, we assume that we are given a bipartite valuebased system F = (**X, A, V, η**) together with a query argument x1. Furthermore, let Xeven and Xodd be the subsets of X containing all arguments x such that the length of a shortest directed path in F from x to x1 is even and odd, respectively.

Lemma 3. Let C = (x1, z1, . . . , xk, zk, t) be a certifying path for x1 in F*. Then* { xi| 1 ≤ i ≤ k }∪{t} ⊆ X**even**
and { zi| 1 ≤ i ≤ k } ⊆ Xodd.

Proof. The claim follows easily via induction on k by using the properties of a certifying path and the fact that F is bipartite.

Based on the observation of Lemma 3, we construct an auxiliary directed graph HF := (**V, E**) as follows.

The vertex set of HF is the set V of values of F. There is a directed edge from u to v if and only if there is an argument x ∈ Xeven with η(x) = u and an argument z with η(z) = v such that (**x, z**) ∈ A. Note that z ∈ Xodd since F is bipartite.

Lemma 4. If C = (x1, z1, . . . , xk, zk, t) is a certifying path for x1 in F*, then* (η(t), η(xk)**, . . . , η**(x1)) *is a* directed path from η(t) to η(x1) in HF .

Proof. By the definition of a certifying path, we have (**t, z**k) ∈ A and for every 2 ≤ i ≤ k it holds that
(xi, zi−1) ∈ A. Lemma 3 implies that for t and xi are contained in Xeven for every 1 ≤ i ≤ k, and hence (η(t), η(xk)),(η(xi), η(xi−1)) ∈ E for every 1 < i ≤ k.

Lemma 4 tells us that each certifying path in F gives rise to a directed path in HF .

Example 7. Figure 5 shows a bipartite value-based system F and the associated auxiliary graph HF . The query argument is x1. Hence Xeven = {x1**, . . . , x**5} and Xodd = {z1**, . . . , z**5}. The query argument x1 is subjectively accepted in F as C = (x1, z1, x2, z2, x4, z4, x5) is a certifying path for x1 in F. Indeed, C gives rise to the directed path v5, v4, v2, v1 (i.e., η(x5), η(x4), η(x2), η(x1)) in HF , as promised by Lemma 4.

It would be desirable if we could find certifying paths by searching for directed paths in HF . However, not every directed path in HF gives rise to a certifying path in F. To overcome this obstacle, we consider for each value v ∈ V the subgraph H
−v Fof HF which is obtained as follows:
If there is an argument z ∈ Xodd ∩ η
−1(v) that is not attacked by some equivalued argument, then for every argument y ∈ Xeven that is attacked by z we remove the vertex η(y) from HF .

Figure 5 shows the graphs H
−v Ffor the value-based system F of Example 7.

Lemma 5. *Consider an odd-length sequence* C = (x1, z1, . . . , xk, zk, t) of distinct arguments of a bipartite value-based system F of value width 2. Then C is a certifying path for x1 in F *if and only if the following* conditions hold:
(1) η(xi) = η(zi) for 1 ≤ i ≤ k.

(2) (η(t), η(xk)**, . . . , η**(x1)) *is a directed path from* η(t) to η(x1) in H
−η(t)
F.

(3) None of the sub-sequences η(xi)**, . . . , η**(x1)*is a directed path from* η(xi)to η(x1)in H
−η(xi)
Ffor 1 ≤ i ≤ k.