Applications of the splittance of a graph/ Turning graphs into splitgraphs

Question

Let $G=(V,E)$ be a graph. For $C\subseteq V$ let $G[C]$ be the subgraph of $G$ induced by $C$.

A split Graph is defined as follow:

$G$ is a split graph if there exists a subset $C\subseteq V$ so that $G[C]$ is a clique and $G[V\setminus C]$ is an independant set (edges between $C$ and $V\setminus C$ do not matter).

There exists an efficient algorithm (linear time) to calculate the shortest sequence of edge insertions & deletions to turn a graph into a split graph (Important: If we also have to remove the edges between $C$ and $V-C$, then this problem turns $\textsf{NP}$-hard).

My question is: what are possible applications of this procedure?

My ideas so far:

Of course, if the distance of $G$ to a split graph is very small (compared to the number of nodes), we can probably adapt the algorithms for split graphs, and that way obtain efficient implementations for problems that would be $\textsf{NP}$-hard on general graphs.

A general situation where we (somewhat probably) have a near-split-graph would be a network to which we add a batch of random new objects, e.g. a company which just got a batch of newcomers.

Though I still wouldn't know what type of problem there is that could use the fact that the graph is a near-split-graph. Link to the complexity of some problems on split graphs

Answer 1

There is nothing deeper to it than what you describe: if the graph is split or it has "small" distance to being split (e.g., you can make it split by removing a small number of edges/vertices), you might be able to devise a polynomial-time algorithm for some otherwise NP-hard problem.

However, it is quite rare such procedures are applied in practice. It can take too much time to decide if the input graph has the desired properties compared to just using a state-of-the-art solver (e.g., integer programming) for the problem you care about. In fact, it is possible these solvers implicitly detect such useful structure and there is no need for this "additional" theoretical analysis.

To summarize, algorithms for split graphs and the kind of situations you describe are mostly theoretical and rarely implemented or used in practice.