
feedback vertex settu

graph sidhaanthathinte ganithashaasthra vibhaagathil, oru graafinte feedback vertex settu (eph. vii. ezz) ennathu oru koottam vertisukalaanu, avaa neekkam cheiyunnathu oru graphine saikkilukalillaathe avasheshippikkunnu ("neekkam cheyyuka" ennaal vertex athinaduthulla ellah arikukalum illaathaakkuka ennaanu ardhamaakkunnathu). thulyamaayi, oro eph. vii. silum graphile eathenkilum saikkilinte oru sheershakamenkilum adangiyirikkunnu. oru graafinte feedback vertex settu nambar oru ettavum cheria feedback vertex settinte valuppamaan. minimum feedback vertex settu prashnam oru enpi-complete prasnamaanu; enpi-complete aanennu kaanikkunna aadya prasnangalil onnaanith. operating sisttangal, daattaabes sisttangal, vlc chipp design ennivayil ithinu vishalamaaya aaplikkeshanukalundu.
nirvachanam.
eph. vii. ezz. theerumaana prashnam iprakaaramaanu
formula 6 ll ninnu formula 5 neekkam cheythathinushesham avasheshikkunna graph formula 7 oru induced phoorast (rep. directed graafukalude kaaryatthil oru induced directed asyclic graph). athinaal, oru graphil ettavum kuranja eph. vii. kall kandethunnathu paramavadhi induced phoorast (rep. directed graafukalude kaaryatthil paramavadhi induced directed asyclic graph).
enn. pii.-kaadinyam.
 directed" graafukalude ettavum kuranja efvs prashnam enpi-complete aanennu kaanichu. paramavadhi inn-digri, outtu-digri randulla directed graafukalilum paramavadhi inn-digri, outtu-digri moonninumulla directed planner graafukalilum prashnam enn. pii. poornnamaayi thudarunnu. 
kaarppinte kuravu soochippikkunnathu "dishaabodhamillaatha" graafukalile efvs prashnatthinte enpi-poornnathayaanu, avide prashnam paramavadhi digri naalile graafukalil enpi-haard aayi thudarunnu. paramavadhi moonnu digri graafukalil polynomial samayat eph. vii. ezz prashnam pariharikkan kazhiyum.
krithyamaaya algorithangal.
oru minimum feedback vertex settinte valuppam kandethunnathinulla anubandha enpi opttimaiseshan prashnam "oo" (1.7347 "enn") samayat pariharikkan kazhiyum, ivide "enn" ennathu graphile vertisukalude ennamaanu. eee algoritam yadhaarthathil oru paramavadhi induced phoorast kanakkakkunnu, atharamoru vanam labhikkumbol, athinte poorakam oru minimum feedback vertex settaanu. oru graphile minimum feedback vertex settukalude ennam "o" (1.8638 "n") kondu parimithappedutthiyirikku. directed feedback vertex settu prashnam ippozhum "o *" (1.9977 "n") samayat pariharikkan kazhiyum, ivide "n" ennathu thannirikkunna directed graphile vertisukalude ennamaanu. directed, directed prashnangalude paaraameettar cheytha pathippukal sthira-paaraameettar tractable aanu.
paramavadhi digri moonnu enna dishaabodhamillaatha graafukalil, feedback vertex settu prashnam polynomial samayat pariharikkanaakum, ithu leanier maatroyidukalude matroid paarity prashnatthinte oru udaaharanamaayi parivartthanam cheiyunnathiloode.
ekadesha kanakk.
dishaabodhamillaatha prashnam apx-poornnamaanu. thaazhepparayunna vasthuthakalil ninnaan ithu pinthudarunnathu.
dishaabodhamillaatha graafukalekkurichulla ettavum ariyappedunna ekadesha algoritam randinte gadakamaanu. 
ithinu vipareethamaayi, prashnatthinte directed pathipp ekadeshamaayi kanakkakkaan valare budhimuttaanennu thonnunnu. theliyikkappedaathathum ennaal saadhaaranayaayi upayogikkunnathumaaya computational kaadinya anumaanamaaya athulyamaaya geyim anumaanathinu keezhil, polynomial samayathile eathenkilum sthiramaaya gadakathinullil prashnam ekadeshamaayi kanakkaakkunnath budhimuttaanu. ithe kaadinyam phalam yadhaarthathil adutha bandhamullah feedback arck settu prashnathinu theliyikkappettirumnum feedback arck settu prashnavum directed graafukalile feedback vertex settu prashnavum parihara valuppangal samrakshikkumbol parasparam kuraykkaan kazhiyunnathinaal, randaamathethinu ithu baadhakamaan. 
athirukal.
erdos-posa sidhaantham anusarichu, oru minimum feedback vertex settinte valuppam thannirikkunna graphile paramavadhi vertex-disjoyint saikkilukalude logarithamik gadakathinullilaanu.