0
$\begingroup$

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$?

$\endgroup$
1
  • $\begingroup$ I can't tell what you are asking. You want to know if there exists an edge subset such that what? The clause after the "such that" is missing a verb. Please proof-read your question and try to clarify. You might want to restate your condition in English, in addition to the mathematics. $\endgroup$
    – D.W.
    May 22, 2014 at 0:24

2 Answers 2

2
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ Your answer is true. But my question was not stated correctly. Now, I made some edits. Could you check it once more, please? $N$ and $P$ are disjoint and $N \bigcup P \neq V$ $\endgroup$
    – padawan
    May 17, 2014 at 16:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.