On finding a minimum dominating set in a tournament (Q1113678)

The problem of finding a minimum dominating set in a tournament can be solved in \(n^{O(\log n)}\) time. It is shown that if this problem has a polynomial-time algorithm, then for every constant C, there is also a polynomial-time algorithm for the satisfiability problem of Boolean formulas in conjunctive normal form with m clauses and C \(log^ 2 m\) variables. On the other hand, the problem can be reduced in polynomial time to a general satisfiability problem of length L with \(O(\log^ 2 L)\) variables. Another relation between the satisfiability problem and the minimum dominating set in a tournament says that the former can be solved in \(2^{O(\sqrt{v})}n^ K\) time (where v is the number of variables, n is the length of the formula, and K is a constant) if and only if the latter has a polynomial-time algorithm.