The complexity of satisfiability problems
From MaRDI portal
Publication:5402560
DOI10.1145/800133.804350zbMath1282.68143OpenAlexW2166566648MaRDI QIDQ5402560
Publication date: 14 March 2014
Published in: Proceedings of the tenth annual ACM symposium on Theory of computing - STOC '78 (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/800133.804350
Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
Constraint satisfaction and semilinear expansions of addition over the rationals and the reals, Tractability in constraint satisfaction problems: a survey, Minimal and almost minimal reaction systems, Traveling salesman problems in temporal graphs, The complexity of counting locally maximal satisfying assignments of Boolean CSPs, Finding good 2-partitions of digraphs. I. Hereditary properties, Complexity versus stability for classes of propositional formulas, Generating all maximal models of a Boolean expression, Computational hardness of enumerating groundstates of the antiferromagnetic Ising model in triangulations, Superpolynomial lower bounds for the \((1+1)\) EA on some easy combinatorial problems, Complexity of approximating CSP with balance/hard constraints, A survey on single crane scheduling in automated storage/retrieval systems, Strong partial clones and the time complexity of SAT problems, The complexity of approximately counting in 2-spin systems on \(k\)-uniform bounded-degree hypergraphs, Complexity of coloring graphs without paths and cycles, Combinatorial sharpness criterion and phase transition classification for random CSPs, From monomials to words to graphs., \(k-L(2,1)\)-labelling for planar graphs is NP-complete for \(k\geq 4\), On the Boolean connectivity problem for Horn relations, Belief revision within fragments of propositional logic, Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems, Generalized satisfiability for the description logic \(\mathcal{ALC}\), The complexity of complex weighted Boolean \#CSP, The complexity of generalized domino tilings, Bilevel programming and the separation problem, The computational complexity of avoiding spurious states in state space abstraction, Taking the final step to a full dichotomy of the possible winner problem in pure scoring rules, On making directed graphs transitive, Distance three labelings of trees, Equilibria of graphical games with symmetries, New results for the longest haplotype reconstruction problem, The complexity of satisfiability for fragments of hybrid logic. I., On the complexity of reconfiguration problems, Popular matchings with variable item copies, Influence of tree topology restrictions on the complexity of haplotyping with missing data, The complexity of recursive constraint satisfaction problems, Unification modulo homomorphic encryption, The root location problem for arc-disjoint arborescences, A dichotomy theorem for the approximate counting of complex-weighted bounded-degree Boolean CSPs, The complexity of surjective homomorphism problems-a survey, Complexity of partial satisfaction. II., Hybrid tractability of valued constraint problems, Colouring, constraint satisfaction, and complexity, Disjunctive closures for knowledge compilation, On embeddings of CAT(0) cube complexes into products of trees via colouring their hyperplanes, Approximating integer programs with positive right-hand sides, Colorful strips, Exact algorithms for Kayles, Boolean max-co-clones, The class of problems that are linearly equivalent to Satisfiability or a uniform method for proving NP-completeness, A linear-time algorithm for computing the intersection of all odd cycles in a graph, Unit-time scheduling problems with time dependent resources, A manually-checkable proof for the NP-hardness of 11-color pattern self-assembly tileset synthesis, Complexity of the satisfiability problem for multilinear forms over a finite field, The complexity of counting quantifiers on equality languages, Tractability conditions for numeric CSPs, Exploring the complexity of the integer image problem in the \(\max\)-algebra, On the complexity of colouring by superdigraphs of bipartite graphs, Rigid binary relations on a 4-element domain, Gap theorems for robust satisfiability: Boolean CSPs and beyond, Approximation complexity of complex-weighted degree-two counting constraint satisfaction problems, Approximate counting for complex-weighted Boolean constraint satisfaction problems, Approximation of Boolean functions to Schaefer's classes, A tractable NP-completeness proof for the two-coloring without monochromatic cycles of fixed length, Rule set design problems for oritatami systems, The complexity of circumscriptive inference in Post's lattice, Trichotomies in the complexity of minimal inference, On the expression complexity of equivalence and isomorphism of primitive positive formulas, Conjunctive query containment over trees, The complexity of the list homomorphism problem for graphs, The complexity of some acyclic improper colourings, Tractable structures for constraint satisfaction with truth tables, Quantified constraint satisfaction and the polynomially generated powers property, Public-key cryptographic system based on generalized satisfiability problem, Recognizing frozen variables in constraint satisfaction problems, Data exchange: semantics and query answering, The checkpoint problem, The complexity of asynchronous model based testing, Computing vertex-surjective homomorphisms to partially reflexive trees, On tree representations of relations and graphs: symbolic ultrametrics and cograph edge decompositions, On the most imbalanced orientation of a graph, Vertex 2-coloring without monochromatic cycles of fixed size is NP-complete, Backdoors into heterogeneous classes of SAT and CSP, Maximizing the minimum voter satisfaction on spanning trees, Regular expression order-sorted unification and matching, Algorithms for the maximum satisfiability problem, Computational complexity of norm-maximization, On linear k-arboricity, Updating the complexity status of coloring graphs without a fixed induced linear forest, Exact thresholds for DPLL on random XOR-SAT and NP-complete extensions of XOR-SAT, The complexity of relating quantum channels to master equations, The stable marriage problem with ties and restricted edges, On weak positive predicates over a finite set, Best-case and worst-case sparsifiability of Boolean CSPs, Signsolvability revisited, The expressive rate of constraints, Periodic constraint satisfaction problems: Tractable subclasses, Backdoors to q-Horn, \(H\)-coloring dichotomy revisited, Seriation in the presence of errors: NP-hardness of \(l_{\infty}\)-fitting Robinson structures to dissimilarity matrices, Edge-Disjoint Branchings in Temporal Graphs, On Embeddability of Unit Disk Graphs onto Straight Lines, Small Promise CSPs that reduce to large CSPs, Simultaneous Approximation of Constraint Satisfaction Problems, On Planar Boolean CSP, A Galois Connection for Valued Constraint Languages of Infinite Size, Ground State Connectivity of Local Hamiltonians, Counting Homomorphisms to Square-Free Graphs, Modulo 2, Algebraic Properties of Valued Constraint Satisfaction Problem, Shortest Reconfiguration Paths in the Solution Space of Boolean Formulas, Belief Update Within Propositional Fragments, Subexponential Time Algorithms for Finding Small Tree and Path Decompositions, On the Complexity of the Model Checking Problem, The phase transition in random horn satisfiability and its algorithmic implications, Necessary Conditions for Tractability of Valued CSPs, Unnamed Item, Nonnegative Weighted #CSP: An Effective Complexity Dichotomy, A Dichotomy Theorem for Polynomial Evaluation, The Complexity of Satisfiability for Fragments of Hybrid Logic—Part I, Circuit Satisfiability and Constraint Satisfaction Around Skolem Arithmetic, The Complexity of Counting Quantifiers on Equality Languages, Satisfiability in Boolean Logic (SAT problem) is polynomial?, Smooth and sharp thresholds for random{k}-XOR-CNF satisfiability, Smooth and sharp thresholds for random{k}-XOR-CNF satisfiability, On the Most Imbalanced Orientation of a Graph, On Symbolic Ultrametrics, Cotree Representations, and Cograph Edge Decompositions and Partitions, Satisfiability in MultiValued Circuits, NP-completeness: A retrospective, NP-Hardness of Reed--Solomon Decoding, and the Prouhet--Tarry--Escott Problem, On the impact of stratification on the complexity of nonmonotonic reasoning, Unnamed Item, A CNF Class Generalizing Exact Linear Formulas, Box Pleating is Hard, On Strong Tree-Breadth, Computational Complexity of Generalized Domination: A Complete Dichotomy for Chordal Graphs, Recognition of Polygon-Circle Graphs and Graphs of Interval Filaments Is NP-Complete, Obstructing Visibilities with One Obstacle, Simultaneous Orthogonal Planarity, Unnamed Item, Unnamed Item, Quantified Constraint Satisfaction and the Polynomially Generated Powers Property, Some Completeness Results on Decision Trees and Group Testing, Unnamed Item, The Complexity of Valued CSPs, Non-uniform Boolean Constraint Satisfaction Problems with Cardinality Constraint, Backdoor Sets for CSP., Quantified Constraints in Twenty Seventeen, On the Complexity of Holant Problems, Operation management in object-oriented knowledge bases, Progress in Complexity of Counting Problems, On the CSP Dichotomy Conjecture, Enumerating All Solutions of a Boolean CSP by Non-decreasing Weight, Locally Injective Homomorphism to the Simple Weight Graphs, Generalized Satisfiability for the Description Logic $\mathcal{ALC}$, Constraint Satisfaction Parameterized by Solution Size, Characterizing Arithmetic Circuit Classes by Constraint Satisfaction Problems, Unification and matching modulo nilpotence, On generating all solutions of generalized satisfiability problems, Finding Reductions Automatically, Unnamed Item, Tractable constraints in finite semilattices, On Some SAT-Variants over Linear Formulas, Satisfiability problems for propositional calculi, Unnamed Item, Unnamed Item, On the Complexity of Solving Restricted Word Equations, Unnamed Item, Unnamed Item, Unnamed Item, Narrowing Down the Gap on the Complexity of Coloring P k -Free Graphs, On the Computational Complexity of Monotone Constraint Satisfaction Problems, Parameterized Complexity of the Workflow Satisfiability Problem, Универсальные алгебры, порождаемые множествами выполняющих векторов биюнктивных и $r$-юнктивных булевых функций, О булевых функциях без верхних биюнктивных аналогов, Parameterized Complexity of Conflict-Free Graph Coloring, Partition into Triangles on Bounded Degree Graphs, Weakly Modular Graphs and Nonpositive Curvature, Исследование некоторых подклассов мультиаффинных, биюнктивных, слабо положительных и слабо отрицательных булевых функций, О весах булевых функций, представимых в виде $2$-КНФ или $3$-КНФ, Параметры метода максимального правдоподобия при его использовании для решения систем дважды биюнктивных уравнений с искаженными правыми частями, NAE-resolution: A new resolution refutation technique to prove not-all-equal unsatisfiability, On m-Junctive Predicates on a Finite Set, Edge-Matching Problems with Rotations, Coloring Graphs without Short Cycles and Long Induced Paths, On Some Aspects of Mixed Horn Formulas, Adventures in monotone complexity and TFNP, Finding a Small Number of Colourful Components, Popular Matchings in Complete Graphs, Colouring (P_r+P_s)-Free Graphs, On the existence and non-existence of improper homomorphisms of oriented and $2$-edge-coloured graphs to reflexive targets, Exact Algorithms for Kayles, Unification Modulo Homomorphic Encryption, A Retrospective on Genomic Preprocessing for Comparative Genomics, The replica symmetric phase of random constraint satisfaction problems, Clique-coloring some classes of odd-hole-free graphs, Solving CSPs Using Weak Local Consistency, A survey on pairwise compatibility graphs, Backdoors into Two Occurrences, Solution-Graphs of Boolean Formulas and Isomorphism1, EXPLORING THE LANDSCAPE OF RELATIONAL SYLLOGISTIC LOGICS, Multicriteria energy policy investments and energy market clearance via integer programming, Zeons, orthozeons, and graph colorings, When road trains supply freight trains: scheduling the container loading process by gantry crane between multi-trailer trucks and freight trains, Computational complexity of inner and outer \(j\)-radii of polytopes in finite-dimensional normed spaces, Complexity and approximation of the minimum recombinant haplotype configuration problem, Finding good 2-partitions of digraphs. II. Enumerable properties, Min (a)cyclic feedback vertex sets and MIN ones monotone 3-SAT, On finding and enumerating maximal and maximum \( k\)-partite cliques in \( k\)-partite graphs, Characteristic function games with restricted agent interactions: core-stability and coalition structures, Hierarchical complexity of 2-clique-colouring weakly chordal graphs and perfect graphs having cliques of size at least 3, CSP for binary conservative relational structures, Backdoors to Satisfaction, List coloring in the absence of two subgraphs, Satisfiability with index dependency, Is the protein model assignment problem under linked branch lengths NP-hard?, Supermodular functions and the complexity of MAX CSP, Domain permutation reduction for constraint satisfaction problems, What makes propositional abduction tractable, Packing Steiner trees with identical terminal sets, Partition into triangles on bounded degree graphs, Relating the Time Complexity of Optimization Problems in Light of the Exponential-Time Hypothesis, Paradigms for parameterized enumeration, Unnamed Item, NP-complete problems for systems of linear polynomial's values divisibilities, NP completeness conditions for verifying the consistency of several kinds of systems of linear Diophantine discongruences, Connectivity of orientations of 3-edge-connected graphs, Universal qudit Hamiltonians, Computational complexity studies of synchronous Boolean finite dynamical systems on directed graphs, Popular matchings in complete graphs, Modeling Musical Structure with Parametric Grammars, The Generalized Popular Condensation Problem, The connectivity of Boolean satisfiability: dichotomies for formulas and circuits, Complexity of tiling a polygon with trominoes or bars, Hadwiger Number of Graphs with Small Chordality, On some variants of Euclidean \(k\)-supplier, Precise Upper and Lower Bounds for the Monotone Constraint Satisfaction Problem, Complexity Classifications for Logic-Based Argumentation, Why Is It Hard to Obtain a Dichotomy for Consistent Query Answering?, Checking Whether an Automaton Is Monotonic Is NP-complete, A Dichotomy Result for Ramsey Quantifiers, On the Structure of Solution-Graphs for Boolean Formulas, Multiaffinity testing of Boolean functions using their Zhegalkin polynomials, Computational Complexity Studies of Synchronous Boolean Finite Dynamical Systems, On the computational complexity of the bipartizing matching problem, Complexity study for the robust stable marriage problem, When an optimal dominating set with given constraints exists, On finite Taylor algebras, Complexity of road coloring with prescribed reset words, On digraph coloring problems and treewidth duality, The complexity of blocking (semi)total dominating sets with edge contractions, On the complexity of recognizing Stick, BipHook and max point-tolerance graphs, Bit-complexity of classical solutions of linear evolutionary systems of partial differential equations, A complete 4-parametric complexity classification of short shop scheduling problems, Solving a real-life, large-scale energy management problem, Constrained hitting set problem with intervals, The complexity of two colouring games, XSAT and NAE-SAT of linear CNF classes, Coloring graphs without short cycles and long induced paths, Edge-intersection graphs of grid paths: the bend-number, The vertex leafage of chordal graphs, A note on the complexity of matching patterns with variables, (Circular) backbone colouring: forest backbones in planar graphs, Predecessor existence problems for finite discrete dynamical systems, The complexity of soft constraint satisfaction, On variable-weighted exact satisfiability problems, Counting truth assignments of formulas of bounded tree-width or clique-width, Complexity of clausal constraints over chains, Combinatorial problems raised from 2-semilattices, Partition a graph with small diameter into two induced matchings, Schaefer's Theorem for Graphs, Complexity Classification of Local Hamiltonian Problems, On graphs that are not PCGs, Dichotomy for finite tournaments of mixed-type, As Close as It Gets, The Geometry of Differential Privacy: The Small Database and Approximate Cases, On the Solvability Problem for Restricted Classes of Word Equations, Robustly Solvable Constraint Satisfaction Problems, A Complete Dichotomy Rises from the Capture of Vanishing Signatures, Solution-Graphs of Boolean Formulas and Isomorphism, Strong Backdoors for Default Logic, SOBRA - Shielding Optimization for BRAchytherapy, Two-element structures modulo primitive positive constructability, On a simple hard variant of \textsc{Not-All-Equal} 3-\textsc{Sat}, A multiparametric view on answer set programming, NodeTrix planarity testing with small clusters, Minimal distance of propositional models, A logic for document spanners, Variations on Instant Insanity, Introduction to reconfiguration, MPF problem over modified medial semigroup is NP-complete, Decomposition into two trees with orientation constraints, An upper bound \(O(2^{0.16254n})\) for exact 3-satisfiability: a simpler proof, The complexity of partition functions, Locally consistent constraint satisfaction problems, Constructing NP-intermediate problems by blowing holes with parameters of various properties, Well-solvable cases of the QAP with block-structured matrices, Pattern matching with variables: a multivariate complexity analysis, On the isomorphism problem for decision trees and decision lists, Partitioning a graph into disjoint cliques and a triangle-free graph, On the multiplicative complexity of some Boolean functions, Pushing vertices in digraphs without long induced cycles, The complexity of propositional closed world reasoning and circumscription, Implications of forbidden structures for extremal algorithmic problems, Scheduling tasks on two processors with deadlines and additional resources, Computing the zig-zag number of directed graphs, Efficient algorithms for minimum weighted colouring of some classes of perfect graphs, Complexity of counting the optimal solutions, Hard constraint satisfaction problems have hard gaps at location 1, The complexity of weighted Boolean \#CSP with mixed signs, Causal approximations, The complexity of constraint satisfaction games and QCSP, On the complexity of some basic problems in computational convexity. I. Containment problems, Hardness results on the man-exchange stable marriage problem with short preference lists, Nonnegative integral subset representations of integer sets, Nominal unification with atom-variables, Polynomial-time inference of all valid implications for Horn and related formulae, Computational complexity of distance edge labeling, The complexity of minimizing wire lengths in VLSI layouts, Symbolic techniques in satisfiability solving, Shortest enclosing walks and cycles in embedded graphs, Observations concerning a public-key cryptosystem based on iterated morphisms, A hierarchy of propositional Horn formuls, Towards a characterization of constant-factor approximable finite-valued CSPs, The complexity of minimum partial truth assignments and implication in negation-free formulae, Towards a dichotomy theorem for the counting constraint satisfaction problem, Reasoning with minimal models: efficient algorithms and applications, Circuit satisfiability and constraint satisfaction around Skolem arithmetic, Maximum \(H\)-colourable subdigraphs and constraint optimization with arbitrary weights, On the complexity of trial and error for constraint satisfaction problems, Decidability and complexity for quiescent consistency and its variations, On the hardness of computing span of subcubic graphs, Satisfiability problems on intervals and unit intervals, On the complexity of \(\mathbb{H}\)-coloring for special oriented trees, Backtracking with multi-level dynamic search rearrangement, Two-machine interval shop scheduling with time lags, Finding non-orientable surfaces in 3-manifolds, Conservative constraint satisfaction re-revisited, A new line of attack on the dichotomy conjecture, On the complexity of the regenerator location problem treewidth and other parameters, Computational complexity of covering three-vertex multigraphs, Generalized satisfiability problems: Minimal elements and phase transitions., The complexity of counting self-avoiding walks in subgraphs of two-dimensional grids and hypercubes., Schemas for unordered XML on a DIME, On the construction of graphs with a planar bipartite double cover from Boolean formulas and its application to counting satisfying solutions, Out-degree reducing partitions of digraphs, Crane scheduling in railway yards: an analysis of computational complexity, On colouring \((2P_2,H)\)-free and \((P_5,H)\)-free graphs, The \((n^ 2-1)\)-puzzle and related relocation problems, Existence of simple propositional formulas, An NP-complete matching problem, NP-completeness of some generalizations of the maximum matching problem, Optimal satisfiability for propositional calculi and constraint satisfaction problems., Learnability of quantified formulas., Pattern matching and membership for hierarchical message sequence charts, On minimum dominating sets with minimum intersection, Computational complexity of auditing finite attributes in statistical databases, Correlation polytopes: Their geometry and complexity, Generalising submodularity and Horn clauses: Tractable optimization problems defined by tournament pair multimorphisms, Structure identification of Boolean relations and plain bases for co-clones, On the counting complexity of propositional circumscription, The complexity of model checking for circumscriptive formulae, The Helly property and satisfiability of Boolean formulas defined on set families, Complexity of (p,1)-total labelling, Complexity of path-forming games, An approximation trichotomy for Boolean \#CSP, Integer programming with 2-variable equations and 1-variable inequalities, Generalized modal satisfiability, Counting complexity of propositional abduction, Generalizing constraint satisfaction on trees: hybrid tractability and variable elimination, Information loss in knowledge compilation: a comparison of Boolean envelopes, A linear-time algorithm for testing the truth of certain quantified Boolean formulas, Existentially restricted quantified constraint satisfaction, A minimization version of a directed subgraph homeomorphism problem, Universal algebra and hardness results for constraint satisfaction problems, The complexity of satisfiability problems: Refining Schaefer's theorem, Stable matching problems with exchange restrictions, Relatively quantified constraint satisfaction, Partially ordered connectives and monadic monotone strict NP, The SAT-UNSAT transition for random constraint satisfaction problems, Constraints, consistency and closure, On the algebraic structure of combinatorial problems, Using clausal graphs to determine the computational complexity of \(k\)-bounded positive one-in-three SAT, An efficient algorithm for Horn description, The complexity of some problems related to GRAPH 3-COLORABILITY, On the complexities of selected satisfiability and equivalence queries over Boolean formulas and inclusion queries over hulls, Boolean constraint satisfaction: Complexity results for optimization problems with arbitrary weights, A combinatorial constraint satisfaction problem dichotomy classification conjecture, NP-hard and linear variants of hypergraph partitioning, On recovering syntenic blocks from comparative maps, Bases for Boolean co-clones, A surprising permanence of old motivations (a not-so-rigid story), An algorithm for exact satisfiability analysed with the number of clauses as parameter, On stable cutsets in graphs, On the computational complexity of reconstructing lattice sets from their \(X\)-rays, Conjunctive-query containment and constraint satisfaction, A two-phase algorithm for solving a class of hard satisfiability problems, Combinatorial analysis (nonnegative matrices, algorithmic problems), Complete problems for space bounded subclasses of NP, The NP-completeness of (1,r)-subcolorability of cubic graphs, Deciding whether a planar graph has a cubic subgraph is NP-complete, Medians in median graphs and their cube complexes in linear time, On regularity of Max-CSPs and Min-CSPs, Fast approximate probabilistically checkable proofs, Dichotomies for classes of homomorphism problems involving unary functions, The complexity of minimal satisfiability problems, On the complexity of minmax regret linear programming, Largest \(j\)-simplices in \(n\)-polytopes, Positive planar satisfiability problems under 3-connectivity constraints, A tetrachotomy of ontology-mediated queries with a covering axiom, The complexity of \(L(p, q)\)-edge-labelling, Structural parameterization for minimum conflict-free colouring, Partitioning \(H\)-free graphs of bounded diameter, Colouring generalized claw-free graphs and graphs of large girth: bounding the diameter, Learning from positive and negative examples: dichotomies and parameterized algorithms, On the complexity of recognizing a class of perfectly orderable graphs, Proof of the interval satisfiability conjecture, The generalized definitions of the two-dimensional largest common substructure problems, Placing quantified variants of 3-SAT and \textsc{not-all-equal} 3-SAT in the polynomial hierarchy, The complexity of approximating bounded-degree Boolean \(\#\)CSP, The complete set of minimal simple graphs that support unsatisfiable 2-CNFs, Low-level dichotomy for quantified constraint satisfaction problems, Hardness results for three kinds of colored connections of graphs, On the complexity of recognizing \(S\)-composite and \(S\)-prime graphs, On the complexity of testing attainment of the optimal value in nonlinear optimization, On the complexity of graph coloring with additional local conditions, Approximating partition functions of bounded-degree Boolean counting constraint satisfaction problems, Using a Min-Cut generalisation to go beyond Boolean surjective VCSPs, The complexity of problems for quantified constraints, Satisfiability threshold for random XOR-CNF formulas, The \(Multi\)-SAT algorithm, Independent sets with domination constraints, Recognition of tractable satisfiability problems through balanced polynomial representations, Partition of a binary matrix into \(k\) (\(k \geq 3\)) exclusive row and column submatrices is difficult, Complexity of inverse constraint problems and a dichotomy for the inverse satisfiability problem, Distance and routing labeling schemes for cube-free median graphs, Particle swarm optimization for computing Nash and Stackelberg equilibria in energy markets, Simultaneous visibility representations of undirected pairs of graphs, Computational complexity of three-dimensional discrete tomography with missing data, \(r\)-gathering problems on spiders: hardness, FPT algorithms, and PTASes, Improved algorithms for the general exact satisfiability problem, Linear discrepancy is \(\Pi_2\)-hard to approximate, Constrained synchronization and commutativity, The exponential-time hypothesis and the relative complexity of optimization and logical reasoning problems, Edge-disjoint branchings in temporal digraphs, On bijunctive predicates over a finite set, Decomposition of university course timetabling. A systematic study of subproblems and their complexities, On the efficiency of normal form systems for representing Boolean functions, Sandwiches for promise constraint satisfaction, Network pollution games, Closing complexity gaps for coloring problems on \(H\)-free graphs, Constant unary constraints and symmetric real-weighted counting constraint satisfaction problems, The complexity of forbidden subgraph sandwich problems and the skew partition sandwich problem, A combinatorial approach to nonlocality and contextuality, A hypocoloring model for batch scheduling, The complexity of tropical graph homomorphisms, New algorithms for exact satisfiability, Realizability and verification of MSC graphs, Popularity at minimum cost, Annotation theories over finite graphs, Minimal functions on the random graph, Balanced vertex-orderings of graphs, A new tractable class of constraint satisfaction problems, Isomorphic implication, On the complexity of deciding typability in the relational algebra, The complexity of Boolean constraint satisfaction local search problems, Exact 3-satisfiability is decidable in time \(O(2^{0.16254 n})\), Constraint satisfaction problems over semilattice block Mal'tsev algebras, A complexity theory for hard enumeration problems, Degree constrained 2-partitions of semicomplete digraphs, Variadic equational matching in associative and commutative theories, Pushing the frontier of minimality, Dichotomy for Holant\(^\ast\) problems on the Boolean domain, Parameterized counting of partially injective homomorphisms, On Frank's conjecture on \(k\)-connected orientations, Role colouring graphs in hereditary classes, Sliding window temporal graph coloring, Complexity of packing common bases in matroids, Complexity results for two kinds of colored disconnections of graphs, On the complexity of the clone membership problem, Sorting, linear time and the satisfiability problem, On the hardness of finding normal surfaces, Bandwidth contrained NP-complete problems, On perturbation resilience of non-uniform \(k\)-center, Univariate ideal membership parameterized by rank, degree, and number of generators, On the complexity of local-equitable coloring of graphs, Investigations on autark assignments, Precedence thinness in graphs, CNF satisfiability in a subspace and related problems, Using edge contractions to reduce the semitotal domination number, Faster exact solutions for some NP-hard problems., On the Hamming distance of constraint satisfaction problems., Complexity of nilpotent unification and matching problems., Parallel approximation schemes for a class of planar and near planar combinatorial optimization problems., Tractable reasoning via approximation, Beyond PCSP (\textbf{1-in-3}, \textbf{NAE}), A perspective on certain polynomial-time solvable classes of satisfiability, Efficient \((j, k)\)-dominating functions, Partitions and well-coveredness: the graph sandwich problem, Bit-complexity of solving systems of linear evolutionary partial differential equations, A refined branching algorithm for the maximum satisfiability problem, Belief Merging within Fragments of Propositional Logic, Quantified Constraint Satisfaction Problem on Semicomplete Digraphs, Merging in the Horn Fragment, CLAP: A New Algorithm for Promise CSPs, Aggregation of Votes with Multiple Positions on Each Issue, The Complexity of General-Valued CSPs, Shortest Reconfiguration Paths in the Solution Space of Boolean Formulas, Complexity and polymorphisms for digraph constraint problems under some basic constructions, An Algebraic Characterization of Testable Boolean CSPs, Hypergraph Cuts with General Splitting Functions, Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy, Ideal Membership Problem over 3-Element CSPs with Dual Discriminator Polymorphism, Unnamed Item, Inapproximability of positive semidefinite permanents and quantum state tomography, Multistage \(s-t\) path: confronting similarity with dissimilarity, The complexity of 2-vertex-connected orientation in mixed graphs, Stable matching with multilayer approval preferences: approvals can be harder than strict preferences, The complexity of finding tangles, Parameterized Complexity of Logic-based Argumentation in Schaefer’s Framework, Mixed Iterated Revisions: Rationale, Algorithms, and Complexity, \(st\)-orientations with few transitive edges, Constraint satisfaction problem: what makes the problem easy, Listing the bonds of a graph in \(\widetilde{O} (n)\)-delay, Computational complexity of necessary envy-freeness, $st$-Orientations with Few Transitive Edges, SAT backdoors: depth beats size, CSP beyond tractable constraint languages, Stable matching with multilayer approval preferences: approvals can be harder than strict preferences, Complexity of public goods games on graphs, Refined computational complexities of hospitals/residents problem with regional caps, A toolbox for barriers on interactive oracle proofs, Hardness of uncertain segment cover, contiguous SAT and visibility with uncertain obstacles, Algorithms and complexity of sandwich problems in graphs (extended abstract), The inverse satisfiability problem, The Complexity of Boolean Surjective General-Valued CSPs, First-order logic axiomatization of metric graph theory, Constrained hitting set problem with intervals: hardness, FPT and approximation algorithms, $(2+\varepsilon)$-Sat Is NP-hard, Binarisation for Valued Constraint Satisfaction Problems, Characterizing polynomial Ramsey quantifiers, Model Reductions for Inference: Generality of Pairwise, Binary, and Planar Factor Graphs, Unnamed Item, Computing Version Spaces in the Qualitative Approach to Multicriteria Decision Aid, The Power of the Combined Basic Linear Programming and Affine Relaxation for Promise Constraint Satisfaction Problems, Global Cardinality Constraints Make Approximating Some Max-2-CSPs Harder, Классы Шефера, классы Поста и соответствия Галуа, Вычисление коэффициента аддитивности для некоторых биюнктивных, слабо положительных и слабо отрицательных булевых функций, Функции из классов Шефера, переходящие при отрицании в другие классы Шефера, Стабилизаторы некоторых семейств булевых функций, образующих Галуа-замкнутые подалгебры алгебры Шефера, On the Computational Complexity of Non-Dictatorial Aggregation, Good edge-labelling of graphs, The Weight in Enumeration, The Next Whisky Bar, On the Minimal Constraint Satisfaction Problem: Complexity and Generation, The complexity of \(L(p, q)\)-edge-labelling, Power indices and easier hard problems, Constraint Satisfaction with Counting Quantifiers, Unnamed Item, Unnamed Item, Unnamed Item, Good edge-labelling of graphs, Tractable constraints on ordered domains, Robust Algorithms with Polynomial Loss for Near-Unanimity CSPs, Parameterized Complexity and Kernelizability of Max Ones and Exact Ones Problems, The Complexity of Symmetric Boolean Parity Holant Problems, Graph isomorphism restricted by lists, Minimum membership covering and hitting, Minimum reload cost graph factors, Unnamed Item, Unnamed Item, Colouring graphs of bounded diameter in the absence of small cycles, Homomorphism Reconfiguration via Homotopy, Maximum independent and disjoint coverage, On the (di)graphs with (directed) proper connection number two, The computational complexity of knot genus and spanning area, Unnamed Item, The Complexity of Finding Read-Once NAE-Resolution Refutations, Testing the Complexity of a Valued CSP Language, A fine-grained analogue of schaefer's Theorem in P: dichotomy of ∃k∀-quantified first-order graph properties, Colouring H-free graphs of bounded diameter., Finding small satisfying assignments faster than brute force: a fine-grained perspective into boolean constraint satisfaction, Unnamed Item, Constraint Satisfaction Problems for Reducts of Homogeneous Graphs, Unnamed Item, Time Complexity of Constraint Satisfaction via Universal Algebra, Counting Restricted Homomorphisms via Möbius Inversion over Matroid Lattices, Unnamed Item, Boolean Constraint Satisfaction Problems: When Does Post’s Lattice Help?, Basics of Galois Connections, Recent Results on the Algebraic Approach to the CSP, A Logical Approach to Constraint Satisfaction, Partial Polymorphisms and Constraint Satisfaction Problems, On Recovering Syntenic Blocks from Comparative Maps, The Power of Linear Programming for General-Valued CSPs, Faster than classical quantum algorithm for dense formulas of exact satisfiability and occupation problems, A non-commuting stabilizer formalism, Unnamed Item, Constraint Satisfaction Problems with Global Modular Constraints: Algorithms and Hardness via Polynomial Representations, On Symbolic Heaps Modulo Permission Theories, A Dichotomy Theorem for the Inverse Satisfiability Problem, Disconnected matchings, On embeddability of unit disk graphs onto straight lines, The complexity of contracting bipartite graphs into small cycles, Induced disjoint paths and connected subgraphs for \(H\)-free graphs, Generating Difficult CNF Instances in Unexplored Constrainedness Regions, Combinatorial properties and recognition of unit square visibility graphs, Induced disjoint paths and connected subgraphs for \(H\)-free graphs, On properties of multiaffine predicates on a finite set, Perfect forests in graphs and their extensions, On the complexity of the storyplan problem, Towards better heuristics for solving bounded model checking problems, An algebraic characterization of tractable constraints, Unnamed Item, Unnamed Item, Multistage s-t Path: Confronting Similarity with Dissimilarity in Temporal Graphs, Minimization and parameterized variants of vertex partition problems on graphs, Fanout limitations on constraint systems, On completing latin squares, Generalized satisfiability problems via operator assignments, Tractable constraints on ordered domains, Maximum cuts in edge-colored graphs, Colouring graphs of bounded diameter in the absence of small cycles, Local search strikes again: PTAS for variants of geometric covering and packing, Disconnected matchings
