feedback_vertex_set: Finding a feedback vertex set in a graph

In igraph/rigraph: Network Analysis and Visualization

Finding a feedback vertex set in a graph

Description

A feedback vertex set of a graph is a subset of vertices whose removal breaks all cycles in the graph. Finding a minimum feedback vertex set is an NP-complete problem, both on directed and undirected graphs.

Usage

feedback_vertex_set(graph, weights = NULL, algo = c("exact_ip"))

Arguments

graph	The input graph
weights	Potential vertex weights. If the graph has a vertex attribute called ‘weight’, and this argument is NULL, then the vertex attribute is used automatically. The goal of the feedback vertex set problem is to find a feedback vertex set with the smallest total weight.
algo	Specifies the algorithm to use. Currently, “exact_ip”, which solves the feedback vertex set problem with an exact integer programming approach, is the only option.

Value

A vertex sequence (by default, but see the return.vs.es option of igraph_options()) containing the feedback vertex set.

Related documentation in the C library

feedback_vertex_set().

See Also

Other structural.properties: bfs(), component_distribution(), connect(), constraint(), coreness(), degree(), dfs(), distance_table(), edge_density(), feedback_arc_set(), girth(), is_acyclic(), is_dag(), is_matching(), k_shortest_paths(), knn(), reciprocity(), subcomponent(), subgraph(), topo_sort(), transitivity(), unfold_tree(), which_multiple(), which_mutual()

Graph cycles feedback_arc_set(), find_cycle(), girth(), has_eulerian_path(), is_acyclic(), is_dag(), simple_cycles()

Examples

g <- make_lattice(c(3,3))
feedback_vertex_set(g)

igraph/rigraph documentation built on June 13, 2025, 1:44 p.m.