2
$\begingroup$

I'm sorry if the title is a bit convoluted. I'm a bit unsure how to formulate this condition in words, see below instead.

Say we are given a set $Y$. I want to find the following set: $\mathcal{A}$ such that for any $x=\{G_1, ..., G_k\} \in \mathcal{A}, G_i \subset Y$, we have that:

$\forall G_i \in x, \exists G_j \in x, i \neq j , \quad G_i \cap G_j \neq \emptyset $

I'm mostly interesting in finding an algorithm which generates this set. This problem arose when trying to figure out how to generate the set of subgraphs of a connected subgraphs, such that their union is still connected. So the sets above would then be vertex sets and I would form their induced graph.

So, I want to find the subgraphs such that the union of all those subgraphs $\bigcup_{i=1}^{k}G_{i} \text{ is connected}$. Since each of the subgraphs themselves are connected (since the graph is), the above stated condition ought to ensure that their union is connected.

Anyone have an idea how to tackle this? Any help is much appreciated!

  • 0
    Can you explain the notation $x=\{G_1,...,G_k\}$?2011-07-26
  • 0
    $x$ is a combination of $k$ subsets of $Y$. $k$ is just an arbitrary number. So for example let $Y=\{1,2,3\}$. We might have $x=\{ \{1,2\}, \{2,3\} \}$ which has one "overlapping" element. Ah, it should be $x \subset A$ rather than $x \in A$ I realized now.2011-07-26
  • 0
    Another example, $Y=\{1,2,3,4,5\}$. An element of $\mathcal{A}$ would be $\{ \{1,2\}, \{2,3\}, \{3,4,5\} \}$. Yet another element would be: $\{ \{1,2,3\}, \{3,4,5\} \}$. I hope this makes it clearer.2011-07-26
  • 0
    This is a weak condition you've outlined and does not imply that the union of all the "subgraphs" is connected. For example you might have $G_1$ and $G_2$ with nonempty intersection and $G_3$ overlapping with $G_4$, yet nothing that connects $G_1 \cup G_2$ with $G_3 \cup G_4$. Have you really asked for what you want?2011-07-26
  • 0
    That is true. Thanks for pointing that out! I guess what I'm really after is for example a 1-vertex overlapping partition of the original graph. That is, I want the union of the set of subgraphs to be the original (by assumption connected) graph. The partition can't be disjoint though. (These subgraphs will then later on be fed to a graph classification algorithm).2011-07-26
  • 0
    To simplify a bit: $x$ is irrelevant, and in fact makes the problem impossible (you ask for a condition that must hold for all subsets $x$ of $\mathcal{A}$, but which cannot be satisfied by singleton subsets of $\mathcal{A}$). Instead, the condition should be placedon $\mathcal{A}$, with the added proviso that $\mathcal{A}$ must be nonempty. But you must want more; otherwise, taking $\mathcal{A}=S-\{\emptyset\}$ (provided $Y$ has more than a single element). Do you want **all** possible $\mathcal{A}$?2011-07-26
  • 0
    I'm sorry for the confusion. I now edited my original post to express it in a (hopefully) correct way. So for any $x=\{G_1, ..., G_k\} \in \mathcal{A}$, every $G_i$ is a subset of the original set (or vertex set of the graph if you like) with the added condition that $\bigcup_{i=1}^{k}G_{i}=G$ as well as the condition that they are overlapping in the sense described above.2011-07-26
  • 0
    I'm not sure what notion of algorithm you're using, but it should be enough to generate the set $\mathcal{B}$ consisting of those $x = \{G_1, G_2\}$ with $G_1 \cap G_2 \neq \emptyset$. Then $\mathcal{A}$ is just the closure of $\mathcal{B}$ under unions. But your most recent comment says something about the union being $G$, and I don't know what that means.2011-07-26
  • 0
    To be fair I'm not quite certain whether or not this is really a [set-theory] related question.2011-07-26
  • 0
    What I'm doing at the moment (which is very slow) is first generating all the subsets and then looking at all possible combinations of these subsets to see if (1) their union actually forms the original graph (i.e they are collectively exhaustive I guess) and (2) that the overlapping condition is satisfied. For {1,2,3,4,5} for example, we would get one element of $\mathcal{A}$ being $\{ \{1,2\}, \{1,3\}, \{1,4\}, \{1,5\} \}$. They are mutually exclusive except for the vertex they "share"(the overlap). In this case they all share one vertex. Thanks everyone for your patience and input! :)2011-07-26
  • 0
    @Erik Are you assuming the sets are finite?2011-07-27

3 Answers 3