Here are some definitions in general:
Choose any $2$ people $p_1,p_2$,
The relationship from $p_1$ to $p_2$ is one of the following:
$1.p_1$ like $p_2$ and $p_1$ dislike $p_2$, or
$2.p_1$ not like $p_2$ and $p_1$ dislike $p_2$, or
$3.p_1$ like $p_2$ and $p_1$ not dislike $p_2$, or
$4.p_1$ not like $p_2$ and $p_1$ not dislike $p_2$A stable party is a group of people whose all members either
$\color{red}{1.}$have no person they dislike in the group, or
$\color{red}{2.}$have exactly one disliked person in the group while also having a person that they like.A unstable party is a group of people with a member who either
$\color{orange}{1.}$doesn’t like another party member and has no friend to compensate, or
$\color{orange}{2.}$has at least two persons that she doesn’t like in the same partyA compact stable party is a stable party that for any people that not in the party, if we add him/her to the party, the party will become unstable.
A strictly stable party is a stable party whose members have no one they dislike in the group (equal to condition $1$ of stable party).
A compact strictly stable party is a strictly stable party that for any people that not in the party, if we add him/her to the party, the party will become not strictly stable.
We denote $x$ Like/Dislike $y$ as $L(x,y)/D(x,y)$ then:
$$\forall x(\underset{\text{$\color{red}{1.}$}}{\underline{\forall y~\neg D(x,y)}}\lor\underset{\text{$\color{red}{2.}$}}{\underline{\exists^{!1}y ~D(x,y)\land \exists z~L(x,z)}})\tag*{Stable}$$
$$\forall x\underset{\text{$\color{red}{1.}$}}{\underline{\forall y~\neg D(x,y)}}\tag*{Strictly stable}$$
$$\exists x(\underset{\text{$\color{orange}{1.}$}}{\underline{\exists y~D(x,y)\land\forall z~\neg L(x,z)}}\lor\underset{\text{$\color{orange}{2.}$}}{\underline{\exists^{\ge2}y~D(x,y)}})\tag*{Unstable}$$
The problem I need to solve is:
Given $n$ people with random relationship, is there an algorithm to find:
$1.$ All possible compact strictly stable parties $?$
$2.$ All possible compact stable parties that not strictly stable $?$
My attempts:
I think this is a graph coloring problem, for part $1$:
Step $1$: Check if there is anyone dislike himself/herself, take them out.
Step $2$: Use the rest people as vertices, connect two vertices if one of them dislike another.
Step $3$: Pick a sufficiently large $n$, find all possible $n$-coloring of this graph
Step $4$: Each color in each $n$-coloring stand for a strictly stable party
Step $5$: Make a set of all strictly stable party from Step $4$, called it $S$
Step $6$: For each party in $S$ If it's a proper subset of another party in $S$, take it out.
Step $7$: The resulting set is all possible compact strictly stable parties.
I still have something not sure about this algorithm:
For $n$ in step $3$, how large is sufficiently large $?$
Here is an old example problem from Mount&Blade,
The dislike relations are showed in the following graph:
(An edge between two vertices $v_1,v_2$ means $v_1$ dislike $v_2$ or $v_2$ dislike $v_1$)
If we pick $n=2$, resulting set only gives all $4$ largest strictly stable parties with $8$ members,
Instead if we let $n=3$, the resulting set is all $85$ compact strictly stable parties.
In this case we say $3$ is sufficiently large for $n$.
This algorithm can also be done by computer, here is my code with sagemath in python: (Result)
from sage.graphs.graph_coloring import all_graph_colorings
G = {'Alayen':['Marnid','Nizar'],
'Artimenner':['Jeremus','Klethi'],
'Baheshtur':['Katrin','Marnid'],
'Borcha':['Deshavi','Klethi'],
'Bunduk':['Lezalit','Rolf'],
'Deshavi':['Borcha','Rolf'],
'Firentis':['Nizar','Katrin'],
'Jeremus':['Artimenner','Matheld'],
'Katrin':['Firentis','Baheshtur'],
'Klethi':['Borcha','Artimenner'],
'Lezalit':['Ymira','Bunduk'],
'Marnid':['Alayen','Baheshtur'],
'Matheld':['Ymira','Jeremus'],
'Nizar':['Firentis','Alayen'],
'Rolf':['Deshavi','Bunduk'],
'Ymira':['Matheld','Lezalit']}
def comb(G,n):# Graph G with n-coloring
G = Graph(G)
G.show()
L1 = []# list that contains all possible coloring
L2 = []# Result list
L3 = []# Sorted Result list
for C in all_graph_colorings(G,n, hex_colors=True):
for i in C:
if C[i] not in L1:
L1.append(C[i])
for i in L1:
c = True# Check if we should append i to result list L2
for j in L1:
if set(i).issubset(set(j)) and set(i) != set(j):
# If it's a proper subset of some set in L1
c = False
# Then we don't append it
for j in L2:
if set(i) == set(j):
# If it's already in L2
c = False
# Then we don't append it
if c:
L2.append(i)
for i in L2:
L3.append([len(i),i])
L3.sort()
print('Total:'+str(len(L3)))
for i in L3:
print(i)
comb(G,2)
comb(G,3)
But for the second part: All possible compact stable parties that not strictly stable, I still don't know where to start.
Any help or hint or suggestion would be appreciated.
A strictly stable party is an Independent Set (IS) with respect to the dislike edges.
More formally, it is an IS in the graph $G'=(V,E_D)$ where $E_D$ is the dislike relation.
This means, a compact strictly stable party is a maximal IS in $G'$ (I'll denote by MIS).
Now, I'm not sure what do you mean by "finding all possibilities".
As for the second part of the question, this is not easier in general.
By easier I mean there is a reduction from the first question to this, and not the my opinion is that it is not easier.
Therefore, for general graphs, you should not look for a polynomial solution.
Remark: If your graph is "special" for example the degree is bounded or some other "very good" properties, there are algorithms that are better than the naive BF solution.
Please clarify which kind of solution you are looking for. algorithmic? exact? is the input very small?
I hope it helps! :)