Constraint composite graph

Last updated

The constraint composite graph is a node-weighted undirected graph associated with a given combinatorial optimization problem posed as a weighted constraint satisfaction problem. Developed and introduced by Satish Kumar Thittamaranahalli (T. K. Satish Kumar), the idea of the constraint composite graph is a big step towards unifying different approaches for exploiting "structure" in weighted constraint satisfaction problems. [1] [2]

A weighted constraint satisfaction problem (WCSP) is a generalization of a constraint satisfaction problem in which the constraints are no longer "hard," but are extended to specify non-negative costs associated with the tuples. The goal is then to find an assignment of values to all the variables from their respective domains so that the total cost is minimized. Weighted constraint satisfaction problems find innumerable applications in artificial intelligence and computer science. They are also variously referred to as markov random fields (in statistics and signal processing) and energy minimization problems (in physics).

While weighted constraint satisfaction problems are NP-hard to solve in general, several subclasses can be solved in polynomial time when their weighted constraints exhibit specific kinds of numerical structure. Tractable subclasses can also be identified by analyzing the way constraints are placed over the variables. Specifically, a weighted constraint satisfaction problem can be solved in time exponential only in the treewidth of its variable-interaction graph (constraint network). However, a major drawback of the constraint network is that it does not provide a computational framework for leveraging the numerical structure of the weighted constraints.

Unlike the constraint network, the constraint composite graph provides a unifying framework for representing both the graphical structure of the variable-interactions as well as the numerical structure of the weighted constraints. It can be constructed using a simple polynomial-time procedure; and a given weighted constraint satisfaction problem is reducible to the problem of computing the minimum weighted vertex cover for its associated constraint composite graph. The "hybrid" computational properties of the constraint composite graph are reflected in the following two important results:

(Result 1) The constraint composite graph of a given weighted constraint satisfaction problem has the same treewidth as its associated constraint network.

(Result 2) Many subclasses of weighted constraint satisfaction problems that are tractable by virtue of the numerical structure of their weighted constraints have associated constraint composite graphs that are bipartite in nature.

Result 1 shows that the constraint composite graph can be used to capture the graphical structure of the variable-interactions (since a minimum weighted vertex cover for any graph can be computed in time exponential only in the treewidth of that graph). Result 2 shows that the constraint composite graph can also be used to capture the numerical structure of the weighted constraints (since a minimum weighted vertex cover can be computed in polynomial time for bipartite graphs).

Empirically, when solving a WCSP, it has been shown that it is more advantageous to apply message passing algorithms and integer linear programming on the WCSP's constraint composite graph than on the WCSP directly. [3] [4]

Related Research Articles

The assignment problem is a fundamental combinatorial optimization problem. In its most general form, the problem is as follows:

Constraint satisfaction problems (CSPs) are mathematical questions defined as a set of objects whose state must satisfy a number of constraints or limitations. CSPs represent the entities in a problem as a homogeneous collection of finite constraints over variables, which is solved by constraint satisfaction methods. CSPs are the subject of intense research in both artificial intelligence and operations research, since the regularity in their formulation provides a common basis to analyze and solve problems of many seemingly unrelated families. CSPs often exhibit high complexity, requiring a combination of heuristics and combinatorial search methods to be solved in a reasonable time. Constraint Programming (CP) is the field of research that specifically focuses on tackling these kinds of problems. Additionally, boolean satisfiability problem (SAT), the satisfiability modulo theories (SMT), mixed integer programming (MIP) and answer set programming (ASP) are all fields of research focusing on the resolution of particular forms of the constraint satisfaction problem. Do not confuse with Communicating sequential processes (CSP).

Vertex cover Set of vertices that includes at least one endpoint of every edge in a graph

In the mathematical discipline of graph theory, a vertex cover of a graph is a set of vertices that includes at least one endpoint of every edge of the graph. The problem of finding a minimum vertex cover is a classical optimization problem in computer science and is a typical example of an NP-hard optimization problem that has an approximation algorithm. Its decision version, the vertex cover problem, was one of Karp's 21 NP-complete problems and is therefore a classical NP-complete problem in computational complexity theory. Furthermore, the vertex cover problem is fixed-parameter tractable and a central problem in parameterized complexity theory.

In the mathematical discipline of graph theory, a matching or independent edge set in an undirected graph is a set of edges without common vertices. Finding a matching in a bipartite graph can be treated as a network flow problem.

Graph homomorphism

In the mathematical field of graph theory, a graph homomorphism is a mapping between two graphs that respects their structure. More concretely, it is a function between the vertex sets of two graphs that maps adjacent vertices to adjacent vertices.

In graph theory, the metric dimension of a graph G is the minimum cardinality of a subset S of vertices such that all other vertices are uniquely determined by their distances to the vertices in S. Finding the metric dimension of a graph is an NP-hard problem; the decision version, determining whether the metric dimension is less than a given value, is NP-complete.

In graph theory, a cut is a partition of the vertices of a graph into two disjoint subsets. Any cut determines a cut-set, the set of edges that have one endpoint in each subset of the partition. These edges are said to cross the cut. In a connected graph, each cut-set determines a unique cut, and in some cases cuts are identified with their cut-sets rather than with their vertex partitions.

The complexity of constraint satisfaction is the application of computational complexity theory on constraint satisfaction. It has mainly been studied for discriminating between tractable and intractable classes of constraint satisfaction problems on finite domains.

In constraint satisfaction, a decomposition method translates a constraint satisfaction problem into another constraint satisfaction problem that is binary and acyclic. Decomposition methods work by grouping variables into sets, and solving a subproblem for each set. These translations are done because solving binary acyclic problems is a tractable problem.

In graph theory, a path decomposition of a graph G is, informally, a representation of G as a "thickened" path graph, and the pathwidth of G is a number that measures how much the path was thickened to form G. More formally, a path-decomposition is a sequence of subsets of vertices of G such that the endpoints of each edge appear in one of the subsets and such that each vertex appears in a contiguous subsequence of the subsets, and the pathwidth is one less than the size of the largest set in such a decomposition. Pathwidth is also known as interval thickness, vertex separation number, or node searching number.

Grundy number

In graph theory, the Grundy number or Grundy chromatic number of an undirected graph is the maximum number of colors that can be used by a greedy coloring strategy that considers the vertices of the graph in sequence and assigns each vertex its first available color, using a vertex ordering chosen to use as many colors as possible. Grundy numbers are named after P. M. Grundy, who studied an analogous concept for directed graphs in 1939. The undirected version was introduced by Christen & Selkow (1979).

In computer science, a holographic algorithm is an algorithm that uses a holographic reduction. A holographic reduction is a constant-time reduction that maps solution fragments many-to-many such that the sum of the solution fragments remains unchanged. These concepts were introduced by Leslie Valiant, who called them holographic because "their effect can be viewed as that of producing interference patterns among the solution fragments". The algorithms are unrelated to laser holography, except metaphorically. Their power comes from the mutual cancellation of many contributions to a sum, analogous to the interference patterns in a hologram.

Clique-width

In graph theory, the clique-width of a graph is a parameter that describes the structural complexity of the graph; it is closely related to treewidth, but unlike treewidth it can be bounded even for dense graphs. It is defined as the minimum number of labels needed to construct by means of the following 4 operations :

  1. Creation of a new vertex v with label i
  2. Disjoint union of two labeled graphs G and H
  3. Joining by an edge every vertex labeled i to every vertex labeled j, where
  4. Renaming label i to label j

In graph theory and theoretical computer science, the longest path problem is the problem of finding a simple path of maximum length in a given graph. A path is called simple if it does not have any repeated vertices; the length of a path may either be measured by its number of edges, or by the sum of the weights of its edges. In contrast to the shortest path problem, which can be solved in polynomial time in graphs without negative-weight cycles, the longest path problem is NP-hard and the decision version of the problem, which asks whether a path exists of at least some given length, is NP-complete. This means that the decision problem cannot be solved in polynomial time for arbitrary graphs unless P = NP. Stronger hardness results are also known showing that it is difficult to approximate. However, it has a linear time solution for directed acyclic graphs, which has important applications in finding the critical path in scheduling problems.

In graph theory, an area of mathematics, an equitable coloring is an assignment of colors to the vertices of an undirected graph, in such a way that

In graph theory, the tree-depth of a connected undirected graph G is a numerical invariant of G, the minimum height of a Trémaux tree for a supergraph of G. This invariant and its close relatives have gone under many different names in the literature, including vertex ranking number, ordered chromatic number, and minimum elimination tree height; it is also closely related to the cycle rank of directed graphs and the star height of regular languages. Intuitively, where the treewidth graph width parameter measures how far a graph is from being a tree, this parameter measures how far a graph is from being a star.

In computational complexity theory, the exponential time hypothesis is an unproven computational hardness assumption that was formulated by Impagliazzo & Paturi (1999). The hypothesis states that 3-SAT cannot be solved in subexponential time in the worst case. The exponential time hypothesis, if true, would imply that P ≠ NP, but it is a stronger statement. It can be used to show that many computational problems are equivalent in complexity, in the sense that if one of them has a subexponential time algorithm then they all do.

In the study of graph algorithms, Courcelle's theorem is the statement that every graph property definable in the monadic second-order logic of graphs can be decided in linear time on graphs of bounded treewidth. The result was first proved by Bruno Courcelle in 1990 and independently rediscovered by Borie, Parker & Tovey (1992). It is considered the archetype of algorithmic meta-theorems.

In the mathematical fields of graph theory and finite model theory, the logic of graphs deals with formal specifications of graph properties using formulas of mathematical logic. There are several variations in the types of logical operation that can be used in these formulas. The first order logic of graphs concerns formulas in which the variables and predicates concern individual vertices and edges of a graph, while monadic second order graph logic allows quantification over sets of vertices or edges. Logics based on least fixed point operators allow more general predicates over tuples of vertices, but these predicates can only be constructed through fixed-point operators, restricting their power to an intermediate level between first order and monadic second order.

Odd cycle transversal

In graph theory, an odd cycle transversal of an undirected graph is a set of vertices of the graph that has a nonempty intersection with every odd cycle in the graph. Removing the vertices of an odd cycle transversal from a graph leaves a bipartite graph as the remaining induced subgraph.

References

  1. ↑ Kumar, T.K.S. (2008). "A Framework for Hybrid Tractability Results in Boolean Weighted Constraint Satisfaction Problems". Proceedings of the Fourteenth International Conference on Principles and Practice of Constraint Programming (CP). Lecture Notes in Computer Science book series. 5202. pp. 282–297. doi:10.1007/978-3-540-85958-1_19. ISBN   978-3-540-85958-1.
  2. ↑ Kumar, T.K.S. (2008). "Lifting Techniques for Weighted Constraint Satisfaction Problems" (PDF). Proceedings of the Tenth International Symposium on Artificial Intelligence and Mathematics (ISAIM'2008).
  3. ↑ Xu, Hong; Kumar, T. K. Satish; Koenig, Sven (2017). "The Nemhauser-Trotter reduction and lifted message passing for the weighted CSP". Proceedings of the 14th International Conference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming (CPAIOR). Lecture Notes in Computer Science book series. 10335. Springer. pp. 387–402. doi:10.1007/978-3-319-59776-8_31. ISBN   978-3-319-59776-8.
  4. ↑ Xu, Hong; Koenig, Sven; Kumar, T. K. Satish (2017). "A constraint composite graph-based ILP encoding of the Boolean weighted CSP". Proceedings of the 23rd International Conference on Principles and Practice of Constraint Programming (CP). Lecture Notes in Computer Science book series. 10416. Springer. pp. 630–8. doi:10.1007/978-3-319-66158-2_40. ISBN   978-3-319-66158-2.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.