On persistent directed graphs
Jørgen Bang‐Jensen, Tibor Jordán · Networks · 2008
Abstract The concept of persistent directed graphs was introduced by Hendrickx et al. to help analyze the stability of autonomous agent systems. They provided a combinatorial characterization for persistence but the complexity of testing persistence remained open. In this note we show that for directed graphs D with ∑vεV(D) min{δD(v), 2} ≤ 2∣V(D)∣ − 3 persistence can be tested in polynomial time, where δD(v) denotes the out‐degree of vertex v in D. This family of directed graphs includes acyclic digraphs (for which an efficient algorithm was known) as well as all digraphs with a leader‐follower structure. We also discuss some related orientation problems. Among others we point out that the existence of an acyclic persistent orientation can be tested in polynomial time for all graphs. © 2008 Wiley Periodicals, Inc. NETWORKS, 2008