I'm studying a graph problem which, strangely, has applications in bioinformatics.
I'm not asking for a solution, but rather for advice as to whether
something similar to what I do has been studied before.
Especially about the notion of connectedness not between
vertices, but subsets of vertices.
Some of the concepts in here might already have names, but
I couldn't find anything.
We're given a graph $G$ and a partition $I$ of $V(G)$ into (not necessarily maximal) independent sets.
The goal is to find a set of independent edges that "connect" $I$. I don't know how to define it precisely, but we could say two parts $X, Y \in I$ are connected if there exists a vertex in $X$ and another in $Y$ that share an edge. And transitively, for some $X, Y, Z \in I$, if $X,Y$ are connected as well as $Y, Z$, then $X, Z$ are connected. This is even if $G$ is not connected. For instance, you could have $I=\{X,Y,Z\}$ with $X=\{x_1, x_2\}, Y=\{y_1, y_2\}, Z=\{z\}$, and if we have the edges $x_1y_1$ and $y_2z$, then we say $I$ is connected.
I guess it's some sort of definition of "connected" generalized to subsets of vertices.
OK, so the problem is given $G$ and $I$, does there exist a set of independent edges $M$ (or a matching if you will), such that $I$ is connected when $G$ is restricted to $M$ ? And the ultimate question is to evaluate the complexity of this decision problem.
It is not too hard to make a reduction using the Hamiltonian path problem to show that this is NP-Complete.
However, it happens that because of some real-life contraints, my graphs are cographs (i.e. they have no induced $P_4$). It has been shown that we can solve the Hamiltonian path problem (and a few others) in linear time for this class of graphs. This makes NP-Hardness reductions much harder, and doesn't make the decision problem any easier either.
One last note, the real problem I'm trying to solve is not to find a matching, but a set of independent cliques that connect I (call it a clique matching I guess - is there a name for that ?). But I start with the seemingly easier case of edge matching.