cycleindependent

Cycleindependent is a term used in graph theory to describe a property of a subset of vertices of a graph G=(V,E). A cycleindependent set S⊆V is one whose induced subgraph G[S] contains no cycles; in other words, G[S] is a forest. Equivalently, S is cycleindependent if every cycle of G contains at least one vertex outside S. This concept is often described as an acyclic induced subgraph or an induced forest in some literature.

Formally, for a graph G=(V,E), a subset S⊆V is cycleindependent if G[S] is acyclic. The size of the largest cycleindependent set in a graph G is called the cycleindependent number, sometimes denoted ci(G). There is a close relationship to the minimum feedback vertex set F (a set of vertices whose removal makes the graph acyclic): G−F is acyclic for a feedback vertex set F, so |V|−|F| is a cycleindependent set. Consequently ci(G)=|V|−fvs(G) in many discussions.

Examples help illustrate the concept. In a tree, the entire vertex set is cycleindependent since the tree itself has no cycles. In a cycle graph C_n, any subset that omits at least one vertex is cycleindependent, and the maximum size is n−1.

Computationally, finding a maximum cycleindependent set is NP-hard for general graphs, since it is equivalent to finding a maximum induced forest. It is also related to the NP-hard problem of determining a minimum feedback vertex set. Some restricted graph classes admit polynomial-time algorithms or better approximations.

Notes: the term cycleindependent is not universally standardized; some sources prefer “induced forest” or “acyclic induced subgraph.” See also induced subgraph, independent set, forest, and the maximum induced forest problem.