Uniconnected subgraph

Input

Directed graph $G = (V, A)$, positive integer $K \leq |A|$.

Question

Is there a subset $A' \subseteq A$ with $|A'| \geq K$ such that $G' = (V, A')$ has at most one directed path between any pair of vertices?

Classes

• NP-complete

Comments

Remains NP-complete for acyclic directed graphs.

Proofs

NP-complete

Transformation from Vertex Cover (Maheshwari, 1976).

Reducible from

• Vertex Cover

References

• Maheshwari, S. (1976). Traversal Marker Placement Problems Are NP-Complete ; CU-CS-092-76.