Parameterized Complexity in the Polynomial Hierarchy was co-recipient of the E.W. Beth Dissertation Prize 2017 for outstanding dissertations in the fields of logic, language, and information. This work extends the theory of parameterized complexity to higher levels of the Polynomial Hierarchy (PH). For problems at higher levels of the PH, a promising solving approach is to develop fixed-parameter tractable reductions to SAT, and to subsequently use a SAT solving algorithm to solve the problem. In this dissertation, a theoretical toolbox is developed that can be used to classify in which cases this is possible. The use of this toolbox is illustrated by applying it to analyze a wide range of problems from various areas of computer science and artificial intelligence.

This book is a state-of-the-art introduction into both algorithmic techniques for fixed-parameter tractability and the structural theory of parameterized complexity classes. It presents detailed proofs of recent advanced results that have not appeared in book form before and replaces the earlier publication "Parameterized Complexity" by Downey and Fellows as the definitive book on this subject. The book will interest computer scientists, mathematicians and graduate students engaged with algorithms and problem complexity.

This comprehensive textbook presents a clean and coherent account of most fundamental tools and techniques in Parameterized Algorithms and is a self-contained guide to the area. The book covers many of the recent developments of the field, including application of important separators, branching based on linear programming, Cut & Count to obtain faster algorithms on tree decompositions, algorithms based on representative families of matroids, and use of the Strong Exponential Time Hypothesis. A number of older results are revisited and explained in a modern and didactic way. The book provides a toolbox of algorithmic techniques. Part I is an overview of basic techniques, each chapter discussing a certain algorithmic paradigm. The material covered in this part can be used for an introductory course on fixed-parameter tractability. Part II discusses more advanced and specialized algorithmic ideas, bringing the reader to the cutting edge of current research. Part III presents complexity results and lower bounds, giving negative evidence by way of W[1]-hardness, the Exponential Time Hypothesis, and kernelization lower bounds. All the results and concepts are introduced at a level accessible to graduate students and advanced undergraduate students. Every chapter is accompanied by exercises, many with hints, while the bibliographic notes point to original publications and related work.

This book constitutes the refereed conference proceedings of the 8th International Conference on Algorithms and Complexity, CIAC 2013, held in Barcelona, Spain, during May 22-24, 2013. The 31 revised full papers presented were carefully reviewed and selected from 75 submissions. The papers present current research in all aspects of computational complexity and the use, design, analysis and experimentation of efficient algorithms and data structures.

This book discusses recent developments in mathematical programming and game theory, and the application of several mathematical models to problems in finance, games, economics and graph theory. All contributing authors are eminent researchers in their respective fields, from across the world. This book contains a collection of selected papers presented at the 2017 Symposium on Mathematical Programming and Game Theory at New Delhi during 9–11 January 2017. Researchers, professionals and graduate students will find the book an essential resource for current work in mathematical programming, game theory and their applications in finance, economics and graph theory. The symposium provides a forum for new developments and applications of mathematical programming and game theory as well as an excellent opportunity to disseminate the latest major achievements and to explore new directions and perspectives.

This book constitutes the proceedings of the 41st International Conference on Current Trends in Theory and Practice of Computer Science held in Pec pod Sněžkou, Czech Republic, during January 24-29, 2015. The book features 8 invited talks and 42 regular papers which were carefully reviewed and selected from 101 submissions. The papers are organized in topical sections named: foundations of computer science; software and Web engineering; data, information, and knowledge engineering; and cryptography, security, and verification.

This book constitutes the refereed proceedings of the 17th International Conference on Theory and Applications of Satisfiability Testing, SAT 2014, held as part of the Vienna Summer of Logic, VSL 2014, in Vienna, Austria, in July 2014. The 21 regular papers, 7 short papers and 4 tool papers presented together with 2 invited talks were carefully reviewed and selected from 78 submissions. The papers have been organized in the following topical sections: maximum satisfiability; minimal unsatisfiability; complexity and reductions; proof complexity; parallel and incremental (Q)SAT; applications; structure; simplification and solving; and analysis.

This book constitutes the refereed proceedings of the 19th International Conference on Formal Engineering Methods, ICFEM 2017, held in Xi'an, China, in November 2017. The 28 revised full papers presented together with one invited talk and two abstracts of invited talks were carefully reviewed and selected from 80 submissions. The conference focuses on all areas related to formal engineering methods, such as verification and validation, software engineering, formal specification and modeling, software security, and software reliability.

This comprehensive and self-contained textbook presents an accessible overview of the state of the art of multivariate algorithmics and complexity. Increasingly, multivariate algorithmics is having significant practical impact in many application domains, with even more developments on the horizon. The text describes how the multivariate framework allows an extended dialog with a problem, enabling the reader who masters the complexity issues under discussion to use the positive and negative toolkits in their own research. Features: describes many of the standard algorithmic techniques available for establishing parametric tractability; reviews the classical hardness classes; explores the various limitations and relaxations of the methods; showcases the powerful new lower bound techniques; examines various different algorithmic solutions to the same problems, highlighting the insights to be gained from each approach; demonstrates how complexity methods and ideas have evolved over the past 25 years.

This thesis is concerned with analyzing the computational complexity of NP-hard problems related to data science. For most of the problems considered in this thesis, the computational complexity has not been intensively studied before. We focus on the complexity of computing exact problem solutions and conduct a detailed analysis identifying tractable special cases. To this end, we adopt a parameterized viewpoint in which we spot several parameters which describe properties of a specific problem instance that allow to solve the instance efficiently. We develop specialized algorithms whose running times are polynomial if the corresponding parameter value is constant. We also investigate in which cases the problems remain intractable even for small parameter values. We thereby chart the border between tractability and intractability for some practically motivated problems which yields a better understanding of their computational complexity. In particular, we consider the following problems. General Position Subset Selection is the problem to select a maximum number of points in general position from a given set of points in the plane. Point sets in general position are well-studied in geometry and play a role in data visualization. We prove several computational hardness results and show how polynomial-time data reduction can be applied to solve the problem if the sought number of points in general position is very small or very large. The Distinct Vectors problem asks to select a minimum number of columns in a given matrix such that all rows in the selected submatrix are pairwise distinct. This problem is motivated by combinatorial feature selection. We prove a complexity dichotomy with respect to combinations of the minimum and the maximum pairwise Hamming distance of the rows for binary input matrices, thus separating polynomial-time solvable from NP-hard cases. Co-Clustering is a well-known matrix clustering problem in data mining where the goal is to partition a matrix into homogenous submatrices. We conduct an extensive multivariate complexity analysis revealing several NP-hard and some polynomial-time solvable and fixed-parameter tractable cases. The generic F-free Editing problem is a graph modification problem in which a given graph has to be modified by a minimum number of edge modifications such that it does not contain any induced subgraph isomorphic to the graph F. We consider three special cases of this problem: The graph clustering problem Cluster Editing with applications in machine learning, the Triangle Deletion problem which is motivated by network cluster analysis, and Feedback Arc Set in Tournaments with applications in rank aggregation. We introduce a new parameterization by the number of edge modifications above a lower bound derived from a packing of induced forbidden subgraphs and show fixed-parameter tractability for all of the three above problems with respect to this parameter. Moreover, we prove several NP-hardness results for other variants of F-free Editing for a constant parameter value. The problem DTW-Mean is to compute a mean time series of a given sample of time series with respect to the dynamic time warping distance. This is a fundamental problem in time series analysis the complexity of which is unknown. We give an exact exponential-time algorithm for DTW-Mean and prove polynomial-time solvability for the special case of binary time series. Diese Dissertation befasst sich mit der Analyse der Berechnungskomplexität von NP-schweren Problemen aus dem Bereich Data Science. Für die meisten der hier betrachteten Probleme wurde die Berechnungskomplexität bisher nicht sehr detailliert untersucht. Wir führen daher eine genaue Komplexitätsanalyse dieser Probleme durch, mit dem Ziel, effizient lösbare Spezialfälle zu identifizieren. Zu diesem Zweck nehmen wir eine parametrisierte Perspektive ein, bei der wir bestimmte Parameter definieren, welche Eigenschaften einer konkreten Probleminstanz beschreiben, die es ermöglichen, diese Instanz effizient zu lösen. Wir entwickeln dabei spezielle Algorithmen, deren Laufzeit für konstante Parameterwerte polynomiell ist. Darüber hinaus untersuchen wir, in welchen Fällen die Probleme selbst bei kleinen Parameterwerten berechnungsschwer bleiben. Somit skizzieren wir die Grenze zwischen schweren und handhabbaren Probleminstanzen, um ein besseres Verständnis der Berechnungskomplexität für die folgenden praktisch motivierten Probleme zu erlangen. Beim General Position Subset Selection Problem ist eine Menge von Punkten in der Ebene gegeben und das Ziel ist es, möglichst viele Punkte in allgemeiner Lage davon auszuwählen. Punktmengen in allgemeiner Lage sind in der Geometrie gut untersucht und spielen unter anderem im Bereich der Datenvisualisierung eine Rolle. Wir beweisen etliche Härteergebnisse und zeigen, wie das Problem mittels Polynomzeitdatenreduktion gelöst werden kann, falls die Anzahl gesuchter Punkte in allgemeiner Lage sehr klein oder sehr groß ist. Distinct Vectors ist das Problem, möglichst wenige Spalten einer gegebenen Matrix so auszuwählen, dass in der verbleibenden Submatrix alle Zeilen paarweise verschieden sind. Dieses Problem hat Anwendungen im Bereich der kombinatorischen Merkmalsselektion. Wir betrachten Kombinationen aus maximalem und minimalem paarweisen Hamming-Abstand der Zeilenvektoren und beweisen eine Komplexitätsdichotomie für Binärmatrizen, welche die NP-schweren von den polynomzeitlösbaren Kombinationen unterscheidet. Co-Clustering ist ein bekanntes Matrix-Clustering-Problem aus dem Gebiet Data-Mining. Ziel ist es, eine Matrix in möglichst homogene Submatrizen zu partitionieren. Wir führen eine umfangreiche multivariate Komplexitätsanalyse durch, in der wir zahlreiche NP-schwere, sowie polynomzeitlösbare und festparameterhandhabbare Spezialfälle identifizieren. Bei F-free Editing handelt es sich um ein generisches Graphmodifikationsproblem, bei dem ein Graph durch möglichst wenige Kantenmodifikationen so abgeändert werden soll, dass er keinen induzierten Teilgraphen mehr enthält, der isomorph zum Graphen F ist. Wir betrachten die drei folgenden Spezialfälle dieses Problems: Das Graph-Clustering-Problem Cluster Editing aus dem Bereich des Maschinellen Lernens, das Triangle Deletion Problem aus der Netzwerk-Cluster-Analyse und das Problem Feedback Arc Set in Tournaments mit Anwendungen bei der Aggregation von Rankings. Wir betrachten eine neue Parametrisierung mittels der Differenz zwischen der maximalen Anzahl Kantenmodifikationen und einer unteren Schranke, welche durch eine Menge von induzierten Teilgraphen bestimmt ist. Wir zeigen Festparameterhandhabbarkeit der drei obigen Probleme bezüglich dieses Parameters. Darüber hinaus beweisen wir etliche NP-Schwereergebnisse für andere Problemvarianten von F-free Editing bei konstantem Parameterwert. DTW-Mean ist das Problem, eine Durchschnittszeitreihe bezüglich der Dynamic-Time-Warping-Distanz für eine Menge gegebener Zeitreihen zu berechnen. Hierbei handelt es sich um ein grundlegendes Problem der Zeitreihenanalyse, dessen Komplexität bisher unbekannt ist. Wir entwickeln einen exakten Exponentialzeitalgorithmus für DTW-Mean und zeigen, dass der Spezialfall binärer Zeitreihen in polynomieller Zeit lösbar ist.