Schuppen über Grenze gebaut

[Opa-Schuppen]

Hallo
A habe folgendes Problem:
A haben ein altes Haus gekauft.
Auf dem Grundstück ist auch ein Schuppen.
Den Schuppen möchte aber der Verkäufer noch bis an sein Lebensende nutzen.
A haben damit kein Problem, weil der Zugang von außen über öffentliches Grundstück möglich ist.

Nun sind A beim Grunstück vermessen,und beim Bauantrag für einen Anbau auf ein Problem gestoßen.
Der Schuppen wurde zu DDR Zeit 1 Meter auf Gemeinde Grundstück gebaut.

A sind Eigentümer von dem Schuppen, im Grundbuch ist der Schuppennutzen nicht eingetragen.
A sind Eigentümer. Einen Mietvertrag hat der Nutzen abgelehnt,es besteht nur eine mündliche Vereinbahrung.

Der Bürgermeister hätte den Fall auch gern gelöst.

A würde dem Vorbesitzer sogar einen neuen Schuppen auf dem Grundstück bauen.
Er weigert sich aber ,er will seinen alten schwarzbau Schuppen behalten.

A möchten keinen Streit mit dem Mann.
Was können A tun ????
An das Bauamt wenden ?
Bekommt man eine Abrissverfügung für den Schuppen ?