In computational complexity theory, the feedback vertex set problem is a graph-theoretical NP-complete problem. It was among the first problems shown to be NP-complete. The decision problem can be formalized as follows: INSTANCE: An undirected graph <math>G = (V, E)</math> and a positive integer <math>k</math>.

PropertyValue
dbpprop:abstract
  • In computational complexity theory, the feedback vertex set problem is a graph-theoretical NP-complete problem. It was among the first problems shown to be NP-complete. The decision problem can be formalized as follows: INSTANCE: An undirected graph <math>G = (V, E)</math> and a positive integer <math>k</math>. QUESTION: Is there a subset <math>X \subseteq V</math> with <math>|X| \leq k</math> such that <math>G</math> with the vertices from <math>X</math> deleted is cycle-free? Karp originally showed the problem NP-complete on directed graphs, but the undirected version is also NP-complete. The problem remains NP-complete for directed graphs with no in-degree or out-degree exceeding 2, and also for planar directed graphs with no in-degree or out-degree exceeding 3. It can be solved in polynomial time for reducible graphs. Note that the problem of deleting edges to make the graph cycle-free is equivalent to finding a minimum spanning tree, which can be done in polynomial time. On the other hand, the problem of deleting directed edges from a directed graph, called the feedback arc set problem, is also NP-complete. The corresponding NP optimization problem of minimizing the number of vertices to delete is APX-complete. The best known approximation is by a factor of 2. The feedback vertex set problem has applications in genome assembly and VLSI chip design.
  • Der Begriff Feedback Vertex Set bzw. kreiskritische Knotenmenge bezeichnet in der Komplexitätstheorie ein graphentheoretisches Entscheidungsproblem, das NP-vollständig ist.
  • Problem zbioru wierzchołków rozrywających cykle (ang. Feedback vertex set problem) jest to zagadnienie z teorii grafów, polegające na znalezieniu podgrafu X, w grafie G, takiego, że co najmniej k jego wierzchołków i krawędzi nie tworzy cyklu. Był pierwszym problemem wobec którego udowodniono, że jest to problem NP-zupełny.
dbpprop:hasPhotoCollection
rdf:type
rdfs:comment
  • In computational complexity theory, the feedback vertex set problem is a graph-theoretical NP-complete problem. It was among the first problems shown to be NP-complete. The decision problem can be formalized as follows: INSTANCE: An undirected graph <math>G = (V, E)</math> and a positive integer <math>k</math>.
  • Der Begriff Feedback Vertex Set bzw. kreiskritische Knotenmenge bezeichnet in der Komplexitätstheorie ein graphentheoretisches Entscheidungsproblem, das NP-vollständig ist.
  • Problem zbioru wierzchołków rozrywających cykle (ang. Feedback vertex set problem) jest to zagadnienie z teorii grafów, polegające na znalezieniu podgrafu X, w grafie G, takiego, że co najmniej k jego wierzchołków i krawędzi nie tworzy cyklu. Był pierwszym problemem wobec którego udowodniono, że jest to problem NP-zupełny.
rdfs:label
  • Feedback vertex set
  • Feedback Vertex Set
  • Problem zbioru wierzchołków rozrywających cykle
owl:sameAs
skos:subject
foaf:page
is dbpprop:disambiguates of
is owl:sameAs of