20 papers · ranked by Valyu relevance
Matthias Mnich, René van Bevern
Machine scheduling problems are a long-time key domain of algorithms and complexity research. A novel approach to machine scheduling problems are fixed-parameter algorithms. To stimulate this thriving research direction, we propose 15 open questions in this area whose resolution we expect to lead to the discovery of…
Aritra Banik, Pratibha Choudhary, Venkatesh Raman, Saket Saurabh
We consider the parameterized complexity of the problem of tracking shortest s-t paths in graphs, motivated by applications in security and wireless networks. Given an undirected and unweighted graph with a source s and a destination t, Tracking Shortest Paths asks if there exists a k-sized subset of vertices (referred…
Iris van de Pol, Iris van Rooij, Jakub Szymanik
Theory of mind refers to the human capacity for reasoning about others’ mental states based on observations of their actions and unfolding events. This type of reasoning is notorious in the cognitive science literature for its presumed computational intractability. A possible reason could be that it may involve…
Hans-Joachim Böckenhauer, Elisabet Burjons, Martin Raszyk, Peter Rossmanith
'Peter Rossmanith'] Parameterized complexity allows us to analyze the time complexity of problems with respect to a natural parameter depending on the problem. Reoptimization looks for solutions or approximations for problem instances when given solutions to neighboring instances. We combine both techniques, in order…
Jesper Nederlof, Céline M. F. Swennenhuis
We study a natural variant of scheduling that we call partial scheduling: in this variant an instance of a scheduling problem along with an integer k is given and one seeks an optimal schedule where not all, but only k jobs, have to be processed. Specifically, we aim to determine the fine-grained parameterized…
Nicolas Bourgeois, Konrad K. Dabrowski, Marc Demange, Vangélis Th. Paschos
'Vangélis Th. Paschos'] When considering a graph problem from a parameterized point of view, the parameter chosen is often the size of an optimal solution of this problem (the "standard" parameter). A natural subject for investigation is what happens when we parameterize such a problem by various other parameters, some…
Marcin Briański, Martin Koutecký, Daniel Král’, Kristýna Pekárková + 1 more
An intensive line of research on fixed parameter tractability of integer programming is focused on exploiting the relation between the sparsity of a constraint matrix A and the norm of the elements of its Graver basis. In particular, integer programming is fixed parameter tractable when parameterized by the primal…
Robert Ganian, Sebastian Ordyniak
This paper revisits the classical edge-disjoint paths (EDP) problem, where one is given an undirected graph G and a set of terminal pairs P and asks whether G contains a set of pairwise edge-disjoint paths connecting every terminal pair in P. Our aim is to identify structural properties (parameters) of graphs which…
Christer Bäckström, Peter Jönsson, Sebastian Ordyniak, Stefan Szeider
'Stefan Szeider'] The propositional planning problem is a notoriously difficult computational problem. Downey et al. (1999) initiated the parameterized analysis of planning (with plan length as the parameter) and B¨ackstr¨om et al. (2012) picked up this line of research and provided an extensive parameterized analysis…
Aditya Pratapa, Amogh P. Jalihal, S. S. Ravi, T. M. Murali
The genetic cross is a fundamental, flexible, and widely-used experimental technique to create new mutant strains from existing ones. Surprisingly, the problem of how to efficiently compute a sequence of crosses that can make a desired target mutant from a set of source mutants has received scarce attention. In this…
Jarosław Błasiok, Marcin Kamiński
Given two finite posets P and Q , P is a chain minor of Q if there exists a partial function f from the elements of Q to the elements of P such that for every chain in P there is a chain C Q in Q with the property that f restricted to C Q is an isomorphism of chains.
Britta Dorn, Ronald de Haan, Ildikó Schlotter
We consider the following control problem on fair allocation of indivisible goods. Given a set I of items and a set of agents, each having strict linear preferences over the items, we ask for a minimum subset of the items whose deletion guarantees the existence of a proportional allocation in the remaining instance; we…
Bertrand Marchand, Yann Ponty, Laurent Bulteau
Hard graph problems are ubiquitous in Bioinformatics, inspiring the design of specialized Fixed-Parameter Tractable algorithms, many of which rely on a combination of tree-decomposition and dynamic programming. The time/space complexities of such approaches hinge critically on low values for the treewidth tw of the…
Simone Bova, Friedrich Slivovsky
We present new results on the size of OBDD representations of structurally characterized classes of CNF formulas. First, we prove that variable convex formulas (that is, formulas with incidence graphs that are convex with respect to the set of variables) have polynomial OBDD size. Second, we prove an exponential lower…
Anna Posfai, Juannan Zhou, David M. McCandlish, Justin B. Kinney
Quantitative models of sequence-function relationships are ubiquitous in computational biology, e.g., for modeling the DNA binding of transcription factors or the fitness landscapes of proteins. Interpreting these models, however, is complicated by the fact that the values of model parameters can often be changed…
Onyekachi Emenike, Fred J. Hickernell, Peter Kritzer
A large literature specifies conditions under which the information complexity for a sequence of numerical problems defined for dimensions 1, 2, . . . grows at a moderate rate, i.e., the sequence of problems is tractable. Here, we focus on the situation where the space of available information consists of all linear…
Juan Pablo Franco, Nitin Yadav, Peter Bossaerts, Carsten Murawski
Life presents us with decisions of varying degrees of difficulty. Many of them are NP-hard, that is, they are computationally intractable. Two important questions arise: which properties of decisions drive extreme computational hardness and what are the effects of these properties on human-decision making? Here, we…
James R. Riehl, Maxwell I. Zimmerman, Matthew F. Singh, Gregory R. Bowman + 1 more
Equilibria, or fixed points, play an important role in dynamical systems across various domains, yet finding them can be computationally challenging. Here, we show how to efficiently compute all equilibrium points of discrete-valued, discrete-time systems on sparse networks. Using graph partitioning, we recursively…
Kousha Etessami, Christos H. Papadimitriou, Aviad Rubinstein, Mihalis Yannakakis
'Mihalis Yannakakis'] The use of monotonicity and Tarski's theorem in existence proofs of equilibria is very widespread in economics, while Tarski's theorem is also often used for similar purposes in the context of verification. However, there has been relatively little in the way of analysis of the complexity of…
Peter L. Bartlett, Chris Junchi Li, Jingfeng Wu, Bin Yu
In the field of optimization, developing accelerated methods for solving minimax and fixed-point problems remains a fundamental challenge. This paper presents a novel family of dual accelerated algorithms that achieve optimal convergence rates for both minimax and fixed-point problems. By exploring new anchoring…