Search

We study the computational complexity of several polynomial-time-solvable graph problems parameterized by vertex integrity, a measure of a graph's vulnerability to vertex removal in terms of connectivity. Vertex integrity is the smallest number $\iota$ such that there is a set $S$ of $\iota' \le \iota$ vertices such that every connected component of $G-S$ contains at most $\iota-\iota'$ vertices. It is known that the vertex integrity lies between the well-studied parameters vertex cover number and tree-depth. Alon and Yuster [ESA 2007] designed algorithms for graphs with small vertex cover number using fast matrix multiplications. We demonstrate that fast matrix multiplication can also be effectively used when parameterizing by vertex integrity $\iota$ by developing efficient algorithms for problems including an $O(\iota^{\omega-1}n)$-time algorithm for computing the girth of a graph, randomized $O(\iota^{\omega - 1}n)$-time algorithms for Maximum Matching and for finding any induced four-vertex subgraph except for a clique or an independent set, and an $O(\iota^{(\omega-1)/2}n^2) \subseteq O(\iota^{0.687} n^2)$-time algorithm for All-Pairs Shortest Paths. These algorithms can be faster than previous algorithms parameterized by tree-depth, for which fast matrix multiplication is not known to be effective.

We examine the possibility of approximating Maximum Vertex-Disjoint Shortest Paths. In this problem, the input is an edge-weighted (directed or undirected) $n$-vertex graph $G$ along with $k$ terminal pairs $(s_1,t_1),(s_2,t_2),\ldots,(s_k,t_k)$. The task is to connect as many terminal pairs as possible by pairwise vertex-disjoint paths such that each path is a shortest path between the respective terminals. Our work is anchored in the recent breakthrough by Lochet [SODA '21], which demonstrates the polynomial-time solvability of the problem for a fixed value of $k$. Lochet's result implies the existence of a polynomial-time $ck$-approximation for Maximum Vertex-Disjoint Shortest Paths, where $c \leq 1$ is a constant. Our first result suggests that this approximation algorithm is, in a sense, the best we can hope for. More precisely, assuming the gap-ETH, we exclude the existence of an $o(k)$-approximations within $f(k) \cdot $poly($n$) time for any function $f$ that only depends on $k$. Our second result demonstrates the infeasibility of achieving an approximation ratio of $n^{\frac{1}{2}-\varepsilon}$ in polynomial time, unless P = NP. It is not difficult to show that a greedy algorithm selecting a path with the minimum number of arcs results in a $\lceil\sqrt{\ell}\rceil$-approximation, where $\ell$ is the number of edges in all the paths of an optimal solution. Since $\ell \leq n$, this underscores the tightness of the $n^{\frac{1}{2}-\varepsilon}$-inapproximability bound. Additionally, we establish that Maximum Vertex-Disjoint Shortest Paths is fixed-parameter tractable when parameterized by $\ell$ but does not admit a polynomial kernel. Our hardness results hold for undirected graphs with unit weights, while our positive results extend to scenarios where the input graph is directed and features arbitrary (non-negative) edge weights.

We explore Cluster Editing and its generalization Correlation Clustering with a new operation called permissive vertex splitting which addresses finding overlapping clusters in the face of uncertain information. We determine that both problems are NP-hard, yet they exhibit significant differences in parameterized complexity and approximability. For Cluster Editing with Permissive Vertex Splitting, we show a polynomial kernel when parameterized by the solution size and develop a polynomial-time algorithm with approximation factor 7. In the case of Correlation Clustering, we establish para-NP-hardness when parameterized by solution size and demonstrate that computing an $n^{1-\epsilon}$-approximation is NP-hard for any constant $\epsilon > 0$. Additionally, we extend the established link between Correlation Clustering and Multicut to the setting with permissive vertex splitting.

We study the parameterized complexity of finding shortest s-t-paths with an additional fairness requirement. The task is to compute a shortest path in a vertex-colored graph where each color appears (roughly) equally often in the solution. We provide a complete picture of the parameterized complexity landscape of the problem with respect to structural parameters by showing a tetrachotomy including polynomial kernels, fixed-parameter tractability, XP-time algorithms (and W[1]-hardness), and para-NP-hardness.

We study a generalization of the classic Spanning Tree problem that allows for a non-uniform failure model. More precisely, edges are either safe or unsafe and we assume that failures only affect unsafe edges. In Unweighted Flexible Graph Connectivity we are given an undirected graph G = (V,E) in which the edge set E is partitioned into a set S of safe edges and a set U of unsafe edges and the task is to find a set T of at most k edges such that T -{u} is connected and spans V for any unsafe edge u ∈ T. Unweighted Flexible Graph Connectivity generalizes both Spanning Tree and Hamiltonian Cycle. We study Unweighted Flexible Graph Connectivity in terms of fixed-parameter tractability (FPT). We show an almost complete dichotomy on which parameters lead to fixed-parameter tractability and which lead to hardness. To this end, we obtain FPT-time algorithms with respect to the vertex deletion distance to cluster graphs and with respect to the treewidth. By exploiting the close relationship to Hamiltonian Cycle, we show that FPT-time algorithms for many smaller parameters are unlikely under standard parameterized complexity assumptions. Regarding problem-specific parameters, we observe that Unweighted Flexible Graph Connectivity admits an FPT-time algorithm when parameterized by the number of unsafe edges. Furthermore, we investigate a below-upper-bound parameter for the number of edges of a solution. We show that this parameter also leads to an FPT-time algorithm., Discrete Mathematics and Optimization

Cluster Editing, also known as correlation clustering, is a well-studied graph modification problem. In this problem, one is given a graph and allowed to perform up to k edge additions and deletions to transform it into a cluster graph, i.e., a graph consisting of a disjoint union of cliques. However, in real-world networks, clusters are often overlapping. For example, in social networks, a person might belong to several communities - e.g. those corresponding to work, school, or neighborhood. Another strong motivation comes from language networks where trying to cluster words with similar usage can be confounded by homonyms, that is, words with multiple meanings like "bat". The recently introduced operation of vertex splitting is one natural approach to incorporating such overlap into Cluster Editing. First used in the context of graph drawing, this operation allows a vertex v to be replaced by two vertices whose combined neighborhood is the neighborhood of v (and thus v can belong to more than one cluster). The problem of transforming a graph into a cluster graph using at most k edge additions, edge deletions, or vertex splits is called Cluster Editing with Vertex Splitting and is known to admit a polynomial kernel with respect to k and an O(9^{k²} + n + m)-time (parameterized) algorithm. However, it was not known whether the problem is NP-hard, a question which was originally asked by Abu-Khzam et al. [Combinatorial Optimization, 2018]. We answer this in the affirmative. We further give an improved algorithm running in O(2^{7klog k} + n + m) time.

We study a generalization of the classic Spanning Tree problem that allows for a non-uniform failure model. More precisely, edges are either safe or unsafe and we assume that failures only affect unsafe edges. In Unweighted Flexible Graph Connectivity we are given an undirected graph G = (V,E) in which the edge set E is partitioned into a set S of safe edges and a set U of unsafe edges and the task is to find a set T of at most k edges such that T - {u} is connected and spans V for any unsafe edge u ∈ T. Unweighted Flexible Graph Connectivity generalizes both Spanning Tree and Hamiltonian Cycle. We study Unweighted Flexible Graph Connectivity in terms of fixed-parameter tractability (FPT). We show an almost complete dichotomy on which parameters lead to fixed-parameter tractability and which lead to hardness. To this end, we obtain FPT-time algorithms with respect to the vertex deletion distance to cluster graphs and with respect to the treewidth. By exploiting the close relationship to Hamiltonian Cycle, we show that FPT-time algorithms for many smaller parameters are unlikely under standard parameterized complexity assumptions. Regarding problem-specific parameters, we observe that Unweighted Flexible Graph Connectivity admits an FPT-time algorithm when parameterized by the number of unsafe edges. Furthermore, we investigate a below-upper-bound parameter for the number of edges of a solution. We show that this parameter also leads to an FPT-time algorithm.

We study the following Two-Sets Cut-Uncut problem on planar graphs. Therein, one is given an undirected planar graph $G$ and two sets of vertices $S$ and $T$. The question is, what is the minimum number of edges to remove from $G$, such that we separate all of $S$ from all of $T$, while maintaining that every vertex in $S$, and respectively in $T$, stays in the same connected component. We show that this problem can be solved in time $2^{|S|+|T|} n^{O(1)}$ with a one-sided error randomized algorithm. Our algorithm implies a polynomial-time algorithm for the network diversion problem on planar graphs, which resolves an open question from the literature. More generally, we show that Two-Sets Cut-Uncut remains fixed-parameter tractable even when parameterized by the number $r$ of faces in the plane graph covering the terminals $S \cup T$, by providing an algorithm of running time $4^{r + O(\sqrt r)} n^{O(1)}$., Comment: 22 pages, 5 figures

We study a generalization of the classic Spanning Tree problem that allows for a non-uniform failure model. More precisely, edges are either \emph{safe} or \emph{unsafe} and we assume that failures only affect unsafe edges. In Unweighted Flexible Graph Connectivity we are given an undirected graph $G = (V,E)$ in which the edge set $E$ is partitioned into a set $S$ of safe edges and a set $U$ of unsafe edges and the task is to find a set $T$ of at most $k$ edges such that $T - \{u\}$ is connected and spans $V$ for any unsafe edge $u \in T$. Unweighted Flexible Graph Connectivity generalizes both Spanning Tree and Hamiltonian Cycle. We study Unweighted Flexible Graph Connectivity in terms of fixed-parameter tractability (FPT). We show an almost complete dichotomy on which parameters lead to fixed-parameter tractability and which lead to hardness. To this end, we obtain FPT-time algorithms with respect to the vertex deletion distance to cluster graphs and with respect to the treewidth. By exploiting the close relationship to Hamiltonian Cycle, we show that FPT-time algorithms for many smaller parameters are unlikely under standard parameterized complexity assumptions. Regarding problem-specific parameters, we observe that Unweighted Flexible Graph Connectivity} admits an FPT-time algorithm when parameterized by the number of unsafe edges. Furthermore, we investigate a below-upper-bound parameter for the number of edges of a solution. We show that this parameter also leads to an FPT-time algorithm., Comment: Accepted at IPEC 2023

We study stable matching problems where agents have multilayer preferences: There are $\ell$ layers each consisting of one preference relation for each agent. Recently, Chen et al. [EC '18] studied such problems with strict preferences, establishing four multilayer adaptions of classical notions of stability. We follow up on their work by analyzing the computational complexity of stable matching problems with multilayer approval preferences. We consider eleven stability notions derived from three well-established stability notions for stable matchings with ties and the four adaptions proposed by Chen et al. For each stability notion, we show that the problem of finding a stable matching is either polynomial-time solvable or NP-hard. Furthermore, we examine the influence of the number of layers and the desired "degree of stability" on the problems' complexity. Somewhat surprisingly, we discover that assuming approval preferences instead of strict preferences does not considerably simplify the situation (and sometimes even makes polynomial-time solvable problems NP-hard).

Liquid democracy is a decision-making paradigm in which each agent can either vote directly for some alternative or (transitively) delegate its vote to another agent. To mitigate the issue of delegation cycles or the concentration of power, delegating agents might be allowed to specify multiple delegation options. Then, a (cycle-free) delegation is selected in which each delegating agent has exactly one representative. We study the winner determination problem for this setting, i.e., whether we can select a delegation such that a given alternative wins (or does not win). Moreover, we study the robustness of winning alternatives in two ways: First, we consider whether we can make a limited number of changes to the preferences cast by the agents such that a given alternative becomes a winner in one/in all delegations, and second, whether we can make a limited number of changes to a selected delegation to make a given alternative a winner.

The computation of short paths in graphs with arc lengths is a pillar of graph algorithmics and network science. In a more diverse world, however, not every short path is equally valuable. For the setting where each vertex is assigned to a group (color), we provide a framework to model multiple natural fairness aspects. We seek to find short paths in which the number of occurrences of each color is within some given lower and upper bounds. Among other results, we prove the introduced problems to be computationally intractable (NP-hard and parameterized hard with respect to the number of colors) even in very restricted settings (such as each color should appear with exactly the same frequency), while also presenting an encouraging algorithmic result ("fixed-parameter tractability") related to the length of the sought solution path for the general problem., Comment: Full version of a paper accepted at AAAI '23

Given an undirected n-vertex graph and k pairs of terminal vertices (s_1,t_1), …, (s_k,t_k), the k-Disjoint Shortest Paths (k-DSP) problem asks whether there are k pairwise vertex-disjoint paths P_1, …, P_k such that P_i is a shortest s_i-t_i-path for each i ∈ [k]. Recently, Lochet [SODA '21] provided an algorithm that solves k-DSP in n^{O(k^{5^k})} time, answering a 20-year old question about the computational complexity of k-DSP for constant k. On the one hand, we present an improved O(kn^{16k ⋅ k! + k + 1})-time algorithm based on a novel geometric view on this problem. For the special case k = 2, we show that the running time can be further reduced to O(nm) by small modifications of the algorithm and a further refined analysis. On the other hand, we show that k-DSP is W[1]-hard with respect to k, showing that the dependency of the degree of the polynomial running time on the parameter k is presumably unavoidable.

The NP-hard MATERIAL CONSUMPTION SCHEDULING Problem and closely related problems have been thoroughly studied since the 1980's. Roughly speaking, the problem deals with minimizing the makespan when scheduling jobs that consume non-renewable resources. We focus on the single-machine case without preemption: from time to time, the resources of the machine are (partially) replenished, thus allowing for meeting a necessary pre-condition for processing further jobs, each of which having individual resource demands. We initiate a systematic exploration of the parameterized (exact) complexity landscape of the problem, providing parameterized tractability as well as intractability results. Doing so, we mainly investigate how parameters related to the resource supplies influence the computational solvability. Thereby, we get a deepened understanding of the algorithmic complexity of this fundamental scheduling problem., Comment: Accepted for publication in The Thirty-Fifth AAAI Conference on Artificial Intelligence (AAAI-21)

Roughly speaking, gerrymandering is the systematic manipulation of the boundaries of electoral districts to make a specific (political) party win as many districts as possible. While typically studied from a geographical point of view, addressing social network structures, the investigation of gerrymandering over graphs was recently initiated by Cohen-Zemach et al. [AAMAS 2018]. Settling three open questions of Ito et al. [AAMAS 2019], we classify the computational complexity of the NP-hard problem Gerrymandering over Graphs when restricted to paths and trees. Our results, which are mostly of negative nature (that is, worst-case hardness), in particular yield two complexity dichotomies for trees. For instance, the problem is polynomial-time solvable for two parties but becomes weakly NP-hard for three. Moreover, we show that the problem remains NP-hard even when the input graph is a path.

Given an undirected $n$-vertex graph and $k$ pairs of terminal vertices $(s_1,t_1), \ldots, (s_k,t_k)$, the $k$-Disjoint Shortest Paths ($k$-DSP)-problem asks whether there are $k$ pairwise vertex-disjoint paths $P_1,\ldots, P_k$ such that $P_i$ is a shortest $s_i$-$t_i$-path for each $i \in [k]$. Recently, Lochet [SODA 2021] provided an algorithm that solves $k$-DSP in $n^{O(k^{5^k})}$ time, answering a 20-year old question about the computational complexity of $k$-DSP for constant $k$. On the one hand, we present an improved $n^{O(k!k)}$-time algorithm based on a novel geometric view on this problem. For the special case $k=2$ on $m$-edge graphs, we show that the running time can be further reduced to $O(nm)$ by small modifications of the algorithm and a refined analysis. On the other hand, we show that $k$-DSP is W[1]-hard with respect to $k$, showing that the dependency of the degree of the polynomial running time on the parameter $k$ is presumably unavoidable.

We investigate parameterized algorithms for the NP-hard problem Min-Power Asymmetric Connectivity (MinPAC) that has applications in wireless sensor networks. Given a directed arc-weighted graph, MinPAC asks for a strongly connected spanning subgraph minimizing the summed vertex costs. Here, the cost of each vertex is the weight of its heaviest outgoing arc in the chosen subgraph. We present linear-time algorithms for the cases where the number of strongly connected components in a so-called obligatory subgraph or the feedback edge number in the underlying undirected graph is constant. Complementing these results, we prove that the problem is W[2]-hard with respect to the solution cost, even on restricted graphs with one feedback arc and binary arc weights.

The efficient and fair distribution of indivisible resources among agents is a common problem in the field of \emph{Multi-Agent-Systems}. We consider a graph-based version of this problem called Reachable Assignments, introduced by Gourves, Lesca, and Wilczynski [AAAI, 2017]. The input for this problem consists of a set of agents, a set of objects, the agent's preferences over the objects, a graph with the agents as vertices and edges encoding which agents can trade resources with each other, and an initial and a target distribution of the objects, where each agent owns exactly one object in each distribution. The question is then whether the target distribution is reachable via a sequence of rational trades. A trade is rational when the two participating agents are neighbors in the graph and both obtain an object they prefer over the object they previously held. We show that Reachable Assignments is NP-hard even when restricting the input graph to be a clique and develop an $O(n^3)$-time algorithm for the case where the input graph is a cycle with $n$ vertices.

In the presented paper we study the Length-Bounded Cut problem for special graph classes as well as from a parameterized-complexity viewpoint. Here, we are given a graph $G$, two vertices $s$ and $t$, and positive integers $\beta$ and $\lambda$. The task is to find a set of edges $F$ of size at most $\beta$ such that every $s$-$t$-path of length at most $\lambda$ in $G$ contains some edge in $F$. Bazgan et al. conjectured that Length-Bounded Cut admits a polynomial-time algorithm if the input graph $G$ is a~proper interval graph. We confirm this conjecture by showing a dynamic-programming based polynomial-time algorithm. We strengthen the W[1]-hardness result of Dvo\v{r}\'ak and Knop. Our reduction is shorter, seems simpler to describe, and the target of the reduction has stronger structural properties. Consequently, we give W[1]-hardness for the combined parameter pathwidth and maximum degree of the input graph. Finally, we prove that Length-Bounded Cut is W[1]-hard for the feedback vertex number. Both our hardness results complement known XP algorithms., Comment: 24 pages

Dealing with NP-hard problems, kernelization is a fundamental notion for polynomial-time data reduction with performance guarantees: in polynomial time, a problem instance is reduced to an equivalent instance with size upper-bounded by a function of a parameter chosen in advance. Kernelization for weighted problems particularly requires to also shrink weights. Marx and V\'egh [ACM Trans. Algorithms 2015] and Etscheid et al. [J. Comput. Syst. Sci. 2017] used a technique of Frank and Tardos [Combinatorica 1987] to obtain polynomial-size kernels for weighted problems, mostly with additive goal functions. We characterize the function types that the technique is applicable to, which turns out to contain many non-additive functions. Using this insight, we systematically obtain kernelization results for natural problems in graph partitioning, network design, facility location, scheduling, vehicle routing, and computational social choice, thereby improving and generalizing results from the literature.

Node connectivity plays a central role in temporal network analysis. We provide a comprehensive study of various concepts of walks in temporal graphs, that is, graphs with fixed vertex sets but edge sets changing over time. Taking into account the temporal aspect leads to a rich set of optimization criteria for "shortest" walks. Extending and significantly broadening state-of-the-art work of Wu et al. [IEEE TKDE 2016], we provide an algorithm for computing optimal walks that is capable to deal with various optimization criteria and any linear combination of these. It runs in $O (|V| + |E| \log |E|)$ time where $|V|$ is the number of vertices and $|E|$ is the number of time edges. A central distinguishing factor to Wu et al.'s work is that our model allows to, motivated by real-world applications, respect waiting-time constraints for vertices, that is, the minimum and maximum waiting time allowed in intermediate vertices of a walk. Moreover, other than Wu et al. our algorithm also allows to search for walks that pass multiple subsequent edges in one time step, and it can optimize a richer set of optimization criteria. Our experimental studies indicate that our richer modeling can be achieved without significantly worsening the running time when compared to Wu et al.'s algorithms.

We study a simple exchange market, introduced by Gourv\'{e}s, Lesca and Wilczynski (IJCAI-17), where every agent initially holds a single object. The agents have preferences over the objects, and two agents may swap their objects if they both prefer the object of the other agent. The agents live in an underlying social network that governs the structure of the swaps: Two agents can only swap their objects if they are adjacent. We investigate the REACHABLE OBJECT problem, which asks whether a given starting situation can ever lead, by means of a sequence of swaps, to a situation where a given agent obtains a given object. Our results answer several central open questions on the complexity of REACHABLE OBJECT. First, the problem is polynomial-time solvable if the social network is a path. Second, the problem is NP-hard on cliques and generalized caterpillars. Finally, we establish a three-versus-four dichotomy result for preference lists of bounded length: The problem is easy if all preference lists have length at most three, and the problem becomes NP-hard even if all agents have preference lists of length at most four.

Election rules are formal processes that aggregate voters preferences, typically to select a single candidate, called the winner. Most of the election rules studied in the literature require the voters to rank the candidates from the most to the least preferred one. This method of eliciting preferences is impractical when the number of candidates to be ranked is large. We ask how well certain election rules (focusing on positional scoring rules and the Minimax rule) can be approximated from partial preferences collected through one of the following procedures: (i) randomized-we ask each voter to rank a random subset of $\ell$ candidates, and (ii) deterministic-we ask each voter to provide a ranking of her $\ell$ most preferred candidates (the $\ell$-truncated ballot). We establish theoretical bounds on the approximation ratios and we complement our theoretical analysis with computer simulations. We find that mostly (apart from the cases when the preferences have no or very little structure) it is better to use the randomized approach. While we obtain fairly good approximation guarantees for the Borda rule already for $\ell = 2$, for approximating the Minimax rule one needs to ask each voter to compare a larger set of candidates in order to obtain good guarantees.

Cluster Editing, also known as Correlation Clustering, is a well-studied graph modification problem. In this problem, one is given a graph and the task is to perform up to $k$ edge additions or deletions to transform it into a cluster graph, i.e., a graph consisting of a disjoint union of cliques. However, in real-world networks, clusters are often overlapping. For example in social networks, a person might belong to several communities - e.g. those corresponding to work, school, or neighborhood. Other strong motivations come from biological network analysis and from language networks. Trying to cluster words with similar usage in the latter can be confounded by homonyms, that is, words with multiple meanings like "bat." In this paper, we introduce a new variant of Cluster Editing whereby a vertex can be split into two or more vertices. First used in the context of graph drawing, this operation allows a vertex $v$ to be replaced by two vertices whose combined neighborhood is the neighborhood of $v$ (and thus $v$ can belong to more than one cluster). We call the new problem Cluster Editing with Vertex Splitting and we initiate the study of it. We show that it is NP-complete and fixed-parameter tractable when parameterized by the total number $k$ of allowed vertex-splitting and edge-editing operations. In particular, we obtain an $O(2^{9k log k} + n + m)$-time algorithm and a $6k$-vertex kernel.

Betweenness centrality - measuring how many shortest paths pass through a vertex - is one of the most important network analysis concepts for assessing the relative importance of a vertex. The well-known algorithm of Brandes [2001] computes, on an n-vertex and m-edge graph, the betweenness centrality of all vertices in O(nm) worst-case time. In follow-up work, significant empirical speedups were achieved by preprocessing degree-one vertices and by graph partitioning based on cut vertices. We further contribute an algorithmic treatment of degree-two vertices, which turns out to be much richer in mathematical structure than the case of degree-one vertices. Based on these three algorithmic ingredients, we provide a strengthened worst-case running time analysis for betweenness centrality algorithms. More specifically, we prove an adaptive running time bound O(kn), where k < m is the size of a minimum feedback edge set of the input graph.

The Tree Containment problem has many important applications in the study of evolutionary history. Given a phylogenetic network N and a phylogenetic tree T whose leaves are labeled by a set of taxa, it asks if N and T are consistent. While the case of binary N and T has received considerable attention, the more practically relevant variant dealing with biological uncertainty has not. Such uncertainty manifests itself as high-degree vertices ("polytomies") that are "jokers" in the sense that they are compatible with any binary resolution of their children. Contrasting the binary case, we show that this problem, called Soft Tree Containment, is NP-hard, even if N is a binary, multi-labeled tree in which each taxon occurs at most thrice. On the other hand, we reduce the case that each label occurs at most twice to solving a 2-SAT instance of size O(|T|^3). This implies NP-hardness and polynomial-time solvability on reticulation-visible networks in which the maximum in-degree is bounded by three and two, respectively.

Betweenness centrality - measuring how many shortest paths pass through a vertex - is one of the most important network analysis concepts for assessing the relative importance of a vertex. The well-known algorithm of Brandes [2001] computes, on an n-vertex and m-edge graph, the betweenness centrality of all vertices in O(nm) worst-case time. In follow-up work, significant empirical speedups were achieved by preprocessing degree-one vertices and by graph partitioning based on cut vertices. We further contribute an algorithmic treatment of degree-two vertices, which turns out to be much richer in mathematical structure than the case of degree-one vertices. Based on these three algorithmic ingredients, we provide a strengthened worst-case running time analysis for betweenness centrality algorithms. More specifically, we prove an adaptive running time bound O(kn), where k < m is the size of a minimum feedback edge set of the input graph.

The Tree Containment problem has many important applications in the study of evolutionary history. Given a phylogenetic network N and a phylogenetic tree T whose leaves are labeled by a set of taxa, it asks if N and T are consistent. While the case of binary N and T has received considerable attention, the more practically relevant variant dealing with biological uncertainty has not. Such uncertainty manifests itself as high-degree vertices ("polytomies") that are "jokers" in the sense that they are compatible with any binary resolution of their children. Contrasting the binary case, we show that this problem, called Soft Tree Containment, is NP-hard, even if N is a binary, multi-labeled tree in which each taxon occurs at most thrice. On the other hand, we reduce the case that each label occurs at most twice to solving a 2-SAT instance of size O(|T|^3). This implies NP-hardness and polynomial-time solvability on reticulation-visible networks in which the maximum in-degree is bounded by three and two, respectively.

Many real-world networks evolve over time, that is, new contacts appear and old contacts may disappear. They can be modeled as temporal graphs where interactions between vertices (which represent people in the case of social networks) are represented by time-stamped edges. One of the most fundamental problems in (social) network analysis is community detection, and one of the most basic primitives to model a community is a clique. Addressing the problem of finding communities in temporal networks, Viard et al. [TCS 2016] introduced $\Delta$-cliques as a natural temporal version of cliques. Himmel et al. [SNAM 2017] showed how to adapt the well-known Bron-Kerbosch algorithm to enumerate $\Delta$-cliques. We continue this work and improve and extend the algorithm of Himmel et al. to enumerate temporal $k$-plexes (notably, cliques are the special case $k=1$). We define a $\Delta$-$k$-plex as a set of vertices and a time interval, where during this time interval each vertex has in each consecutive $\Delta + 1$ time steps at least one edge to all but at most $k-1$ vertices in the chosen set of vertices. We develop a recursive algorithm for enumerating all maximal $\Delta$-$k$-plexs and perform experiments on real-world social networks that demonstrate the practical feasibility of our approach. In particular, for the special case of $\Delta$-1-plexes (that is, $\Delta$-cliques), we observe that our algorithm is on average significantly faster than the previous algorithms by Himmel et al. [SNAM 2017] and Viard et al. [IPL 2018] for enumerating $\Delta$-cliques.

Diameter -- the task of computing the length of a longest shortest path -- is a fundamental graph problem. Assuming the Strong Exponential Time Hypothesis, there is no $O(n^{1.99})$-time algorithm even in sparse graphs [Roditty and Williams, 2013]. To circumvent this lower bound we aim for algorithms with running time $f(k)(n+m)$ where $k$ is a parameter and $f$ is a function as small as possible. We investigate which parameters allow for such running times. To this end, we systematically explore a hierarchy of structural graph parameters.

Betweenness centrality---measuring how many shortest paths pass through a vertex---is one of the most important network analysis concepts for assessing the relative importance of a vertex. The well-known algorithm of Brandes [J. Math. Sociol.~'01] computes, on an $n$-vertex and $m$-edge graph, the betweenness centrality of all vertices in $O(nm)$ worst-case time. In later work, significant empirical speedups were achieved by preprocessing degree-one vertices and by graph partitioning based on cut vertices. We contribute an algorithmic treatment of degree-two vertices, which turns out to be much richer in mathematical structure than the case of degree-one vertices. Based on these three algorithmic ingredients, we provide a strengthened worst-case running time analysis for betweenness centrality algorithms. More specifically, we prove an adaptive running time bound $O(kn)$, where $k < m$ is the size of a minimum feedback edge set of the input graph., Comment: An extended abstract of this work appears in the proceedings of the 29th International Symposium on Algorithms and Computation (ISAAC 2018)

We study an NP-hard problem motivated by energy-efficiently maintaining the connectivity of a symmetric wireless communication network: Given an edge-weighted $n$-vertex graph, find a connected spanning subgraph of minimum cost, where the cost is determined by letting each vertex pay the most expensive edge incident to it in the subgraph. On the negative side, we show that $o(\log n)$-approximating the difference $d$ between the optimal solution cost and a natural lower bound is NP-hard and that, under the Exponential Time Hypothesis, there are no exact algorithms running in $2^{o(n)}$ time or in $f(d)\cdot n^{O(1)}$ time for any computable function $f$. Moreover, we show that the special case of connecting $c$ network components with minimum additional cost generally cannot be polynomial-time reduced to instances of size $c^{O(1)}$ unless the polynomial-time hierarchy collapses. On the positive side, we provide an algorithm that reconnects $O(\log n)$ connected components with minimum additional cost in polynomial time. These algorithms are motivated by application scenarios of monitoring areas or where an existing sensor network may fall apart into several connected components due to sensor faults. In experiments, the algorithm outperforms CPLEX with known ILP formulations when $n$ is sufficiently large compared to $c$., Comment: Additional experiments, lower bounds strengthened to metric case, added kernelization lower bounds

The task of listing all triangles in an undirected graph is a fundamental graph primitive with numerous applications. It is trivially solvable in time cubic in the number of vertices. It has seen a significant body of work contributing to both theoretical aspects (e.g., lower and upper bounds on running time, adaption to new computational models) as well as practical aspects (e.g. algorithms tuned for large graphs). Motivated by the fact that the worst-case running time is cubic, we perform a systematic parameterized complexity study of triangle enumeration. We provide both positive results (new enumerative kernelizations, "subcubic" parameterized solving algorithms) as well as negative results (presumable uselessness in terms of "faster" parameterized algorithms of certain parameters such as graph diameter). To this end, we introduce new and extend previous concepts., Comment: Appeared at FCT 2017

Inductive $k$-independent graphs generalize chordal graphs and have recently been advocated in the context of interference-avoiding wireless communication scheduling. The NP-hard problem of finding maximum-weight induced $c$-colorable subgraphs, which is a generalization of finding maximum independent sets, naturally occurs when selecting $c$ sets of pairwise non-conflicting jobs (modeled as graph vertices). We investigate the parameterized complexity of this problem on inductive $k$-independent graphs. We show that the Independent Set problem is W[1]-hard even on 2-simplicial 3-minoes---a subclass of inductive 2-independent graphs. In contrast, we prove that the more general Maximum $c$-Colorable Subgraph problem is fixed-parameter tractable on edge-wise unions of cluster and chordal graphs, which are 2-simplicial. In both cases, the parameter is the solution size. Aside from this, we survey other graph classes between inductive 1-inductive and inductive 2-inductive graphs with applications in scheduling.