Uniconnected subgraph

In graph theory, a uniconnected subgraph is a directed graph that has at most one path between any pair of vertices.^[1][2]

Given a directed graph ${\displaystyle G=(V,E)}$, where ${\displaystyle V}$ denotes the set of vertices and ${\displaystyle E}$ denotes the set of edges, a subgraph ${\displaystyle G'=(V,E')}$ where ${\displaystyle E'\subseteq E}$ is called uniconnected if for every pair of vertices ${\displaystyle u,v\in V}$, there exists at most one directed path from ${\displaystyle u}$ to ${\displaystyle v}$ in ${\displaystyle G'}$.^[1]

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 ${\displaystyle \rho _{1}\neq \rho _{2}}$ that begin and end at the same pair of states.^[3]

The maximal uniconnected subgraph problem (also called the uniconnected subgraph problem or minimal marker placement problem^[3]) involves finding the largest subset of edges from a directed graph that forms a uniconnected subgraph. More formally, given a directed graph ${\displaystyle G=(V,A)}$ and a positive integer ${\displaystyle K<|A|}$, the decision problem asks whether there exists a subset ${\displaystyle A'\subseteq A}$ with ${\displaystyle |A'|\geq K}$ such that ${\displaystyle G'=(V,A')}$ is uniconnected.^[2]

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 ${\displaystyle E^{*}\subseteq E}$ of minimum cardinality such that ${\displaystyle G'=(V,E\setminus E^{*})}$ is uniconnected.^[1]

The uniconnected subgraph problem is NP-complete.^[2] For acyclic directed graphs (including acyclic flow graphs with a single source and sink), the problem remains NP-complete.^[1][2] This was proven by Maheshwari (1976) through a polynomial-time reduction from the vertex cover problem.^[1]

The problem remains NP-complete even with strong restrictions on the graph, such as small indegree and outdegree.^[3] Furthermore, even finding an ${\displaystyle \varepsilon }$-approximate solution to the problem is NP-complete for any ${\displaystyle \varepsilon >0}$, where an ${\displaystyle \varepsilon }$-approximate algorithm for a minimization problem produces a solution with cardinality ${\displaystyle {\tilde {F}}}$ such that ${\displaystyle \left|{\frac {F^{*}-{\tilde {F}}}{F^{*}}}\right|<\varepsilon }$, with ${\displaystyle F^{*}}$ being the cardinality of the optimal solution and ${\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.^[1][3]

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.^[1]

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.^[1]

In transactional Web services, the uniconnected subgraph problem arises when determining minimal logging requirements. Services modeled as finite state machines require logging of certain transitions to enable recovery through compensation in case of failure. The problem of finding the minimal set of transitions to log such that any execution can be uniquely determined from the partial log is equivalent to the uniconnected subgraph problem.^[3]

• Graph connectivity
• Directed acyclic graph
• Path (graph theory)
• NP-completeness
• Software testing
• Finite-state machine