Graph Algorithms: Structural Parameters and Applications in Algorithmic Game Theory

This dissertation studies graph algorithms from two perspectives: exploiting structural decompositions to solve hard problems on graphs and applying graph-algorithmic techniques to fairness in resource allocation. Part I asks how efficiently the structure of a graph can be measured and exploited. Structural width parameters and separator decompositions are what make hard problems tractable on sparse graphs; part I explores the price of obtaining and using them. The first chapter presents an improved algorithm for 2-approximate treewidth computation, reducing the exponential base from 1782^k to 81^k while maintaining linear dependence on n. The second chapter studies the leading constant of the fill bound for planar nested dissection and analyzes approaches to decreasing it. We reduce the constant from 55.8 to 34.2 unconditionally, and show that further gains require a separator balancing the inherited boundary and vertex count. We also prove simulating such a separator by vertex weighting cannot be certified by a potential function of the classical form. For both chapters, the asymptotic landscape is settled by prior work; the contributions are to the constants that govern practical performance. Part II maps the computational landscape of envy minimization in house allocation and applies graph-algorithmic techniques to algorithmic game theory. Here, the structure in question is the pattern of comparisons between agents, and the objective is to maximize fairness in the allocation of indivisible resources. The third chapter analyzes the complexity and trade-offs involved in balancing three distinct efficiency notions (allocation size, utilitarian welfare, egalitarian welfare) against four envy measures. We show that maximizing utilitarian welfare makes every envy-minimization variant polynomial, while egalitarian welfare preserves NP-hardness. The fourth chapter introduces minimax envy on graphs embedding social networks and analyzes the complexity of finding an allocation when only adjacent neighbors may envy each other. We find an exact solution in O^*(6^n) for identical strict preferences, and show that arbitrary distinct preferences yield an upper bound 2^{O(nlog n)} poly(m) FPT algorithm. We also provide exact algorithms, singly exponential in n, parameterized by treewidth tw and the disagreement. In both parts, the object of the study remains the same: understanding how the structure of the graph makes difficult problems tractable.