Similarly to BF, BFD detects the improper input—a graph G with a negative cycle reachable from s—in V 1 rounds.6 Let us show a way to also enjoy the neg(G) bound and its derivatives for the improper input case. The following statement is straightforward.