Mathias Weller

Abstract. Abstract We study the NP-hard Target Set Selection (TSS) problem occurring in social network analysis. Roughly speaking, given a graph where each vertex is associated with a threshold, in TSS the task is to select a minimum-size "target set" such that all vertices of the graph get activated. Activation is a dynamic process. First, only the vertices in the target set are active. Then, a vertex becomes active if the number of its active neighbors exceeds its threshold, and so on. TSS models the spread of information, infections, and influence in networks. Complementing results on its polynomial-time approximability and extending results for its restriction to trees and bounded treewidth graphs, we classify the influence of the parameters "diameter", "cluster editing number", "vertex cover number", and "feedback edge set number" of the underlying graph on the problem's computational complexity, revealing both tractable and intractable cases. For instance, even for diameter-two split graphs TSS remains W[2]-hard with respect to the parameter "size of the target set". TSS can be efficiently solved on graphs with small feedback edge set number and also turns out to be fixed-parameter tractable when parameterized by the vertex cover number. Both results contrast known parameterized intractability results for the parameter "treewidth". While these tractability results are relevant for sparse networks, we also show efficient fixed-parameter algorithms for the parameter "cluster editing number", yielding tractability for certain dense networks.

Abstract. We provide a new characterization of the NP-hard arc routing problem Rural Postman in terms of a constrained variant of minimum-weight perfect matching on bipartite graphs. To this end, we employ a parameterized equivalence between Rural Postman and Eulerian Extension, a natural arc addition problem in directed multigraphs. We indicate the NP-hardness of the introduced matching problem. In particular, we use the matching problem to make partial progress towards answering the open question about the parameterized complexity of Rural Postman with respect to the parameter "number of weakly connected components in the graph induced by the required arcs". This is a more than thirty years open and long-time neglected question with significant practical relevance.

Abstract. We present a first thorough theoretical analysis of the Transitivity Editing problem on digraphs. Herein, the task is to make a given digraph transitive by a minimum number of arc insertions or deletions. Transitivity Editing has applications in for the detection of hierarchical structure in molecular characteristics of diseases. We demonstrate that if the input digraph does not contain "diamonds", then there is an optimal solution that performs only arc deletions. This fact helps us construct a first proof of NP-hardness, which also extends to the restricted cases in which the input digraph is acyclic or has maximum degree three. By providing an O(k²)-vertex problem kernel, we answer an open question from the literature. In case of digraphs with maximum degree d, an O(kd)-vertex problem kernel can be shown. Moreover, we improve previous fixed-parameter algorithms, now achieving a running time of O(2.57^k + n³) for an n-vertex digraph if k arc modifications are sufficient to make it transitive. Our hardness as well as algorithmic results transfer to Transitivity Deletion, where only arc deletions are allowed.

Abstract. Golomb rulers are special rulers where for any two marks it holds that the distance between them is unique. They find applications in positioning of radio channels, radio astronomy, communication networks, and bioinformatics. An important subproblem in constructing "compact" Golomb rulers is Golomb Subruler Mark Deletion (GSMD), which asks whether it is possible to make a given ruler Golomb by removing at most k marks. We initiate a study of GSMD from a parameterized complexity perspective. In particular, we develop a hypergraph characterization of rulers and consider the construction and structure of the corresponding hypergraphs. We exploit their properties to derive polynomial-time data reduction rules that lead to a problem kernel for GSMD with O(k³) marks. Finally, we provide a simplified NP-hardness construction for GSMD.

Abstract. We present a linear-time kernelization algorithm that transforms a given planar graph G with domination number γ(G) into a planar graph G of size O(γ(G)) with γ(G) = γ(G). In addition, a minimum dominating set for G can be inferred from a minimum dominating set for G . In terms of parameterized algorithmics, this implies a linear-size problem kernel for the NP-hard Dominating Set problem on planar graphs, where the kernelization takes linear time. This improves on previous kernelization algorithms that provide linear-size kernels in cubic time.

Abstract. Given a collection C of partitions of a base set S, the NP-hard Consensus Clustering problem asks for a partition of S which has a total Mirkin distance of at most t to the partitions in C, where t is a nonnegative integer. We present a parameterized algorithm for Consensus Clustering with running time O(4.24^k k³ + |C||S|² ), where k := t/|C| is the average Mirkin distance of the solution partition to the partitions of C. Furthermore, we strengthen previous hardness results for Consensus Clustering, showing that Consensus Clustering remains NP-hard even when all input partitions contain at most two subsets. Finally, we study a local search variant of Consensus Clustering, showing W[1]-hardness for the parameter "radius of the Mirkin-distance neighborhood". In the process, we also consider a local search variant of the related Cluster Editing problem, showing W[1]-hardness for the parameter "radius of the edge modification neighborhood".

Abstract. Eulerian Extension (EE) is the problem to make an arc-weighted directed multigraph Eulerian by adding arcs of minimum total cost. EE is NP-hard and has been shown fixed-parameter tractable with respect to the number of arc additions. Complementing this result, on the way to answering an open question, we show that EE is fixed-parameter tractable with respect to the combined parameter "number of connected components in the underlying undirected multigraph" and "sum of indeg(v)-outdeg(v) over all vertices v in the input multigraph where this value is positive." Moreover, we show that EE is unlikely to admit a polynomial-size problem kernel for this parameter combination and for the parameter "number of arc additions".

Abstract. We study the NP-complete TARGET SET SELECTION (TSS) problem occurring in social network analysis. Complementing results on its approximability and extending results for its restriction to trees and bounded treewidth graphs, we classify the influence of the parameters "diameter", "cluster edge deletion number", "vertex cover number", and "feedback edge set number" of the underlying graph on the problem's complexity, revealing both tractable and intractable cases. For instance, even for diameter-two split graphs TSS remains very hard. TSS can be efficiently solved on graphs with small feedback edge set number and also turns out to be fixed-parameter tractable when parameterized by the vertex cover number, both results contrasting known parameterized intractability results for the parameter treewidth. While these tractability results are relevant for sparse networks, we also show efficient fixed-parameter algorithms for the parameter cluster edge deletion number, yielding tractability for certain dense networks.

Abstract. Eulerian extension problems aim at making a given (directed) (multi-)graph Eulerian by adding a minimum-cost set of edges (arcs). These problems have natural applications in scheduling and routing and are closely related to the CHINESE POSTMAN and RURAL POSTMAN problems. Our main result is to show that the NP-hard WEIGHTED MULTIGRAPH EULERIAN EXTENSION is fixed-parameter tractable with respect to the number k of extension edges (arcs). The corresponding running time amounts to O(4^k n⁴). This implies a fixed-parameter tractability result for the "equivalent" RURAL POSTMAN problem. In addition, we develop several polynomial-time algorithms for natural Eulerian extension problems.

Abstract. Parsimony haplotyping is the problem of finding a smallest size set of haplotypes that can explain a given set of genotypes. The problem is NP-hard, and many heuristic and approximation algorithms as well as polynomial-time solvable special cases have been discovered. We propose improved fixed-parameter tractability results with respect to the parameter "size of the target haplotype set" k by presenting an O^*(k^(4k))-time algorithm. This also applies to the practically important constrained case, where we can only use haplotypes from a given set. Furthermore, we show that the problem becomes polynomial-time solvable if the given set of genotypes is complete, i.e., contains all possible genotypes that can be explained by the set of haplotypes.

Abstract. Given an undirected graph G and an integer k≥0, the NP-hard 2-LAYER PLANARIZATION problem asks whether G can be transformed into a forest of caterpillar trees by removing at most k edges. Since transforming G into a forest of caterpillar trees requires breaking every cycle, the size f of a minimum feedback edge set is a natural parameter with f≤k. We improve on previous fixed-parameter tractability results with respect to k by presenting a problem kernel with O(f) vertices and edges and a new search-tree based algorithm, both with about the same worst-case bounds for f as the previous results for k, although we expect f to be smaller than k for a wide range of input instances.

Abstract. We first-time present a thorough theoretical analysis of the Transitivity Editing problem on digraphs. Herein, the task is to perform a minimum number of arc insertions or deletions in order to make a given digraph transitive. This problem has recently been identified as important for the detection of hierarchical structure in molecular characteristics of disease. Mixing Transitivity Editing up with the companion problems on undirected graphs, in the literature it has been erroneously claimed to be NP-hard. We correct this error by presenting a first proof of NP-hardness, which also extends to showing that the restricted cases where the input digraph is acyclic or has maximum degree four remain NP-hard. Moreover, we improve previous fixed-parameter algorithms, now achieving a running time of O(2.57^k +n³) for an n-vertex digraph where k arc modifications have to be performed. In particular, providing an O(k²)-vertex kernel, we positively answer an open question from the literature. In case of digraphs with maximum degree d, an O(kd)-vertex problem kernel can be shown. We also demonstrate that if the input digraph contains no "diamond structure", then one can always find an optimal solution that exclusively performs arc deletions. Most of our results (including NP-hardness) can be transferred to the Transitivity Deletion problem, where only arc deletions are allowed.

Abstract. In Bioinformatics, the task of hierarchically classifying diseases with noisy data recently led to studying the Transitivity Editing problem, which is to change a given digraph by adding and removing a minimum number of arcs such that the resulting digraph is transitive. We show that both Transitivity Editing and Transitivity Deletion, which does not allow the insertion of arcs, are NP-complete even when restricted to DAGs. We provide polynomial-time executable data reduction rules that yield an O(k²)-vertex kernel for general digraphs and an O(k)-vertex kernel for digraphs of bounded degree. Furthermore, a heuristic approach and a search tree algorithm are presented. We show an asymptotic running time of O(2.57^k + n³) for Transitivity Editing and O(2^k + n³) for Transitivity Deletion.

Abstract. In this work, we give an overview of the research done so far on the topic of Sudoku grid enumeration, solving, and generating Sudoku puzzles. We examine possible extensions and generalizations of previous work on solving and generating Sudoku puzzles focusing mainly on rulebased solvers. A possible way to influence the difficulty of a generated Sudoku puzzle is described and we introduce new deduction rules for solving a puzzle based on the rules described by David Eppstein in his paper "Nonrepetitive Paths and Cycles in Graphs with Application to Sudoku". We then generalize these new rules further leading to an efficient constraint propagation algorithm that is able to solve puzzles that could not be solved by applying only Eppstein's deduction rules. The implementation of this strategy and how it may be used to implement the special cases is explained, followed by a practical evaluation of the solving power of all presented solvers.