The parameterized space complexity of model-checking bounded variable first-order logic [PDF]
Logical Methods in Computer Science, 2019 The parameterized model-checking problem for a class of first-order sentences (queries) asks to decide whether a given sentence from the class holds true in a given relational structure (database); the parameter is the length of the sentence.
Yijia Chen +2 more
doaj +8 more sources
Parameterized Complexity of Equitable Coloring [PDF]
Discrete Mathematics & Theoretical Computer Science, 2019 A graph on $n$ vertices is equitably $k$-colorable if it is $k$-colorable and every color is used either $\left\lfloor n/k \right\rfloor$ or $\left\lceil n/k \right\rceil$ times.
Guilherme de C. M. Gomes +2 more
doaj +6 more sources
On the Parameterized Complexity of Symmetric Directed Multicut [PDF]
International Symposium on Parameterized and Exact Computation, 2022 We study the problem Symmetric Directed Multicut from a parameterized complexity perspective. In this problem, the input is a digraph $D$, a set of cut requests $C=\{(s_1,t_1),\ldots,(s_\ell,t_\ell)\}$ and an integer $k$, and the task is to find a set $X
Dániel Marx +2 more
openalex +3 more sources
A Survey on Approximation in Parameterized Complexity: Hardness and Algorithms [PDF]
Algorithms, 2020 Parameterization and approximation are two popular ways of coping with NP-hard problems. More recently, the two have also been combined to derive many interesting results.
Andreas Emil Feldmann +3 more
doaj +2 more sources
Model-Checking Problems as a Basis for Parameterized Intractability [PDF]
Logical Methods in Computer Science, 2005 Most parameterized complexity classes are defined in terms of a parameterized version of the Boolean satisfiability problem (the so-called weighted satisfiability problem). For example, Downey and Fellow's W-hierarchy is of this form.
Joerg Flum, Martin Grohe
doaj +4 more sources
Optimal Complexity of Parameterized Quantum Circuits [PDF]
EntropyParameterized quantum circuits are central to the development of variational quantum algorithms in the NISQ era. A key feature of these circuits is their ability to generate an expressive set of quantum states, enabling the approximation of solutions to ...
Guilherme I. Correr +3 more
doaj +2 more sources
Parameterized Complexity of Theory of Mind Reasoning in Dynamic Epistemic Logic. [PDF]
J Logic Lang Inf, 2018 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 ...
van de Pol I, van Rooij I, Szymanik J.
europepmc +2 more sources
Approximation and Parameterized Complexity of Minimax Approval Voting [PDF]
, 2016 We present three results on the complexity of Minimax Approval Voting. First, we study Minimax Approval Voting parameterized by the Hamming distance $d$ from the solution to the votes. We show Minimax Approval Voting admits no algorithm running in time $\
Cygan, Marek +3 more
core +2 more sources
On the parameterized complexity of the median and closest problems under some permutation metrics [PDF]
Algorithms for Molecular BiologyGenome rearrangements are events where large blocks of DNA exchange places during evolution. The analysis of these events is a promising tool for understanding evolutionary genomics, providing data for phylogenetic reconstruction based on genome ...
Luís Cunha, Ignasi Sau, Uéverton Souza
doaj +2 more sources
ON PARAMETERIZED COMPLEXITY OF HITTING SET PROBLEM FOR AXIS–PARALLEL SQUARES INTERSECTING A STRAIGHT LINE [PDF]
Ural Mathematical Journal, 2016 The Hitting Set Problem (HSP) is the well known extremal problem adopting research interest in the fields of combinatorial optimization, computational geometry, and statistical learning theory for decades.
Daniel M. Khachay, Michael Yu. Khachay
doaj +2 more sources