I have a question: It is known that it is easy to find the maximum cliques of an interval graph. I would like to ask whether the same task is also easy when considering the following subgraph of an interval graph:

Let $ G=(\mathcal{I},E) $ be an interval graph and let $ k:\mathcal{I}\rightarrow (0,1) $ be a vertex weight function. Now we delete every edge $ \lbrace i,j \rbrace \in E $ with $ k_i+k_j \le 1 $ from $ E $. The remaining edge set is called $ \tilde{E} $. Moreover, we remove vertices that are not part of an edge anymore, so that we end up with a subgraph $ \tilde{G}=(\tilde{\mathcal{I}},\tilde{E}) $ of $ G $.

It is also easy to find the maximum cliques of this graph? (I would call it a 'mixture' between an interval graph and a threshold graph.)

Thanks for your help!


Each clique in $\tilde G$ contains at most one vertex with weight $\le \frac12$. So we can do casework on which of these vertices, if any, we include:

  • Find a maximum clique in the subgraph of $G$ containing all vertices with weight more than $\frac12$. (This clique survives in $\tilde{G}$.)
  • For each vertex $i$ with $k_i \le \frac12$, find a maximum clique in the subgraph of $G$ containing all vertices adjacent to $i$ and with weight more than $1 - k_i$. (Such a clique, together with vertex $i$ itself, is still a clique in $\tilde{G}$.)

Then, just take the largest clique of any found in this process. Note that an induced subgraph of an interval graph is also an interval graph, so all of these steps should be easy.

  • $\begingroup$ Thanks for your answer. I just have two little questions: (1) Is $ \tilde{G} $ really an induced subgraph of $ G $? I mean, not all the edges between the nodes $ \tilde{I}$ are overtaken from $ G $? (2) Am I right that the cliques described in your construction actually form an edge cover of $ \tilde{G}$? $\endgroup$ – Phil Mar 18 at 17:44
  • $\begingroup$ (1) $\tilde{G}$ is definitely not an induced subgraph of $G$! But if we are looking at a set of vertices, each with weight more than $\frac12$, then they induce the same subgraph in $G$ and in $\tilde{G}$, because $\tilde{G}$ keeps all edges between such vertices. $\endgroup$ – Misha Lavrov Mar 18 at 18:24
  • $\begingroup$ (2) The subgraphs we find include all the edges of $\tilde{G}$ between them - sort of. In the first step, we cover all edges between vertices of weight more than $\frac12$. In the next step, for each vertex $i$ with $k_i \le \frac12$, we cover all edges out of $i$ - sort of, because I defined these subgraphs not to include vertex $i$ itself, but you could modify the definition to include it. The cliques themselves, I don't see why they'd cover all the edges, unless this follows from some property of interval graphs. $\endgroup$ – Misha Lavrov Mar 18 at 18:26
  • $\begingroup$ Ok, in fact, finally I am looking for an edge cover of $ \tilde{G} $ by a preferaby small number of maximum cliques of that graph. (Of course, I had to know first whether or not it is easy to find maximum cliques in $ \tilde{G} $.) $\endgroup$ – Phil Mar 18 at 19:36
  • $\begingroup$ Do you want maximum cliques or just maximal ones? In general, a graph might not have a cover by any number of maximum cliques. $\endgroup$ – Misha Lavrov Mar 18 at 20:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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