Loading…
Multivariate complexity analyses for algorithmic challenges in fairness and sustainability
Kellerhals, Leon
This thesis studies selected algorithmic challenges related to the emerging fields of fairness in algorithms and computational sustainability, with a focus on the parameterized complexity of the underlying computational problems. The field of fairness in algorithms deals with problems that are applied to make decisions which have an impact on individuals, with the goal to ensure that no individuals are affected disparately by the decision. The field of computational sustainability deals with problems that arise in our efforts to balance out environmental, economic, and societal needs for a sustainable future. Specifically, we study the following four algorithmic challenges.
Modification-Fair Cluster Editing. Standard algorithms for cluster editing (also known as correlation clustering) may output solutions that are discriminatory against some groups, i.e., by having most modifications incident to one group. We propose a fairness concept with the goal to keep the number of edits incident to each group proportional to its size. Focusing on the setting with two groups, we show (among other results) that our modification-fair variant of the cluster editing problem is NP-hard even in the restricted case in which one may only insert edges within the groups, while still remaining fixed-parameter tractable with respect to the number of edge edits in its unrestricted form. A preliminary empirical analysis shows that the cost of optimal modification-fair solutions differs from the cost of optimal “non-fair” solutions only by a small percentage.
Range-Fair Paths. We consider a general fairness measure which encompasses several existing ones and can be modeled as a matroid. We incorporate this measure into the problem of finding paths in vertex-colored paths, which results in an NP-hard problem. We study said problem in terms of its parameterized complexity, focusing on the canonical parameters number of colors and length of the desired path, as well as on parameters that measure the structural complexity of the given graph. We show, among other results, that there is an algorithm for finding shortest fair paths that runs in polynomial time if there are constantly many colors, and an algorithm for finding fair paths of length ℓ whose running time is single-exponential in ℓ and polynomial in the graph size.
Locally Diverse Paths. We next study the problem of finding paths on vertex-colored graphs with a local constraint that prohibits colors to be visited more than once within any subpath of fixed length. Thinking of the time until a color may be revisited as regeneration time of a natural resource or ecosystem, this has applications in preserving biodiversity. Among other results, our thorough fine-grained complexity analysis proves that finding shortest such paths is fixed-parameter tractable with respect to the subpath length. Remarkably, the problem remains tractable even when allowing the paths to take short detours.
Placing Green Bridges. Animal habitats are increasingly fragmented due to human-made infrastructure like roads or train tracks. To preserve biodiversity, it is imperative to reconnect such habitats with wildlife crossings, so-called green bridges. We study the problem of finding the best (few) places for green bridges such that the habitat of each animal species is sufficiently connected. In brief, we introduce multiple problem variants that provide different types and grades of connectivity, and study these problems in terms of their classical as well as their parameterized complexity with respect to the number of green bridges and the number of habitats. We also consider the setting in which habitats are structurally restricted. Finally, we provide a preliminary empirical analysis of a selection of our algorithms on real-world graphs.
Die vorliegende Dissertation befasst sich mit theoretischen algorithmischen Herausforderungen aus den jungen Forschungsrichtungen „Fairness in Algorithms“ und „Computational Sustainability“. Dabei liegt der Fokus auf der parametrisierten Komplexität der zugrunde liegenen Berechnungsprobleme. „Fairness in Algorithms“ beschäftigt sich mit der Vermeidung unmittelbarer oder mittelbarer individueller Nachteile durch algorithmisch gesteuerte Entscheidungsprozesse. „Computational Sustainability“ setzt sich mit Berechnungsproblemen aus der Nachhaltigkeitsforschung auseinander, mit dem Ziel, die ökologischen, ökonomischen und gesellschaftlichen Bedürfnisse für eine nachhaltige Zukunft auszubalancieren. Kern der Dissertation sind die folgenden vier algorithmischen Problemstellungen.
Modification-Fair Cluster Editing. Übliche Algorithmen für Cluster Editing (auch Correlation Clustering) können zu unfairen, eine (bspw. demographische) Gruppe benachteiligenden Lösungen führen. Dieser Problematik kann grundsätzlich bereits auf algorithmischer Ebene begegnet werden. Der Nachteil ist beispielsweise an der Zahl der Kantenänderungen inzident zu jeder Gruppe messbar. Wir stellen ein Fairnesskonzept vor, dessen Ziel ist, die jeweilige Anzahl der Kantenänderungen an die proportionale Größe der Gruppe anzugleichen. Dabei beschränken wir uns auf den Fall mit zwei Gruppen und zeigen (unter anderem), dass unsere Fairnessvariante des Cluster Editing Problems NP-schwer ist, selbst wenn man nur Kanten innerhalb einer Gruppe einfügen darf, während die uneingeschränkte Variante des Problems parametrisiert mit der Anzahl an Knotenänderungen in FPT liegt. Eine vorläufige empirische Studie zeigt, dass die Kosten einer optimalen fairen Lösung nur geringfügig höher sind als die einer optimalen „unfairen“ Lösung.
Range-Fair Paths. Wir betrachten ein Maß, das mehrere bekannte Fairnessmaße verallgemeinert und als Matroid modelliert werden kann. Dieses Maß wenden wir auf das Pfadfindungsproblem in knotengefärbten Graphen an, welches durch die entstehenden Einschränkungen NP-schwer wird. Wir untersuchen das Problem hinsichtlich seiner parametrisierten Komplexität. Unser Schwerpunkt liegt hierbei auf den kanonischen Parametern Anzahl von Farben und Länge des gesuchten Pfades, sowie auf Parametern die die strukturelle Komplexität des gegebenen Graphen messen. Unter anderem zeigen wir, dass das Problem parametrisiert mit der Pfadlänge in FPT liegt.
Locally Diverse Paths. Wir betrachten das Pfadfindungsproblem auf knotengefärbten Graphen mit einer lokalen Einschränkung und suchen nach Pfaden, für die gilt, dass jede Farbe in jedem Subpfad fixer Länge höchstens einmal vorkommt. Dies kann eine Regenerationszeit für jede Farbe modellieren und hat Anwendungen im Schutz von Ökosystemen. Unter anderem zeigt unsere ausführliche feingranulare Komplexitätsanalyse, dass das Finden von kürzesten Pfaden mit dieser lokalen Beschränkung in FPT parametrisiert mit der Subpfadlänge ist. Tatsächlich bleibt das Problem (algorithmisch) selbst dann handhabbar, wenn die Pfade kleine Umwege enthalten dürfen, also etwas länger als kürzeste Pfade sind.
Placing Green Bridges. Die Lebensräume von Tieren werden zunehmend durch menschengemachte Infrastruktur wie Straßen oder Zugtrassen zerteilt. Die Aufrechterhaltung der Biodiversität verlangt die so zerstückelten Lebensräume beispielsweise durch Wildtierbrücken wieder zu verbinden. Zur Optimierung der Kosten-Nutzen-Relation untersuchen wir wie mit einer minimalen Anzahl solcher Verbindungen die Lebensräume unterschiedlicher Tierarten verbunden werden können. Dazu führen wir drei Problemvarianten ein, welche verschiedene Arten von Verbundenheit modellieren und untersuchen diese hinsichtlich ihrer klassischen und parametrisierten Komplexität (bezüglich der Parameter Anzahl der Brücken und Anzahl der Tierarten). Wir untersuchen auch den Fall, in dem die Lebensräume spezielle Strukturen aufweisen. Schließlich untersuchen wir einige unserer Algorithmen in einer vorläufigen empirischen Studie.
