Skip to main content
OverflowAI is here! AI power for your Stack Overflow for Teams knowledge community. Learn more
11 votes

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", "...
Pål GD's user avatar
  • 16.4k
9 votes

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 ...
D.W.'s user avatar
  • 160k
3 votes
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)$ ...
Smylic's user avatar
  • 225
3 votes
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 ...
D.W.'s user avatar
  • 160k
2 votes
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 ...
D.W.'s user avatar
  • 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 ...
D.W.'s user avatar
  • 160k

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