27
$\begingroup$

This problem is highly related to the CNF one.

Here is the problem: given two DAG (directed acyclic graphs), if they have the same counting of topological sorts, answer "Yes", otherwise, answer "No".

Intuitively, the complexity of this problem is $C_=P$-complete, just as the CNF one. It is easy to see it is in $C_=P$, but is it $C_=P$-hard?

$\endgroup$
  • $\begingroup$ @Mike Chen Could you, please, explain what is $C_=P$? And what do you mean by the "counting of topological sorts"? $\endgroup$ – Oleksandr Bondarenko Nov 17 '10 at 22:34
  • $\begingroup$ @Oleksandr: I added a link to $C_=P$ in the question. "counting of topological sorts" means the number of topological sorts. $\endgroup$ – Mike Chen Nov 17 '10 at 22:44
  • 2
    $\begingroup$ Right, the counting version of this problem is $\#P$-complete. But what I really wanna know is if counting of solutions is $\#P$-complete, is the problem of deciding whether two have the same number of solutions $C_=P$-complete? $\endgroup$ – Mike Chen Nov 17 '10 at 22:59
  • 4
    $\begingroup$ You probably already know this, but let me write this down for others: this problem is not (apparently) the same as the other question on deciding whether two CNF formulas have the same number of solutions. The reason is that counting the solutions to a given CNF formula is #P-complete under parsimonious reductions whereas counting the topological sorts of a given DAG is not (unless P=NP). Counting the topological sorts is #P-complete only under functional reductions between counting problems (also called weakly parsimonious reductions). $\endgroup$ – Tsuyoshi Ito Dec 2 '10 at 4:42
  • 2
    $\begingroup$ Somewhat related: Deciding whether two unweighted graphs have the same number of perfect matchings is C=P-complete. Like in your problem, the counting problem here is also not #P-complete under parsimonious reductions. arxiv.org/abs/1511.07480 $\endgroup$ – Radu Curticapean Feb 8 '16 at 23:34

Your Answer

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

Browse other questions tagged or ask your own question.