![](/files/happy5.png)
list partition
The stubborn list partition problem ★★
Author(s): Cameron; Eschen; Hoang; Sritharan
Problem Does there exist a polynomial time algorithm which takes as input a graph
and for every vertex
a subset
of
, and decides if there exists a partition of
into
so that
only if
and so that
are independent,
is a clique, and there are no edges between
and
?
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
![$ v \in V(G) $](/files/tex/1466419f1101030390df1795c6f6a568ac18776b.png)
![$ \ell(v) $](/files/tex/fa7556a65d20c6dbe9ae8911f5247691d913dca7.png)
![$ \{1,2,3,4\} $](/files/tex/de0625f2e589e27a7b57cc4b66560e0e0d0e5daf.png)
![$ V(G) $](/files/tex/b324b54d8674fa66eb7e616b03c7a601ccdab6b8.png)
![$ \{A_1,A_2,A_3,A_4\} $](/files/tex/332fca63ad23d0f750116b00770cf8b73f25bf0b.png)
![$ v \in A_i $](/files/tex/526a8824e06e79af8564522aa70897d4c46c6fdc.png)
![$ i \in \ell(v) $](/files/tex/aa7e74539033b93194f38cd4ef8273a0543143b5.png)
![$ A_1,A_2 $](/files/tex/abb6004b066dae60842422a05109dd268e25b013.png)
![$ A_4 $](/files/tex/50c3d5221f6420416edde366fd2b081acada5bfe.png)
![$ A_1 $](/files/tex/cad9bfcb5f598c9f3e6780be0cf006515579b1fb.png)
![$ A_3 $](/files/tex/1979729d0d75e585787ae2a135d16b37f3e434f2.png)
Keywords: list partition; polynomial algorithm
![Syndicate content Syndicate content](/misc/feed.png)