Mapping Graphs to Trees : Partition Trees, Leaf Powers and Decompositions

Abstract

Mange anvendelsar i informatikken kan kokast ned til å finne struktur i datamengder. Datamengder kan gjerne framstillast som grafar, og mange slags strukturar kan framstillast som tre. Difor er det ofte ønskjeleg å overføre ein graf til eit tre, for at strukturen som finst i dataa som er framstilte i grafen skal kome til syne. I denne avhandlinga legg me fram bidrag til forståinga vår av tre einskilde typar overføringar frå grafar til tre: Spaltetre av hjørne og kantar; lauv-røter og lauv-knytingar; og grein-dekomposisjonar og mim-breidda deira.

Spaltetre er nokså generelle strukturar som gjev føresegner om korleis ein graf kan takast frå einannan. Me innfører fire beslekta graf-invariantar, kalla EPT-max, VPT-max, EPT-sum og VPT-sum, som skildrar den minste moglege høgda eller gjennomsnittlege djupna på spaltetrea av ein graf. Alle graf-invariantane er kjende i litteraturen frå før (ikkje minst er VPT-max kjend som tre-djupna av ein graf), men me gjev ei sameina skildring av desse fire invariantane som me trur er den fyrste i sitt slag. Me syner at spaltetre har mange samband til problem som kjem frå ulike område av informatikken. Me syner særskilt at ein mål-funksjon for hierarkisk klynging som fyrst var omtala av Dasgupta er lik på EPT-sum av kant-vekta grafar. Me beviser så at å rekne ut denne invarianten er NP-hardt på uvekta grafar, men kan gjerast i polynom tid på uvekta "åmer''. Me syner òg at det er ein ekvivalens mellom VPT-sum og grafproblemet "trivielt perfekt fullføring''. Me ser på ein grådig strategi for å tilnærme EPT-sum av hjørne-vekta tre, og syner at denne strategien oppnår ei 1.5-tilnærming (som svarer til ein nedre skranke funnen i 2014), og me gjev ein algoritme for å utføre den grådige strategien som køyrer i O(n log n) tid.

Lauv-knytingar er grafar som kan verte gjorde av tre, gjennom å knyte saman par av lauv som har lita avstand i treet. Ikkje alle grafar er lauv-knytingar (lauv-knytingane er særskilt kordale grafar), og eit av dei viktigaste spørsmåla rundt denne grafklassen er om dei kan kjennast att i polynom tid. Me gjev to resultat angåande den såkalla lauv-rangen åt lauv-knytingar, altså det minste heiltalet k slik at ein graf kan verte gjord av eit tre der par av hjørne vert knytte saman om dei tilsvarande lauva har avstand toppen k. Fyrst syner me at det finst ein uendeleg familie av grafar som har eksponentielt høg lauv-rang som ein funksjon av talet på hjørne. Dette går på tvers av alle andre kjende grafklassar me kjenner lauv-rangen på; dei har lauv-rang som er lineær i forhold til talet på hjørne. Elles syner me at greie intervall-grafar (ein underklasse av lauv-eksponentar) kan verte gjorde av tre med ein særs enkel struktur; dette resultatet opnar dørene for ein polynom-tids algoritme for å rekne ut lauv-rangen av desse grafane.

Grein-dekomposisjonar (slik dei er definerte i denne avhandlinga) er overføringar frå mengda av hjørne på ein graf til eit tre med lågt gradtal. Mim-breidd er ein algoritmisk graf-parameter som vurderer kor kompliserte kutta som er skapte ut ifrå ei grein-dekomposisjon er. Grein dekomposisjonar med låg mim-breidd kan brukast for å løyse mange grafproblem raskare. Me gjev nokre førebels resultat angåande mim-breidd: Fyrst syner me at den lineære mim-breidda av kvadrata av tre har ei heller laus tilknytning til den lineære mim-breidda av treet sjølv; men den er aldri mindre. Elles ser me på ein forboden struktur (såkalla stjerne-triplar av kantar) i grafar med mim-breidd éin, og gjev den formodninga at dette er den einaste forbodne strukturen som skil grafar med lineær mim-breidd éin frå grafar med mim-breidd éin. Me syner óg at den same strukturen er forboden frå toleransegrafar og komplementa deira, som gjev ein interessant parallell mellom desse grafane og grafar med mim-breidd éin.

Many applications in computer science can be boiled down to finding structures in data sets. Data sets may often be represented as graphs, and many types of structures may be represented by trees. Therefore, mapping a graph to a tree is often a desirable way to display structure in the data represented by a graph. In this thesis, we contribute to the knowledge of three specific tree mappings of graphs: Edge and vertex partition trees; leaf roots and leaf powers; and branch decompositions and their mim-width.

Partition trees are rather general structures that give instructions for dismantling graphs. We introduce four related graph invariants, EPT-max, VPT-max, EPT-sum and VPT-sum, which all describe the minimum height or average depth of partition trees of a graph. All of these invariants are known in the literature (in particular, VPT-max is known as the tree-depth of a graph); however, we give what we believe to be the first unified treatment of these graph invariants. We show that partition trees have many connections to problems that arise in different domains in computer science. In particular, we prove that an objective function for hierarchical clustering first described by Dasgupta is equal to the EPT-sum of edge-weighted graphs, and show this invariant to be NP-hard to compute on unweighted graphs, but polynomial-time solvable on unweighted caterpillars. We also give an equivalence between VPT-sum of unweighted graphs and the problem of trivially perfect completion. We study a greedy strategy for approximating the EPT-sum of vertex-weighted trees, showing that it achieves 1.5-approximation (matching a lower bound for the same strategy that was shown in 2014) and offering an O(n log n) time algorithm for executing this greedy strategy.

Leaf powers are graphs that can be generated from trees by connecting leaves with low distance. Not all graphs are leaf powers (specifically, leaf powers are chordal graphs), and the question of whether leaf powers can be recognized in polynomial time is one of the most important questions regarding this graph class. We give two results pertaining to the leaf rank of leaf powers, i.e. the minimum integer k such that the graph is generated from a tree where the leaves must have distance at most k in order to be connected in the graph. First, we show that there exists an infinite family of graphs that have leaf rank exponential in the number of vertices. This is in contrast to every other known subclass of leaf powers, which was known to have at most linear leaf rank. Second, we show that proper interval graphs (a subclass of leaf powers) can be generated from trees with a very simple structure; this opens an avenue towards poly-time computation of the leaf rank of this graph class.

Branch decompositions (as defined in this thesis) are mappings from the vertex sets of graphs onto trees with low degree. Mim-width is an algorithmic graph parameter that estimates the complexity of edge cuts defined by a branch decomposition; branch decompositions of low mim-width can be exploited to solve problems on the graph faster. We provide some tentative results on this parameter: First, we show that the linear mim-width of trees is only loosely connected to the linear mim-width of their squares; though it is never lower. Second, we look at a forbidden structure (so-called asteroidal edge triples) in graphs of linear mim-width one, and conjecture that this is the only forbidden structure in these graphs relative to graphs of mim-width one. We also show that the same structure is forbidden in tolerance graphs and their complements, which shows an interesting parallel between these graphs and graphs of linear mim-width one.