# Tag Info

### Why are search problems assumed to have the structure of "find a path in a graph"?

You are completely right: The problems we call search problems are typically problems that can be modeled as a graph problem. The general gist of it is that there are "states", "...
• 16.4k

### Why are search problems assumed to have the structure of "find a path in a graph"?

There are at least two meanings of the word "search problem". In one context, we use the phrase "search problem" to refer to searching for paths in a graph, or making a sequence of ...
• 160k
Accepted

### Number of graphs that almost contain a $k$-clique

It is easy to see that for $k = 2$ the only graph almost containing $k$-clique is an empty graph $nK_1$. I don't have a proof, but I guess, that $\#G(n, 3)$ is exponential. Also the number $\#G(n, 3)$ ...
• 225
Accepted

### How to solve a system of XOR equations in a cyclic graph?

You can express this as an instance of XOR-SAT, then find a solution using Gaussian elimination. I am assuming that each value $1,2,3,$ represents a bit-vector of some appropriate length, and you are ...
• 160k
Accepted

### Pseudo-Traveling Salesman on a colored graph

The problem is NP-hard. If each node has its own unique color, then you are asking for a solution to the Traveling Salesman Problem, which is NP-hard. Therefore, you should not expect any efficient ...
• 160k
1 vote

### Global optimization of state assignments in a directed graph with a tree-based distance cost

One approach is to use the big guns, i.e., a SAT solver or ILP (integer linear programming) solver. You could implement both and see if either is satisfactory for problems of the size you are dealing ...
• 160k

Only top scored, non community-wiki answers of a minimum length are eligible