In graph theory, a uniconnected subgraph is a directed graph that has at most one path between any pair of vertices.
Definition Given a directed graph G = ( V , E ) {\displaystyle G=(V,E)} , where V {\displaystyle V} denotes the set of vertices and E {\displaystyle E} denotes the set of edges, a subgraph G ′ = ( V , E ′ ) {\displaystyle G'=(V,E')} where E ′ ⊆ E {\displaystyle E'\subseteq E} is called uniconnected if for every pair of vertices u , v ∈ V {\displaystyle u,v\in V} , there exists at most one directed path from u {\displaystyle u} to v {\displaystyle v} in G ′ {\displaystyle G'} . In the context of finite state machines, a graph obtained by deleting a set of transitions from the original FSM is uniconnected if there does not exist a pair of paths ρ 1 ≠ ρ 2 {\displaystyle \rho _{1}\neq \rho _{2}} that begin and end at the same pair of states.
Maximal uniconnected subgraph problem The maximal uniconnected subgraph problem (also called the uniconnected subgraph problem or minimal marker placement problem) involves finding the largest subset of edges from a directed graph that forms a uniconnected subgraph. More formally, given a directed graph G = ( V , A ) {\displaystyle G=(V,A)} and a positive integer K < | A | {\displaystyle K<|A|} , the decision problem asks whether there exists a subset A ′ ⊆ A {\displaystyle A'\subseteq A} with | A ′ | ≥ K {\displaystyle |A'|\geq K} such that G ′ = ( V , A ′ ) {\displaystyle G'=(V,A')} is uniconnected. Equivalently, the problem can be stated as finding the smallest subset of edges whose removal from a directed graph results in a uniconnected subgraph: find a set E ∗ ⊆ E {\displaystyle E^{*}\subseteq E} of minimum cardinality such that G ′ = ( V , E ∖ E ∗ ) {\displaystyle G'=(V,E\setminus E^{*})} is uniconnected.
Computational complexity The uniconnected subgraph problem is NP-complete. For acyclic directed graphs (including acyclic flow graphs with a single source and sink), the problem remains NP-complete. This was proven by Maheshwari (1976) through a polynomial-time reduction from the vertex cover problem. The problem remains NP-complete even with strong restrictions on the graph, such as small indegree and outdegree. Furthermore, even finding an ε {\displaystyle \varepsilon } -approximate solution to the problem is NP-complete for any ε > 0 {\displaystyle \varepsilon >0} , where an ε {\displaystyle \varepsilon } -approximate algorithm for a minimization problem produces a solution with cardinality F ~ {\displaystyle {\tilde {F}}} such that | F ∗ − F ~ F ∗ | < ε {\displaystyle \left|{\frac {F^{*}-{\tilde {F}}}{F^{*}}}\right|<\varepsilon } , with F ∗ {\displaystyle F^{*}} being the cardinality of the optimal solution and F ~ {\displaystyle {\tilde {F}}} being the cardinality of the approximate solution. This implies that any polynomial-time approximation algorithm for this problem will produce arbitrarily bad outputs on some inputs.
Applications
Software testing Uniconnected subgraphs have applications in software testing, particularly in the optimal placement of software monitors called traversal markers. When programs are viewed as flow graphs, the problem of optimally placing traversal markers to identify test paths is equivalent to the maximal uniconnected subgraph problem for acyclic flow graphs. The traversal marker placement problem seeks to find the minimal number of locations needed to place monitors such that each path from source to sink in the program's flow graph covers a unique subset of monitored edges. The deletion of these traversal marker edges results in a uniconnected subgraph.
… excerpt ends here. Continue reading the full article.
