Last call to make your voice heard! Our 2022 Developer Survey closes in less than a week. Take survey.
4 votes
Accepted

Question about algorithm for enumerating minimal AB-separators

tldr: your counterexample is correct. Longer Answer: The way $A$-$B$-separators are defined above the problem to determine whether at least one $A$-$B$-separator exists is NP-complete. In particular ...
user avatar
  • 3,216
1 vote
Accepted

Is there FPT or XP algorithms knowm for Shortest Steiner cycle and $(a,b)$-Steiner path problem

Note that you can reduce shortest $(a,b)$-Steiner path to shortest Steiner cycle by adding a terminal vertex of degree 2 adjacent to $a$ and $b$. If you are asking for derandomization of the Björklund,...
user avatar
  • 1,423

Only top scored, non community-wiki answers of a minimum length are eligible