Timeline for Is number of quasi-kernels NP-hard?
Current License: CC BY-SA 3.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 24, 2012 at 14:07 | vote | accept | Felix Goldberg | ||
| Oct 24, 2012 at 14:07 | comment | added | Felix Goldberg | @Colin: I got it now, thanks! You are right. | |
| Oct 24, 2012 at 13:23 | comment | added | Colin McQuillan | @FelixGoldberg: calling the vertices $\{v_1,v_2,v_3,v_4\}$, I am claiming that $\{v_1,v_1'',v_2'',v_3'',v_4''\}$ is a quasi-kernel of $G'$. Which condition fails? | |
| Oct 24, 2012 at 10:40 | comment | added | Felix Goldberg | @Colin: Suppose that $G$ is an oriented $4$-cycle and let $I=\{v\}$ for any $v \in V(G)$. Then $I$ is not a quasi-kernel of $G$ and $I \cup \{v^{''}$ is not a quasi-kernel of $G^{'}$. | |
| Oct 23, 2012 at 19:12 | comment | added | Colin McQuillan | @Felix: I am claiming that every independent set $I$ of $G$ gives a quasi-kernel $I\cup\{v''\mid v\in V(G)\}$ of $G'$, and that every quasi-kernel of $G'$ is of this form. | |
| Oct 23, 2012 at 17:45 | comment | added | Felix Goldberg | I am not sure I get it: not every independent set of $G$ will give you a quasi-kernel of $G^{'}$. It seems you have to start with a quasi-kernel of $G$ to get a quasi-kernel of $G^{'}$ - or am I missing some argument here? | |
| Oct 23, 2012 at 14:31 | comment | added | joro | So when directly converted to SAT it is counting IS (via 2SAT) with additional clauses (maybe again 2SAT)? | |
| Oct 23, 2012 at 14:04 | history | answered | Colin McQuillan | CC BY-SA 3.0 |