A List of P-Complete Problems
Satoru Miyano, Shuji Shiraishi, Takayoshi Shoudai · QIR (Kyushu University Institutional Repository) (Kyushu University) · 1989
can show the following two facts:(i) 6, has a unique minimum feedback vertex set having TL vertices, (ii) The value of B, is true iff u, is included in this minimum feedback vertex set.OIt si~ould be remarked that in the reduction of the proof of Tl-ieorem 4 a cyclicai2y reducible graph is constructed from a circuit so that the graph has a unique rnir,imum feedback vertex set.Hence the problem itself allows several solutions but an instance in the reduction has only one solution.This is the reason why the reduction from MGVP has succeeded.