Evaluation of the Iwata–Yokoi Algorithm

Abstract

Gitt en urettet multigraf, G = (V, E), uten løkker, og en delmengde terminaler, T ⊆ V, kalles en sti mellom to distinkte terminaler, hvor alle interne noder i stien ikke er terminaler, en T-sti. Gitt denne definisjonen formulerte Gallai kantdisjunkte-T-stier problemet, som senere ble popularisert av Mader. Dette problemet handler om, for arbitærer grafer og mengder av terminaler, å finne maksimale mengder, med hensyn til kardinalitet, av parvis kantdisjunkte T-stier. På SODA2020 presenterte Iwata og Yokoi en ny kombinatorisk algoritme for kantdisjunkte-T-stier problemet. Denne algoritmen anvender en lignende strategi som Edmonds’ blomstringsalgoritme for maksimal matching problemet. Denne masteroppgaven presenterer en håndfull spesialtilfeller, oppdaget under implementasjon av Iwata–Yokoi algoritmen, som enten er uhåndtert eller delvis feilhåndtert i algoritmen. Disse tilfellene finner alle sted i forøkningsprosedyren til algoritmen, og tar tak i overflødige løkker, ugyldige snarveier, ulovlig dobbel bruk av kanter samt opptredener av sykler i T-stier. Hvert av disse spesialtilfellene blir diskutert og passende endringer av algoritmen blir presentert og får sin korrekthet bevist. Endringene og de problematiske tilfellene blir også diskutert i sammenheng med endringene som ble foreslått til, den da upubliserte, Iwata–Yokoi algoritmen i forprosjektet til denne masteroppgaven. I tillegg inneholder masteroppgaven noen foreslåtte endringer og diskusjon knyttet til empirisk ytelse.

Given an undirected multigraph, G = (V, E), without self-loops, and a subset of terminals, T ⊆ V, a path between two distinct terminals, with all path-internal vertices being non-terminals, is called a T-path. Given this definition, Gallai formulated the edge-disjoint T-paths problem, later popularized by Mader, which is concerned with finding maximum-cardinality sets of pairwise edge-disjoint T-paths, given arbitrary graphs and subsets of terminals. At SODA 2020, Iwata and Yokoi presented a new combinatorial algorithm for the edge-disjoint T-paths problem, employing a similar strategy to the one used by Edmonds in his blossom algorithm for the maximum matching problem. This master’s thesis presents a handful of either slightly mishandled or unhandled edge cases discovered while working with and implementing the Iwata–Yokoi algorithm. The edge cases discussed in this master’s thesis are all found in the augmentation procedure of the Iwata–Yokoi algorithm, concerning redundant self-loops, invalid shortcuts, illegal double usage of labeled edges and the appearance of cycles in the T-paths. Each of these edge cases are discussed and appropriate modifications to the algorithm, to mitigate each edge case individually, are presented and proven. The modifications and edge cases are also discussed in the context of the improvements suggested to the, then unpublished, Iwata–Yokoi algorithm in the preliminary project for this master’s thesis. Additionally, some minor discussion on efficiency and suggestions for modifications based on predicted empirical efficiency are included.