Sachverhalt:
A.
Das Kriminalgericht des Kantons Luzern stellte am 8. Mai 2000 fest, dass X._ gemeinsam mit seiner Mutter seinen Vater, A._, getötet und damit den Tatbestand des Mordes erfüllt hat. Infolge Unzurechnungsfähigkeit sprach das Kriminalgericht X._ von Schuld und Strafe frei und ordnete gleichzeitig eine ambulante Massnahme an. Nachdem das kantonale Sicherheitsdepartement das Scheitern dieser Massnahme festgestellt hatte, ordnete das Kriminalgericht am 29. März 2004 eine stationäre Massnahme an. Am 26. Mai 2011 wurde X._ aus der Massnahme bedingt entlassen; am 22. Oktober 2015 wurde er in den stationären Massnahmevollzug zurückversetzt.
B.
Im Rahmen der jährlichen Überprüfung lehnte der Vollzugs- und Bewährungsdienst des Kantons Luzern die bedingte Entlassung von X._ ab und ordnete die Weiterführung des Massnahmevollzugs an. Die von X._ gegen diesen Entscheid erhobene Verwaltungsgerichtsbeschwerde wies das Kantonsgericht Luzern am 11. September 2018 ab.
C.
X._ führt Beschwerde in Strafsachen. Er beantragt, der Entscheid des Kantonsgerichts sei aufzuheben und er sei in eine offene Wohnsituation bedingt zu entlassen. Eventualiter sei die Sache zu neuer Entscheidung an die Vorinstanz zurückzuweisen. Die Eingaben der Staatsanwaltschaft sowie des Vollzugs- und Bewährungsdienstes seien aufzuheben und zu relativieren. Ihm sei die unentgeltliche Rechtspflege zu gewähren.
Die Oberstaatsanwaltschaft des Kantons Luzern, der kantonale Vollzugs- und Bewährungsdienst und das Kantonsgericht beantragen, die Beschwerde sei abzuweisen, soweit darauf einzutreten sei. X._ replizierte.

Erwägungen:
1.
1.1. Der Beschwerdeführer macht sinngemäss geltend, dass keine Gefahr weiterer Gewalt- und Tötungsdelikte bestehe (Beschwerde, S. 8 f.).
1.2. Die Vorinstanz behandelt diese Frage unter dem Blickwinkel der Verhältnismässigkeit. Sie erwägt, dass diesem Aspekt - anders als in Fällen, in welchen die Verlängerung oder die Behandlung einer Massnahme zu beurteilen seien - nur eine untergeordnete Rolle zukomme. Es lasse sich allerdings feststellen, dass dem Beschwerdeführer die Weiterführung der Massnahme in einem geschlossenen Setting aufgrund dessen Gesundheitszustandes, der durchaus weitere (Gewalt-) Delinquenz auslösen könnte, zuzumuten sei. Dies gelte nicht zuletzt auch deshalb, weil die Institution, in welcher der Beschwerdeführer untergebracht sei, in einem relativ offenen Rahmen geführt werde. In dem relativ kurz bevorstehenden Verfahren nach <ref-law> müsse immerhin ernsthaft die Frage geprüft werden, ob einem allfälligen Behandlungsbedürfnis des Beschwerdeführers in Zukunft nicht über eine fürsorgerische Unterbringung im Sinne von <ref-law> Rechnung zu tragen sei. Die Vorinstanz erwägt weiter, dass das Verhältnismässigkeitsprinzip mit zunehmender Dauer des Vollzugs an Bedeutung gewinne. Je länger der Freiheitsentzug gedauert habe, umso höhere Anforderungen seien an die Art und Wahrscheinlichkeit künftiger Straftaten zu stellen. Es dürfe in diesem Zusammenhang nicht ausser Acht gelassen werden, dass beim Beschwerdeführer auf psychiatrischer Seite noch ein gewisses Aggressionspotential erkannt werde, entsprechende Gesetzesverstösse nach einhelliger Auffassung aber einzig im Bereich von Bagatelldelinquenz zu erwarten seien. Es dürfte unter diesen Umständen fraglich sein, ob sich eine Fortführung der strafrechtlichen Massnahme unter rechtlichen Aspekten begründen lasse. Die entsprechende rechtliche Situation scheine auch die zuständige Vollzugsbehörde nicht verkannt zu haben. Jedenfalls sei in diesem Sinne positiv zu bewerten, dass gemäss einem letzten Standortgespräch im Hinblick auf den Ablauf der Massnahme in anderthalb Jahren konkrete Lockerungen ins Auge gefasst worden seien. So seien extensivere Ausgänge in den nächsten sechs Monaten und die Etablierung einer offeneren Platzierung im Pflegezentrum in einem Jahr vorgesehen. Auf diese Weise sollen später im Verfahren betreffend Verlängerung oder Aufhebung der Massnahme die vernünftigen weiteren Vorkehren zufriedenstellend evaluiert werden können. Zu begrüssen sei auch, dass auf eine Depotmedikation hingearbeitet werde. Im Ergebnis sei eine bedingte Entlassung aus der stationären therapeutischen Massnahme zum heutigen Zeitpunkt verfrüht (Urteil, S. 14 f.).
1.3.
1.3.1. Gemäss <ref-law> ist eine Massnahme anzuordnen, wenn eine Strafe alleine nicht geeignet ist, die Gefahr weiterer Straftaten des Täters zu begegnen (lit. a), ein Behandlungsbedürfnis des Täters besteht oder die öffentliche Sicherheit dies erfordert (lit. b) und die Voraussetzungen der Artikel 59-61, 63 oder 64 StGB erfüllt sind (lit. c). Nach <ref-law> setzt die Anordnung einer Massnahme voraus, dass der mit ihr verbundene Eingriff in die Persönlichkeitsrechte des Täters im Hinblick auf die Wahrscheinlichkeit und Schwere weiterer Straftaten nicht unverhältnismässig ist. Die Voraussetzungen von Art. 56 Abs. 1 und 2 StGB müssen stets vorliegen und nach der Rechtsprechung auch im Rahmen von Folgeentscheidungen beachtet werden. Eine Massnahme, für welche die Voraussetzungen nicht mehr erfüllt sind, ist gemäss <ref-law> aufzuheben (Urteile 6B_798/2014 vom 20. Mai 2015 E. 2, nicht publiziert in: <ref-ruling>; 6B_669/2017 vom 27. April 2018 E. 1.2.1).
Bei der im Rahmen von <ref-law> erforderlichen Abwägung der sich widerstreitenden Interessen sind die vom Täter ausgehenden Gefahren zur Schwere des mit der Massnahme verbundenen Eingriffs ins Verhältnis zu setzen. Es kommt insbesondere darauf an, ob und welche Straftaten vom Massnahmeunterworfenen drohen, wie ausgeprägt das Mass der Gefährdung ist und welches Gewicht den bedrohten Rechtsgütern zukommt. Je schwerer die Delikte wiegen, die der Massnahmeunterworfene in Freiheit begehen könnte, desto geringer kann die Gefahr sein, die eine freiheitsentziehende Massnahme rechtfertigt, und umgekehrt (Urteil 6B_823/2018 vom 12. September 2018 E. 2.1; Urteil 6B_109/2013 vom 19. Juli 2013 E. 4.4.3). Unzulässig ist die Anordnung einer Massnahme, wenn von einem Täter in Zukunft blosse Übertretungen oder andere Delikte von weniger grosser Tragweite zu erwarten sind (MARIANNE HEER, in: Basler Kommentar, Strafrecht I, 4. Aufl. 2019, N. 37 zu <ref-law>).
1.3.2. Im Hinblick auf die Wahrscheinlichkeit und Schwere weiterer Straftaten erwägt die Vorinstanz lediglich, dass es fraglich sein dürfte, ob sich eine Fortführung der Massnahme unter rechtlichen Aspekten begründen lasse. Eine Abwägung der (einzig) relevanten Umstände - Schwere des massnahmebedingten Eingriffs einerseits und der noch möglichen Straftaten anderseits - findet aber nicht statt. Die Sache ist an die Vorinstanz zurückzuweisen, damit diese die Verhältnismässigkeit der Massnahme unter diesem Blickwinkel überprüft und entsprechend ihrer Erkenntnis neu entscheidet.
2.
Das angefochtene Urteil ist aufzuheben und die Sache zu neuer Entscheidung an die Vorinstanz zurückzuweisen. Es erübrigt sich damit, auf die weiteren Rügen des Beschwerdeführers einzugehen.
Für das bundesgerichtliche Verfahren sind keine Kosten zu erheben (Art. 66 Abs. 1 und 4 BGG). Das Gesuch des Beschwerdeführers um unentgeltliche Rechtspflege wird damit gegenstandslos.

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird gutgeheissen. Das Urteil des Kantonsgerichts Luzern vom 11. September 2018 wird aufgehoben und die Sache zu neuer Entscheidung an die Vorinstanz zurückgewiesen.
2.
Es werden keine Kosten erhoben.
3.
Dieses Urteil wird den Parteien und dem Kantonsgericht Luzern, 2. Abteilung, schriftlich mitgeteilt.
Lausanne, 1. Februar 2019
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Denys
Der Gerichtsschreiber: Moses