Search

In this work, we first study a natural generalisation of the Min-Cut problem, where a graph is augmented by a superadditive set function defined on its vertex subsets. The goal is to select a vertex subset such that the weight of the induced cut plus the set function value are minimised. In addition, a lower and upper bound is imposed on the solution size. We present a polynomial-time algorithm for enumerating all near-optimal solutions of this Bounded Generalised Min-Cut problem. Second, we apply this novel algorithm to surjective general-valued constraint satisfaction problems (VCSPs), i.e., VCSPs in which each label has to be used at least once. On the Boolean domain, Fulla, Uppman, and Živný (ACM ToCT'18) have recently established a complete classification of surjective VCSPs based on an unbounded version of the Generalised Min-Cut problem. Their result features the discovery of a new non-trivial tractable case called EDS that does not appear in the non-surjective setting. As our main result, we extend the class EDS to arbitrary finite domains and provide a conditional complexity classification for surjective VCSPs of this type based on a reduction to smaller domains. On three-element domains, this leads to a complete classification of such VCSPs. [ABSTRACT FROM AUTHOR]

Random constraint satisfaction problems exhibit several phase transitions when their density of constraints is varied. One of these threshold phenomena, known as the clustering or dynamic transition, corresponds to a transition for an information theoretic problem called tree reconstruction. In this article we study this threshold for two CSPs, namely the bicoloring of k-uniform hypergraphs with a density α of constraints, and the q-coloring of random graphs with average degree c. We show that in the large k, q limit the clustering transition occurs for α = 2 k - 1 k (ln k + ln ln k + γ d + o (1)) , c = q (ln q + ln ln q + γ d + o (1)) , where γ d is the same constant for both models. We characterize γ d via a functional equation, solve the latter numerically to estimate γ d ≈ 0.871 , and obtain an analytic lowerbound γ d ≥ 1 + ln (2 (2 - 1)) ≈ 0.812 . Our analysis unveils a subtle interplay of the clustering transition with the rigidity (naive reconstruction) threshold that occurs on the same asymptotic scale at γ r = 1 . [ABSTRACT FROM AUTHOR]

Finding a solution to a Constraint Satisfaction Problem (CSP) is known to be an NP-hard task. This has motivatedthe multitude of works that have been devoted to developing techniques that simplify CSP instances before or duringtheir resolution.The present work proposes rigidly enforced schemes for simplifying binary CSPs that allow the narrowing of valuedomains, either via value merging or via value suppression. The proposed schemes can be viewed as parametrizedgeneralizations of two widely studied CSP simplification techniques, namely, value merging and neighbourhoodsubstitutability. Besides, we show that both schemes may be strengthened in order to allow variable elimination,which may result in more significant simplifications. This work contributes also to the theory of tractable CSPs byidentifying a new tractable class of binary CSP.

An important tool in the study of the complexity of Constraint Satisfaction Problems (CSPs) is the notion of a relational clone, which is the set of all relations expressible using primitive positive formulas over a particular set of base relations. Post's lattice gives a complete classification of all Boolean relational clones, and this has been used to classify the computational difficulty of CSPs. Motivated by a desire to understand the computational complexity of (weighted) counting CSPs, we develop an analogous notion of functional clones and study the landscape of these clones. One of these clones is the collection of log-supermodular (lsm) functions, which turns out to play a significant role in classifying counting CSPs. In the conservative case (where all nonnegative unary functions are available), we show that there are no functional clones lying strictly between the clone of lsm functions and the total clone (containing all functions). Thus, any counting CSP that contains a single nontrivial non-lsm function is computationally as hard to approximate as any problem in #P. Furthermore, we show that any nontrivial functional clone (in a sense that will be made precise) contains the binary function "implies". As a consequence, in the conservative case, all nontrivial counting CSPs are as hard to approximate as #BIS, the problem of counting independent sets in a bipartite graph. Given the complexity-theoretic results, it is natural to ask whether the "implies" clone is equivalent to the clone of lsm functions. We use the Möbius transform and the Fourier transform to show that these clones coincide precisely up to arity 3. It is an intriguing open question whether the lsm clone is finitely generated. Finally, we investigate functional clones in which only restricted classes of unary functions are available. [ABSTRACT FROM AUTHOR]

Holant problems are a general framework to study counting problems. Both counting constraint satisfaction problems (#CSP) and graph homomorphisms are special cases. We prove a complexity dichotomy theorem for Holant ∗ (F) , where F is a set of constraint functions on Boolean variables and taking complex values. The constraint functions need not be symmetric functions. We identify four classes of problems which are polynomial time computable; all other problems are proved to be #P-hard. The main proof technique and indeed the formulation of the theorem use holographic algorithms and reductions. By considering these counting problems with the broader scope that allows complex-valued constraint functions, we discover surprising new tractable classes, which are associated with isotropic vectors, i.e., a (non-zero) vector whose dot product with itself is zero. [ABSTRACT FROM AUTHOR]

We continue the investigation of polynomial-time sparsification for NP-complete Boolean Constraint Satisfaction Problems (CSPs). The goal in sparsification is to reduce the number of constraints in a problem instance without changing the answer, such that a bound on the number of resulting constraints can be given in terms of the number of variables n. We investigate how the worst-case sparsification size depends on the types of constraints allowed in the problem formulation—the constraint language—and identify constraint languages giving the best-possible and worst-possible behavior for worst-case sparsifiability. Two algorithmic results are presented. The first result essentially shows that for any arity k, the only constraint type for which no nontrivial sparsification is possible has exactly one falsifying assignment, and corresponds to logical OR (up to negations). Our second result concerns linear sparsification, that is, a reduction to an equivalent instance with O (n) constraints. Using linear algebra over rings of integers modulo prime powers, we give an elegant necessary and sufficient condition for a constraint type to be captured by a degree-1 polynomial over such a ring, which yields linear sparsifications. The combination of these algorithmic results allows us to prove two characterizations that capture the optimal sparsification sizes for a range of Boolean CSPs. For NP-complete Boolean CSPs whose constraints are symmetric (the satisfaction depends only on the number of 1 values in the assignment, not on their positions), we give a complete characterization of which constraint languages allow for a linear sparsification. For Boolean CSPs in which every constraint has arity at most three, we characterize the optimal size of sparsifications in terms of the largest OR that can be expressed by the constraint language. [ABSTRACT FROM AUTHOR]

We show a computational complexity dichotomy theorem for symmetric complex-weighted Boolean #CSP when the constraint graph of the input must be planar. The problems that are #P-hard over general graphs but tractable over planar graphs are precisely those with a holographic reduction to matchgates. We also obtain a dichotomy theorem for a symmetric arity 4 signature with complex weights in the planar Holant framework, which we use in the proof of our #CSP dichotomy. [ABSTRACT FROM AUTHOR]

A cut varepsilon-sparsifier of a weighted graph G is a reweighted subgraph of G of (quasi)linear size that preserves the size of all cuts up to a multiplicative factor of varepsilon. Since their introduction by Benczur and Karger [Approximating s-t minimum cuts in O~ (n2) time, in Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing (STOC96), 1996, pp. 47-55], cut sparsifiers have proved extremely influential and found various applications. Going beyond cut sparsifiers, Filtser and Krauthgamer [SIAM J. Discrete Math., 31 (2017), pp. 1263--1276] gave a precise classification of which binary Boolean CSPs are sparsifiable. In this paper, we extend their result to binary CSPs on arbitrary finite domains. [ABSTRACT FROM AUTHOR]

Finding a solution to a Constraint Satisfaction Problem (CSP) is known to be an NP-hard task. This has motivated the multitude of works that have been devoted to developing techniques that simplify CSP instances before or during their resolution. The present work proposes rigidly enforced schemes for simplifying binary CSPs that allow the narrowing of value domains, either via value merging or via value suppression. The proposed schemes can be viewed as parametrized generalizations of two widely studied CSP simplification techniques, namely, value merging and neighbourhood substitutability. Besides, we show that both schemes may be strengthened in order to allow variable elimination, which may result in more significant simplifications. This work contributes also to the theory of tractable CSPs by identifying new tractable classes of binary CSP. [ABSTRACT FROM AUTHOR]

This paper proposes an algorithm to reason on constraints expressed in terms of polynomials with integer coefficients whose variables take values from finite subsets of the integers. The proposed algorithm assumes that an initial approximation of the domains of variables is available in terms of a bounding box, and it recursively subdivides the box into disjoint boxes until a termination condition is met. The algorithm includes three termination conditions that allow using it for three related reasoning tasks: constraint satisfaction, enumeration of solutions, and hyper-arc consistency enforcement. Considered termination conditions are based on suitable lower and upper bounds for polynomial functions over boxes that are determined using new results proved in the paper. The algorithm is particularly appropriate to reason on high-degree polynomial constraints because the proposed method to determine lower and upper bounds can outperform alternative methods when high-degree polynomials in a moderate number of variables are considered. [ABSTRACT FROM AUTHOR]

In this paper, we propose an improved filtering algorithm for regular constraint, which demand that the sequence of all assignments for variables can be accepted by a Deterministic Finite Automaton (DFA) or a regular language. Regular constraint is a type of global constraint in Constraint Satisfaction Problems (CSPs) and a natural expression of deterministic patterns in planning and decision making, and it utilizes the properties of DFA to pre-specify the optional paths for multiple variables. Thus, it is sensible to improve the filtering algorithm that enforces Generalized Arc Consistency (GAC) for regular constraint in order to minimize memory and time consumption. With the goal in mind, we encode DFA using bit vectors and then devise a bit operations algorithm to maintain the domain consistency for regular constraint. Lastly, we carry out an experiment to compare to the state-of-the-art filtering algorithm. The experimental results demonstrates that the proposed algorithm significantly improves both memory and time. • The improved filtering algorithm improves efficiency for regular constraints. • Our filtering algorithm uses a large number of bit operations. • The proposed algorithm maintains generalized arc consistency. • The experimental results show that our algorithm provides a significant improvement. [ABSTRACT FROM AUTHOR]

For n ≥ 3, let (Hn, E) denote the nth Henson graph, i.e., the unique countable homogeneous graph with exactly those finite graphs as induced subgraphs that do not embed the complete graph on n vertices. We show that for all structures Γ with domain Hn whose relations are first-order definable in (Hn, E) the constraint satisfaction problem for Γ either is in P or is NP-complete. We moreover show a similar complexity dichotomy for all structures whose relations are first-order definable in a homogeneous graph whose reflexive closure is an equivalence relation. Together with earlier results, in particular for the random graph, this completes the complexity classification of constraint satisfaction problems of structures first-order definable in countably infinite homogeneous graphs: all such problems are either in P or NP-complete. [ABSTRACT FROM AUTHOR]

This paper focuses on the control of a cooperative system composed of an Unmanned Aerial Vehicle (UAV) and an Unmanned Ground Vehicle (UGV) manipulating an object. The two units are subject to input saturations and collaborate to move the object to a desired pose characterized by its position and inclination. The dynamics are derived using the Euler–Lagrange method. A stabilizing control law is proposed where the UGV is tasked to deploy the object to a certain position whereas the UAV adjusts its inclination. In particular, a proportional–derivative control law is proposed for the UGV, and a cascade control is used for the UAV, where the inner loop controls the attitude of the UAV and the outer loop stabilizes the inclination of the object. The stability of the points of equilibrium is proven using small gain arguments. To ensure constraints satisfaction at all times, a reference governor unit is added to this stabilizing control law. Simulations and experimental results are provided to validate the effectiveness of the proposed control scheme. [ABSTRACT FROM AUTHOR]

For each finite relational structure A, let CSP(\bfA) denote the CSP instances whose constraint relations are taken from A. The resulting family of problems CSP(A) has been considered heavily in a variety of computational contexts. In this article, we consider this family from the perspective of property testing: given a CSP instance and query access to an assignment, one wants to decide whether the assignment satisfies the instance or is far from doing so. While previous work on this scenario studied concrete templates or restricted classes of structures, this article presents a comprehensive classification theorem. Our main contribution is a dichotomy theorem completely characterizing the finite structures A such that CSP(A) is constant-query testable: (i) If A has a majority polymorphism and a Maltsev polymorphism, then CSP(A) is constant-query testable with one-sided error. (ii) Otherwise, testing CSP(A) requires a superconstant number of queries. [ABSTRACT FROM AUTHOR]

We carry out a detailed analysis of the effects of different dynamic variable and value ordering heuristics on the search space of Sudoku when the encoding method and the filtering algorithm are fixed. Our study starts by examining lexicographical variable and value ordering and evaluates different combinations of dynamic variable and value ordering heuristics. We eventually build up to a dynamic variable ordering heuristic that has two rounds of tie-breakers, where the second tie-breaker is a dynamic value ordering heuristic. We show that our method that uses this interlinked heuristic outperforms the previously studied ones with the same experimental setup. Overall, we conclude that constructing insightful dynamic variable ordering heuristics that also utilize a dynamic value ordering heuristic in their decision making process could improve the search effort for some NP-Complete problems. [ABSTRACT FROM AUTHOR]

Over the last decade, developments in unmanned aerial vehicles (UAVs) has greatly increased, and they are being used in many fields including surveillance, crisis management or automated mission planning. This last field implies the search of plans for missions with multiple tasks, UAVs and ground control stations; and the optimization of several objectives, including makespan, fuel consumption or cost, among others. In this work, this problem has been solved using a multi-objective evolutionary algorithm combined with a constraint satisfaction problem model, which is used in the fitness function of the algorithm. The algorithm has been tested on several missions of increasing complexity, and the computational complexity of the different element considered in the missions has been studied. [ABSTRACT FROM AUTHOR]

The prefrontal cortex (PFC) plays an important role in complex cognitive computations, including planning and decision making. Although recurrent spiking neural network (SNN) software models of PFC have been successful in reproducing many of its cognitive computational aspects, little attention has been devoted to the question of how such systems can perform with low-resolution parameters and be robust to noise and variability in their input signals and state variables. Here, we present a mixed-signal analog/digital neuromorphic implementation of a state-dependent SNN architecture that addresses these issues by construction. The network relies on synaptic dis-inhibition to ensure robust decision making even in the face of very large variability. Depending on its connectivity, the network can either perform robustly in a deterministic way or exploit the device mismatch and noise to explore stochastically multiple states in constraint satisfaction problems (CSPs). We validate the architecture by mapping it onto a network of spiking neurons in a multi-core mixed-signal neuromorphic system and presenting experimental results for three different examples of CSPs. [ABSTRACT FROM AUTHOR]

Singleton arc consistency is an important type of local consistency which has been recently shown to solve all constraint satisfaction problems (CSPs) over constraint languages of bounded width. We aim to characterise all classes of CSPs defined by a forbidden pattern that are solved by singleton arc consistency and closed under removing constraints. We identify five new patterns whose absence ensures solvability by singleton arc consistency, four of which are provably maximal and three of which generalise 2-SAT. Combined with simple counter-examples for other patterns, we make significant progress towards a complete classification. [ABSTRACT FROM AUTHOR]

The applicability of different selection methods for power systems on board ships is highly dependent on the number of options possible. With the introduction of new technologies in the maritime sector, this number is increasing. However, its exact value, or even its order of magnitude is still unknown. This article shows the complexity of modern on-board power system by quantifying the number of possible system configurations currently available. A constraint satisfaction algorithm generates different configurations and the results are supported by combinatorics principles. The set of constraints used led to a significant reduction in the design space, and the influence of each of the constraints is investigated independently. Traditional mechanical propulsion is present in less than 1% of the generated configurations, whereas electric and hybrid propulsion are dominant. In particular, the impact of energy storage on the size of the design space is made evident. The order of magnitude of the total number of configurations obtained supports the use of modern selection methods instead of ones based on expert intuition and past experience. The presented work offers a tool to determine and restrict the size of the design space. It can therefore be integrated into existing selection methods and is a starting point for the development of new ones. [ABSTRACT FROM AUTHOR]

Abstract The loss of coolant accident (LOCA) of a nuclear power plant (NPP) is a severe accident in the nuclear energy industry. Nowadays, neural networks have been trained on nuclear simulation transient datasets to detect LOCA. This paper proposes a constraint-based genetic algorithm (GA) to find optimised 2-hidden layer network architectures for detecting LOCA of a NPP. The GA uses a proposed constraint satisfaction algorithm called random walk heuristic to create an initial population of neural network architectures of high performance. At each generation, the GA population is split into a sub-population of feature subsets and a sub-population of 2-hidden layer architectures to breed offspring from each sub-population independently in order to generate a wide variety of network architectures. During breeding 2-hidden layer architectures, a constraint-based nearest neighbor search algorithm is proposed to find the nearest neighbors of the offspring population generated by mutation. The results showed that for LOCA detection, the GA-optimised network outperformed a random search, an exhaustive search and a RBF kernel support vector regression (SVR) in terms of generalization performance. For the skillcraft dataset of the UCI machine learning repository, the GA-optimised network has a similar performance to the RBF kernel SVR and outperformed the other approaches. [ABSTRACT FROM AUTHOR]