# Be sparse! Be dense! Be robust!

## Inst. Softwaretechnik und Theoretische Informatik

In this thesis we study the computational complexity of five NP-hard graph problems. It is widely accepted that, in general, NP-hard problems cannot be solved efficiently, that is, in polynomial time, due to many unsuccessful attempts to prove the contrary. Hence, we aim to identify properties of the inputs other than their length, that make the problem tractable or intractable. We measure these properties via parameters, mappings that assign to each input a nonnegative integer. For a given parameter k, we then attempt to design fixed-parameter algorithms, algorithms that on input q have running time upper bounded by f(k(q)) * |q|^c , where f is a preferably slowly growing function, |q| is the length of q, and c is a constant, preferably small. In each of the graph problems treated in this thesis, our input represents the setting in which we shall find a solution graph. In addition, the solution graphs shall have a certain property specific to our five graph problems. This property comes in three flavors. First, we look for a graph that shall be sparse! That is, it shall contain few edges. Second, we look for a graph that shall be dense! That is, it shall contain many edges. Third, we look for a graph that shall be robust! That is, it shall remain a good solution, even when it suffers several small modifications. Be sparse! In this part of the thesis, we analyze two similar problems. The input for both of them is a hypergraph H , which consists of a vertex set V and a family E of subsets of V , called hyperedges. The task is to find a support for H , a graph G such that for each hyperedge W in E we have that G[W ] is connected. Motivated by applications in network design, we study SUBSET INTERCONNECTION DESIGN, where we additionally get an integer f , and the support shall contain at most |V| - f + 1 edges. We show that SUBSET INTERCONNECTION DESIGN admits a fixed-parameter algorithm with respect to the number of hyperedges in the input hypergraph, and a fixed-parameter algorithm with respect to f + d , where d is the size of a largest hyperedge. Motivated by an application in hypergraph visualization, we study r-OUTERPLANAR SUPPORT where the support for H shall be r -outerplanar, that is, admit a edge-crossing free embedding in the plane with at most r layers. We show that r-OUTER-PLANAR SUPPORT admits a fixed-parameter algorithm with respect to m + r , where m is the number of hyperedges in the input hypergraph H. Be dense! In this part of the thesis, we study two problems motivated by community detection in social networks. Herein, the input is a graph G and an integer k. We look for a subgraph G' of G containing (exactly) k vertices which adheres to one of two mathematically precise definitions of being dense. In mu-CLIQUE, 0 < mu <= 1, the sought k-vertex subgraph G' should contain at least mu time k choose 2 edges. We study the complexity of mu-CLIQUE with respect to three parameters of the input graph G: the maximum vertex degree delta, h-index h, and degeneracy d. We have delta >= h >= d in every graph and h as well as d assume small values in graphs derived from social networks. For delta and for h, respectively, we obtain fixed-parameter algorithms for mu-CLIQUE and we show that for d + k a fixed-parameter algorithm is unlikely to exist. We prove the positive algorithmic results via developing a general framework for optimizing objective functions over k-vertex subgraphs. In HIGHLY CONNECTED SUBGRAPH we look for a k-vertex subgraph G' in which each vertex shall have degree at least floor(k/2)+1. We analyze a part of the so-called parameter ecology for HIGHLY CONNECTED SUBGRAPH, that is, we navigate the space of possible parameters in a quest to find a reasonable trade-off between small parameter values in practice and efficient running time guarantees. The highlights are that no 2^o(n) * n^c -time algorithms are possible for n-vertex input graphs unless the Exponential Time Hypothesis fails; that there is a O(4^g * n^2)-time algorithm for the number g of edges outgoing from the solution G; and we derive a 2^(O(sqrt(a)log(a)) + a^2nm-time algorithm for the number a of edges not in the solution. Be robust! In this part of the thesis, we study the VECTOR CONNECTIVITY problem, where we are given a graph G, a vertex labeling ell from V(G) to {1, . . . , d }, and an integer k. We are to find a vertex subset S of V(G) of size at most k such that each vertex v in V (G)\S has ell(v) vertex-disjoint paths from v to S in G. Such a set S is useful when placing servers in a network to satisfy robustness-of-service demands. We prove that VECTOR CONNECTIVITY admits a randomized fixed-parameter algorithm with respect to k, that it does not allow a polynomial kernelization with respect to k + d but that, if d is treated as a constant, then it allows a vertex-linear kernelization with respect to k.
In dieser Dissertation untersuchen wir die BerechnungskomplexitÃ¤t von fÃ¼nf NP-schweren Graphproblemen. Es wird weithin angenommen, dass NP-schwere Probleme im Allgemeinen nicht effizient gelÃ¶st werden kÃ¶nnen, das heiÃŸt, dass sie keine Polynomialzeitalgorithmen erlauben. Diese Annahme basiert auf vielen bisher nicht erfolgreichen Versuchen das Gegenteil zu beweisen. Aus diesem Grund versuchen wir Eigenschaften der Eingabe herauszuarbeiten, die das betrachtete Problem handhabbar oder unhandhabbar machen. Solche Eigenschaften messen wir mittels Parametern, das heiÃŸt, Abbildungen, die jeder mÃ¶glichen Eingabe eine natÃ¼rliche Zahl zuordnen. FÃ¼r einen gegebenen Parameter k versuchen wir dann Fixed-Parameter Algorithmen zu entwerfen, also Algorithmen, die auf Eingabe q eine obere Laufzeitschranke von f(k(q)) * |q|^c erlauben, wobei f eine, vorzugsweise schwach wachsende, Funktion ist, |q| die LÃ¤nge der Eingabe, und c eine Konstante, vorzugsweise klein. In den Graphproblemen, die wir in dieser Dissertation studieren, reprÃ¤sentiert unsere Eingabe eine Situation in der wir einen LÃ¶sungsgraph finden sollen. ZusÃ¤tzlich sollen die LÃ¶sungsgraphen bestimmte problemspezifische Eigenschaften haben. Wir betrachten drei Varianten dieser Eigenschaften: ZunÃ¤chst suchen wir einen Graphen, der sparse sein soll. Das heiÃŸt, dass er wenige Kanten enthalten soll. Dann suchen wir einen Graphen, der dense sein soll. Das heiÃŸt, dass er viele Kanten enthalten soll. Zuletzt suchen wir einen Graphen, der robust sein soll. Das heiÃŸt, dass er eine gute LÃ¶sung bleiben soll, selbst wenn er einige kleine Modifikationen durchmacht. Be sparse! In diesem Teil der Arbeit analysieren wir zwei Ã¤hnliche Probleme. In beiden ist die Eingabe ein Hypergraph H, bestehend aus einer Knotenmenge V und einer Familie E von Teilmengen von V, genannt Hyperkanten. Die Aufgabe ist einen Support fÃ¼r H zu finden, einen Graphen G, sodass fÃ¼r jede Hyperkante W in E der induzierte Teilgraph G[W] verbunden ist. Motiviert durch Anwendungen im Netzwerkdesign betrachten wir SUBSET INTERCONNECTION DESIGN, worin wir eine natÃ¼rliche Zahl f als zusÃ¤tzliche Eingabe bekommen, und der Support hÃ¶chstens |V| - f + 1 Kanten enthalten soll. Wir zeigen, dass SUBSET INTERCONNECTION DESIGN einen Fixed-Parameter Algorithmus in Hinsicht auf die Zahl der Hyperkanten im Eingabegraph erlaubt, und einen Fixed-Parameter Algorithmus in Hinsicht auf f + d, wobei d die GrÃ¶ÃŸe einer grÃ¶ÃŸten Hyperkante ist. Motiviert durch eine Anwendung in der Hypergraphvisualisierung studieren wir r-OUTERPLANAR SUPPORT, worin der Support fÃ¼r H r-outerplanar sein soll, das heiÃŸt, er soll eine kantenkreuzungsfreie Einbettung in die Ebene erlauben mit hÃ¶chstens r Schichten. Wir zeigen, dass r-OUTERPLANAR SUPPORT einen Fixed-Parameter Algorithmus in Hinsicht auf m + r zulÃ¤sst, wobei m die Anzahl der Hyperkanten im Eingabehypergraphen H ist. Be dense! In diesem Teil der Arbeit studieren wir zwei Probleme, die durch Community Detection in sozialen Netzwerken motiviert sind. Dabei ist die Eingabe ein Graph G und eine natÃ¼rliche Zahl k. Wir suchen einen Teilgraphen G' von G, der (genau) k Knoten enthÃ¤lt und dabei eine von zwei mathematisch prÃ¤zisen Definitionen davon, dense zu sein, aufweist. In mu-CLIQUE, 0 < mu <= 1, soll der gesuchte Teilgraph G' mindestens mu mal k Ã¼ber 2 Kanten enthalten. Wir studieren die BerechnungskomplexitÃ¤t von mu-CLIQUE in Hinsicht auf drei Parameter des Eingabegraphen G: dem maximalen Knotengrad delta, dem h-Index h, und der Degeneracy d. Es gilt delta >= h >= d fÃ¼r jeden Graphen und h als auch d nehmen kleine Werte in Graphen an, die aus sozialen Netzwerken abgeleitet sind. FÃ¼r delta und h erhalten wir Fixed-Parameter Algorithmen fÃ¼r mu-CLIQUE und wir zeigen, dass fÃ¼r d + k wahrscheinlich kein Fixed-Parameter Algorithmus existiert. Unsere positiven algorithmischen Resultate erhalten wir durch Entwickeln eines allgemeinen Frameworks zum Optimieren von Zielfunktionen Ã¼ber k-Knoten-Teilgraphen. In HIGHLY CONNECTED SUBGRAPH soll in dem gesuchten k-Knoten-Teilgraphen G' jeder Knoten Knotengrad mindestens floor(k/2) + 1 haben. Wir analysieren einen Teil der sogenannten Parameter Ecology fÃ¼r HIGHLY CONNECTED SUBGRAPH. Das heiÃŸt, wir navigieren im Raum der mÃ¶glichen Parameter auf der Suche nach einem vernÃ¼nftigen Trade-off zwischen kleinen Parameterwerten in der Praxis und effizienten oberen Laufzeitschranken. Die Highlights hier sind, dass es keine Algorithmen mit 2^o(n) * poly(n)-Laufzeit fÃ¼r HIGHLY CONNECTED SUBGRAPH gibt, es sei denn die Exponential Time Hypothesis stimmt nicht; die Entwicklung eines Algorithmus mit O(4^y * n^2 )-Laufzeit, wobei y die Anzahl der Kanten ist, die aus dem LÃ¶sungsgraphen G' herausgehen; und die Entwicklung eines Algorithmus mit 2^O(sqrt(a) log(a)) + O(a^2nm)-Laufzeit, wobei a die Anzahl der Kanten ist, die nicht in G' enthalten sind.
• Published in print by UniversitÃ¤tsverlag der TU Berlin, ISBN 978-3-7983-2885-3 (ISSN 2199-5249)