Hajirasouliha in Raphael sta pred nekaj leti (WABI 2014) predlagala model za študij mešanih vzorcev tumorjev, izmerjenih prek dane množice DNA ali proteinskih zaporedij, dobljenih z metodami visokozmogljivostnega sekvenciranja. Problem je povezan z razumevanjem razvoja tumorja in kritičnih rakastih mutacij. Formulacija Hajirasoulihe in Raphaela sprašuje po takem razcepu vrstic binarne matrike, da nastala matrika ustreza pogoju popolne filogenije in ima med vsemi matrikami s to lastnostjo najmanjše število vrstic. V prispevku smo ovrgli številne trditve o tem problemu, vključno z dokazom NP-polnosti problema. Z drugačnim pristopom smo pokazali, da problem dejansko je NP-težek. Dokazali smo tudi NP-težkost variante problema, ki smo jo uvedli v članku. Razvili smo učinkovit (sicer ne nujno optimalen) hevrističen algoritem, ki temelji na barvanju komplementov primerljivostnih grafov, in algoritem polinomske časovne zahtevnosti za optimalno reševanje problema na matrikah, v katerih noben stolpec ni vsebovan v paru konfliktnih stolpcev. Implementacije algoritmov so prosto dostopne na spletni strani https://github.com/alexandrutomescu/MixedPerfectPhylogeny.
COBISS.SI-ID: 1538780868
Ko je obravnaval svojo spektralno mejo za neodvisnostno število grafa, je Herbert Wilf leta 1986 zastavil vprašanje, kateri grafi dopuščajo lastni vektor, ki sestoji samo iz +1/-1 komponent? Dokažemo, da je Wilfov problem NP-poln, pa tudi, da je množica grafov, ki imajo +1/-1 lastni vektor precej bogata, saj je zaprta za številne različne kompozicije grafov.
COBISS.SI-ID: 1538772420
Poglavitni cilj tega interdisciplinarnega članka je klasifikacija vseh preslikav na končnem analogu prostora Minkowskega poljubne dimenzije n, ki slikajo pare različnih dogodkov svetlobnega tipa v pare različnih dogodkov svetlobnega tipa. Pri tem ni privzeta niti bijektivnost preslikav niti ohranjanje omenjene lastnosti v obratni smeri, tj. iz kodomene v domeno. Popolna klasifikacija je podana v mnogih primerih, ki vključujejo dimenzije n, ki so deljive s 4 ter lihe dimezije vsaj 9. V splošnem je pokazano, da je obstoj tovrstnih preslikav, ki niso bijektivne, neposredno povezan z obstojem ovoidov v ortogonalnem polarnem prostoru, kar predstavlja pomemben problem v končni geometriji. Slednji je odprt že nekaj desetletij kljub številnim raziskavam na tem področju. Dokazi temeljijo na preučevanju jedra afinega polarnega grafa, kar med drugim privede do sorodnih rezultatov, kot sta jih pred tem za točkovni graf polarnega prostora dognala Cameron in Kazanidis (2008).
COBISS.SI-ID: 17898329