The complexity of homomorphism and constraint satisfaction problems seen from the other side
From MaRDI portal
Publication:3546332
DOI10.1145/1206035.1206036zbMath1312.68101OpenAlexW2111829945WikidataQ56389124 ScholiaQ56389124MaRDI QIDQ3546332
Publication date: 21 December 2008
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/1206035.1206036
Analysis of algorithms and problem complexity (68Q25) Database theory (68P15) Structural characterization of families of graphs (05C75) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Relational systems, laws of composition (08A02)
Related Items
Structural tractability of counting of solutions to conjunctive queries, Tractability in constraint satisfaction problems: a survey, Structural decompositions for problems with global constraints, The Power of Local Consistency in Conjunctive Queries and Constraint Satisfaction Problems, Lower Bounds for the Graph Homomorphism Problem, Binary constraint satisfaction problems defined by excluded topological minors, Some complete and intermediate polynomials in algebraic complexity theory, Unnamed Item, Quantified conjunctive queries on partially ordered sets, A tetrachotomy of ontology-mediated queries with a covering axiom, Strong partial clones and the time complexity of SAT problems, On planar valued CSPs, Unnamed Item, An Algebraic Characterization of Testable Boolean CSPs, Circuit satisfiability and constraint satisfaction around Skolem arithmetic, On Singleton Arc Consistency for CSPs Defined by Monotone Patterns, Tractable counting of the answers to conjunctive queries, Quantified Conjunctive Queries on Partially Ordered Sets, The dynamic complexity of acyclic hypergraph homomorphisms, Tree projections and structural decomposition methods: minimality and game-theoretic characterization, The complexity of weighted counting for acyclic conjunctive queries, An algorithmic framework for locally constrained homomorphisms, Reconfiguration in bounded bandwidth and tree-depth, Counting Homomorphic Cycles in Degenerate Graphs, Exploiting Database Management Systems and Treewidth for Counting, On the non-efficient PAC learnability of conjunctive queries, PTAS for Sparse General-valued CSPs, Answer Counting under Guarded TGDs, Parameterised counting in logspace, The challenges of unbounded treewidth in parameterised subgraph counting problems, Enumerating homomorphisms, A survey of parameterized algorithms and the complexity of edge modification, Majority constraints have bounded pathwidth duality, Unnamed Item, The power of propagation: when GAC is enough, Unnamed Item, Non-dichotomies in Constraint Satisfaction Complexity, Computing hypergraph width measures exactly, New plain-exponential time classes for graph homomorphism, Graph theory in Coq: minors, treewidth, and isomorphisms, Hybrid tractability of valued constraint problems, Constraint satisfaction with succinctly specified relations, Hybrid Tractable Classes of Constraint Problems, The Complexity of Valued CSPs, Dismantlability, connectedness, and mixing in relational structures, Quantified Constraints in Twenty Seventeen, Bounded Tree-Width and CSP-Related Problems, Counting linear extensions: parameterizations by treewidth, On singleton arc consistency for CSPs defined by monotone patterns, Tree projections and constraint optimization problems: fixed-parameter tractability and parallel algorithms, On retracts, absolute retracts, and foldings in cographs, On the complexity of existential positive queries, Algorithmic meta-theorems for restrictions of treewidth, Parameterized modal satisfiability, Tractable structures for constraint satisfaction with truth tables, On the $AC^0$ Complexity of Subgraph Isomorphism, Approximability of clausal constraints, The treewidth of proofs, Decomposing Quantified Conjunctive (or Disjunctive) Formulas, Finding vertex-surjective graph homomorphisms, Unnamed Item, Unnamed Item, A note on some collapse results of valued constraints, Causal graphs and structurally restricted planning, Unnamed Item, A note on width-parameterized SAT: an exact machine-model characterization, Unnamed Item, A polynomial relational class of binary CSP, Generalizing constraint satisfaction on trees: hybrid tractability and variable elimination, Linear min-max relation between the treewidth of an \(H\)-minor-free graph and its largest grid minor, Characterizing tractability of simple well-designed pattern trees with projection, Galois connections for patterns: an algebra of labelled graphs, Unnamed Item, New Plain-Exponential Time Classes for Graph Homomorphism, Counting Answers to Existential Questions, Uniformly Automatic Classes of Finite Structures, Counting edge-injective homomorphisms and matchings on restricted graph classes, How many variables are needed to express an existential positive query?, Tree Projections: Game Characterization and Computational Aspects, Counting induced subgraphs: a topological approach to \#W[1-hardness], Uniform Constraint Satisfaction Problems and Database Theory, The Power of Linear Programming for General-Valued CSPs, Characterising the complexity of constraint satisfaction problems defined by 2-constraint forbidden patterns, Counting Homomorphisms to $K_4$-Minor-Free Graphs, Modulo 2, Unnamed Item, Structural tractability of enumerating CSP solutions, Unnamed Item, Constructing NP-intermediate problems by blowing holes with parameters of various properties, Locally constrained homomorphisms on graphs of bounded treewidth and bounded degree, Tractability beyond \(\beta\)-acyclicity for conjunctive queries with negation and SAT, The Complexity of General-Valued Constraint Satisfaction Problems Seen from the Other Side, Broken triangles: from value merging to a tractable class of general-arity constraint satisfaction problems, New limits of treewidth-based tractability in optimization
