6 results
Filters
Settings
Now showing1 - 6 of 6
- Some of the metrics are blocked by yourconsent settings
Item type:Publication, Access status: without files , Collapsing the Bounded Width Hierarchy for Infinite-Domain Constraint Satisfaction Problems: When Symmetries Are Enough(Society for Industrial & Applied Mathematics (SIAM), 2024-12-11); ; ; We prove that relational structures admitting specific polymorphisms (namely, canonical pseudo-WNU operations of all arities n>3) have low relational width. This implies a collapse of the bounded width hierarchy for numerous classes of infinite-domain constraint satisfaction problems (CSPs) studied in the literature. Moreover, we obtain a characterization of bounded width for first-order reducts of unary structures and a characterization of Monotone Monadic SNP (MMSNP) sentences that are equivalent to a Datalog program, answering a question posed by Bienvenu et al. In particular, the bounded width hierarchy collapses in those cases as well. Our results extend the scope of theorems of Barto and Kozik characterizing bounded width for finite structures and show the applicability of infinite-domain CSPs to other fields.Publicationtype: Journal Article17 - Some of the metrics are blocked by yourconsent settings
Item type:Publication, Access status: without files , Complexity classification transfer for CSPs via algebraic products(Society for Industrial & Applied Mathematics (SIAM), 2024); ; ; ; Semanisinova, ZanetaWe study the complexity of infinite-domain constraint satisfaction problems (CSPs): our basic setting is that a complexity classification for the CSPs of first-order expansions of a structure Б can be transferred to a classification of the CSPs of first-order expansions of another structure Б. We exploit a product of structures (the algebraic product) that corresponds to the product of the respective polymorphism clones and present a complete complexity classification of the CSPs for first-order expansions of the n-fold algebraic power of (Q; <). This is proved by various algebraic and logical methods in combination with knowledge of the polymorphisms of the tractable first-order expansions of (Q; <) and explicit descriptions of the expressible relations in terms of syntactically restricted first-order formulas. By combining our classification result with general classification transfer techniques, we obtain surprisingly strong new classification results for highly relevant formalisms such as Allen's Interval Algebra, the n-dimensional Block Algebra, and the Cardinal Direction Calculus, even if higher-arity relations are allowed. Our results confirm the infinite-domain tractability conjecture for classes of structures that have been difficult to analyze with older methods. For the special case of structures with binary signatures, the results can be substantially strengthened and tightly connected to Ord-Horn formulas; this solves several longstanding open problems from the artificial intelligence (AI) literature.Publicationtype: Journal Article8 - Some of the metrics are blocked by yourconsent settings
Item type:Publication, Access status: without files , When Symmetries Are Not Enough: A Hierarchy of Hard Constraint Satisfaction ProblemsWe produce a class of ω-categorical structures with finite signature by applying a model-theoretic construction-a refinement of the Hrushovski-encoding-to ω-categorical structures in a possibly infinite signature. We show that the encoded structures retain desirable algebraic properties of the original structures, but that the constraint satisfaction problems (CSPs) associated with these structures can be badly behaved in terms of computational complexity. This method allows us to systematically generate ω-categorical templates whose CSPs are complete for a variety of complexity classes of arbitrarily high complexity and ω-categorical templates that show that membership in any given complexity class containing AC0 cannot be expressed by a set of identities on the polymorphisms. It moreover enables us to prove that recent results about the relevance of topology on polymorphism clones of ω-categorical structures also apply for CSP templates, i.e., structures in a finite language. Finally, we obtain a concrete algebraic criterion which could constitute a description of the delineation between tractability and NP-hardness in the dichotomy conjecture for first-order reducts of finitely bounded homogeneous structures.Publicationtype: Journal Article17 - Some of the metrics are blocked by yourconsent settings
Item type:Publication, Access status: without files , A proof of the algebraic tractability conjecture for monotone monadic SNPThe logic MMSNP is a restricted fragment of existential second-order logic which can express many interesting queries in graph theory and finite model theory. The logic was introduced by Feder and Vardi, who showed that every MMSNP sentence is computationally equivalent to a finite-domain constraint satisfaction problem (CSP); the involved probabilistic reductions were derandomized by Kun using explicit constructions of expander structures. We present a new proof of the reduction to finite-domain CSPs that does not rely on the results of Kun. The new universalalgebraic proof allows us to obtain a stronger statement and to verify the more general Bodirsky-Pinsker dichotomy conjecture for CSPs in MMSNP. Our approach uses the fact that every MMSNP sentence describes a finite union of CSPs for countably infinite ω-categorical structures; moreover, by a recent result of Hubička and Nešetřil, these structures can be expanded to homogeneous structures with finite relational signature and the Ramsey property.Publicationtype: Journal Article42 - Some of the metrics are blocked by yourconsent settings
Item type:Publication, Access status: without files , Mondshein sequences (A.K.A. (2; 1)-orders)(2016)Canonical orderings have been used as a key tool in graph drawing, graph encoding, and visibility representations for the last decades [H. de Fraysseix, J. Pach, and R. Pollack, Proceedings of the 20th Annual ACM Symposium on Theory of Computing (STOC '88), ACM, New York, 1988, pp. 426-433; G. Kant, Proceedings of the 33rd Annual Symposium on Foundations of Computer Science (FOCS '92), IEEE Press, Piscataway, NJ, 1992, pp. 101-110]. We study a far-reaching generalization of canonical orderings to nonplanar graphs that was published by Lee Mondshein in a Ph.D. thesis as early as 1971. Mondshein proposed to order the vertices of a graph in a sequence such that for any i, the vertices from 1 to i essentially induce a 2-connected graph, while the remaining vertices from i+1 to n induce a connected graph. Mondshein's sequence generalizes canonical orderings and later became independently known as nonseparating ear decomposition. Surprisingly, this fundamental link between canonical orderings and nonseparating ear decomposition had not been previously established. Currently, the fastest known algorithm for computing a Mondshein sequence achieves a running time of O(nm); the main open problem in Mondshein's and follow-up work is to improve this running time to subquadratic time. After putting Mondshein's work into context, we present an algorithm that computes a Mondshein sequence in optimal time and space O(m). This improves the previous best running time by a factor of n. We illustrate the impact of this result by deducing linear-time algorithms for five other problems-in four of these, the previous best running time was quadratic. In particular, we show how to compute three independent spanning trees in a 3-connected graph in time O(m), improving a result of Cheriyan and Maheshwari [J. Algorithms, 9 (1988), pp. 507-537]; improve the preprocessing time from O(n2) to O(m) for the output-sensitive data structure of Di Battista, Tamassia, and Vismara [Algorithmica, 23 (1999), pp. 302-340] that reports three internally disjoint paths between any given vertex pair; derive a very simple O(n)-time planarity test once a Mondshein sequence is computed; compute a nested family of contractible subgraphs of 3-connected graphs in time O(m); and compute a 3-partition in time O(m) (the previous best running time is O(n2) due to Suzuki et al. [Information Processing Society of Japan (IPSJ), 31 (1990), pp. 584-592 (in Japanese)]).Publicationtype: Journal Article67 - Some of the metrics are blocked by yourconsent settings
Item type:Publication, Access status: without files , Contractions, removals, and certifying 3-connectivity in line AR timeOne of the most noted construction methods of 3-vertex-connected graphs is due to Tutte and is based on the following fact: Any 3-vertex-connected graph G = (V, E) on more than 4 vertices contains a contractible edge, i.e., an edge whose contraction generates a 3-connected graph. This implies the existence of a sequence of edge contractions from G to the complete graph K4, such that every intermediate graph is 3-vertex-connected. A theorem of Barnette and Grünbaum gives a similar sequence using removals on edges instead of contractions. We show how to compute both sequences in optimal time, improving the previously best known running times of O(|V|2) to O(|E|). This result has a number of consequences; an important one is a new linear-time test of 3-connectivity that is certifying; finding such an algorithm has been a major open problem in the design of certifying algorithms in recent years. The test is conceptually different from well-known linear-time 3-connectivity tests and uses a certificate that is easy to verify in time O(|E|). We show how to extend the results to an optimal certifying test of 3-edge-connectivity. © 2013 Society for Industrial and Applied Mathematics.Publicationtype: Journal Article48