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

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