arrow-up icon

This website uses cookies to improve your user experience on this site. By continuing to view this site, you agree to our group's privacy policy decoration.

14 NP problems in A. Lucas (2014)

Fixstars Amplify is used to solve the 14 NP problems presented in the paper, A. Lucas, Front. Phys. (2014).

graphical divider
Image
Tutorials (applied)

1. Graph Partitioning Problem

Difficulty level decoration decoration decoration decoration decoration

In this tutorial, we will partition a graph into two sets with the same number of vertices so that we minimize the number of edges connecting two points belonging to different sets.

Sample code
Image
Tutorials (applied)

2. Maximum Clique Problem

Difficulty level decoration decoration decoration decoration decoration

For a given graph, we find the subset of vertices that has the most significant number of vertices where an edge connects any two vertices in the subset.

Sample code
Image
Tutorials (applied)

3. Exact Cover Problem

Difficulty level decoration decoration decoration decoration decoration

Suppose we have a set and are given several subsets of that set. In the exact cover problem, we choose subsets so that precisely one of the selected subsets contains any element of the set.

Sample code
Image
Tutorials (applied)

4. Set Packing Problem

Difficulty level decoration decoration decoration decoration decoration

Suppose we have a set and are given several subsets of the set. In the set packing problem, we choose the subsets that have no common part so that the number of elements in the chosen subset is maximized.

Sample code
Image
Tutorials (applied)

5. Minimum Vertex Cover Problem

Difficulty level decoration decoration decoration decoration decoration

A vertex cover is a subset of the vertices of a graph such that every edge of the graph is connected to a vertex of this subset. The minimum vertex cover problem finds the vertex cover with the fewest elements.

Sample code
Image
Tutorials (applied)

6. Satisfiability Problem (SAT)

Difficulty level decoration decoration decoration decoration decoration

Given a single Boolean formula, it may be possible to make the value of the formula true by successfully determining the values of the variables in it. The satisfiability problem determines this, and we will solve a problem called 3-SAT.

Sample code
Image
Tutorials (applied)

7. Minimum Maximum Matching Problem

Difficulty level decoration decoration decoration decoration decoration

In this tutorial, we will find a subset of the edges of a given graph where the edges in the subset are not adjacent to each other, and the edges not in the subset are always adjacent to the edges in the subset, with the fewest elements.

Sample code
Image
Tutorials (applied)

8. Graph Coloring Problem

Difficulty level decoration decoration decoration decoration decoration

The graph coloring problem involves coloring the vertices of a graph with a given number of colors and determining whether or not the vertices connected by edges can be colored with different colors.

Sample code
Image
Tutorials (applied)

9. Clique Cover Problem

Difficulty level decoration decoration decoration decoration decoration

Given a graph and a certain number of colors, the clique cover problem is the problem of determining whether it is possible to paint the vertices of the graph so that edges connect all pairs of vertices of the same color.

Sample code
Image
Tutorials (applied)

10. Job Sequencing Problem

Difficulty level decoration decoration decoration decoration decoration

Suppose you have several jobs and machines, and you know how long each job will take. You assign each job to one of the machines. The job scheduling problem asks how to assign the jobs to complete all jobs as quickly as possible.

Sample code
Image
Tutorials (applied)

11. Hamiltonian Cycle Problem

Difficulty level decoration decoration decoration decoration decoration

For a given graph, a closed path that passes through all graph vertices once and returns to its origin is called a Hamiltonian cycle, and in general, for large graphs, it is difficult to determine whether such a path exists.

Sample code
Image
Tutorials (applied)

12. Directed Feedback Vertex Set Problem

Difficulty level decoration decoration decoration decoration decoration

Given a directed graph, a directed feedback vertex set is a subset of graph vertices such that the closed path of any graph passes through at least one vertex in the subset. The directed feedback vertex set problem seeks to find a set with the fewest elements.

Sample code
Image
Tutorials (applied)

13. Minimum Feedback Edge Set Problem

Difficulty level decoration decoration decoration decoration decoration

Given a directed graph, a feedback edge set is a subset of graph edges where every closed path contains at least one edge in this subset. The minimum feedback edge set problem searches for a feedback edge set with the fewest elements.

Sample code
Image
Tutorials (applied)

14. Graph Isomorphism Problem

Difficulty level decoration decoration decoration decoration decoration

Two given graphs are said to be isomorphic if there is a one-to-one correspondence between their vertices and if the two corresponding vertices are both connected by an edge. It is generally challenging to determine isomorphism, but this example program tackles this problem.

Sample code

See the list of Live Demo