Univerza na Primorskem
Fakulteta za matematiko, naravoslovje in informacijske tehnologije
Več informacij o projektu / More info about the project
Opis / Description
SLO:
Š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 algoritemični metateoremi 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, tj. razrede, pri katerih je ta zadosten pogoj za veliko drevesno širino — prisotnost velike klike — 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š <span style="left: calc(var(--scale-factor)*552.47px); top: calc(var(--scale-factor)*116.50px); font-size: calc(var(--scale-factor)*10.70px); font-family: sans-serif; transform: scaleX(1.0376