Finding a feedback vertex set in a graph

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.

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.

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()

Related documentation in the C library

feedback_vertex_set().

Examples

g <- make_lattice(c(3,3))
feedback_vertex_set(g)
#> + 2/9 vertices, from a4d3999:
#> [1] 2 8