<p>Disclaimer: Not a full answer, but too long for a comment.</p>
<p>Cool problem. I was thinking of reducing from vertex cover on connected graphs. If a graph has a vertex cover of size <span class="math-container">$k$</span>, then you can do exactly <span class="math-container">$|V|$</span> loads on <span class="math-container">$m = k+1$</span>. The converse (that there's a sequence of <span class="math-container">$|V|$</span> loads on <span class="math-container">$m$</span>, then there is a vertex cover of size <span class="math-container">$m-1$</span>), seems not so easy to prove or refute; but here are some observations:</p>
<ul>
<li><p>We can assume without loss of generality that the optimal sequence is of the form: (1) <span class="math-container">$m$</span> loads, (2) <span class="math-container">$|V| - m$</span> repetitions of <span class="math-container">$[\textrm{evict}(\cdot), \textrm{load}(\cdot)]$</span>.</p>
</li>
<li><p>Because of the previous point, there must be <span class="math-container">$m$</span> vertices that are never evicted, one of which is the last loaded vertex.</p>
</li>
<li><p>A covering sequence of <span class="math-container">$|V|$</span> loads implies that no vertex is evicted before its entire neighborhood has been loaded.</p>
</li>
<li><p>We can assume without loss of generality that in an optimal sequence the first eviction (operation <span class="math-container">$m+1$</span>) takes out the vertex loaded immediately before, and because of the previous point, that means that all its neighborhood is within the first <span class="math-container">$m-1$</span> loaded vertices.</p>
</li>
</ul>

CC BY-SA 4.0
2024-10-20T16:44:40.927Z
2024-10-20T16:44:40.927Z
Bernardo Subercaseaux
<p>This is a partial answer.</p>
<p>If all you're interested in is NP-hardness, I believe that the value of <span class="math-container">$m$</span> is irrelevant. Basically, what you do is you start with a graph <span class="math-container">$G$</span> for which you want to find a solution with memory of size <span class="math-container">$2$</span> (so we have the problem pair <span class="math-container">$(G,2)$</span>, and I claim there exists a graph <span class="math-container">$G_m$</span> for which the problem is just as hard when the memory has size <span class="math-container">$m$</span>. In other words,</p>
<p><span class="math-container">$(G,2)$</span> is at most as hard as <span class="math-container">$(G_m,m)$</span>.</p>
<p>So increasing the value of <span class="math-container">$m$</span> does not make the problem easier or harder in full generality; there are always certain graphs that become as hard to sole vas if the memory was of size <span class="math-container">$2$</span>.</p>
<p>To build <span class="math-container">$G_m$</span>: consider the complete graph <span class="math-container">$K_m$</span> with vertex set <span class="math-container">$[m]=\{1, \cdots , m\}$</span>. The vertex set of <span class="math-container">$G_m$</span> is <span class="math-container">$V_G \times [m]$</span> and the edge set of <span class="math-container">$G_m$</span> contains all edges of the form <span class="math-container">$((v,1),(w,1))$</span> where <span class="math-container">$(v,w)$</span> is an edge in <span class="math-container">$G$</span> and <span class="math-container">$((v,i),(v,j))$</span> where <span class="math-container">$v \in V_G$</span> and <span class="math-container">$i,j \in [m]$</span>.</p>
<p>So if you have a solution for <span class="math-container">$(G,2)$</span>, use the same solution for <span class="math-container">$G_m$</span> in the sense that when a solution <span class="math-container">$s$</span> for <span class="math-container">$(G,2)$</span> loads <span class="math-container">$v$</span>, in the solution <span class="math-container">$s_m$</span>, load <span class="math-container">$\{v\}\times[m]$</span> (in <span class="math-container">$m$</span> loads); when <span class="math-container">$s$</span> evicts <span class="math-container">$v$</span> to load <span class="math-container">$v'$</span>, in <span class="math-container">$s_m$</span>, perform the following sequence:</p>
<ul>
<li>Evict <span class="math-container">$\{v\} \times \{2,\cdots,m\}$</span></li>
<li>Load <span class="math-container">$\{v'\} \times \{1,\cdots,m-1\}$</span></li>
<li>Evict <span class="math-container">$(v,1)$</span></li>
<li>Load <span class="math-container">$(v',m)$</span>.</li>
</ul>
<p>So basically, by replacing vertices with complete graphs of size <span class="math-container">$m$</span>, you clog the memory, rendering it irrelevant.</p>
<p>In the case where <span class="math-container">$m=2$</span>, it sounds like you're trying to do a form of graph traversal (but not quite, I'm a bit rusty). This is where the partiality of my answer ends!</p>
<p>Hope that helps,</p>

CC BY-SA 4.0
2024-10-21T20:07:15.710Z
I think this would show that hardness of the case $m=2$ would imply hardness of the general case, but I believe $m=2$ is solvable in polynomial time using [the Chinese Postman Problem](https://en.wikipedia.org/wiki/Chinese_postman_problem)
Bernardo Subercaseaux
CC BY-SA 4.0
2024-10-21T17:12:42.940Z
2024-10-25T05:59:33.427Z
2024-10-25T05:59:33.427Z
Patrick Da Silva
<p>I'm studying on the following problem:</p>
<p>Given an undirected graph <span class="math-container">$G=(V,E)$</span> and a dynamic memory <span class="math-container">$M$</span> with
capacity of <span class="math-container">$m$</span> vertices. Initially the memory is empty. It supports two
operations: 1) load(<span class="math-container">$v$</span>), load the vertex <span class="math-container">$v$</span> into memory and 2) evict(<span class="math-container">$v$</span>),
evict vertex <span class="math-container">$v$</span> from the memory if memory is full. An edge of the
graph is said to be covered if its two endpoints are both present in
the memory at some timestamp. The minimum edge covering with
dynamic memory problem is to find a vertex load and evict sequence
that covers all the edges of <span class="math-container">$G$</span> with minimum length (i.e., needs
to load a minimum number of vertices).</p>
<p>A simple example:</p>
<p>Graph: <span class="math-container">$A-B-C$</span>, <span class="math-container">$m=2$</span>; solution: [load(A), load(B), evict(A), load(C)], number of loads = 3</p>
<p>I suspect this problem is NP-hard but haven't managed to prove it. Could you please suggest some related reduction methods?</p>

<cc.complexity-theory><graph-theory><graph-algorithms><np-hardness>
NP-hardness of the edge covering with dynamic memory problem
Yanqi Chen
# NP-hardness of the edge covering with dynamic memory problem

(Asked by: username_0 on 2024-10-15)

I'm studying on the following problem:

Given an undirected graph $G=(V,E)$ and a dynamic memory $M$ with
capacity of $m$ vertices. Initially the memory is empty. It supports two
operations: 1) load($v$), load the vertex $v$ into memory and 2) evict($v$),
evict vertex $v$ from the memory if memory is full. An edge of the
graph is said to be covered if its two endpoints are both present in
the memory at some timestamp. The minimum edge covering with
dynamic memory problem is to find a vertex load and evict sequence
that covers all the edges of $G$ with minimum length (i.e., needs
to load a minimum number of vertices).

A simple example:

Graph: $A-B-C$, $m=2$; solution: [load(A), load(B), evict(A), load(C)], number of loads = 3

I suspect this problem is NP-hard but haven't managed to prove it. Could you please suggest some related reduction methods?

**Tags:** cc.complexity-theory, graph-theory, graph-algorithms, np-hardness

---

## 2 answers

### Answer by username_1 on 2024-10-20. Score: 0

Disclaimer: Not a full answer, but too long for a comment.

Cool problem. I was thinking of reducing from vertex cover on connected graphs. If a graph has a vertex cover of size $k$, then you can do exactly $|V|$ loads on $m = k+1$. The converse (that there's a sequence of $|V|$ loads on $m$, then there is a vertex cover of size $m-1$), seems not so easy to prove or refute; but here are some observations:

* We can assume without loss of generality that the optimal sequence is of the form: (1) $m$ loads, (2) $|V| - m$ repetitions of $[\textrm{evict}(\cdot), \textrm{load}(\cdot)]$.
* Because of the previous point, there must be $m$ vertices that are never evicted, one of which is the last loaded vertex.
* A covering sequence of $|V|$ loads implies that no vertex is evicted before its entire neighborhood has been loaded.
* We can assume without loss of generality that in an optimal sequence the first eviction (operation $m+1$) takes out the vertex loaded immediately before, and because of the previous point, that means that all its neighborhood is within the first $m-1$ loaded vertices.


---

### Answer by username_2 on 2024-10-21. Score: 0

This is a partial answer.

If all you're interested in is NP-hardness, I believe that the value of $m$ is irrelevant. Basically, what you do is you start with a graph $G$ for which you want to find a solution with memory of size $2$ (so we have the problem pair $(G,2)$, and I claim there exists a graph $G\_m$ for which the problem is just as hard when the memory has size $m$. In other words,

$(G,2)$ is at most as hard as $(G\_m,m)$.

So increasing the value of $m$ does not make the problem easier or harder in full generality; there are always certain graphs that become as hard to sole vas if the memory was of size $2$.

To build $G\_m$: consider the complete graph $K\_m$ with vertex set $[m]=\{1, \cdots , m\}$. The vertex set of $G\_m$ is $V\_G \times [m]$ and the edge set of $G\_m$ contains all edges of the form $((v,1),(w,1))$ where $(v,w)$ is an edge in $G$ and $((v,i),(v,j))$ where $v \in V\_G$ and $i,j \in [m]$.

So if you have a solution for $(G,2)$, use the same solution for $G\_m$ in the sense that when a solution $s$ for $(G,2)$ loads $v$, in the solution $s\_m$, load $\{v\}\times[m]$ (in $m$ loads); when $s$ evicts $v$ to load $v'$, in $s\_m$, perform the following sequence:

* Evict $\{v\} \times \{2,\cdots,m\}$
* Load $\{v'\} \times \{1,\cdots,m-1\}$
* Evict $(v,1)$
* Load $(v',m)$.

So basically, by replacing vertices with complete graphs of size $m$, you clog the memory, rendering it irrelevant.

In the case where $m=2$, it sounds like you're trying to do a form of graph traversal (but not quite, I'm a bit rusty). This is where the partiality of my answer ends!

Hope that helps,

> **Comments:**
> **username_1**: I think this would show that hardness of the case $m=2$ would imply hardness of the general case, but I believe $m=2$ is solvable in polynomial time using [the Chinese Postman Problem](https://en.wikipedia.org/wiki/Chinese_postman_problem)  

---

