Obdobje trajanja: 1. 10. 2022 – 30. 9. 2025
Projekt financira: ARIS
Naziv projekta: Drevesno neodvisnostno število grafov
Vrsta projekta: Razvojno raziskovalni projekt
Vloga FIŠ: Partner
Vodilni partner: UP Famnit
Vodja projekta: prof. dr. Martin Milanič
Vodja projekta na FIŠ: izr. prof. dr. Borut Lužar
Kratek opis projekta:
Številni algoritmični problemi na grafih so bili obširno raziskovani tako v matematiki kot tudi v računalništvu, zaradi njihovih mnogih uporab na različnih področjih. Vendar za številne praktično pomembne probleme teorija računske kompleksnosti nakazuje — z zanašanjem med drugim na razvpito P!=NP domnevo — da učinkovito natančno ali približno reševanje problemov v splošnem ni mogoče. Eden od možnih pristopov k algoritmično težkim problemom je opredelitev omejitev na vhodnih primerih, pri katerih problem postane učinkovito rešljiv. V primeru problemov na grafih so eno osrednjih orodij za to nalogo postala različne mere strukturne kompleksnosti grafov, splošno znane kot širinski parametri grafov. V literaturi so bili razviti številni algoritmični metaizreki za različne parametre širine grafa, vključno z drevesno širino, vejitveno širino, klično širino, rangovno širino, Booleovo širino, mim-širino in v zadnjem času tudi širino dvojčkov.
Kljub vse večji raznolikosti širinskih parametrov grafov in z njimi povezanih algoritmičnih rezultatov, obstajajo določeni dobro strukturirani razredi grafov, za katere so vsi zgoraj našteti širinski parametri neomejeni, na primer razred tetivnih grafov. Ima pa ta razred zanimivo lastnost v povezavi s klasičnim širinskim parametrom grafov, drevesno širino. Ta parameter meri, grobo rečeno, kako podoben drevesu je graf. Za grafe z velikimi klikami velja, da imajo veliko drevesno širino; v tetivnih grafih pa velja tudi obratno. Pred kratkim so Dallard, Milanič in Štorgel začeli sistematično preučevati (tw, omega)-omejene razrede grafov, pri katerih je ta zadosten pogoj za veliko drevesno širino tudi potreben. Družina (tw, omega)-omejenih razredov grafov predstavlja združitven okvir za številne zelo različne družine grafov obravnavane v literaturi in vsebuje dobre algoritmične lastnosti povezane s problemoma največje klike in barvanja grafov. Zanimiv odprt problem je, ali ima (tw, omega)-omejenost nadaljnje algoritmične posledice, na primer, za probleme povezane z neodvisnimi množicami.
Da bi odgovorili na to vprašanje, so Dallard, Milanič in Štorgel pred kratkim uvedli koncept drevesnega neodvisnostnega števila grafov. Gre za nov min-maks širinski parameter grafov, povezan z drevesnimi dekompozicijami. Iz Ramseyjevega izreka sledi, da omejeno drevesno neodvisnostno število implicira (tw, omega)-omejenost. Razredi grafov omejenega drevesnega neodvisnostnega števila vključujejo različne družine razredov grafov, podedujejo vse dobre algoritmične lastnosti (tw, omega)-omejenih razredov grafov in imajo dodatne dobre lastnosti v zvezi s problemom neodvisne množice in sorodnimi problemi. Naši preliminarni rezultati nakazujejo, da je drevesno neodvisnostno število pomemben dodatek v zbirko orodij v strukturni in algoritmični teoriji grafov. Ne tvori le skupne posplošitve drevesne širine in tetivnosti, ampak je povezano tudi s slavno domnevo Erdősa in Hajnala in s hitro razvijajočo se teorijo hi-omejenosti. Vse te motivacije vodijo do glavnega cilja predlaganega projekta: temeljite študije drevesnega neodvisnostnega števila, s končnim ciljem razvoja teorije te nove invariante grafov. Naš cilj je raziskati številna pomembna vprašanja, razdeljena na dve medsebojno povezani raziskovalni temi (Tema 1: temelji, Tema 2: izboljšave), vsaka z več podnalogami. Pričakujemo, da bo predlagan projekt dodatno utemeljil uporabnost drevesnega neodvisnostnega števila in z njim povezanih širinskih parametrov grafov, kar bo pripomoglo k povečanemu razumevanju strukturnih lastnosti (tw, omega)-omejenih razredov grafov in računske kompleksnosti različnih grafovskih optimizacijskih problemov na takih razredih. Na primer, za probleme povezane z neodvisnimi množicami.
Projekt financira:
