Dagstuhl Publishing
http://www.dagstuhl.de
RSS feed announcing the latest publications published by Schloss Dagstuhlen-en2010-06-082010-06-08http://www.dagstuhl.de/rss.phpLIPIcs, Volume 69, TYPES'15, Complete Volume
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8622
LIPIcs, Volume 69, TYPES'15, Complete VolumeFri, 16 Mar 2018 08:41:51 +0100http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8622Body-Centric Computing (Dagstuhl Reports 17392)
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8592
The rise of technology that can support the active human body – in contrast to the previously prevalent paradigm of interacting with computers while sitting still – such as wearables, quantified self systems and mobile computing highlights an opportunity for a new era of "body-centric computing". However, most work in this area has taken quite an instrumental perspective, focusing on achieving extrinsic performance objectives. Phenomenology, however, highlights that it is also important to support the experiential perspective of living an active life, that is, technology should also help people focus on their lived experiences and personal growth to deepen their understanding and engagement with their own bodies.We find that despite the work on embodiment, the use of technology to support the corporeal, pulsating and felt body has been notably absent. We believe the reason for this is due to limited knowledge about how to understand, analyse and correlate the vast amount of data from the various sensors worn by individuals and populations in real-time so that we can present it in a way that it supports people's felt experience. In order to drive such an agenda that supports both instrumental and experiential perspectives of the active human body, this seminar brings together leading experts, including those who are central to the development of products and ideas relating to wearables, mobile computing, quantified self, data analysis and visualization, exertion games and computer sports science. The goal is to address key questions around the use of sensor data to support both instrumental and experiential perspectives of the active human body and to jump-start collaborations between people from different backgrounds to pioneer new approaches for a body-centric computing future.Fri, 16 Mar 2018 07:56:18 +0100http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8592LIPIcs, Volume 73, TQC'17, Complete Volume
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8620
LIPIcs, Volume 73, TQC'17, Complete VolumeWed, 14 Mar 2018 09:32:32 +0100http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8620LIPIcs, Volume 89, IPEC'17, Complete Volume
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8616
LIPIcs, Volume 89, IPEC'17, Complete VolumeTue, 13 Mar 2018 13:56:32 +0100http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8616LIPIcs, Volume 96, STACS'18, Complete Volume
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8617
LIPIcs, Volume 96, STACS'18, Complete VolumeTue, 13 Mar 2018 13:53:58 +0100http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8617Deep Learning for Computer Vision (Dagstuhl Seminar 17391)
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8591
The field of computer vision engages in the goal to enable and enhance a machine’s ability to infer knowledge and information from spatial and visual input data. Recent advances in data-driven learning approaches, accelerated by increasing parallel computing power and a ubiquitous availability of large amounts of data, pushed the boundaries of almost every vision related subdomain. The most prominent example of these machine learning approaches is a so called deep neural network (DNN), which works as a general function approximator and can be trained to learn a mapping between given input and target output data. Research on and with these DNN is generally referred to as Deep Learning. Despite its high dimensional and complex input space, research in the field of computer vision was and still is one of the main driving forces for new development in machine and deep learning, and vice versa. This seminar aims to discuss recent works on theoretical and practical advances in the field of deep learning itself as well as state-of-the-art results achieved by applying learning based approaches to various vision problems. Our diverse spectrum of topics includes theoretical and mathematical insights focusing on a better understanding of the fundamental concepts behind deep learning and a multitude of specific research topics facilitating an exchange of knowledge between peers of the research community.Wed, 07 Mar 2018 14:52:02 +0100http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8591Approaches and Applications of Inductive Programming (Dagstuhl Seminar 17382)
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8590
This report documents the program and the outcomes of Dagstuhl Seminar 17382 "Approaches and Applications of Inductive Programming". After a short introduction to the state of the art toinductive programming research, an overview of the introductory tutorials, the talks, program demonstrations, and the outcomes of discussion groups is given.Wed, 07 Mar 2018 14:51:30 +0100http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8590Recent Trends in Knowledge Compilation (Dagstuhl Seminar 17381)
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8589
Knowledge compilation (KC) is a research topic which aims to investigate the possibility of circumventing the computational intractability of hard tasks, by preprocessing part of the available information, common to a number of instances. Pioneered almost three decades ago, KC is nowadays a very active research field, transversal to several areas within computer science. Among others, KC intersects knowledge representation, constraint satisfaction, algorithms, complexity theory, machine learning, and databases.The results obtained so far take various forms, from theory (compilability settings, definition of target languages for KC, complexity results, succinctness results, etc.) to more practical results (development and evaluation of compilers and other preprocessors, applications to diagnosis, planning, automatic configuration, etc.). Recently, KC has been positioned as providing a systematic method for solving problems beyond NP, and also found applications in machine learning.The goal of this Dagstuhl Seminar was to advance both aspects of KC, and to pave the way for a fruitful cross-fertilization between the topics, from theory to practice. The program included a mixture of long and short presentations, with discussions. Several long talks with a tutorial flavor introduced the participants to the variety of aspects in knowledge compilation and the diversity of techniques used. System presentations as well as an open problem session were also included in the program.Wed, 07 Mar 2018 14:50:47 +0100http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8589Cybersafety in Modern Online Social Networks (Dagstuhl Reports 17372)
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8588
This report documents the program and the outcomes of Dagstuhl Seminar 17372 "Cybersafety in Modern Online Social Networks." The main motivation behind the seminar stems from the increased relevance of threats and challenges in the context of cybersafety, especially in modern online social networks, where the range of malicious activities perpetrated by malevolent actors is regrettably wide. These include spreading malware and spam, controlling and operating fake/compromised accounts, artificially manipulating the reputation of accounts and pages, and spreading false information as well as terrorist propaganda.The reasons for the success of such attacks are manifold. The users of social networking services tend to extend their trust of the services and profiles of their acquaintances to unknown users and other third parties: despite the service providers' attempts at keeping their audiences identifiable and accountable, creating a fake profile, also in another person's name, is very simple. Even partially or fully taking over a profile is comparatively easy, and comes with the benefit of the trust this profile has accrued over time, as many credentials are easy to acquire. Further, even seemingly innocuous issues such as the design and presentation of user interfaces can result in implications for cybersafety. The failure to understand the interfaces and ramifications of certain online actions can lead to extensive over-sharing. Even the limited information of partial profiles may be sufficient for abuse by inference on specific features only. This is especially worrisome for new or younger users of a system that might unknowingly expose information or have unwanted interactions simply due to not fully understanding the platform they are using. Unfortunately, research in cybersafety has looked at the various sub-problems in isolation, almost exclusively relying on algorithms aimed at detecting malicious accounts that act similarly, or analyzing specific lingual patterns. This ultimately yields a cat-and-mouse game, mostly played on economic grounds, whereby social network operators attempt to make it more and more costly for fraudsters to evade detection, which unfortunately tends to fail to measure and address the impact of safety threats from the point of view of regular individuals.This prompts the need for a multi-faceted, multi-disciplinary, holistic approach to advancing the state of knowledge on cybersafety in online social networks, and the ways in which it can be researched and protected. Ultimately, we want to work towards development of a cutting-edge research agenda and technical roadmap that will allow the community to develop and embed tools to detect malice within the systems themselves, and to design effective ways to enhance their safety online. This seminar was intended to bring together researchers from synergistic research communities, including experts working on information and system security on one hand, and those with expertise in human/economic/sociological factors of security on the other. More specifically, in the field of cybersafety, there exist a number of interconnected, complex issues that cannot be addressed in isolation, but have to be tackled and countered together. Moreover, it is necessary for these challenges to be studied under a multi-disciplinary light. Consequently, we identified and focused on the most relevant issues in cybersafety, and explored both current and emerging solutions. Specifically, we discussed four problems that are the most pressing both in terms of negative impact and potential danger on individuals and society, and challenging open research problems requiring a multi-disciplinary approach:Cyberbullying & Hate Speech, CyberFraud & Scams, Reputation Manipulation & Fake Activities, and Propaganda.Overall, the seminar was organized to include a number of long talks from senior experts in the field, covering the four main topics above, followed by a series of short talks from the participants about work in progress and recent results, and finally working groups to foster collaborations, brainstorming, and setting of a research agenda forward.Wed, 07 Mar 2018 14:50:22 +0100http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8588Deduction Beyond First-Order Logic (Dagstuhl Seminar 17371)
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8587
This report documents the program and the outcomes of Dagstuhl Seminar 17371 "Deduction Beyond First-Order Logic." Much research in the past two decades was dedicated to automating first-order logic with equality. However, applications often need reasoning beyond this logic. This includes genuinely higher-order reasoning, reasoning in theories that are not finitely axiomatisable in first-order logic (such as those including transitive closureoperators or standard arithmetic on integers or reals), or reasoning by mathematical induction. Other practical problems need a mixture of first-order proof search and some more advanced reasoning (for instance, about higher-order formulas), or simply higher-level reasoning steps. The aim of the seminar was to bring together first-order automated reasoning experts and researchers working on deduction methods and tools that go beyond first-order logic. The seminar was dedicated to the exchange of ideas to facilitate the transition from first-order to more expressive settings.Wed, 07 Mar 2018 14:49:27 +0100http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8587Finite and Algorithmic Model Theory (Dagstuhl Seminar 17361)
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8586
This report documents the program and the outcomes of Dagstuhl Seminar 17361 "Finite and Algorithmic Model Theory".Wed, 07 Mar 2018 14:48:29 +0100http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8586Front Matter, Table of Contents, Preface, Conference Organization
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8593
Front Matter, Table of Contents, Preface, Conference OrganizationWed, 28 Feb 2018 15:29:17 +0100http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8593Evaluation and Enumeration Problems for Regular Path Queries
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8594
Regular path queries (RPQs) are a central component of graph databases. We investigate decision- and enumeration problems concerning the evaluation of RPQs under several semantics that have recently been considered: arbitrary paths, shortest paths, and simple paths. Whereas arbitrary and shortest paths can be enumerated in polynomial delay, the situation is much more intricate for simple paths. For instance, already the question if a given graph contains a simple path of a certain length has cases with highly non-trivial solutions and cases that are long-standing open problems. We study RPQ evaluation for simple paths from a parameterized complexity perspective and define a class of simple transitive expressions that is prominent in practice and for which we can prove a dichotomy for the evaluation problem. We observe that, even though simple path semantics is intractable for RPQs in general, it is feasible for the vast majority of RPQs that are used in practice. At the heart of our study on simple paths is a result of independent interest: the two disjoint paths problem in directed graphs is W[1]-hard if parameterized by the length of one of the two paths.Wed, 28 Feb 2018 15:29:17 +0100http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8594Rewriting Guarded Existential Rules into Small Datalog Programs
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8595
The goal of this paper is to understand the relative expressiveness of the query language in which queries are specified by a set of guarded (disjunctive) tuple-generating dependencies (TGDs) and an output (or 'answer') predicate. Our main result is to show that every such query can be translated into a polynomially-sized (disjunctive) Datalog program if the maximal number of variables in the (disjunctive) TGDs is bounded by a constant. To overcome the challenge that Datalog has no direct means to express the existential quantification present in TGDs, we define a two-player game that characterizes the satisfaction of the dependencies, and design a Datalog query that can decide the existence of a winning strategy for the game. For guarded disjunctive TGDs, we can obtain Datalog rules with disjunction in the heads. However, the use of disjunction is limited, and the resulting rules fall into a fragment that can be evaluated in deterministic single exponential time. We proceed quite differently for the case when the TGDs are not disjunctive and we show that we can obtain a plain Datalog query. Notably, unlike previous translations for related fragments, our translation requires only polynomial time if the maximal number of variables in the (disjunctive) TGDs is bounded by a constant. Wed, 28 Feb 2018 15:29:17 +0100http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8595Satisfiability for SCULPT-Schemas for CSV-Like Data
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8596
SCULPT is a simple schema language inspired by the recent working effort towards a recommendation by the World Wide Web Consortium (W3C) for tabular data and metadata on the Web. In its core, a SCULPT schema consists of a set of rules where left-hand sides select sets of regions in the tabular data and the right-hand sides describe the contents of these regions. A document (divided in cells by row- and column-delimiters) then satisfies a schema if it satisfies every rule. In this paper, we study the satisfiability problem for SCULPT schemas. As SCULPT describes grid-like structures, satisfiability obviously becomes undecidable rather quickly even for very restricted schemas. We define a schema language called L-SCULPT (Lego SCULPT) that restricts the walking power of SCULPT by selecting rectangular shaped areas and only considers tables for which selected regions do not intersect. Depending on the axes used by L-SCULPT, we show that satisfiability is PTIME-complete or undecidable. One of the tractable fragments is practically useful as it extends the structural core of the current W3C proposal for schemas over tabular data. We therefore see how the navigational power of the W3C proposal can be extended while still retaining tractable satisfiability tests.Wed, 28 Feb 2018 15:29:17 +0100http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8596Querying the Unary Negation Fragment with Regular Path Expressions
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8597
The unary negation fragment of first-order logic (UNFO) has recently been proposed as a generalization of modal logic that shares many of its good computational and model-theoretic properties. It is attractive from the perspective of database theory because it can express conjunctive queries (CQs) and ontologies formulated in many description logics (DLs). Both are relevant for ontology-mediated querying and, in fact, CQ evaluation under UNFO ontologies (and thus also under DL ontologies) can be `expressed' in UNFO as a satisfiability problem. In this paper, we consider the natural extension of UNFO with regular expressions on binary relations. The resulting logic UNFOreg can express (unions of) conjunctive two-way regular path queries (C2RPQs) and ontologies formulated in DLs that include transitive roles and regular expressions on roles. Our main results are that evaluating C2RPQs under UNFOreg ontologies is decidable, 2ExpTime-complete in combined complexity, and coNP-complete in data complexity, and that satisfiability in UNFOreg is 2ExpTime-complete, thus not harder than in UNFO.Wed, 28 Feb 2018 15:29:17 +0100http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8597Enumeration Complexity of Conjunctive Queries with Functional Dependencies
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8598
We study the complexity of enumerating the answers of Conjunctive Queries (CQs) in the presence of Functional Dependencies (FDs). Our focus is on the ability to list output tuples with a constant delay in between, following a linear-time preprocessing. A known dichotomy classifies the acyclic self-join-free CQs into those that admit such enumeration, and those that do not. However, this classification no longer holds in the common case where the database exhibits dependencies among attributes. That is, some queries that are classified as hard are in fact tractable if dependencies are accounted for. We establish a generalization of the dichotomy to accommodate FDs; hence, our classification determines which combination of a CQ and a set of FDs admits constant-delay enumeration with a linear-time preprocessing.In addition, we generalize a hardness result for cyclic CQs to accommodate a common type of FDs. Further conclusions of our development include a dichotomy for enumeration with linear delay, and a dichotomy for CQs with disequalities. Finally, we show that all our results apply to the known class of "cardinality dependencies" that generalize FDs (e.g., by stating an upper bound on the number of genres per movies, or friends per person).Wed, 28 Feb 2018 15:29:17 +0100http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8598Answering UCQs under Updates and in the Presence of Integrity Constraints
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8599
We investigate the query evaluation problem for fixed queries overfully dynamic databases where tuples can be inserted or deleted.The task is to design a dynamic data structure that can immediatelyreport the new result of a fixed query after every database update.We consider unions of conjunctive queries (UCQs) and focus on the query evaluation tasks testing (decide whether an input tuple belongs to the query result), enumeration (enumerate, without repetition,all tuples in the query result), and counting (output the number of tuples in the query result).We identify three increasingly restrictive classes of UCQs which wecall t-hierarchical, q-hierarchical, and exhaustively q-hierarchical UCQs.Our main results provide the following dichotomies:If the query's homomorphic core is t-hierarchical (q-hierarchical,exhaustively q-hierarchical), then the testing (enumeration, counting)problem can be solved with constant update time and constant testing time (delay, counting time). Otherwise, it cannot be solved with sublinear update time and sublinear testing time (delay, counting time), unless the OV-conjecture and/or the OMv-conjecture fails. We also study the complexity of query evaluation in the dynamic setting in the presence of integrity constraints, and we obtain similar dichotomy results for the special case of small domain constraints (i.e., constraints which state that all values in a particular column of a relation belong to a fixed domain of constant size).Wed, 28 Feb 2018 15:29:17 +0100http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8599On the Expressive Power of Query Languages for Matrices
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8600
We investigate the expressive power of MATLANG, a formal language for matrix manipulation based on common matrix operations and linear algebra. The language can be extended with the operation inv of inverting a matrix. In MATLANG + inv we can compute the transitive closure of directed graphs, whereas we show that this is not possible without inversion. Indeed we show that the basic language can be simulated in the relational algebra with arithmetic operations, grouping, and summation. We also consider an operation eigen for diagonalizing a matrix, which is defined so that different eigenvectors returned for a same eigenvalue are orthogonal. We show that inv can be expressed in MATLANG + eigen. We put forward the open question whether there are boolean queries about matrices, or generic queries about graphs, expressible in MATLANG + eigen but not in MATLANG + inv. The evaluation problem for MATLANG + eigen is shown to be complete for the complexity class Exists R.Wed, 28 Feb 2018 15:29:17 +0100http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8600Preserving Constraints with the Stable Chase
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8601
Conjunctive query answering over databases with constraints – also known as (tuple-generating) dependencies – is considered a central database task. To this end, several versions of a construction called chase have been described. Given a set Sigma of dependencies, it is interesting to ask which constraints not contained in Sigma that are initially satisfied in a given database instance are preserved when computing a chase over Sigma. Such constraints are an example for the more general class of incidental constraints, which when added to Sigma as new dependencies do not affect certain answers and might even speed up query answering. After formally introducing incidental constraints, we show that deciding incidentality is undecidable for tuple-generating dependencies, even in cases for which query entailment is decidable. For dependency sets with a finite universal model, the core chase can be used to decide incidentality. For the infinite case, we propose the stable chase, which generalises the core chase, and study its relation to incidental constraints.Wed, 28 Feb 2018 15:29:17 +0100http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8601A More General Theory of Static Approximations for Conjunctive Queries
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8602
Conjunctive query (CQ) evaluation is NP-complete, but becomes tractable for fragments of bounded hypertreewidth. If a CQ is hard to evaluate, it is thus useful to evaluate an approximation of it in such fragments. While underapproximations (i.e., those that return correct answers only) are well-understood, the dual notion of overapproximations that return complete (but not necessarily sound) answers, and also a more general notion of approximation based on the symmetric difference of query results, are almost unexplored. In fact, the decidability of the basic problems of evaluation, identification, and existence of those approximations, is open. We develop a connection with existential pebble game tools that allows the systematic study of such problems. In particular, we show that the evaluation and identification of overapproximations can be solved in polynomial time. We also make progress in the problem of existence of overapproximations, showing it to be decidable in 2EXPTIME over the class of acyclic CQs. Furthermore, we look at when overapproximations do not exist, suggesting that this can be alleviated by using a more liberal notion of overapproximation. We also show how to extend our tools to study symmetric difference approximations. We observe that such approximations properly extend under- and over-approximations, settle the complexity of its associated identification problem, and provide several results on existence and evaluation. Wed, 28 Feb 2018 15:29:17 +0100http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8602Distribution Policies for Datalog
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8603
Modern data management systems extensively use parallelism to speed up query processing over massive volumes of data. This trend has inspired a rich line of research on how to formally reason about the parallel complexity of join computation. In this paper, we go beyond joins and study the parallel evaluation of recursive queries. We introduce a novel framework to reason about multi-round evaluation of Datalog programs, which combines implicit predicate restriction with distribution policies to allow expressing a combination of data-parallel and query-parallel evaluation strategies. Using our framework, we reason about key properties of distributed Datalog evaluation, including parallel-correctness of the evaluation strategy, disjointness of the computation effort, and bounds on the number of communication rounds.Wed, 28 Feb 2018 15:29:17 +0100http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8603Parallel-Correctness and Transferability for Conjunctive Queries under Bag Semantics
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8604
Single-round multiway join algorithms first reshuffle data over many servers and then evaluate the query at hand in a parallel and communication-free way. A key question is whether a given distribution policy for the reshuffle is adequate for computing a given query. This property is referred to as parallel-correctness. Another key problem is to detect whether the data reshuffle step can be avoided when evaluating subsequent queries. The latter problem is referred to as transfer of parallel-correctness. This paper extends the study of parallel-correctness and transfer of parallel-correctness of conjunctive queries to incorporate bag semantics. We provide semantical characterizations for both problems, obtain complexity bounds and discuss the relationship with their set semantics counterparts. Finally, we revisit both problems under a modified distribution model that takes advantage of a linear order on compute nodes and obtain tight complexity bounds.Wed, 28 Feb 2018 15:29:17 +0100http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8604Massively Parallel Entity Matching with Linear Classification in Low Dimensional Space
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8605
In entity matching classification, we are given two sets R and S of objects where whether r and s form a match is known for each pair (r, s) in R x S. If R and S are subsets of domains D(R) and D(S) respectively, the goal is to discover a classifier function f: D(R) x D(S) -> {0, 1} from a certain class satisfying the property that, for every (r, s) in R x S, f(r, s) = 1 if and only if r and s are a match. Past research is accustomed to running a learning algorithm directly on all the labeled (i.e., match or not) pairs in R times S. This, however, suffers from the drawback that even reading through the input incurs a quadratic cost. We pursue a direction towards removing the quadratic barrier. Denote by T the set of matching pairs in R times S. We propose to accept R, S, and T as the input, and aim to solve the problem with cost proportional to |R|+|S|+|T|, thereby achieving a large performance gain in the (typical) scenario where |T|<<|R||S|. This paper provides evidence on the feasibility of the new direction, by showing how to accomplish the aforementioned purpose for entity matching with linear classification, where a classifier is a linear multi-dimensional plane separating the matching and non-matching pairs. We actually do so in the MPC model, echoing the trend of deploying massively parallel computing systems for large-scale learning. As a side product, we obtain new MPC algorithms for three geometric problems: linear programming, batched range counting, and dominance join. Wed, 28 Feb 2018 15:29:17 +0100http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8605Enumeration on Trees under Relabelings
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8606
We study how to evaluate MSO queries with free variables on trees, within theframework of enumeration algorithms. Previous work has shown how to enumerateanswers with linear-time preprocessing and delay linear in the size of eachoutput, i.e., constant-delay for free first-order variables. We extend thisresult to support relabelings, a restricted kind of update operations ontrees which allows us to change the node labels. Our main result shows that wecan enumerate the answers of MSO queries on trees with linear-time preprocessingand delay linear in each answer, while supporting node relabelings in logarithmic time. Toprove this, we reuse the circuit-based enumeration structure from our earlierwork, and develop techniques to maintain its index under node relabelings. Wealso show how enumeration under relabelings can be applied to evaluate practicalquery languages, such as aggregate, group-by, and parameterized queries.Wed, 28 Feb 2018 15:29:17 +0100http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8606Expressivity and Complexity of MongoDB Queries
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8607
In this paper, we consider MongoDB, a widely adopted but not formally understood database system managing JSON documents and equipped with a powerful query mechanism, called the aggregation framework. We provide a clean formal abstraction of this query language, which we call MQuery. We study the expressivity of MQuery, showing the equivalence of its well-typed fragment with nested relational algebra. We further investigate the computational complexity of significant fragments of it, obtaining several (tight) bounds in combined complexity, which range from LogSpace to alternating exponential-time with a polynomial number of alternations.Wed, 28 Feb 2018 15:29:17 +0100http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8607Connecting Width and Structure in Knowledge Compilation
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8608
Several query evaluation tasks can be done via knowledge compilation: the query result is compiled as a lineage circuit from which the answer can be determined. For such tasks, it is important to leverage some width parameters of the circuit, such as bounded treewidth or pathwidth, to convert the circuit to structured classes, e.g., deterministic structured NNFs (d-SDNNFs) or OBDDs. In this work, we show how to connect the width of circuits to the size of their structured representation, through upper and lower bounds. For the upper bound, we show how bounded-treewidth circuits can be converted to a d-SDNNF, in time linear in the circuit size. Our bound, unlike existing results, is constructive and only singly exponential in the treewidth. We show a related lower bound on monotone DNF or CNF formulas, assuming a constant bound on the arity (size of clauses) and degree (number of occurrences of each variable). Specifically, any d-SDNNF (resp., SDNNF) for such a DNF (resp., CNF) must be of exponential size in its treewidth; and the same holds for pathwidth when compiling to OBDDs. Our lower bounds, in contrast with most previous work, apply to any formula of this class, not just a well-chosen family. Hence, for our language of DNF and CNF, pathwidth and treewidth respectively characterize the efficiency of compiling to OBDDs and (d-)SDNNFs, that is, compilation is singly exponential in the width parameter. We conclude by applying our lower bound results to the task of query evaluation.Wed, 28 Feb 2018 15:29:17 +0100http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8608Fast Sketch-based Recovery of Correlation Outliers
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8609
Many data sources can be interpreted as time-series, and a key problem is to identify which pairs out of a large collection of signals are highly correlated. We expect that there will be few, large, interesting correlations, while most signal pairs do not have any strong correlation. We abstract this as the problem of identifying the highly correlated pairs in a collection of n mostly pairwise uncorrelated random variables, where observations of the variables arrives as a stream. Dimensionality reduction can remove dependence on the number of observations, but further techniques are required to tame the quadratic (in n) cost of a search through all possible pairs.We develop a new algorithm for rapidly finding large correlations based on sketch techniques with an added twist: we quickly generate sketches of random combinations of signals, and use these in concert with ideas from coding theory to decode the identity of correlated pairs. We prove correctness and compare performance and effectiveness with the best LSH (locality sensitive hashing) based approach.Wed, 28 Feb 2018 15:29:17 +0100http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8609Covers of Query Results
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8610
We introduce succinct lossless representations of query results called covers. They are subsets of the query results that correspond to minimal edge covers in the hypergraphs of these results.We first study covers whose structures are given by fractional hypertree decompositions of join queries. For any decomposition of a query, we give asymptotically tight size bounds for the covers of the query result over that decomposition and show that such covers can be computed in worst-case optimal time up to a logarithmic factor in the database size. For acyclic join queries, we can compute covers compositionally using query plans with a new operator called cover-join. The tuples in the query result can be enumerated from any of its covers with linearithmic pre-computation time and constant delay.We then generalize covers from joins to functional aggregate queries that express a host of computational problems such as aggregate-join queries, in-database optimization, matrix chain multiplication, and inference in probabilistic graphical models.Wed, 28 Feb 2018 15:29:17 +0100http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8610An Update on Dynamic Complexity Theory
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8611
In many modern data management scenarios, data is subject to frequent changes. In order to avoid costly re-computing query answers from scratch after each small update, one can try to use auxiliary relations that have been computed before. Of course, the auxiliary relations need to be updated dynamically whenever the data changes.Dynamic complexity theory studies which queries and auxiliary relations can be updated in a highly parallel fashion, that is, by constant-depth circuits or, equivalently, by first-order formulasor the relational algebra. After gently introducing dynamic complexity theory, I will discuss recent results of the area with a focus on the dynamic complexity of the reachability query.Wed, 28 Feb 2018 15:29:17 +0100http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8611Join Algorithms: From External Memory to the BSP
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8612
Database systems have been traditionally disk-based, which had motivated the extensive study on external memory (EM) algorithms. However, as RAMs continue to get larger and cheaper, modern distributed data systems are increasingly adopting a main memory based, shared-nothing architecture, exemplified by systems like Spark and Flink. These systems can be abstracted by the BSP model (with variants like the MPC model and the MapReduce model), and there has been a strong revived interest in designing BSP algorithms for handling large amounts of data.With hard disks starting to fade away from the picture, EM algorithms may now seem less relevant. However, we observe that many of the recently developed join algorithms under the BSP model have a high degree of resemblance with their counterparts in the EM model. In this talk, I will present some recent results on join algorithms in the EM and BSP model, examine their relationships, and discuss a general theoretical framework for converting EM algorithms tothe BSP.Wed, 28 Feb 2018 15:29:17 +0100http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8612Fine-grained Algorithms and Complexity
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8613
A central goal of algorithmic research is to determine how fast computational problems can be solved in the worst case. Theorems from complexity theory state that there are problems that, on inputs of size n, can be solved in t(n) time but not in O(t(n)^{1-epsilon}) time for epsilon>0. The main challenge is to determine where in this hierarchy various natural and important problems lie. Throughout the years, many ingenious algorithmic techniques have been developed and applied to obtain blazingly fast algorithms for many problems. Nevertheless, for many other central problems, the best known running times are essentially those of their classical algorithms from the 1950s and 1960s.Unconditional lower bounds seem very difficult to obtain, and so practically all known time lower bounds are conditional. For years, the main tool for proving hardness of computational problems have been NP-hardness reductions, basing hardness on P neq NP. However, when we care about the exact running time (as opposed to merely polynomial vs non-polynomial), NP-hardness is not applicable, especially if the problem is already solvable in polynomial time. In recent years, a new theory has been developed, based on "fine-grained reductions" that focus on exact running times. Mimicking NP-hardness, the approach is to (1) select a key problem X that is conjectured to require essentially t(n) time for some t, and (2) reduce X in a fine-grained way to many important problems. This approach has led to the discovery of many meaningful relationships between problems, and even sometimes to equivalence classes.The main key problems used to base hardness on have been: the 3SUM problem, the CNF-SAT problem (based on the Strong Exponential Time Hypothesis (SETH)) and the All Pairs Shortest Paths Problem. Research on SETH-based lower bounds has flourished in particular in recent years showing that the classical algorithms are optimal for problems such as Approximate Diameter, Edit Distance, Frechet Distance, Longest Common Subsequence etc.In this talk I will give an overview of the current progress in this area of study, and will highlight some exciting new developments and their relationship to database theory.Wed, 28 Feb 2018 15:29:17 +0100http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8613Front Matter, Table of Contents, Preface, Conference Organization
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8574
Front Matter, Table of Contents, Preface, Conference OrganizationMon, 26 Feb 2018 07:53:33 +0100http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8574Approximate Reversal of Quantum Gaussian Dynamics
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8575
Recently, there has been focus on determining the conditions under which the data processing inequality for quantum relative entropy is satisfied with approximate equality. The solution of the exact equality case is due to Petz, who showed that the quantum relative entropy between two quantum states stays the same after the action of a quantum channel if and only if there is a reversal channel that recovers the original states after the channel acts. Furthermore, this reversal channel can be constructed explicitly and is now called the Petz recovery map. Recent developments have shown that a variation of the Petz recovery map works well for recovery in the case of approximate equality of the data processing inequality. Our main contribution here is a proof that bosonic Gaussian states and channels possess a particular closure property, namely, that the Petz recovery map associated to a bosonic Gaussian state \sigma and a bosonic Gaussian channel N is itself a bosonic Gaussian channel. We furthermore give an explicit construction of the Petz recovery map in this case, in terms of the mean vector and covariance matrix of the state \sigma and the Gaussian specification of the channel N.Mon, 26 Feb 2018 07:53:33 +0100http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8575Quantum Coin Hedging, and a Counter Measure
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8576
A quantum board game is a multi-round protocol between a single quantum player against the quantum board. Molina and Watrous discovered quantum hedging. They gave an example for perfect quantum hedging: a board game with winning probability < 1, such that the player can win with certainty at least 1-out-of-2 quantum board games played in parallel. Here we show that perfect quantum hedging occurs in a cryptographic protocol – quantum coin flipping. For this reason, when cryptographic protocols are composed in parallel, hedging may introduce serious challenges into their analysis.We also show that hedging cannot occur when playing two-outcome board games in sequence. This is done by showing a formula for the value of sequential two-outcome board games, which depends only on the optimal value of a single board game; this formula applies in a more general setting of possible target functions, in which hedging is only a special case.Mon, 26 Feb 2018 07:53:33 +0100http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8576The Complexity of Simulating Local Measurements on Quantum Systems
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8577
An important task in quantum physics is the estimation of local quantities for ground states of local Hamiltonians. Recently, Ambainis defined the complexity class P^QMA[log], and motivated its study by showing that the physical task of estimating the expectation value of a local observable against the ground state of a local Hamiltonian is P^QMA[log]-complete. In this paper, we continue the study of P^QMA[log], obtaining the following results.The P^QMA[log]-completeness result of Ambainis requires O(log n)-local observ- ables and Hamiltonians. We show that simulating even a single qubit measurement on ground states of 5-local Hamiltonians is P^QMA[log]-complete, resolving an open question of Ambainis. We formalize the complexity theoretic study of estimating two-point correlation functions against ground states, and show that this task is similarly P^QMA[log]-complete.P^QMA[log] is thought of as "slightly harder" than QMA. We justify this formally by exploiting the hierarchical voting technique of Beigel, Hemachandra, and Wechsung to show P^QMA[log] \subseteq PP. This improves the containment QMA \subseteq PP from Kitaev and Watrous. A central theme of this work is the subtlety involved in the study of oracle classes in which the oracle solves a promise problem. In this vein, we identify a flaw in Ambainis' prior work regarding a P^UQMA[log]-hardness proof for estimating spectral gaps of local Hamiltonians. By introducing a "query validation" technique, we build on his prior work to obtain P^UQMA[log]-hardness for estimating spectral gaps under polynomial-time Turing reductions.Mon, 26 Feb 2018 07:53:33 +0100http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8577 Quantum Hedging in Two-Round Prover-Verifier Interactions
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8578
We consider the problem of a particular kind of quantum correlation that arises in some two-party games. In these games, one player is presented with a question they must answer, yielding an outcome of either "win" or "lose". Molina and Watrous previously studied such a game that exhibited a perfect form of hedging, where the risk of losing a first game can completely offset the corresponding risk for a second game. This is a non-classical quantum phenomenon, and establishes the impossibility of performing strong error-reduction for quantum interactive proof systems by parallel repetition, unlike for classical interactive proof systems. We take a step in this article towards a better understanding of the hedging phenomenon by giving a complete characterization of when perfect hedging is possible for a natural generalization of the game in the prior work of Molina and Watrous. Exploring in a different direction the subject of quantum hedging, and motivated by implementation concerns regarding loss-tolerance, we also consider a variation of the protocol where the player who receives the question can choose to restart the game rather than return an answer. We show that in this setting there is no possible hedging for any game played with state spaces corresponding to finite-dimensional complex Euclidean spaces.Mon, 26 Feb 2018 07:53:33 +0100http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8578Multiparty Quantum Communication Complexity of Triangle Finding
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8579
Triangle finding (deciding if a graph contains a triangle or not) is a central problem in quantum query complexity. The quantum communication complexity of this problem, where the edges of the graph are distributed among the players, was considered recently by Ivanyos et al. in the two- party setting. In this paper we consider its k-party quantum communication complexity with k >= 3. Our main result is a ~O(m^(7/12))-qubit protocol, for any constant number of players k, deciding with high probability if a graph with m edges contains a triangle or not. Our approach makes connections between the multiparty quantum communication complexity of triangle finding and the quantum query complexity of graph collision, a well-studied problem in quantum query complexity.Mon, 26 Feb 2018 07:53:33 +0100http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8579A Single Entangled System Is an Unbounded Source of Nonlocal Correlations and of Certified Random Numbers
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8580
The outcomes of local measurements made on entangled systems can be certified to be random provided that the generated statistics violate a Bell inequality. This way of producing randomness relies only on a minimal set of assumptions because it is independent of the internal functioning of the devices generating the random outcomes. In this context it is crucial to understand both qualitatively and quantitatively how the three fundamental quantities – entanglement, non-locality and randomness – relate to each other. To explore these relationships, we consider the case where repeated (non projective) measurements are made on the physical systems, each measurement being made on the post-measurement state of the previous measurement. In this work, we focus on the following questions: Given a single entangled system, how many nonlocal correlations in a sequence can we obtain? And from this single entangled system, how many certified random numbers is it possible to generate? In the standard scenario with a single measurement in the sequence, it is possible to generate non-local correlations between two distant observers only and the amount of random numbers is very limited. Here we show that we can overcome these limitations and obtain any amount of certified random numbers from a single entangled pair of qubit in a pure state by making sequences of measurements on it. Moreover, the state can be arbitrarily weakly entangled. In addition, this certification is achieved by near-maximal violation of a particular Bell inequality for each measurement in the sequence. We also present numerical results giving insight on the resistance to imperfections and on the importance of the strength of the measurements in our scheme.Mon, 26 Feb 2018 07:53:33 +0100http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8580Provably Secure Key Establishment Against Quantum Adversaries
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8581
At Crypto 2011, some of us had proposed a family of cryptographic protocols for key establishment capable of protecting quantum and classical legitimate parties unconditionally against a quantum eavesdropper in the query complexity model. Unfortunately, our security proofs were unsatisfactory from a cryptographically meaningful perspective because they were sound only in a worst-case scenario. Here, we extend our results and prove that for any \eps > 0, there is a classical protocol that allows the legitimate parties to establish a common key after O(N) expected queries to a random oracle, yet any quantum eavesdropper will have a vanishing probability of learning their key after O(N^(1.5-\eps)) queries to the same oracle. The vanishing probability applies to a typical run of the protocol. If we allow the legitimate parties to use a quantum computer as well, their advantage over the quantum eavesdropper becomes arbitrarily close to the quadratic advantage that classical legitimate parties enjoyed over classical eavesdroppers in the seminal 1974 work of Ralph Merkle. Along the way, we develop new tools to give lower bounds on the number of quantum queries required to distinguish two probability distributions. This method in itself could have multiple applications in cryptography. We use it here to study average-case quantum query complexity, for which we develop a new composition theorem of independent interest.Mon, 26 Feb 2018 07:53:33 +0100http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8581Minimum Quantum Resources for Strong Non-Locality
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8582
We analyse the minimum quantum resources needed to realise strong non-locality, as exemplified e.g. by the classical GHZ construction. It was already known that no two-qubit system, with any finite number of local measurements, can realise strong non-locality. For three-qubit systems, we show that strong non-locality can only be realised in the GHZ SLOCC class, and with equatorial measurements. However, we show that in this class there is an infinite family of states which are pairwise non LU-equivalent that realise strong non-locality with finitely many measurements. These states have decreasing entanglement between one qubit and the other two, necessitating an increasing number of local measurements on the latter.Mon, 26 Feb 2018 07:53:33 +0100http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8582Fidelity of Quantum Strategies with Applications to Cryptography
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8583
We introduce a definition of the fidelity function for multi-round quantum strategies, which we call the strategy fidelity, that is a generalization of the fidelity function for quantum states. We provide many interesting properties of the strategy fidelity including a Fuchs-van de Graaf relationship with the strategy norm. We illustrate an operational interpretation of the strategy fidelity in the spirit of Uhlmann's Theorem and discuss its application to the security analysis of quantum protocols for interactive cryptographic tasks such as bit-commitment and oblivious string transfer. Our analysis is very general in the sense that the actions of the protocol need not be fully specified, which is in stark contrast to most other security proofs. Lastly, we provide a semidefinite programming formulation of the strategy fidelity.Mon, 26 Feb 2018 07:53:33 +0100http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8583Improved reversible and quantum circuits for Karatsuba-based integer multiplication
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8584
Integer arithmetic is the underpinning of many quantum algorithms, with applications ranging from Shor's algorithm over HHL for matrix inversion to Hamiltonian simulation algorithms. A basic objective is to keep the required resources to implement arithmetic as low as possible. This applies in particular to the number of qubits required in the implementation as for the foreseeable future this number is expected to be small. We present a reversible circuit for integer multiplication that is inspired by Karatsuba's recursive method. The main improvement over circuits that have been previously reported in the literature is an asymptotic reduction of the amount of space required from O(n^1.585) to O(n^1.427). This improvement is obtained in exchange for a small constant increase in the number of operations by a factor less than 2 and a small asymptotic increase in depth for the parallel version. The asymptotic improvement are obtained from analyzing pebble games on complete ternary trees.Mon, 26 Feb 2018 07:53:33 +0100http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8584Front Matter, Table of Contents, Preface, Conference Organization
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8543
Front Matter, Table of Contents, Preface, Conference OrganizationFri, 23 Feb 2018 14:22:47 +0100http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8543On the Parameterized Complexity of Contraction to Generalization of Trees
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8544
For a family of graphs F, the F-Contraction problem takes as an input a graph G and an integer k, and the goal is to decide if there exists S \subseteq E(G) of size at most k such that G/S belongs to F. Here, G/S is the graph obtained from G by contracting all the edges in S. Heggernes et al.[Algorithmica (2014)] were the first to study edge contraction problems in the realm of Parameterized Complexity. They studied \cal F-Contraction when F is a simple family of graphs such as trees and paths. In this paper, we study the F-Contraction problem, where F generalizes the family of trees. In particular, we define this generalization in a "parameterized way". Let T_\ell be the family of graphs such that each graph in T_\ell can be made into a tree by deleting at most \ell edges. Thus, the problem we study is T_\ell-Contraction. We design an FPT algorithm for T_\ell-Contraction running in time O((\ncol)^{O(k + \ell)} * n^{O(1)}). Furthermore, we show that the problem does not admit a polynomial kernel when parameterized by k. Inspired by the negative result for the kernelization, we design a lossy kernel for T_\ell-Contraction of size O([k(k + 2\ell)] ^{(\lceil {\frac{\alpha}{\alpha-1}\rceil + 1)}}).Fri, 23 Feb 2018 14:22:47 +0100http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8544Solving and Sampling with Many Solutions: Satisfiability and Other Hard Problems
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8545
We investigate parameterizing hard combinatorial problems by the size of the solution set compared to all solution candidates. Our main result is a uniform sampling algorithm for satisfying assignments of 2-CNF formulas that runs in expected time O^*(eps^{-0.617}) where eps is the fraction of assignments that are satisfying. This improves significantly over the trivial sampling bound of expected Theta^*(eps^{-1}), and on all previous algorithms whenever eps = Omega(0.708^n). We also consider algorithms for 3-SAT with an eps fraction of satisfying assignments, and prove that it can be solved in O^*(eps^{-2.27}) deterministic time, and in O^*(eps^{-0.936}) randomized time. Finally, to further demonstrate the applicability of this framework, we also explore how similar techniques can be used for vertex cover problems.Fri, 23 Feb 2018 14:22:47 +0100http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8545Merging Nodes in Search Trees: an Exact Exponential Algorithm for the Single Machine Total Tardiness Scheduling Problem
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8546
This paper proposes an exact exponential algorithm for the problem of minimizing the total tardiness of jobs on a single machine. It exploits the structure of a basic branch-and-reduce framework based on the well known Lawler's decomposition property. The proposed algorithm, called branch-and-merge, is an improvement of the branch-and-reduce technique with the embedding of a node merging operation. Its time complexity is O*(2.247^n) keeping the space complexity polynomial. The branch-and-merge technique is likely to be generalized to other sequencing problems with similar decomposition properties.Fri, 23 Feb 2018 14:22:47 +0100http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8546Odd Multiway Cut in Directed Acyclic Graphs
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8547
We investigate the odd multiway node (edge) cut problem where the input is a graph with a specified collection of terminal nodes and the goal is to find a smallest subset of non-terminal nodes (edges) to delete so that the terminal nodes do not have an odd length path between them. In an earlier work, Lokshtanov and Ramanujan showed that both odd multiway node cut and odd multiway edge cut are fixed-parameter tractable (FPT) when parameterized by the size of the solution in undirected graphs. In this work, we focus on directed acyclic graphs (DAGs) and design a fixed-parameter algorithm. Our main contribution is an extension of the shadow-removal framework for parity problems in DAGs. We complement our FPT results with tight approximability as well as polyhedral results for 2 terminals in DAGs. Additionally, we show inapproximability results for odd multiway edge cut in undirected graphs even for 2 terminals.Fri, 23 Feb 2018 14:22:47 +0100http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8547Contraction-Bidimensionality of Geometric Intersection Graphs
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8548
Given a graph G, we define bcg(G) as the minimum k for which G can be contracted to the uniformly triangulated grid Gamma_k. A graph class G has the SQGC property if every graph G in G has treewidth O(bcg(G)c) for some 1 <= c < 2. The SQGC property is important for algorithm design as it defines the applicability horizon of a series of meta-algorithmic results, in the framework of bidimensionality theory, related to fast parameterized algorithms, kernelization, and approximation schemes. These results apply to a wide family of problems, namely problems that are contraction-bidimensional. Our main combinatorial result reveals a general family of graph classes that satisfy the SQGC property and includes bounded-degree string graphs. This considerably extends the applicability of bidimensionality theory for several intersection graph classes of 2-dimensional geometrical objects.Fri, 23 Feb 2018 14:22:47 +0100http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8548K-Best Solutions of MSO Problems on Tree-Decomposable Graphs
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8549
We show that, for any graph optimization problem in which the feasible solutions can be expressed by a formula in monadic second-order logic describing sets of vertices or edges and in which the goal is to minimize the sum of the weights in the selected sets, we can find the k best solution values for n-vertex graphs of bounded treewidth in time O(n + k log n). In particular, this applies to finding the k shortest simple paths between given vertices in directed graphs of bounded treewidth, giving an exponential speedup in the per-path cost over previous algorithms.Fri, 23 Feb 2018 14:22:47 +0100http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8549Optimal Data Reduction for Graph Coloring Using Low-Degree Polynomials
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8550
The theory of kernelization can be used to rigorously analyze data reduction for graph coloring problems. Here, the aim is to reduce a q-Coloring input to an equivalent but smaller input whose size is provably bounded in terms of structural properties, such as the size of a minimum vertex cover. In this paper we settle two open problems about data reduction for q-Coloring.First, we use a recent technique of finding redundant constraints by representing them as low-degree polynomials, to obtain a kernel of bitsize O(k^(q-1) log k) for q-Coloring parameterized by Vertex Cover for any q >= 3. This size bound is optimal up to k^o(1) factors assuming NP is not a subset of coNP/poly, and improves on the previous-best kernel of size O(k^q). Our second result shows that 3-Coloring does not admit non-trivial sparsification: assuming NP is not a subset of coNP/poly, the parameterization by the number of vertices n admits no (generalized) kernel of size O(n^(2-e)) for any e > 0. Previously, such a lower bound was only known for coloring with q >= 4 colors.Fri, 23 Feb 2018 14:22:47 +0100http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8550Treewidth with a Quantifier Alternation Revisited
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8551
In this paper we take a closer look at the parameterized complexity of \exists\forall SAT, the prototypical complete problem of the class Sigma_2^p, the second level of the polynomial hierarchy. We provide a number of tight fine-grained bounds on the complexity of this problem and its variants with respect to the most important structural graph parameters. Specifically, we show the following lower bounds (assuming the ETH):- It is impossible to decide \exists\forall SAT in time less than double-exponential in the input formula's treewidth. More strongly, we establish the same bound with respect to the formula's primal vertex cover, a much more restrictive measure. This lower bound, which matches the performance of known algorithms, shows that the degeneration of the performance of treewidth-based algorithms to a tower of exponentials already begins in problems with one quantifier alternation.- For the more general \exists\forall CSP problem over a non-boolean domain of size B, there is no algorithm running in time 2^{B^{o(vc)}}, where vc is the input's primal vertex cover.- \exists\forall SAT is already NP-hard even when the input formula has constant modular treewidth (or clique-width), indicating that dense graph parameters are less useful for problems in Sigma_2^p.- For the two weighted versions of \exists\forall SAT recently introduced by de Haan and Szeider, called \exists_k\forall SAT and \exists\forall_k SAT, we give tight upper and lower bounds parameterized by treewidth (or primal vertex cover) and the weight k. Interestingly, the complexity of these two problems turns out to be quite different: one is double-exponential in treewidth, while the other is double-exponential in k.We complement the above negative results by showing a double-exponential FPT algorithm for QBF parameterized by vertex cover, showing that for this parameter the complexity never goes beyond double-exponential, for any number of quantifier alternations.Fri, 23 Feb 2018 14:22:47 +0100http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8551An Output Sensitive Algorithm for Maximal Clique Enumeration in Sparse Graphs
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8552
The degeneracy of a graph G is the smallest integer k such that every subgraph of G contains a vertex of degree at most k. Given an n-order k-degenerate graph G, we present an algorithm for enumerating all its maximal cliques. Assuming that c is the number of maximal cliques of G, our algorithm has setup time O(n(k^2+s(k+1))) and enumeration time cO((k+1)f(k+1)) where s(k+1) (resp. f(k+1)) is the preprocessing time (resp. enumeration time) for maximal clique enumeration in a general (k+1)-order graph. This is the first output sensitive algorithm whose enumeration time depends only on the degeneracy of the graph.Fri, 23 Feb 2018 14:22:47 +0100http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8552The Dominating Set Problem in Geometric Intersection Graphs
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8553
We study the parameterized complexity of dominating sets in geometric intersection graphs. In one dimension, we investigate intersection graphs induced by translates of a fixed pattern Q that consists of a finite number of intervals and a finite number of isolated points. We prove that Dominating Set on such intersection graphs is polynomially solvable whenever Q contains at least one interval, and whenever Q contains no intervals and for any two point pairs in Q the distance ratio is rational. The remaining case where Q contains no intervals but does contain an irrational distance ratio is shown to be NP-complete and contained in FPT (when parameterized by the solution size). In two and higher dimensions, we prove that Dominating Set is contained in W[1] for intersection graphs of semi-algebraic sets with constant description complexity. This generalizes known results from the literature. Finally, we establish W[1]-hardness for a large class of intersection graphs.Fri, 23 Feb 2018 14:22:47 +0100http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8553Parameterized Complexity of Finding a Spanning Tree with Minimum Reload Cost Diameter
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8554
We study the minimum diameter spanning tree problem under the reload cost model (DIAMETER-TREE for short) introduced by Wirth and Steffan (2001). In this problem, given an undirected edge-colored graph G, reload costs on a path arise at a node where the path uses consecutive edges of different colors. The objective is to find a spanning tree of G of minimum diameter with respect to the reload costs. We initiate a systematic study of the parameterized complexity of the DIAMETER-TREE problem by considering the following parameters: the cost of a solution, and the treewidth and the maximum degree Delta of the input graph. We prove that DIAMETER-TREE is para-np-hard for any combination of two of these three parameters, and that it is FPT parameterized by the three of them. We also prove that the problem can be solved in polynomial time on cactus graphs. This result is somehow surprising since we prove DIAMETER-TREE to be NP-hard on graphs of treewidth two, which is best possible as the problem can be trivially solved on forests. When the reload costs satisfy the triangle inequality, Wirth and Steffan (2001) proved that the problem can be solved in polynomial time on graphs with Delta=3, and Galbiati (2008) proved that it is NP-hard if Delta=4. Our results show, in particular, that without the requirement of the triangle inequality, the problem is NP-hard if Delta=3, which is also best possible. Finally, in the case where the reload costs are polynomially bounded by the size of the input graph, we prove that DIAMETER-TREE is in XP and W[1]-hard parameterized by the treewidth plus Delta.Fri, 23 Feb 2018 14:22:47 +0100http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8554Optimal Algorithms for Hitting (Topological) Minors on Graphs of Bounded Treewidth
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8555
For a fixed collection of graphs F, the F-M-DELETION problem consists in, given a graph G and an integer k, decide whether there exists a subset S of V(G) of size at most k such that G-S does not contain any of the graphs in F as a minor. We are interested in the parameterized complexity of F-M-DELETION when the parameter is the treewidth of G, denoted by tw. Our objective is to determine, for a fixed F}, the smallest function f_F such that F-M-DELETION can be solved in time f_F(tw)n^{O(1)} on n-vertex graphs. Using and enhancing the machinery of boundaried graphs and small sets of representatives introduced by Bodlaender et al. [J ACM, 2016], we prove that when all the graphs in F are connected and at least one of them is planar, then f_F(w) = 2^{O(wlog w)}. When F is a singleton containing a clique, a cycle, or a path on i vertices, we prove the following asymptotically tight bounds:- f_{K_4}(w) = 2^{Theta(wlog w)}.- f_{C_i}(w) = 2^{Theta(w)} for every i<5, and f_{C_i}(w) = 2^{Theta(wlog w)} for every i>4.- f_{P_i}(w) = 2^{Theta(w)} for every i<5, and f_{P_i}(w) = 2^{Theta(wlog w)} for every i>5.The lower bounds hold unless the Exponential Time Hypothesis fails, and the superexponential ones are inspired by a reduction of Marcin Pilipczuk [Discrete Appl Math, 2016]. The single-exponential algorithms use, in particular, the rank-based approach introduced by Bodlaender et al. [Inform Comput, 2015]. We also consider the version of the problem where the graphs in F are forbidden as topological minors, and prove essentially the same set of results holds.Fri, 23 Feb 2018 14:22:47 +0100http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8555How Much Does a Treedepth Modulator Help to Obtain Polynomial Kernels Beyond Sparse Graphs?
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8556
In the last years, kernelization with structural parameters has been an active area of research within the field of parameterized complexity. As a relevant example, Gajarsky et al. [ESA 2013] proved that every graph problem satisfying a property called finite integer index admits a linear kernel on graphs of bounded expansion and an almost linear kernel on nowhere dense graphs, parameterized by the size of a c-treedepth modulator, which is a vertex set whose removal results in a graph of treedepth at most c for a fixed integer c>0. The authors left as further research to investigate this parameter on general graphs, and in particular to find problems that, while admitting polynomial kernels on sparse graphs, behave differently on general graphs.In this article we answer this question by finding two very natural such problems: we prove that VERTEX COVER admits a polynomial kernel on general graphs for any integer c>0, and that DOMINATING SET does not for any integer c>1 even on degenerate graphs, unless NP is a subset of coNP/poly. For the positive result, we build on the techniques of Jansen and Bodlaender [STACS 2011], and for the negative result we use a polynomial parameter transformation for c>2 and an OR-cross-composition for c=2. As existing results imply that DOMINATING SET admits a polynomial kernel on degenerate graphs for c=1, our result provides a dichotomy about the existence of polynomial problems for DOMINATING SET on degenerate graphs with this parameter.Fri, 23 Feb 2018 14:22:47 +0100http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8556Turing Kernelization for Finding Long Paths in Graphs Excluding a Topological Minor
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8557
The notion of Turing kernelization investigates whether a polynomial-time algorithm can solve an NP-hard problem, when it is aided by an oracle that can be queried for the answers to bounded-size subproblems. One of the main open problems in this direction is whether k-PATH admits a polynomial Turing kernel: can a polynomial-time algorithm determine whether an undirected graph has a simple path of length k, using an oracle that answers queries of size k^{O(1)}?We show this can be done when the input graph avoids a fixed graph H as a topological minor, thereby significantly generalizing an earlier result for bounded-degree and K_{3,t}-minor-free graphs. Moreover, we show that k-PATH even admits a polynomial Turing kernel when the input graph is not H-topological-minor-free itself, but contains a known vertex modulator of size bounded polynomially in the parameter, whose deletion makes it so. To obtain our results, we build on the graph minors decomposition to show that any H-topological-minor-free graph that does not contain a k-path has a separation that can safely be reduced after communication with the oracle.Fri, 23 Feb 2018 14:22:47 +0100http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8557The PACE 2017 Parameterized Algorithms and Computational Experiments Challenge: The Second Iteration
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8558
In this article, the Program Committee of the Second Parameterized Algorithms and Computational Experiments challenge (PACE 2017) reports on the second iteration of the PACE challenge. Track A featured the Treewidth problem and Track B the Minimum Fill-In problem. Over 44 participants on 17 teams from 11 countries submitted their implementations to the competition.Fri, 23 Feb 2018 14:22:47 +0100http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8558FO Model Checking of Geometric Graphs
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8559
Over the past two decades the main focus of research into first-order (FO) model checking algorithms has been on sparse relational structures – culminating in the FPT algorithm by Grohe, Kreutzer and Siebertz for FO model checking of nowhere dense classes of graphs. On contrary to that, except the case of locally bounded clique-width only little is currently known about FO model checking of dense classes of graphs or other structures. We study the FO model checking problem for dense graph classes definable by geometric means (intersection and visibility graphs). We obtain new nontrivial FPT results, e.g., for restricted subclasses of circular-arc, circle, box, disk, and polygon-visibility graphs. These results use the FPT algorithm by Gajarský et al. for FO model checking of posets of bounded width. We also complement the tractability results by related hardness reductions.Fri, 23 Feb 2018 14:22:47 +0100http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8559An Exponential Lower Bound for Cut Sparsifiers in Planar Graphs
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8560
Given an edge-weighted graph G with a set Q of k terminals, a mimicking network is a graph with the same set of terminals that exactly preserves the sizes of minimum cuts between anypartition of the terminals. A natural question in the area of graph compression is to provide as small mimicking networks as possible for input graph G being either an arbitrary graph or coming from a specific graph class.In this note we show an exponential lower bound for cut mimicking networks in planar graphs: there are edge-weighted planar graphs with k terminals that require 2^(k-2) edges in any mimicking network. This nearly matches an upper bound of O(k * 2^(2k)) of Krauthgamer and Rika [SODA 2013, arXiv:1702.05951] and is in sharp contrast with the O(k^2) upper bound under the assumption that all terminals lie on a single face [Goranci, Henzinger, Peng, arXiv:1702.01136]. As a side result we show a hard instance for the double-exponential upper bounds given by Hagerup, Katajainen, Nishimura, and Ragde [JCSS 1998], Khan and Raghavendra [IPL 2014], and Chambers and Eppstein [JGAA 2013].Fri, 23 Feb 2018 14:22:47 +0100http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8560A Fixed-Parameter Perspective on #BIS
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8561
The problem of (approximately) counting the independent sets of a bipartite graph (#BIS) is the canonical approximate counting problem that is complete in the intermediate complexity class #RHPi_1. It is believed that #BIS does not have an efficient approximation algorithm but also that it is not NP-hard. We study the robustness of the intermediate complexity of #BIS by considering variants of the problem parameterised by the size of the independent set. We map the complexity landscape for three problems, with respect to exact computation and approximation and with respect to conventional and parameterised complexity. The three problems are counting independent sets of a given size, counting independent sets with a given number of vertices in one vertex class and counting maximum independent sets amongst those with a given number of vertices in one vertex class. Among other things, we show that all of these problems are NP-hard to approximate within any polynomial ratio. (This is surprising because the corresponding problems without the size parameter are complete in #RHPi_1, and hence are not believed to be NP-hard.) We also show that the first problem is #W[1]-hard to solve exactly but admits an FPTRAS, whereas the other two are W[1]-hard to approximate even within any polynomial ratio. Finally, we show that, when restricted to graphs of bounded degree, all three problems have efficient exact fixed-parameter algorithms. Fri, 23 Feb 2018 14:22:47 +0100http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8561Finding Connected Secluded Subgraphs
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8562
Problems related to finding induced subgraphs satisfying given properties form one of the most studied areas within graph algorithms. Such problems have given rise to breakthrough results and led to development of new techniques both within the traditional P vs NP dichotomy and within parameterized complexity. The Pi-Subgraph problem asks whether an input graph contains an induced subgraph on at least k vertices satisfying graph property Pi. For many applications, it is desirable that the found subgraph has as few connections to the rest of the graph as possible, which gives rise to the Secluded Pi-Subgraph problem. Here, input k is the size of the desired subgraph, and input t is a limit on the number of neighbors this subgraph has in the rest of the graph. This problem has been studied from a parameterized perspective, and unfortunately it turns out to be W[1]-hard for many graph properties Pi, even when parameterized by k+t. We show that the situation changes when we are looking for a connected induced subgraph satisfying Pi. In particular, we show that the Connected Secluded Pi-Subgraph problem is FPT when parameterized by just t for many important graph properties Pi. Fri, 23 Feb 2018 14:22:47 +0100http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8562Smaller Parameters for Vertex Cover Kernelization
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8563
We revisit the topic of polynomial kernels for Vertex Cover relative to structural parameters. Our starting point is a recent paper due to Fomin and Strømme [WG 2016] who gave a kernel with O(|X|^{12}) vertices when X is a vertex set such that each connected component of G-X contains at most one cycle, i.e., X is a modulator to a pseudoforest. We strongly generalize this result by using modulators to d-quasi-forests, i.e., graphs where each connected component has a feedback vertex set of size at most d, and obtain kernels with O(|X|^{3d+9}) vertices. Our result relies on proving that minimal blocking sets in a d-quasi-forest have size at most d+2. This bound is tight and there is a related lower bound of O(|X|^{d+2-epsilon}) on the bit size of kernels.In fact, we also get bounds for minimal blocking sets of more general graph classes: For d-quasi-bipartite graphs, where each connected component can be made bipartite by deleting at most d vertices, we get the same tight bound of d+2 vertices. For graphs whose connected components each have a vertex cover of cost at most d more than the best fractional vertex cover, which we call d-quasi-integral, we show that minimal blocking sets have size at most 2d+2, which is also tight. Combined with existing randomized polynomial kernelizations this leads to randomized polynomial kernelizations for modulators to d-quasi-bipartite and d-quasi-integral graphs. There are lower bounds of O(|X|^{d+2-epsilon}) and O(|X|^{2d+2-epsilon}) for the bit size of such kernels.Fri, 23 Feb 2018 14:22:47 +0100http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8563Polynomial-Time Algorithms for the Longest Induced Path and Induced Disjoint Paths Problems on Graphs of Bounded Mim-Width
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8564
We give the first polynomial-time algorithms on graphs of bounded maximum induced matching width (mim-width) for problems that are not locally checkable. In particular, we give n^O(w)-time algorithms on graphs of mim-width at most w, when given a decomposition, for the following problems: Longest Induced Path, Induced Disjoint Paths and H-Induced Topological Minor for fixed H. Our results imply that the following graph classes have polynomial-time algorithms for these three problems: Interval and Bi-Interval graphs, Circular Arc, Per- mutation and Circular Permutation graphs, Convex graphs, k-Trapezoid, Circular k-Trapezoid, k-Polygon, Dilworth-k and Co-k-Degenerate graphs for fixed k.Fri, 23 Feb 2018 14:22:47 +0100http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8564Generalized Feedback Vertex Set Problems on Bounded-Treewidth Graphs: Chordality Is the Key to Single-Exponential Parameterized Algorithms
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8565
It has long been known that Feedback Vertex Set can be solved in time 2^O(w log w)n^O(1) on graphs of treewidth w, but it was only recently that this running time was improved to 2^O(w)n^O(1), that is, to single-exponential parameterized by treewidth. We investigate which generalizations of Feedback Vertex Set can be solved in a similar running time. Formally, for a class of graphs P, Bounded P-Block Vertex Deletion asks, given a graph G on n vertices and positive integers k and d, whether G contains a set S of at most k verticessuch that each block of G-S has at most d vertices and is in P. Assuming that P is recognizable in polynomial time and satisfies a certain natural hereditary condition, we give a sharp characterization of when single-exponential parameterized algorithms are possible for fixed values of d:- if P consists only of chordal graphs, then the problem can be solved in time 2^O(wd^2) n^{O}(1), - if P contains a graph with an induced cycle of length ell>= 4, then the problem is not solvable in time 2^{o(w log w)} n^O(1)} even for fixed d=ell, unless the ETH fails.We also study a similar problem, called Bounded P-Component Vertex Deletion, where the target graphs have connected components of small size instead of having blocks of small size, and present analogous results.Fri, 23 Feb 2018 14:22:47 +0100http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8565An Improved Fixed-Parameter Algorithm for One-Page Crossing Minimization
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8566
Book embedding is one of the most well-known graph drawing models and is extensively studied in the literature. The special case where the number of pages is one is of particular interest: an embedding in this case has a natural circular representation useful for visualization and graphs that can be embedded in one page without crossings form an important graph class, namely that of outerplanar graphs.In this paper, we consider the problem of minimizing the number of crossings in a one-page book embedding, which we call one-page crossing minimization. Here, we are given a graph G with n vertices together with a non-negative integer k and are asked whether G can be embedded into a single page with at most k crossings. Bannister and Eppstein (GD 2014) showed that this problem is fixed-parameter tractable. Their algorithm is derived through the application of Courcelle's theorem (on graph properties definable in the monadic second-order logic of graphs) and runs in f(L)n time, where L = 2^{O(k^2)} is the length of the formula defining the property that the one-page crossing number is at most k and f is a computable function without any known upper bound expressible as an elementary function. We give an explicit dynamic programming algorithm with a drastically improved running time of 2^{O(k log k)}n.Fri, 23 Feb 2018 14:22:47 +0100http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8566Computing Treewidth on the GPU
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8567
We present a parallel algorithm for computing the treewidth of a graph on a GPU. We implement this algorithm in OpenCL, and experimentally evaluate its performance. Our algorithm is based on an O*(2^n)-time algorithm that explores the elimination orderings of the graph using a Held-Karp like dynamic programming approach. We use Bloom filters to detect duplicate solutions.GPU programming presents unique challenges and constraints, such as constraints on the use of memory and the need to limit branch divergence. We experiment with various optimizations to see if it is possible to work around these issues. We achieve a very large speed up (up to 77x) compared to running the same algorithm on the CPU.Fri, 23 Feb 2018 14:22:47 +0100http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8567On the Parameterized Complexity of Red-Blue Points Separation
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8568
We study the following geometric separation problem: Given a set R of red points and a set B of blue points in the plane, find a minimum-size set of lines that separate R from B. We show that, in its full generality, parameterized by the number of lines k in the solution, the problem is unlikely to be solvable significantly faster than the brute-force n^{O(k)}-time algorithm, where n is the total number of points. Indeed, we show that an algorithm running in time f(k)n^{o(k/log k)}, for any computable function f, would disprove ETH. Our reduction crucially relies on selecting lines from a set with a large number of different slopes (i.e., this number is not a function of k).Conjecturing that the problem variant where the lines are required to be axis-parallel is FPT in the number of lines, we show the following preliminary result. Separating R from B with a minimum-size set of axis-parallel lines is FPT in the size of either set, and can be solved in time O^*(9^{|B|}) (assuming that B is the smallest set).Fri, 23 Feb 2018 14:22:47 +0100http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8568Finding Small Weight Isomorphisms with Additional Constraints is Fixed-Parameter Tractable
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8569
Lubiw showed that several variants of Graph Isomorphism are NP-complete, where the solutions are required to satisfy certain additional constraints [SICOMP 10, 1981]. One of these, called Isomorphism With Restrictions, is to decide for two given graphs X_1=(V,E_1) and X_2=(V,E_2) and a subset R\subseteq V\times V of forbidden pairs whether there is an isomorphism \pi from X_1 to X_2 such that i^\pi\ne j for all (i,j)\in R. We prove that this problem and several of its generalizations are in fact in \FPT:- The problem of deciding whether there is an isomorphism between two graphs that moves k vertices and satisfies Lubiw-style constraints is in FPT, with k and the size of R as parameters. The problem remains in FPT even if a conjunction of disjunctions of such constraints is allowed. As a consequence of the main result it follows that the problem to decide whether there is an isomorphism that moves exactly k vertices is in FPT. This solves a question left open in our article on exact weight automorphisms [STACS 2017].- When the number of moved vertices is unrestricted, finding isomorphisms that satisfy a CNF of Lubiw-style constraints can be solved in FPT with access to a GI oracle.- Checking if there is an isomorphism π between two graphs with complexity t is also in FPT with t as parameter, where the complexity of a permutation is the Cayley measure defined as the minimum number t such that \pi can be expressed as a product of t transpositions.- We consider a more general problem in which the vertex set of a graph X is partitioned into Red and Blue, and we are interested in an automorphism that stabilizes Red and Blue and moves exactly k vertices in Blue, where k is the parameter. This problem was introduced by [Downey and Fellows 1999], and we showed [STACS 2017] that it is W[1]-hard even with color classes of size 4 inside Red. Now, for color classes of size at most 3 inside Red, we show the problem is in FPT.In the non-parameterized setting, all these problems are NP-complete. Also, they all generalize in several ways the problem to decide whether there is an isomorphism between two graphs that moves at most k vertices, shown to be in FPT by Schweitzer [ESA 2011].Fri, 23 Feb 2018 14:22:47 +0100http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8569Tight Conditional Lower Bounds for Longest Common Increasing Subsequence
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8570
We consider the canonical generalization of the well-studied Longest Increasing Subsequence problem to multiple sequences, called k-LCIS: Given k integer sequences X_1,...,X_k of length at most n, the task is to determine the length of the longest common subsequence of X_1,...,X_k that is also strictly increasing. Especially for the case of k=2 (called LCIS for short), several algorithms have been proposed that require quadratic time in the worst case.Assuming the Strong Exponential Time Hypothesis (SETH), we prove a tight lower bound, specifically, that no algorithm solves LCIS in (strongly) subquadratic time. Interestingly, the proof makes no use of normalization tricks common to hardness proofs for similar problems such as LCS. We further strengthen this lower bound to rule out O((nL)^{1-epsilon}) time algorithms for LCIS, where L denotes the solution size, and to rule out O(n^{k-epsilon}) time algorithms for k-LCIS. We obtain the same conditional lower bounds for the related Longest Common Weakly Increasing Subsequence problem.Fri, 23 Feb 2018 14:22:47 +0100http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8570Relativization and Interactive Proof Systems in Parameterized Complexity Theory
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8571
We introduce some classical complexity-theoretic techniques to Parameterized Complexity. First, we study relativization for the machine models that were used by Chen, Flum, and Grohe (2005) to characterize a number of parameterized complexity classes. Here we obtain a new and non-trivial characterization of the A-Hierarchy in terms of oracle machines, and parameterize a famous result of Baker, Gill, and Solovay (1975), by proving that, relative to specific oracles, FPT and A[1] can either coincide or differ (a similar statement holds for FPT and W[P]). Second, we initiate the study of interactive proof systems in the parameterized setting, and show that every problem in the class AW[SAT] has a proof system with "short" interactions, in the sense that the number of rounds is upper-bounded in terms of the parameter value alone.Fri, 23 Feb 2018 14:22:47 +0100http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8571Generalized Kakeya Sets for Polynomial Evaluation and Faster Computation of Fermionants
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8572
We present two new data structures for computing values of an n-variate polynomial P of degree at most d over a finite field of q elements. Assuming that d divides q-1, our first data structure relies on (d+1)^{n+2} tabulated values of P to produce the value of P at any of the q^n points using O(nqd^2) arithmetic operations in the finite field. Assuming that s divides d and d/s divides q-1, our second data structure assumes that P satisfies a degree-separability condition and relies on (d/s+1)^{n+s} tabulated values to produce the value of P at any point using O(nq^ssq) arithmetic operations. Our data structures are based on generalizing upper-bound constructions due to Mockenhaupt and Tao (2004), Saraf and Sudan (2008), and Dvir (2009) for Kakeya sets in finite vector spaces from linear to higher-degree polynomial curves.As an application we show that the new data structures enable a faster algorithm for computing integer-valued fermionants, a family of self-reducible polynomial functions introduced by Chandrasekharan and Wiese (2011) that captures numerous fundamental algebraic and combinatorial invariants such as the determinant, the permanent, the number of Hamiltonian cycles in a directed multigraph, as well as certain partition functions of strongly correlated electron systems in statistical physics. In particular, a corollary of our main theorem for fermionants is that the permanent of an m-by-m integer matrix with entries bounded in absolute value by a constant can be computed in time 2^{m-Omega(sqrt(m/log log m))}, improving an earlier algorithm of Bjorklund (2016) that runs in time 2^{m-Omega(sqrt(m/log m))}.Fri, 23 Feb 2018 14:22:47 +0100http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8572DynASP2.5: Dynamic Programming on Tree Decompositions in Action
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8573
Efficient, exact parameterized algorithms are a vibrant theoretical research area. Recent solving competitions, such as the PACE challenge, show that there is also increasing practical interest in the parameterized algorithms community. An important research question is whether such algorithms can be built to efficiently solve specific problems in practice, that is, to be competitive with established solving systems. In this paper, we consider Answer Set Programming (ASP), a logic-based declarative modeling and problem solving framework. State-of-the-art ASP solvers generally rely on SAT-based algorithms. In addition, DynASP2, an ASP solver that is based on a classical dynamic programming on tree decompositions, has recently been introduced. DynASP2 outperforms modern ASP solvers when the goal is to count the number of solutions of programs that have small treewidth. However, for quickly finding one solutions, DynASP2 proved uncompetitive. In this paper, we present a new algorithm and implementation, called DynASP2.5, that shows competitive behavior compared to state-of-the-art ASP solvers on problems like Steiner tree for low-treewidth graphs, even when thetask is to find just one solution. Our implementation is based on a novel approach that we call multi-pass dynamic programming.Fri, 23 Feb 2018 14:22:47 +0100http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8573OASIcs, Volume 60, ICCSW'17, Complete Volume
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8542
OASIcs, Volume 60, ICCSW'17, Complete VolumeWed, 21 Feb 2018 11:53:40 +0100http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8542OASIcs, Volume 58, ICLP'17, Complete Volume
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8540
OASIcs, Volume 58, ICLP'17, Complete VolumeWed, 21 Feb 2018 11:19:20 +0100http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8540LIPIcs, Volume 93, FSTTCS'17, Complete Volume
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8539
LIPIcs, Volume 93, FSTTCS'17, Complete VolumeWed, 21 Feb 2018 08:11:11 +0100http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8539