  Reachability problems in infinite-state systems are often subject to
extremely high complexity. This motivates the investigation of efficient
overapproximations, where we add transitions to obtain a system in which
reachability can be decided more efficiently. We consider bidirected
infinite-state systems, where for every transition there is a transition with
opposite effect.
  We study bidirected reachability in the framework of valence systems, an
abstract model featuring finitely many control states and an infinite-state
storage that is specified by a finite graph. By picking suitable graphs,
valence systems can uniformly model counters as in vector addition systems,
pushdowns, integer counters, and combinations thereof.
  We provide a comprehensive complexity landscape for bidirected reachability
and show that the complexity drops (often to polynomial time) from that of
general reachability, for almost every storage mechanism where reachability is
known to be decidable.
