9
$\begingroup$

The Triangle Finding decision problem asks whether there exists a triangle in a graph $G$ containing $n$ vertices. A triangle is a triple of vertices $(a, b, c)$ such that $a$ is adjacent to $b$, $b$ is adjacent to $c$, and $c$ is adjacent to $a$.

It is known that Triangle Finding is closely related to Boolean matrix multiplication and that Triangle Finding is deterministically solvable in $O(n^{\omega})$ time where $\omega$ is the matrix multiplication exponent. Also, it is known that $\omega < 2.373$.

My Question: Is the complement of Triangle Finding solvable more efficiently with nondeterminism? In particular, is Triangle Finding in $coNTIME(\tilde{O}(n^2))$? If this is not known, would there be any interesting implications if it was true?

$\endgroup$
0
7
$\begingroup$

Update: Sadly, it seems that my initial idea (see below) was incorrect, but it led to some fruitful discussion in the comments. As a result, the question is still open.

Please let me know if you have any ideas. :)


Initial Idea: One way to solve Triangle Finding is to find all pairs of vertices that are connected by a path of length 2. Then, you check if there is an edge between any of these pairs.

A standard way to compute all pairs of vertices that are connected by a path of length 2 is to square the adjacency matrix of the graph. We can perform Boolean matrix multiplication for the squaring. All of the 1's in the result will represent pairs of vertices that are connected by a path of length 2.

With nondeterminism, we can compute Boolean matrix multiplication of two n by n matrices in $\tilde{O}(n^2)$ time by guessing the witness for Boolean matrix multiplication (the concept of witness for Boolean matrix multiplication has been discussed in [1] https://doi.org/10.1007/s00453-012-9742-3 and [2] https://doi.org/10.1109/SFCS.1992.267748). Finally, we check in $O(n^2)$ time if all of the pairs of vertices do not form edges. <- This paragraph doesn't quite work.

$\endgroup$
5
  • 1
    $\begingroup$ Hi Michael, I don't see how the two references you cite solve the problem. Suppose you guess the output of matrix multiplication. For those output entries which are 1, yes you can guess witnesses. How do you prove the 0 entries are correct, nondeterministically, in approximately n^2 time? You have to prove there is no witness in the matrix squaring for all 1-entries in the adjacency matrix, this is what you would need to prove there is no triangle. $\endgroup$ – Ryan Williams Feb 19 at 6:13
  • $\begingroup$ Thank you for your comment! The references define the concept of witness for Boolean matrix multiplication. I cited them only to provide background on this concept. $\endgroup$ – Michael Wehar Feb 19 at 7:50
  • $\begingroup$ I think that you made a good point. The witness for Boolean matrix multiplication may only help identify entries that should be 1's. Let me think about this more. $\endgroup$ – Michael Wehar Feb 19 at 7:53
  • $\begingroup$ Looking at this again, you would need a for all quantifier to check the 0's efficiently. In other words, we can guess and check a witness for Boolean matrix multiplication with a $\Sigma_2 TIME(\tilde{O}(n^2))$ machine which might still be interesting. But, as far as I can tell, we don't seem to get triangle finding in $coNTIME(\tilde{O}(n^2))$. I will update my incomplete / flawed answer tomorrow. $\endgroup$ – Michael Wehar Feb 19 at 8:43
  • 3
    $\begingroup$ I know there is a Merlin Arthur protocol for proving there are no triangles running in close to linear time (in the number of edges), but I don't know a nondeterministic algorithm. It is an interesting problem! In the literature the related problem of matrix multiplication verification has been studied. (If you could verify a matrix mult in n^2 time, even with nondeterminism, you would be done.) One can verify a matrix mult quickly with randomness, this is known as Freivalds's checker. But I don't know how to do it with nondeterminism. $\endgroup$ – Ryan Williams Feb 19 at 14:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.