Given a graph, finding if a node has three adjacents from a node subset $N$

Question

Given a graph $G = (V,E)$, assume that we have two disjoint vertex sets $N = \{n_1, n_2 ...\} \subset V$ and $P = \{p_1, p_2, ...\} \subset V$ such that $N \bigcup P \neq V$.

I want to find if there exists an edge subset such that $\{<n_i,p_l>, <n_j,p_l>, <n_k, p_l>\}$ i.e. three nodes from $N$ and one node frpm $P$.

Should I first list the triplets of $N$ and search if they have a common adjacent in $P$ or for each $p \in P$, check if $p$ has three adjacents in $N$?

Which method would be more efficient? Or does it depend on the sizes of the sets?

Edit: What if I want to list all the edge subsets for all $p_l$?

Answer 1

To find such triples of edges, partition the adjacency list $L_i$ of each node $p_i$ in $P$ into three sets: $P_i$, the set of neighbors in $P$, $N_i$, the set of neighbors in $N$, and $Q_i$, the set of neighbors in $V \setminus (N \cup P)$. If each vertex is labeled with which set it belongs to, then the partitioning can be accomplished in linear time. Then, for each $p_i$, check if $P_i$ contains at least 3 vertices. If so, then you have an edge subset that meets your requirements.

If you want to generate all possible edge subsets of the outgoing edges in each node, you would be generating the powerset of the neighbors of $p_i$. If a vertex has $n$ neighbors, the size of the powerset will be $2^n$. This strategy is impractical for all but the smallest input graphs.

If you only want to list the edge subsets from each $p_i$ that meet your requirements, the number of subsets for a vertex with $n$ neighbors in $V$ will be ${n \choose 3}$, but the algorithm to enumerate them should not be complicated.

Answer 2

If you can find a single node in $V$ of degree $3$, you know that there exists the $N$ and $P$ for the edge subset you are looking for.

Finding every possible combination of triplets is slower than $O(n)$.

However checking the degree of each node in $V$ is $O(n)$.

So which is more efficient?