Is this finite graph problem decidable? What factors make a problem decidable?

Question

I want to know if the following problem is decidable and how to find out. Every problem I see I can say "yes" or "no" to it, so are most problems and algorithms decidable except a few (which is provided here)?

Input: A directed and finite graph $G$, with $v$ and $u$ as vertices
Question: Does a path in $G$ with $u$ as initial vertex and $v$ as final vertex exist?

Answer 1

Any problem that requires only examining a finite amount of data is decidable, because there is an algorithm that consists of enumerating all the potential solutions. It may be ridiculously slow, but that's not relevant: if there is an algorithm, it's decidable.

The problem you state assumes a finite graph, which strongly hints that it's decidable. Strictly speaking, you need to look a bit further. The problem is a property on the paths in the graph, and there is sometimes an infinite number of paths, when the graph contains a cycle (you can loop around this cycle as many times as you like). However, it's easy to turn the problem to a finite problem: if there is any path beginning with $u$ and ending with $v$ that includes a cycle, then you can cut out all the cycles in that path, and you have a new solution which does not include a cycle. Since there is a finite number of paths that do not involve a cycle (if the graph has $k$ edges, there are at most $k!$ paths that do not use the same edge more than once), the problem of finding a path from $u$ to $v$ is finitary, hence decidable.

Incidentally, this property is called connectivity.

This approach is a common one, called reduction. Given a problem which is not straightforward, we reduced it to a problem we knew how to solve.

It is often difficult to prove that a problem is undecidable. To prove that a problem is decidable, all we need to do is exhibit an algorithm that decides it. To prove that a problem is undecidable, we need to prove that no algorithm can exist. There are a few well-known undecidable problems. In practice, most of the time, when we prove that a problem is undecidable, we show that there is a well-known undecidable problem that reduces to our problem. Since an algorithm for our problem would solve the well-known undecidable problem, our problem must also be undecidable.

You can't really say that “most” problems are decidable or “most” problems are undecidable. In some theoretical sense, almost all problems are undecidable, but we have a strong tendency to tackle “interesting” problems, and those are more likely to have a solution.

Answer 2

The problem is trivially decidable, as pointed out by Gilles in a comment. As for your other question...

are most problems and algorithms decidable except a few (which is provided here)?

Nope. Actually, most problems are undecidable. In fact, there are uncountably many problems (languages), but there are only countable many Turing Machines, which means there are at most countable many decidable problems.

Answer 3

Yes, this is decidable, because you can do an exhaustive search of all possible paths. There is no need to look at any paths that repeat a vertex, since the "detour" could be skipped. But the length of any non-repetitive path is bounded by the size of the graph, which is finite, and so there are only finitely many such paths, which can be checked one by one.

What is not decidable is the following: given an infinite graph $G$ and two vertices $a$ and $b$, decide whether there is a path from $a$ to $b$. This is not decidable if the graph is given as an oracle and is also not decidable if the graph is given via a program that computes it.

Answer 4

There is no method that tells you whether a specific problem is decidable or not. With time, you might get a good "hunch" whether or not a specific problem is decidable.

What I usually do is the following:

1. try to solve the problem. That is, try to think of a computer program that solves the given problem. For your suggested problem - a very simple program will just check any possible path and thus will always succeed to find it (if it exists), or tell you no path exists otherwise.
2. formulate the problem clearly. Many problems are just too vague, but when written clearly it is very easy to see if decidable or not (by comparing to other problems, known to be un/decidable, or by using known methods like Rice's theorem)
3. If (2) didn't work but you still believe the problem is undecidable, try to prove it by reduction from an undecidable problem (Halting problem (or its complement) works for many cases).

Almost always, when trying to do step (1) for an undecidable problem, you will need your program to check infinite number of things. This is usually a sign that the problem is not decidable.