###### tags: `Research`
# Graph interpolation

## Outline

Given graphs $H$ and $G$ with $|H| \leq |G|$ an *interpolation* is a sequence of graphs $H = G_1, G_2, \ldots, G_p = G$ such that $G_{i+1}$ is derived from $G_i$ by some elementary operation (which we can choose) such that certain graph-measures are 'preserved'. That is, for some isomorphism invariant function $f\colon \cal G \to \mathbb R$ we have that $\max_i f(G_i) - \min_i f(G_i) = O(|f(H)-f(G)|)$ (this could of course be further relaxed to include factors like $\log n$).

In this setting I suggest that we assume $H$ and $G$ to be sparse. It would be great to find results for bounded expansion classes, but initially we could restrict ourselves to e.g. bounded treedepth or even just trees.

## Measures interesting in practice

Since this problem is inspired by practical applications, the following measures are of interest:

- All degree measures: min degree $\delta$, max degree $\Delta$, average degree $\bar d$.
- Global clustering coefficient: $\frac{3\#_GK_3}{3\#_GK_3 + 2\#_GP_3}$ where $\#_GU$ denotes the number of induced subgraphs in $G$ isomorphic to $U$ (the coefficients count the automorphisms)
- The degree *distribution*. This is much more complicated as we have to choose a suitable measure of similarity for distributions.

Other properties we should care about and might be good "proving grounds":
- Any width measure
- Chromatic number
- Connectivity (number of connected components, vertex/edge connectvity)

## Interpolation operation

I suggest that we look at twin-width inspired operation of copying vertices and making small changes to the resulting neighbourhood. To that end, fix the *edit parameter* $t$. To construct $G_{i+1}$ from $G_i$ we proceed as follows:
1. Choose a vertex $v \in G_i$
2. (Optional: make a copy $v'$ of $v$)
3. Edit the neighbourhood of $N(v)$ by adding/removing up to $t$ edges with $v$ as one endpoint

We make step 2. optional so we can still edit the graph when $|G_i| = |G|$.

In the spirit of twin-width, we do not want the edit-operations to accumulate too much. Let us therefore add 'red' edges $R(G_i)$ to every graph $G_i$ which record what we changed: every edge that we added/removed in step 3. is added as a red edge to $R(G_{i+1})$. Further, if we copy a vertex in step 2. we also copy the red edges incident to it. Now we demand that the graph induced by the red edges at every step $i$ has maximum degree $t$.

> **Question**: Does this operation make sense?

*Sanity check*: Assume that $|H| = |G|$. Then the interpolation $\{G_i\}$ cannot add any additional vertices and will only add/remove edges. As the 'red graph' has bounded degree and it is exactly $E(H) \Delta E(G)$. In other words: $H$ and $G$ are graphs that 'differ by a bounded-degree graph'.

This is encouraging in the sense that the degree distributions of $H$ and $G$ are not too different, in particular the min- and max-degree of both graphs differ by at most $t$.

> **Question**: What about other measures?

If we want our graphs to be (and remain) sparse, it might be enough to ask that $H$ and $G$ are sparse (have bounded expansion) and that the interpolation process does not generate $K_{s,s}$ as a subgraph at any point. This is inspired by the fact that graphs of bounded twin-width which exclude $K_{s,s}$ have bounded expansion (see e.g. https://arxiv.org/pdf/2107.03711.pdf).

> **Question**: If $H,G$ have bounded expansion, is exlucding $K_{s,s}$ in the interpolation process enough to ensure that the $G_i$ have bounded expansion?
> **Answer**: This is currently **false**. Let $G'$ be a two-subdivision of $K_n$ and let $H,G$ be $K_n$ minus a matching (the middle edge of every subdivided edge). Then we can let $G'$ appear and dissapear in the interpolation process!

This tells us that we need to impose some form of monotonicity: it is dangerious if we allow edges to be added an later removed.

## The algorithmic case

For the problem of *computing* an interpolation, we run into the issue that for even for $H \simeq G$ we probably implicitly compute an isomorphism. To simplify matters, we can assume that we are provided with an injective mapping $\tau \colon V(H) \to 2^{V(G)}$ such that $\tau(V(H))$ is a partition of $G$. This mapping tells us which vertices of $H$ will be 'turned' into vertices of $G$ by use of the copy-operation defined above.

For $|H| = |G|$ this means that the problem is trivially polynomial-time, but what about $|H| < |G|$?

> **Question**:
> Given $H$, $G$, $\tau$ and $t$ as input, what is the complexity of computing a $t$-interpolation from $H$ to $G$?

## Possibly related work

In the *graph sandwich problem* for some fixed graph property $\Pi$ we are given edge sets $E^1, E^2$ over $V$ and asked whether there exist an edge set $E^1 \subseteq E \subseteq E^2$ such that $G = (V,E)$ satisfies $\Pi$. Golumbic, Kaplan, and Shamir introduced this problem [GMKS95].

They first observe that all subgraph-closed properties $\Pi$ are trivial in the sense that we only have to check whether $G^1 = (V, E^1)$ satisfies the property. If not, there cannot be a sandwich graph, otherwise $G^1$ is a solution. In the other direction, if $\Pi$ is 'upwards closed' (if $G$ has $\Pi$ then all supergraphs of $G$ have $\Pi$ as well) then the problem reduces to checking whether $G^2 = (V, E^2)$ is in $\Pi$. Finally, they observe that the sandwhich problem for the complement property $\bar \Pi$ is polynomially equivalent to the one for $\Pi$.

They further show that the problen is NP-complete for a range of graph properties/classes: permutation graphs, co-comparability graphs, circle graphs, unit interval graphs, (unit/proper) circular arc graphs, circular permutation graphs, and chordal graphs. Dantas et al. [DFPT19] showed that the sandwich problem is hard for the property of $H$-freeness when $H$ obeys certain properties; in particular their result applies to wheel-graphs with 7 or more vertices.

## References
@article{GMKS95,
title={Graph sandwich problems},
author={M. Golumbic and H. Kaplan and R. Shamir},
journal={Journal of Algorithms},
volume={19},
number={3},
pages={449--473},
year={1995},
publisher={Elsevier}
}

@article{DFPT19,
title={A General Method for Forbidden Induced Subgraph Sandwich Problem NP-completeness},
author={S. Dantas and C. de Figueiredo and P. Petito and R.B. Teixeira},
journal={Electronic Notes in Theoretical Computer Science},
volume={346},
pages={393--400},
year={2019},
publisher={Elsevier}
}