Skip to main content

New answers tagged

4 votes
Accepted

Deciding whether there are directed paths between two vertices of all possible lengths

While the initial problem of determining if an integer LRS has a zero is indeed not known to be decidable, the graph problem you mention is very much decidable. It is simply used for coNP-hardness in ...
Corto's user avatar
  • 136
2 votes

Is the protocol perfect zero knowledge?

Zero-knowledge proofs do not in general compose in parallel. See this paper by Feige and Shamir for a (contrived) counterexample. Beyond this counterexample, there are several constraints to actually ...
lamontap's user avatar
  • 1,010
7 votes

What is the smallest graph of treewidth $k$ having less edges than the $(k+1)$-clique?

The smallest such example that is known to the House of Graphs is for $k = 9$. There is a graph of tree-width $9$ having only $44$ edges (while the $10$-clique contains $45$ edges).
tomil's user avatar
  • 71

Top 50 recent answers are included