Borsik Nóra Anna: Megszorított Feedback arc set és sorbarendezési feladatok

Önálló projekt, szakmai gyakorlat II

2022/23 II. félév

Témavezető:
Madarasi Péter (ELTE TTK, Operációkutatási Tsz.)

Egy élsúlyozott irányított gráf minden v csúcsára adott egy f(v) alsó és egy g(v) felső korlát. Szeretnénk eldönteni, hogy létezik-e olyan csúcssorrend, amely szerint minden v csúcs bal súlyozott kifoka f(v) és g(v) között van. A fenti kérdés NP-teljes, viszont polinom időben megoldható, amikor vagy csak alsó, vagy csak felső korlát adott. Speciális esetként az is eldönthető, hogy egy irányított gráf felbomlik-e egy befenyves és egy aciklikus gráf uniójára.

A projekt célja ezen kérdéskör és néhány kapcsolódó megszorított Feedback Arc Set feladat vizsgálata. Ilyen feladat például, hogy mikor bontható fel egy irányított gráf egy aciklikus és egy befenyő uniójára?