Feedback vertex set problem

(0,3)-colorable ∩ chordal
(1,1)-colorable
(1,2)-colorable ∩ chordal
(1,2)-polar ∩ chordal
(2,0)-colorable
(2,2)-colorable ∩ chordal
2-bounded bipartite
2-connected ∩ (4-fan,C_n+4,K₅ - e,S₃,H,K₃ ∪ 2K₁)-free
2-connected ∩ cubic ∩ planar
2-outerplanar
2-terminal series-parallel
2-tree
2-tree ∩ probe interval
(2K₂,3K₁,C₅,C₆,C₇,C₈,H,K_1,4,X₈₅)-free
(2K₂,3K₁,C₅,C₆,C₇,C₈,H,X₈₅)-free
(2K₂,3K₁,C₅,C₆,C₇,C₈)-free
(2K₂,3K₁)-free
(2K₂,4K₁,C₅,co-diamond)-free
(2K₂,4K₁,co-claw,co-diamond)-free
(2K₂,5K₁,C₅,K₃ ∪ 2K₁,P₃ ∪ 2K₁,C₆,C₇,C₈,K_1,4,K₅ - e,claw ∪ K₁,co-butterfly,co-cricket,co-dart,co-gem)-free
(2K₂,A,H)-free
(2K₂,C₄,C₅,S₃,co-rising sun,net)-free
(2K₂,C₄,C₅,S₃,net)-free
(2K₂,C₄,C₅,co-sun)-free
(2K₂,C₄,C₅,sun)-free
(2K₂,C₄,C₅)-free
(2K₂,C₄)-free
(2K₂,C₅,S₃,X₁₅₉,X₁₆₀,X₁₆₁,X₁₆₂,X₄₆,X₇₀,2P₃,3K₂,H,P₂ ∪ P₄,X₁,co-rising sun,house,net)-free
(2K₂,C₅,C₆,C₇,C₈,XC₁₁,co-claw,co-diamond)-free
(2K₂,C₅,C₆,C₇,C₈)-free
(2K₂,C₅,C₆,net)-free
(2K₂,C₅,T₂)-free
(2K₂,C₅)-free
(2K₂,2P₃,C₆)-free
(2K₂,C₆,C₈,K_1,4,odd anti-cycle)-free
(2K₂,C₆,odd anti-cycle)-free
(2K₂,P₆)-free
(2K₂,X₉₁,co-claw)-free
(2K₂,claw)-free
(2K₂,co-claw,co-diamond)-free
(2K₂,co-diamond)-free
(2K₂,house)-free
(2K₂,net)-free
(2K₂,odd anti-hole)-free
2K₂-free
2K₂-free ∩ probe cograph
2K₂-free ∩ probe trivially perfect
(2K₃ + e,3K₁,C₅,T₂,X₁₈,X₉₄,co-domino)-free
(2K₃,2K₃ + e,3K₁,A,H,T₂,X₁₈,X₄₅,co-domino)-free
(2K₃,2P₃,C_n+4,K₃ ∪ P₃)-free
(2K₃,3K₁,A,H,X₄₅)-free
(2K₃,C_n+4)-free
3-tree
3-tree ∩ planar
(3K₁,C₅,K₃ ∪ K₄,BW₃,K_3,4-e,T₂,X₁₈,X₉₂,X₉₃)-free
(3K₁,C₅,K₅ - e,C₆ ∪ K₁,C₇,K_3,3 ∪ K₁,K_3,3-e ∪ K₁,domino ∪ K₁)-free
(3K₁,C₅,C₆,P₆)-free
(3K₁,C₅,C₆,X₁₆₄,X₁₆₅,sunlet₄)-free
(3K₁,2P₃)-free
(3K₁,3K₂)-free
(3K₁,C₆)-free
(3K₁,E)-free
(3K₁,H)-free
(3K₁,K_1,5)-free
(3K₁,K₂ ∪ claw)-free
(3K₁,P₂ ∪ P₄)-free
(3K₁,P₆)-free
(3K₁,T₂,X₂,X₃,anti-hole)-free
(3K₁,X₁₇₂)-free
(3K₁,XC₁₂)-free
(3K₁,co-cross)-free
3K₁-free
(3K₂,C₄ ∪ P₂,C₅,P₂ ∪ P₄,P₅,S₃,X₁,X₄₆,X₇₀,3K₂,C₄ ∪ P₂,P₂ ∪ P₄,X₁,X₄₆,X₇₀,co-fish,co-rising sun,fish,house,net,rising sun)-free
(3K₂,C₆,P₇,X₁₆₄,X₁₆₅,odd-cycle,sunlet₄)-free
(3K₂,P,co-gem,house)-free
(3K₂,co-paw,odd anti-hole)-free
(3K₃,C_n+4)-free
(3P₃,C_n+4,P₃ ∪ P₄,P₅,X₁₀₂,X₁₈₀,X₁₈₁,X₁₈₂,X₁₈₃,A)-free
(4,0)-colorable
(4-fan,C_n+4,K₅ - e,S₃,X₁₀₀,X₁₀₁,X₁₀₂,H,K₃ ∪ 2K₁)-free
(4-fan,C_n+4,K₅ - e,S₃,H,K₃ ∪ 2K₁)-free
4-leaf power
(4K₁,C₇,S₃,X₁₇₅,X₁₇₆,X₄₂,X₃₆,claw,co-antenna,net,odd anti-hole)-free
(4K₁,C₇,X₁₉₅,X₁₉₆,X₃₈,X₃₉,W₅,X₁₉₄,X₈₆,X₈₈,X₈₉,X₉₀,house)-free
(4K₁,C₇,X₃₈,X₃₉,K_3,3 ∪ K₁,W₄ ∪ K₁,W₅,X₈₆,X₈₇,X₈₈,X₈₉,X₉₀,butterfly ∪ K₁,diamond)-free
(4K₁,C_n+4)-free
(4K₁,co-claw,co-diamond)-free
(4K₁,gem)-free
(4K₁,house)-free
(4K₁,net)-free
(4K₁,odd anti-hole,odd-hole)-free
4K₁-free
5-leaf power
(6,1)-chordal ∩ bipartite
6K₁-free
7K₁-free
(A,E,S₃,X₁,domino,hole,house,net,rising sun)-free
(A,T₂,odd-cycle)-free
(A,3P₃,C_n+4,P₃ ∪ P₄,X₁₀₂,X₁₈₀,X₁₈₁,X₁₈₂,X₁₈₃,house)-free
AT-free
AT-free ∩ claw-free
Apollonian network
B₀-VPG ∩ chordal
B₀-VPG ∩ strongly chordal
(C₄,C₅,C₆,C₇,C₈,H,K_1,4,X₈₅,triangle)-free
(C₄,C₅,C₆,C₇,C₈,H,X₈₅,triangle)-free ∩ K_1,4-free
(C₄,C₅,C₆,C₇,C₈,K_1,4,K₅,K₅ - e,K₃ ∪ 2K₁,P₃ ∪ 2K₁,claw ∪ K₁,butterfly,cricket,dart,gem)-free
(C₄,C₅,C₆,C₇,C₈,K_1,4,K₅,K₅ - e,K₃ ∪ 2K₁,P₃ ∪ 2K₁,claw ∪ K₁,butterfly,cricket,dart,gem)-free ∩ planar
(C₄,C₅,C₆,C₇,C₈)-free ∩ maximum degree 3 ∩ planar
(C₄,C₆,C₈,K_1,4,odd-cycle)-free
(C₄,C₆,C₈,K_1,4,odd-cycle)-free ∩ planar
C₄-free ∩ induced-hereditary pseudo-modular
(C₅,C₆ ∪ K₁,C₇,K_3,3 ∪ K₁,K_3,3-e ∪ K₁,K₅ - e,domino ∪ K₁,triangle)-free
(C₅,P,P₅,P,bull,co-gem,fork)-free
(C₅,P₅,gem)-free
(C₅,bull,co-gem,gem)-free
(C₅,co-gem,gem)-free
(C₅,co-gem,house)-free
(C_n+4 ∪ K₁,C(n,k),W₄,odd-cycle ∪ K₁,even anti-hole,net)-free
(C_n+4 ∪ K₁,C(n,k),X₄₂,T₂,X₂,X₃,odd-cycle ∪ K₁,even anti-hole,net)-free
(C_n+4 ∪ K₁,K_2,3,T₂,W_n+4,X₃₁,XF₂ⁿ⁺¹,XF₃ⁿ,C₆,X₃₇,X₉₀,domino,twin-C₅)-free
(C_n+4 ∪ K₁,K_2,3,T₂,C₆,X₁₀₃,X₃₇,X₈₈,X₉₀,diamond,domino,eiffeltower,net ∪ K₁,twin-C₅)-free
(C_n+4 ∪ K₁,K_2,3,T₂,X₉₀,domino,paw,twin-C₅)-free
(C_n+4 ∪ K₁,S₃ ∪ K₁,X₄₂,T₂,X₂,X₃,odd-cycle ∪ K₁,even anti-hole,net)-free
(C_n+4 ∪ K₁,S₃ ∪ K₁,X₄₂,T₂,X₂₀₅,X₂₀₆,X₂₀₇,X₂₀₈,odd-cycle ∪ K₁,even anti-hole,net)-free
(C_n+4 ∪ K₁,S₃,W₄,W₅,C₆,claw,net)-free
(C_n+4 ∪ K₁,S₃,W₄,odd-cycle ∪ K₁,even anti-hole,net)-free
(C_n+4,H)-free
(C_n+4,K₄)-free
(C_n+4,S₃ ∪ K₁,X₁₀₃,claw,eiffeltower,net ∪ K₁)-free
(C_n+4,S₃ ∪ K₁,claw,net)-free
(C_n+4,S₃,net)-free
(C_n+4,S₃)-free
(C_n+4,T₂,XF₂ⁿ⁺¹)-free
(C_n+4,T₂,net)-free
(C_n+4,X₅₉,longhorn)-free
(C_n+4,XF₁²ⁿ⁺³,XF₆²ⁿ⁺²,X₃₄,X₃₆,co-XF₂ⁿ⁺¹,co-XF₃ⁿ)-free
(C_n+4,claw,net)-free
(C_n+4,claw)-free
(C_n+4,odd-sun)-free
(C_n+4,sun)-free
C_n+4-free
(C_n+6,T₂,X₂,X₃,X₃₀,X₃₁,X₃₂,X₃₃,X₃₄,X₃₅,X₃₆,X₃₇,X₃₈,X₃₉,X₄₀,X₄₁,XF₂ⁿ⁺¹,XF₃ⁿ,XF₄ⁿ)-free
(C_n+6,T₂,X₂,X₃,X₃₀,X₃₁,X₃₂,X₃₃,X₃₄,X₃₅,X₃₆,XF₂ⁿ⁺¹,XF₃ⁿ,XF₄ⁿ,anti-hole,co-XF₁²ⁿ⁺³,co-XF₅²ⁿ⁺³,co-XF₆²ⁿ⁺²)-free
(C_n+6,T₂,X₂,X₃,X₃₀,X₃₁,X₃₂,X₃₃,X₃₄,X₃₅,X₃₆,XF₂ⁿ⁺¹,XF₃ⁿ,XF₄ⁿ,co-XF₁²ⁿ⁺³,co-XF₅²ⁿ⁺³,co-XF₆²ⁿ⁺²,odd anti-hole)-free
(C_n+6,T₂,X₂,X₃,X₃₀,X₃₁,X₃₂,X₃₃,X₃₄,X₃₆,XF₁²ⁿ⁺³,XF₂ⁿ⁺¹,XF₃ⁿ,XF₄ⁿ,XF₅²ⁿ⁺³,XF₆²ⁿ⁺²,C_n+6,T₂,X₂,X₃,X₃₀,X₃₁,X₃₂,X₃₃,X₃₄,X₃₆,co-XF₁²ⁿ⁺³,co-XF₂ⁿ⁺¹,co-XF₃ⁿ,co-XF₄ⁿ,co-XF₅²ⁿ⁺³,co-XF₆²ⁿ⁺²,odd anti-hole)-free
(C_n+6,T₂,X₂,X₃,X₃₀,X₃₁,X₃₂,X₃₃,X₃₄,X₃₆,XF₁²ⁿ⁺³,XF₂ⁿ⁺¹,XF₃ⁿ,XF₄ⁿ,XF₅²ⁿ⁺³,XF₆²ⁿ⁺²,C_n+6,T₂,X₂,X₃,X₃₀,X₃₁,X₃₂,X₃₃,X₃₄,X₃₆,co-XF₁²ⁿ⁺³,co-XF₂ⁿ⁺¹,co-XF₃ⁿ,co-XF₄ⁿ,co-XF₅²ⁿ⁺³,co-XF₆²ⁿ⁺²,odd-hole)-free
(C_n+6,X₃₇,claw,co-antenna,net,sun)-free
(C_n+6,odd-cycle)-free
Dilworth 2
(E,odd-cycle)-free
E-free ∩ bipartite
EPT ∩ chordal
(H,K₃ ∪ 2K₁,C_n+4,K₅ - e,X₁₀₀,X₁₀₁,X₁₀₂,co-4-fan,net)-free
(H,K₃ ∪ 2K₁,C_n+4,K₅ - e,co-4-fan,net)-free
Halin
Helly chordal
Helly chordal ∩ clique-chordal
Helly circle
Helly circular arc
Helly circular arc ∩ (C₇,odd-hole)-free
Helly circular arc ∩ concave-round
Helly circular arc ∩ perfect
Helly circular arc ∩ quasi-line
Helly circular arc ∩ self-clique
H_n,q grid
(K_1,4,odd-cycle)-free
(K_1,4,odd-cycle)-free ∩ planar
(K₂ ∪ K₃,X₉₀,C_n+4 ∪ K₁,T₂,co-domino,co-paw,co-twin-C₅)-free
(K₂ ∪ claw,triangle)-free
(K_2,3,K₄)-minor-free
(K₃ ∪ 3K₁,C_n+4,co-dart,co-gem)-free
(K_3,3,3,C_n+4)-free
(K_3,3,K_3,3+e,2P₃,C_n+4)-free
(K_3,3,C_n+4)-free
K₄-minor-free
(K₅,X₁₂₆,X₁₇₄,3K₂)-minor-free
N^*
(P,P₅,3K₂,gem)-free
(P,P₅,co-fork)-free
(P,co-butterfly,co-fork,co-gem)-free
(P,co-fork,co-gem)-free
(P,co-gem,house)-free
(P₃ ∪ 2K₁,C_n+4,X₁₀₂,X₂₀₄,co-gem)-free
P₄-indifference
(P₅,S₃,anti-hole,co-domino,co-gem)-free
(P₅,P,gem)-free
(P₅,anti-hole,co-domino,co-gem)-free
(P₅,bull,co-fork)-free
(P₅,bull,odd anti-hole)-free
(P₅,bull)-free
(P₅,gem)-free
(P₆,triangle)-free
PI
PI^*
(S₃,C_n+4,S₃ ∪ K₁,co-claw)-free
(S₃,C_n+4,T₂)-free
(S₃,C_n+4,co-claw,net)-free
(S₃,C_n+4,co-claw)-free
(S₃,C_n+4,net)-free
(S₃,net)-free ∩ chordal
(S₃,net)-free ∩ split
S₃-free ∩ chordal
SC 2-tree
SC 3-tree
SC k-tree, fixed k
(T₂,X₂₀₅,X₂₀₆,X₂₀₇,X₂₀₈,even-hole,odd-cycle)-free
X-conformal ∩ bipartite ∩ hereditary X-chordal
(X₁₀₃,C_n+4,S₃ ∪ K₁,net ∪ K₁,co-claw,co-eiffeltower)-free
(X₁₇₂,triangle)-free
(X₁₇₇,odd-cycle)-free
(X₃₄,X₃₆,XF₂ⁿ⁺¹,XF₃ⁿ,C_n+4,co-XF₁²ⁿ⁺³,co-XF₆²ⁿ⁺²)-free
(X₄₂,T₂,X₂₀₅,X₂₀₆,X₂₀₇,X₂₀₈,net)-free ∩ normal circular arc ∩ quasi-line
(XC₁₂,triangle)-free
(XC₁₂,triangle)-free ∩ planar
(XC₇,XC₁,XC₂,XC₃,XC₄,XC₅,XC₆,XC₈)-free
β-perfect ∩ co-β-perfect
β-perfect ∩ perfect
(2C₄,3K₂,C₆,E,P₂ ∪ P₄,P₆,X₂₅,X₂₆,X₂₇,X₂₈,X₂₉,odd anti-cycle)-free
(3K₂,C₆,P₇,X₁₆₄,X₁₆₅,sunlet₄,odd anti-cycle)-free
(A,T₂,odd anti-cycle)-free
(C_n+3 ∪ K₁,co-diamond,co-paw)-free
(C_n+4,H)-free
(C_n+4,T₂,X₃₁,co-XF₂ⁿ⁺¹,co-XF₃ⁿ)-free
(C_n+4,T₂,co-XF₂ⁿ⁺¹)-free
(C_n+4,X₅₉,co-longhorn)-free
(C_n+4,bull,co-dart,co-gem)-free
(C_n+4,co-claw,co-gem)-free
(C_n+4,co-claw)-free
(C_n+4,co-dart,co-gem)-free
(C_n+4,co-diamond)-free
(C_n+4,co-gem)-free
(C_n+4,co-sun)-free
(C_n+4,net)-free
(C_n+4,odd co-sun)-free
C_n+4-free
(C_n+6,odd anti-cycle)-free
(E,odd anti-cycle)-free
(K_1,4,co-paw)-free
(K_1,4,odd anti-cycle)-free
(P₇,star_1,2,3,sunlet₄,odd anti-cycle)-free
(P₇,star_1,2,3,odd anti-cycle)-free
(P₇,odd anti-cycle)-free
(T₂,X₂₀₅,X₂₀₆,X₂₀₇,X₂₀₈,even anti-hole,odd anti-cycle)-free
(T₂,co-cycle)-free
(T₃,X₈₁,co-cycle)-free
(T₃,co-cycle)-free
W_2n+3-free
(X₁₇₇,odd anti-cycle)-free
(X₃₇,co-diamond,even anti-cycle)-free
(XC₁₁,co-claw,co-diamond)-free
(XC₁₁,odd anti-cycle)-free
XC₁₁-free
(XC₁₂,co-cycle)-free
XC₁₂-free
XC₁₃-free
(claw ∪ 3K₁,odd anti-cycle)-free
(star_1,2,3,sunlet₄,odd anti-cycle)-free
(star_1,2,3,odd anti-cycle)-free
τ_k-perfect for all k >= 2
absolutely perfect
almost CIS
almost tree (1)
alternately orientable ∩ co-comparability
(anti-hole,co-domino,odd anti-cycle)-free
(anti-hole,odd anti-cycle)-free
b-perfect ∩ chordal
balanced ∩ chordal
basic 4-leaf power
biconvex
bipartite ∩ co-perfectly orderable
bipartite ∩ co-trapezoid
bipartite ∩ convex-round
bipartite ∩ cubic ∩ planar
bipartite ∩ girth >=9 ∩ maximum degree 3 ∩ planar
bipartite ∩ maximum degree 3
bipartite ∩ maximum degree 3 ∩ planar
bipartite ∩ mock threshold
bipartite ∩ probe interval
bipartite ∩ tolerance
bipartite ∩ weakly chordal
bounded bitolerance
bounded multitolerance
bounded tolerance
boxicity 2 ∩ co-bipartite
(bull,co-fork,co-gem)-free
(bull,co-gem,gem)-free
cactus
chordal
chordal ∩ circular arc ∩ claw-free
chordal ∩ (claw,net)-free
chordal ∩ claw-free
chordal ∩ clique-Helly
chordal ∩ clique-chordal
chordal ∩ co-chordal
chordal ∩ comparability
chordal ∩ diametral path
chordal ∩ dominating pair
chordal ∩ domination perfect
chordal ∩ dually chordal
chordal ∩ hamiltonian
chordal ∩ hamiltonian ∩ planar
chordal ∩ hereditary clique-Helly
chordal ∩ irredundance perfect
chordal ∩ maximal planar
chordal ∩ neighbourhood perfect
chordal ∩ odd-sun-free
chordal ∩ planar
chordal ∩ proper circular arc
chordal ∩ sun-free
chordal ∩ unipolar
chordal ∪ co-chordal
chordal bipartite
circle
circle ∩ diamond-free
circle graph with equator
circle-n-gon, fixed n
circle-trapezoid
circular arc
circular arc ∩ clique-Helly
circular arc ∩ co-bipartite
circular arc ∩ comparability
circular arc ∩ diamond-free
circular arc ∩ paw-free
circular arc ∩ perfect
circular interval
circular strip
(claw ∪ 3K₁,odd-cycle)-free
claw-free ∩ normal Helly circular arc
clique graphs of Helly circular arc
clique graphs of normal Helly circular arc
cliquewidth 3
cliquewidth 4
co-2-subdivision
co-β-perfect
co-biconvex
co-bipartite
co-bipartite ∩ concave-round
co-bipartite ∩ normal circular arc
co-bipartite ∩ proper circular arc
co-bithreshold ∩ split
co-chordal
co-chordal ∩ comparability
co-chordal ∩ superperfect
co-comparability
co-comparability ∩ comparability
co-comparability ∩ tolerance
co-comparability graphs of dimension d posets
co-comparability graphs of posets of interval dimension 2
co-comparability graphs of posets of interval dimension 2, height 2
co-comparability graphs of posets of interval dimension d
co-cycle-free
(co-diamond,even anti-cycle)-free
(co-diamond,house)-free
(co-gem,gem)-free
(co-gem,house)-free
co-interval
co-interval ∪ interval
co-interval bigraph
co-interval containment bigraph
co-leaf power
(co-paw,odd anti-hole)-free
co-paw-free
co-planar
co-probe cograph
co-proper interval bigraph
co-strongly chordal
co-threshold tolerance
comparability ∩ split
comparability graphs of dimension 2 posets
comparability graphs of posets of interval dimension 2, height 2
comparability graphs of semiorders
concave-round
containment graph of intervals
convex
cubic
cubic ∩ hamiltonian
cubic ∩ hamiltonian ∩ planar
cubic ∩ planar
d-trapezoid
directed path
doubly chordal
even anti-cycle-free
grid graph ∩ maximum degree 3
hamiltonian ∩ split
hereditary Helly
hereditary disk-Helly
hereditary dually chordal
hereditary perfect elimination bipartite
(hole,odd-cycle)-free
intersection graphs of parallelograms (squares)
interval bigraph
interval containment bigraph
k-outerplanar
k-path graph, fixed k
k-polygon
k-starlike
k-tree, fixed k
leaf power
leaf power ∩ min leaf power
leaf power ∪ min leaf power
maximal outerplanar
maximum degree 3
maximum degree 3 ∩ planar ∩ triangle-free
min leaf power
mock threshold ∩ split
normal Helly circular arc
normal circular arc
odd anti-cycle-free
(odd-cycle,star_1,2,3,sunlet₄)-free
(odd-cycle,star_1,2,3)-free
outerplanar
overlap
partial 2-tree
partial 3-tree
partial 3-tree ∩ planar
partial 4-tree
partial k-tree, fixed k
path orderable
permutation
planar of maximum degree 3
power-chordal
probe P₄-reducible
probe P₄-sparse
probe bipartite chain
probe bipartite distance-hereditary
probe co-trivially perfect
probe co-trivially perfect ∩ probe trivially perfect
probe cograph
probe distance-hereditary
probe proper interval
probe ptolemaic
probe threshold
probe trivially perfect
probe unit interval
proper Helly circular arc
proper circular arc
proper tolerance
pseudo-split
rigid circuit
rooted directed path
series-parallel
split
split ∩ strongly chordal
split ∩ superperfect
square of tree
strong asteroid free
strong tree-cograph
strongly chordal
threshold signed
threshold tolerance
tolerance ∩ triangle-free
trapezoid
tree-cograph
treewidth 2
treewidth 3
treewidth 4
treewidth 5
triad convex
triangulated
undirected path
unicyclic
unit Helly circle
unit Helly circular arc
unit circular arc
unit tolerance

Input:	A graph G in this class and an integer k.
Output:	True iff G contains a set S of vertices, with \|S\| <= k, such that every cycle in G contains a vertex from S.

Problem: Feedback vertex set

Linear

Polynomial

GI-complete

NP-hard

NP-complete

coNP-complete

Open

Unknown to ISGCI