The 2-admissibility of a graph is a promising measure to identify real-world networks which have an algorithmically favourable structure. In contrast to other related measures, like the weak/strong 2-colouring numbers or the maximum density of graphs that appear as 1-subdivisions, the 2-admissibility can be computed in polynomial time. However, so far these results are theoretical only and no practical implementation to compute the 2-admissibility exists. Here we present an algorithm which decides whether the 2-admissibility of an input graph G is at most p in time O(p⁴ |V(G)|) and space O(|E(G)| + p²). The simple structure of the algorithm makes it easy to implement. We evaluate our implementation on a corpus of 214 real-world networks and find that the algorithm runs efficiently even on networks with millions of edges, that it has a low memory footprint, and that indeed many networks have a small 2-admissibility.

We unify and extend previous kernelization techniques in sparse classes [6,17] by defining water lilies and show how they can be used in bounded expansion classes to construct linear bikernels for (r, c)-Dominating Set, (r, c)-Scattered Set, Total r-Domination, r-Roman Domination, and a problem we call (r, [λ, μ])-Domination (implying a bikernel for r-Perfect Code). At the cost of slightly changing the output graph class our bikernels can be turned into kernels. We further demonstrate how these constructions can be combined to create 'multikernels', meaning graphs that represent kernels for multiple problems at once. Concretely, we show that r-Dominating Set, Total r-Domination, and r-Roman Domination admit a multikernel; as well as r-Dominating Set and 2r-Independent Set for multiple values of r at once.

Inspired by the potential of improving tractability via gap- or above-guarantee parametrisations, we investigate the complexity of Dominating Set when given a suitable lower-bound witness. Concretely, we consider being provided with a maximal r-independent set X (a set in which all vertices have pairwise distance at least r+1) along the input graph G which, for r >= 2, lower-bounds the minimum size of any dominating set of G. In the spirit of gap-parameters, we consider a parametrisation by the size of the "residual" set R := V(G) \ N[X]. Our work aims to answer two questions: How does the constant r affect the tractability of the problem and does the restriction to sparse graph classes help here? For the base case r = 2, we find that the problem is paraNP-complete even in apex- and bounded-degree graphs. For r = 3, the problem is W[2]-hard for general graphs but in FPT for nowhere dense classes and it admits a linear kernel for bounded expansion classes. For r >= 4, the parametrisation becomes essentially equivalent to the natural parameter, the size of the dominating set.

We study several problems related to graph modification under connectivity constraints from the perspective of parameterized complexity. In particular, we study (a) (Weighted) Biconnectivity Deletion, where we are tasked with deleting k edges while preserving biconnectivity in an undirected graph, and (b) Path-contraction Preserving Strong Connectivity, where we want to maintain strong connectivity of a digraph while path-contracting k arcs. The parameterized tractability of this last problem was posed in Bang-Jensen and Yeo (2008) [1] as an open question and we answer it here in the negative. On the other hand, we show that preserving (weighted) biconnectivity is fixed-parameter tractable (FPT) and the unweighted case even admits a randomized polynomial kernel. Finally, we show that the most general case of the (unweighted) problem where one would like to preserve ρ-vertex connectivity for any ρ is (non-uniformly) FPT parameterized by k and ρ.

The Flow Decomposition problem, which asks for the smallest set of weighted paths that “covers” a flow on a DAG, has recently been used as an important computational step in transcript assembly. We prove the problem is in FPT when parameterized by the number of paths by giving a practical linear fpt algorithm. Further, we implement and engineer a Flow Decomposition solver based on this algorithm, and evaluate its performance on RNA-sequence data. Crucially, our solver finds exact solutions while achieving runtimes competitive with a state-of-the-art heuristic. Finally, we contextualize our design choices with two hardness results related to preprocessing and weight recovery. Specifically, k-Flow Decomposition does not admit polynomial kernels under standard complexity assumptions, and the related problem of assigning (known) weights to a given set of paths is NP-hard.

We consider the problems ZERO EXTENSION and METRIC LABELLING under the paradigm of parameterized complexity. These are natural, well-studied problems with important applications, but have previously not received much attention from parameterized complexity. Depending on the chosen cost function $μ$, we find that different algorithmic approaches can be applied to design FPT-algorithms: for arbitrary $μ$ we parameterized by the number of edges that cross the cut (not the cost) and show how to solve ZERO EXTENSION in time $O(|D|^{O(k^2)} n^4 \log n)$ using randomized contractions. We improve this running time with respect to both parameter and input size to $O(|D|^{O(k)} m)$ in the case where $μ$ is a metric. We further show that the problem admits a polynomial sparsifier, that is, a kernel of size $O(k^{|D|+1})$ that is independent of the metric $μ$. With the stronger condition that $μ$ is described by the distances of leaves in a tree, we parameterize by a gap parameter $(q - p)$ between the cost of a true solution $q$ and a `discrete relaxation' $p$ and achieve a running time of $O(|D|^{q-p} |T|m + |T|ϕ(n,m))$ where $T$ is the size of the tree over which $μ$ is defined and $ϕ(n,m)$ is the running time of a max-flow computation. We achieve a similar running for the more general METRIC LABELLING, while also allowing $μ$ to be the distance metric between an arbitrary subset of nodes in a tree using tools from the theory of VCSPs. We expect the methods used in the latter result to have further applications.

An out-branching and an in-branching of a digraph D are called k -distinct if each of them has k arcs absent in the other. Bang-Jensen, Saurabh and Simonsen (2016) proved that the problem of deciding whether a strongly connected digraph D has k -distinct out-branching and in-branching is fixed-parameter tractable (FPT) when parameterized by k . They asked whether the problem remains FPT when extended to arbitrary digraphs. Bang-Jensen and Yeo (2008) asked whether the same problem is FPT when the out-branching and in-branching have the same root. By linking the two problems with the problem of whether a digraph has an out-branching with at least k leaves (a leaf is a vertex of out-degree zero), we first solve the problem of Bang-Jensen and Yeo (2008). We then develop a new digraph decomposition and using it prove that the problem of Bang-Jensen et al. (2016) is FPT for all digraphs.

We study the computational complexity of identifying dense substructures, namely r/2-shallow topological minors and r-subdivisions. Of particular interest is the case r = 1, when these substructures correspond to very localized relaxations of subgraphs. Since Densest Subgraph can be solved in polynomial time, we ask whether these slight relaxations also admit efficient algorithms. In the following, we provide a negative answer: Dense r/2-Shallow Topological Minor and Dense r-Subdivsion are already NP-hard for r = 1 in very sparse graphs. Further, they do not admit algorithms with running time 2^(o(tw^2)) n^O(1) when parameterized by the treewidth of the input graph for r > 2 unless ETH fails.

Growing interest in modeling large, complexnetworks has spurred significant research into generative graphmodels. Kronecker-style models (e.g. SKG and R-MAT) are oftenused due to their scalability and ability to mimic key propertiesof real-world networks. Although a few papers theoreticallyestablish these models' behavior for specific parameters, manyclaims used to justify their use are supported only empirically. In this work, we prove several results using asymptotic analysiswhich illustrate that empirical studies may not fully capture thetrue behavior of the models. Paramount to the widespread adoption of Kronecker-stylemodels was the introduction of a linear-time edge-samplingvariant (R-MAT), which existing literature typically treats asinterchangeable with SKG. We prove that although several R-MAT formulations are asymptotically equivalent, their behaviordiverges from that of SKG. Further, we show these resultsare observable even at relatively small graph sizes. Second, weconsider a case where asymptotic analysis reveals unexpectedbehavior within a given model.

We present a linear-time algorithm to compute a decomposition scheme for graphs G that have a set X ⊆ V ( G ), called a treewidth-modulator , such that the treewidth of G − X is bounded by a constant. Our decomposition, called a protrusion decomposition , is the cornerstone in obtaining the following two main results. Our first result is that any parameterized graph problem (with parameter k ) that has a finite integer index and such that Y es -instances have a treewidth-modulator of size O ( k ) admits a linear kernel on the class of H -topological-minor-free graphs, for any fixed graph H . This result partially extends previous meta-theorems on the existence of linear kernels on graphs of bounded genus and H -minor-free graphs. Let F be a fixed finite family of graphs containing at least one planar graph. Given an n -vertex graph G and a non-negative integer k , P lanar - F -D eletion asks whether G has a set X ⊆ V ( G ) such that | X | ⩽ k and G − X is H -minor-free for every H ϵ F . As our second application, we present the first single-exponential algorithm to solve P lanar - F -D eletion . Namely, our algorithm runs in time 2 O ( k ) · n 2 , which is asymptotically optimal with respect to k . So far, single-exponential algorithms were only known for special cases of the family F .

We study two clustering problems, Starforest Editing, the problem of adding and deleting edges to obtain a disjoint union of stars, and the generalization Bicluster Editing. We show that, in addition to being NP-hard, none of the problems can be solved in subexponential time unless the exponential time hypothesis fails. Misra, Panolan, and Saurabh (MFCS 2013) argue that introducing a bound on the number of connected components in the solution should not make the problem easier: In particular, they argue that the subexponential time algorithm for editing to a fixed number of clusters (p-Cluster Editing) by Fomin et al. (J. Comput. Syst. Sci., 80(7) 2014) is an exception rather than the rule. Here, p is a secondary parameter, bounding the number of components in the solution. However, upon bounding the number of stars or bicliques in the solution, we obtain algorithms which run in time O(2^{3*sqrt(pk)} + n + m) for p-Starforest Editing and O(2^{O(p * sqrt(k) * log(pk))} + n + m) for p-Bicluster Editing. We obtain a similar result for the more general case of t-Partite p-Cluster Editing. This is subexponential in k for a fixed number of clusters, since p is then considered a constant. Our results even out the number of multivariate subexponential time algorithms and give reasons to believe that this area warrants further study.

A fundamental theorem of Courcelle states that every problem definable in Monadic Second-Order Logic (MSO) is solvable in linear time on graphs of bounded treewidth.In this paper, we report on our ongoing effort to develop a general purpose software tool designed to solve MSO-definable optimization and decision problems on graphs of small treewidth.We discuss the theoretical underpinnings of our tool and present experimental results, which indicate that for some natural optimization problems MSO based approaches might be a suitable alternative to ILP solvers.