wiki_research

personal research wiki
git clone https://a3nm.net/git/wiki_research/
Log | Files | Refs

minimum_feedback_vertex_set (480B)

      1 # Minimum feedback vertex set
      2 
      3 [computational_problem] of finding minimum-[cardinality] [feedback_vertex_set]
      4 
      5 [np_complete]
      6 - already on [graph_directed] with maximal [indegree] 2 and maximal [outdegree] 2
      7   - and on [directed_planar_graph] with maximal [indegree] 3 and maximal [outdegree] 3
      8 - and on [undirected_graphs] with [maximal_degree] 4
      9   - [ptime] on graphs with maximal degree 3
     10     - reduction to [matroid] parity?
     11 
     12 Up: [computational_problem], [feedback_vertex_set]