Temeljni projekt J1-4008
Drevesno neodvisnostno število grafov

 

Naslov projekta: Drevesno neodvisnostno število grafov

Vodja projekta: Martin Milanič

Šifra projekta: J1-4008.

Tip projekta: temeljni projekt.

Financer: Javna agencija RS za raziskovalno dejavnost (ARRS).

Raziskovalno področje (ARRS): 1.01.00 - Naravoslovno-matematične vede / Matematika.

Trajanje projekta: 1. 10. 2022 - 30. 9. 2025.

Cenovna kategorija projekta: B.

Letni obseg projekta: 1.46 FTE (2.481 raziskovalnih ur).

Sicris profil projekta je dostopen tukaj.

Raziskovalne organizacije v okviru katere se izvaja projekt:

Univerza na Primorskem, Fakulteta za matematiko, naravoslovje in informacijske tehnologije
Univerza v Ljubljani, Fakulteta za matematiko in fiziko
Univerza v Mariboru, Fakulteta za naravoslovje in matematiko
Fakulteta za informacijske študije - FIŠ

Člani raziskovalnega projekta:

Martin Milanič (ARRS šifra 30211)

Nina Chiarelli (ARRS šifra 35452)

Edward Tauscher Dobson (ARRS šifra 34109)

Matjaž Krnc (ARRS šifra 34562)

Štefko Miklavič (ARRS šifra 21656)

Peter Muršič (ARRS šifra 53028)

Blas Fernandez (ARRS šifra 52892)

Nevena Pivač (ARRS šifra 50673)

Riste Škrekovski (ARRS šifra 15518)

Mirko Petrushevski (ARRS šifra 55615)

Slobodan Filipovski (ARRS šifra 37715)

Boštjan Brešar (ARRS šifra 17005)

Borut Lužar (ARRS šifra 31670)

Mirza Krbezlija (ARRS šifra 55941)

Kenny Štorgel (ARRS šifra 53598)

 

Povzetek 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 domnevo, da je P ≠ NP—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 postale 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 širinske parametre grafov, 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 je graf drevesu. 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 ima 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 zahtevnosti različnih grafovskih optimizacijskih problemov na takih razredih.