Sachverhalt:
A.
Das Bezirksgericht Bülach verurteilte A._ am 27. Mai 2014 wegen vorsätzlicher Tötung, Diebstahls und Widerhandlung gegen das Betäubungsmittelgesetz zu einer Freiheitsstrafe von 13 Jahren.
B.
B.a. A._ befindet sich derzeit in der Justizvollzugsanstalt Pöschwies. Ein Drittel seiner Freiheitsstrafe hatte er am 9. Juni 2017 verbüsst. Am 9. Oktober 2021 wird er zwei Drittel der Strafe erstanden haben. Das Strafende fällt auf den 9. Februar 2026.
B.b. Am 19. Februar 2018 ersuchte A._ um Gewährung von Urlaub für den 5. April 2018 für einen Gedenkgottesdienst für seine im Oktober 2014 verstorbene Tochter.
Mit Verfügung vom 12. März 2018 wies das Amt für Justizvollzug des Kantons Zürich dieses Gesuch wegen Fluchtgefahr ab, was die Direktion der Justiz und des Innern des Kantons Zürich (DJI) auf Rekurs hin mit Verfügung vom 12. Juli 2018 bestätigte. Dagegen erhob A._ Beschwerde. Er beantragte unter anderem, es sei festzustellen, dass künftige Urlaubsgesuche bzw. ein neues Urlaubsgesuch, wie dasjenige vom 19. Februar 2018, grundsätzlich zu bewilligen seien bzw. sei.
Das Verwaltungsgericht des Kantons Zürich hiess die Beschwerde mit Urteil vom 18. Dezember 2018 gut und hob die Verfügungen des Amts für Justizvollzug des Kantons Zürich vom 12. März 2018 und der DJI vom 12. Juli 2018 auf.
C.
Die Oberstaatsanwaltschaft des Kantons Zürich beantragt mit Beschwerde in Strafsachen im Wesentlichen, das Urteil des Verwaltungsgerichts des Kantons Zürich vom 18. Dezember 2018 sei aufzuheben und das Urlaubsgesuch von A._ sei abzuweisen. Eventualiter sei das Urteil des Verwaltungsgerichts aufzuheben und die Sache zur neuen Beurteilung an die Vorinstanz zurückzuweisen.
Das Verwaltungsgericht des Kantons Zürich verzichtet unter Verweis auf die Erwägungen im angefochtenen Urteil auf eine Vernehmlassung und beantragt die Abweisung der Beschwerde. A._ beantragt, auf die Beschwerde sei nicht einzutreten; eventualiter sei sie abzuweisen. Zudem ersucht er um unentgeltliche Rechtspflege.
D.
Die Strafrechtliche Abteilung des Bundesgerichts hat die Angelegenheit am 12. Dezember 2019 an einer öffentlichen Sitzung beraten.

Erwägungen:
1.
1.1. Die Beschwerdeführerin ist zur Beschwerde legitimiert (Art. 81 Abs. 3 i.V.m. <ref-law>).
Die Behördenbeschwerde ist grundsätzlich nur unter den Voraussetzungen von Art. 81 Abs. 1 lit. b Ziff. 7 und Abs. 3 BGG gegeben. Entsprechend sind die kantonalen Vollzugsbehörden von der Beschwerde ausgeschlossen (<ref-ruling> E. 2.3 S. 53; <ref-ruling> E. 1.1 f. S. 123 f.). Die Staatsanwaltschaft ist nach Art. 81 Abs. 1 lit. b Ziff. 3 BGG ohne Einschränkung beschwerdeberechtigt (<ref-ruling> E. 2 S. 200 mit Hinweis; Urteil 6B_664/2013 vom 16. Dezember 2013 E. 1.1 f.). Die Interessen "tangierter Behörden" sind vom Staatsanwalt zu wahren (Urteil 6B_1203/2017 vom 1. November 2017 E. 2 mit Hinweisen).
1.2. Das rechtlich geschützte Interesse an der Aufhebung oder Änderung des angefochtenen Entscheides muss ein aktuelles und praktisches sein (<ref-ruling> E. 2.3.1 S. 84 f.; <ref-ruling> E. 1.3.1 S. 77; je mit Hinweisen). Mit der Beschwerdeführerin ist festzuhalten (Beschwerde S. 3 f. Ziff. 3), dass hier ein aktuelles und praktisches Rechtsschutzinteresse an der Aufhebung bzw. Abänderung des angefochtenen Entscheids besteht, auch wenn der ursprünglich beantragte Urlaubstermin inzwischen verstrichen ist. Die Vorinstanz heisst die Beschwerde des Beschwerdegegners gut und hält ausdrücklich fest, dass das Amt für Justizvollzug ein künftiges Urlaubsgesuch von ihm, wie dasjenige vom 19. Februar 2018, grundsätzlich zu bewilligen habe, sofern dannzumal keine wichtigen Gründe dagegen sprechen würden.
1.3.
1.3.1. Der Beschwerdegegner wendet ein, die Beschwerde in Strafsachen sei verspätet erhoben worden. Gemäss Rechtsprechung gelte der Fristenstillstand nach <ref-law> nicht, wenn eine strafprozessuale Haft zu beurteilen sei. Weil es bei der Verweigerung des Anspruchs auf Urlaubsgewährung einer im Strafvollzug befindlichen Person auch um die Beurteilung einer angeblichen Fluchtgefahr gehe, sei diese Praxis hier ebenfalls massgebend (Vernehmlassung S. 2 ff., act. 12).
1.3.2. Nach <ref-law> ist die Beschwerde innert 30 Tagen nach der Eröffnung der vollständigen Ausfertigung des angefochtenen Entscheids beim Bundesgericht einzureichen. Gemäss <ref-law> stehen gesetzlich oder richterlich nach Tagen bestimmte Fristen still: (lit. a) vom siebenten Tag vor Ostern bis und mit dem siebenten Tag nach Ostern; (lit. b) vom 15. Juli bis und mit dem 15. August; (lit. c) vom 18. Dezember bis und mit dem 2. Januar. Diese Vorschrift gilt nicht in Verfahren betreffend aufschiebende Wirkung und andere vorsorgliche Massnahmen sowie in der Wechselbetreibung, für Stimmrechtssachen (Art. 82 Bst. c) und auf den Gebieten der internationalen Rechtshilfe in Strafsachen und der internationalen Amtshilfe in Steuersachen (<ref-law>). In Fällen der strafprozessualen Haft gilt der Fristenstillstand gemäss <ref-law> nicht (<ref-ruling> E. 1.2 mit Hinweis; <ref-ruling> E. 1.2.2 S. 274; Urteil 1B_275/2015 vom 29. September 2015 E. 2 mit Hinweisen).
1.3.3. Nach eigenen Angaben ging der Beschwerdeführerin das vorinstanzliche Urteil am 27. Dezember 2018 zu. Diese hat ihre Beschwerde - unter Inanspruchnahme des Friststillstands nach <ref-law> - am 30. Januar 2019 eingereicht. Dem Beschwerdegegner ist zwar beizupflichten, dass bei der Prüfung einer Gewährung von Urlaub im Strafvollzug, wie bei der Anordnung der Untersuchungshaft, u.a. die Fluchtgefahr zu beurteilen ist. Bei der Frage, ob eine Ausnahme vom Fristenstillstand nach <ref-law> vorliegt, ist dies allerdings nicht wesentlich. Es ist unbestritten, dass sich der Beschwerdeführer nicht in strafprozessualer Haft (u.a. weder in Untersuchungs- oder Sicherheitshaft noch im vorzeitigen Strafantritt, vgl. <ref-ruling> E. 2.1), sondern im Strafvollzug befindet. Somit beruft sich die Beschwerdeführerin zu Recht auf den Fristenstillstand <ref-law>, weshalb auf ihre Beschwerde einzutreten ist.
2.
2.1. Die Beschwerdeführerin rügt, die Vorinstanz verletze <ref-law>, indem sie bei der Prüfung der Voraussetzungen einer Urlaubsgewährung wesentliche Gesichtspunkte ausser Acht gelassen und die zur Beurteilung der Fluchtgefahr herangezogenen Elemente unter Überschreitung ihres Ermessens falsch gewichtet habe (Beschwerde S. 5 ff.).
2.2. Die Vorinstanz hält fest, der Beschwerdegegner verhalte sich im Vollzug - mit Ausnahme zweier Disziplinierungen - tadellos. Er halte sich an den Vollzugsplan und komme seiner Mitwirkungspflicht ohne Einwände nach. Dass der Beschwerdegegner noch keine Wiedergutmachungszahlungen geleistet habe, falle angesichts der Unterhaltszahlungen für den Sohn im vorliegenden Kontext nicht überwiegend negativ ins Gewicht (Urteil S. 5 E. 3.1). Im psychiatrischen Gutachten vom 10. Januar 2014 sei die Rückfallgefahr für Gewaltstraftaten oder Tötungsdelikte als gering eingeschätzt worden. Es sei nicht davon auszugehen, dass das Rückfallrisiko mehr als gering einzustufen sei. Damit spreche die Rückfallgefahr entgegen der Ansicht der DJI nicht gegen eine Urlaubsgewährung (Urteil S. 5 f. E. 3.2).
Die Vorinstanz führt ferner aus, Fluchtgefahr dürfe nicht bereits dann angenommen werden, wenn die Möglichkeit der Flucht in abstrakter Weise bestehe. Es brauche vielmehr eine gewisse Wahrscheinlichkeit, dass der Inhaftierte, wenn er in Freiheit wäre, sich dem Vollzug der Strafe durch Flucht entzöge. Es müssten konkrete Gründe dargetan werden, die eine Flucht nicht nur als möglich, sondern insgesamt als wahrscheinlich erscheinen lasse. Dabei seien die gesamten Verhältnisse der betroffenen Person wie die Lebensumstände, familiäre Bindungen, berufliche und finanzielle Situation sowie Kontakte zum Ausland in Betracht zu ziehen. Die Aussicht, nach Verbüssung der Strafe aus der Schweiz ausgeschafft zu werden, erhöhe die Fluchtgefahr zwar regelmässig in nicht unbeträchtlichem Umfang. Doch auch dann sei eine Gesamtwürdigung vorzunehmen und es sei von Schematismen abzusehen. Dass ausländischen Gefangenen, welche die Schweiz nach dem Strafvollzug zu verlassen haben, in der Regel nur dann Urlaub gewährt werde, wenn sie eine enge, dauerhafte Beziehung zu einer in der Schweiz lebenden Bezugsperson mit Aufenthaltsrecht nachweisen, wie dies die Richtlinien über die Ausgangs- und Urlaubsgewährung der Ostschweizer Strafvollzugskommission vom 7. April 2006 vorsähen, sei zu einschränkend und verstosse gegen übergeordnetes Recht (Urteil S. 6 f. E. 3.5).
Die Vorinstanz erwägt weiter, es sei zutreffend, dass der Beschwerdegegner die Schweiz nach seiner Entlassung zu verlassen habe und damit grundsätzlich die Fluchtgefahr erhöht sei. Allerdings habe er aufgrund seiner Biographie und seiner Familienangehörigen, welche in Deutschland leben würden und zu denen er ein enges Verhältnis habe, ein evidentes Interesse, nach der Verbüssung der Strafe nach Deutschland zurückkehren zu können. Da vom Beschwerdegegner bei seiner Entlassung mutmasslich nur ein geringes Rückfallrisiko für Gewaltstrafen ausgehen werde, er ansonsten nicht vorbestraft sei, er über einen schulpflichtigen Sohn in Deutschland verfüge, zu welchem er einen engen Kontakt pflege, und selber in Deutschland in geordneten Verhältnissen aufgewachsen sei, habe der Beschwerdegegner eine reelle Chance, sich nach der Verbüssung seiner Strafe wieder in Deutschland aufhalten zu dürfen. Würde er sich durch eine Flucht nach Griechenland der weiteren Strafe entziehen, könnte er nicht mehr nach Deutschland zurückkehren. Nur in Griechenland wäre er vor der Schweizer Justiz geschützt, da davon auszugehen sei, dass Griechenland gestützt auf Art. 6 des Europäischen Auslieferungsabkommens vom 13. Dezember 1957 (SR 0.353.1) seine eigenen Staatsangehörigen nicht ausliefere. Deutschland würde jedoch, da er neben der griechischen Staatsbürgerschaft nicht auch die deutsche besitze, an die Schweiz ausliefern und seine gegenwärtig gute Legalprognose wäre für den Erhalt einer Aufenthaltsbewilligung in Deutschland getrübt. Ein Untertauchen in Deutschland würde ihm den Kontakt zu seinem Sohn geradezu verunmöglichen. Würde der Beschwerdegegner nach Griechenland flüchten und wolle er mit seinem Sohn zusammenleben, müsste er diesen aus seiner gewohnten Umgebung bei seinen Grosseltern in Deutschland herausreissen. Für eine solche Absicht würden keine Anhaltspunkte bestehen. Im Ergebnis würde damit gar eine noch mehr gegen eine Flucht sprechende Ausgangslage vorliegen, als wenn der definitiv aus der Schweiz weggewiesene Beschwerdegegner hier nahe Angehörige hätte. Denn er habe seine Aufenthaltsperspektive in Deutschland zu verlieren, wenn er sich der Reststrafe durch Flucht nach Griechenland entziehe. Damit sei unter den vorliegenden Umständen eine hinreichend konkrete Fluchtgefahr zu verneinen (Urteil S. 7 f. E. 3.6). Vorliegend sei die gemeinsam mit der aus Süddeutschland anzureisenden Familie verbrachte Urlaubszeit in der Schweiz und die Verarbeitung des Traumas durch den Tod seiner Tochter für die soziale Wiedereingliederung des Beschwerdegegners in Süddeutschland geeignet und diene damit dem Strafziel der künftigen Deliktsfreiheit. Die grundsätzliche Verweigerung von Urlaub erweise sich in Anbetracht der dargelegten Umstände als unverhältnismässig. Der Justizvollzug des Kantons Zürich werde ein künftiges Gesuch des Beschwerdegegners, wie dasjenige vom 19. Februar 2018, grundsätzlich zu bewilligen haben, ausser es würden dannzumal wichtige Gründe dagegen sprechen (Urteil S. 9 E. 3.7).
2.3. Für den Straf- und Massnahmenvollzug sind die Kantone zuständig, soweit das Gesetz nichts anderes vorsieht (<ref-law>). <ref-law> regeln die Grundzüge des Straf- und Massnahmenvollzugs. Die Einzelheiten des Vollzugs richten sich nach kantonalem Recht und den für den einzelnen Kanton jeweils massgebenden Konkordatsrichtlinien.
Der Strafvollzug muss gemäss <ref-law> die Menschenwürde achten und darf die Rechte des Gefangenen nur soweit beschränken, als der Freiheitsentzug und das Zusammenleben in der Anstalt es erfordern (<ref-ruling> E. 2b S. 204 mit Hinweis). Art. 74 und 75 StGB schreiben einen namentlich auf Wiedereingliederung und Resozialisierung des Insassen ausgerichteten Strafvollzug vor. Nach <ref-law> sollen Gefangene im Vollzug denn auch vorab dazu befähigt werden, künftig straffrei zu leben. Die Vollzugsbedingungen haben sich somit am Grundsatz der Rückfallverhütung nach der Entlassung aus dem Vollzug zu orientieren. Der Vollzug beruht auf einem Stufensystem. Dem Gefangenen werden im Hinblick auf seine Rückkehr in die Gesellschaft zunehmend mehr Freiheiten gewährt. Je grösser die Flucht- oder Rückfallgefahr ist, desto engere Grenzen sind allerdings solchen stufenweisen Vollzugsöffnungen gesetzt (Urteile 6B_240/2018 vom 23. November 2018 E. 2.3; 6B_619/2015 vom 18. Dezember 2015 E. 2.7; je mit Hinweis; 6B_1028/2014 vom 17. Juli 2015 E. 3.2).
Gemäss <ref-law> ist dem Gefangenen zur Pflege der Beziehungen zur Aussenwelt, zur Vorbereitung seiner Entlassung oder aus anderen Gründen in angemessenem Umfang Urlaub zu gewähren, soweit sein Verhalten im Strafvollzug dem nicht entgegensteht und keine Gefahr besteht, dass er flieht oder weitere Straftaten begeht. Der Anspruch auf Urlaub hängt davon ab, dass das Verhalten des Gefangenen einer Urlaubsgewährung nicht entgegensteht und keine Rückfall- oder Fluchtgefahr vorliegt. Die Anforderungen an das Verhalten des Gefangenen im Strafvollzug und die Risiken einer Rückfallgefährlichkeit im Sinne von <ref-law> richten sich nach den Massstäben, wie sie bei der bedingten Entlassung nach <ref-law> gelten. Für die Beurteilung der Fluchtgefahr sind die vom Bundesgericht bei der Anordnung von Untersuchungshaft entwickelten Kriterien heranzuziehen (Urteile 6B_254/2012 vom 18. Juni 2012 E. 3; 6B_577/2011 vom 12. Januar 2012 E. 2.1 mit Hinweis).
Fluchtgefahr darf nicht bereits angenommen werden, wenn die Möglichkeit der Flucht in abstrakter Weise besteht. Es braucht vielmehr eine gewisse Wahrscheinlichkeit, dass der Inhaftierte, wenn er in Freiheit wäre, sich dem Vollzug der Strafe durch Flucht entzöge. Es müssen konkrete Gründe dargetan werden, die eine Flucht als wahrscheinlich erscheinen lassen. Hierfür sind die gesamten Verhältnisse des Eingewiesenen wie beispielsweise die Lebensumstände, familiäre Bindungen, berufliche und finanzielle Situation sowie Kontakte zum Ausland, in Betracht zu ziehen (<ref-ruling> E. 4.3 S. 167; <ref-ruling> E. 3a S. 62; je mit Hinweisen; <ref-ruling> E. 3d S. 36 f.; Urteile 6B_655/2013 vom 10. September 2013 E. 2; 6B_577/2011 vom 12. Januar 2012 E. 2.2; je mit Hinweisen). Selbst bei einer befürchteten Ausreise in ein Land, das die beschuldigte Person grundsätzlich an die Schweiz ausliefern bzw. stellvertretend verfolgen könnte, fiele die Annahme von Fluchtgefahr nicht dahin (BGE <ref-ruling> E. 3d S. 36 f.).
Die kantonalen Behörden verfügen im Bereich des Straf- und Massnahmenvollzugs über ein weites Ermessen. Das Bundesgericht greift auf Beschwerde in Strafsachen hin nur ein bei Ermessensüberschreitung bzw. -unterschreitung oder Ermessensmissbrauch. Ermessensmissbrauch ist gegeben, wenn die Behörde zwar im Rahmen des ihr eingeräumten Ermessens bleibt, sich aber von unsachlichen, dem Zweck der massgebenden Vorschriften fremden Erwägungen leiten lässt, oder allgemeine Rechtsprinzipien, wie das Verbot von Willkür und von rechtsungleicher Behandlung, das Gebot von Treu und Glauben sowie den Grundsatz der Verhältnismässigkeit verletzt (<ref-ruling> E. 5.1 S. 72 f. mit Hinweis). Dagegen liegt Ermessensüberschreitung vor, wenn die Behörde Ermessen walten lässt, wo ihr das Gesetz keines einräumt, oder wo sie statt zweier zulässiger Lösungen eine dritte wählt. In diesem Zusammenhang ist auch die Ermessensunterschreitung bedeutsam, die darin besteht, dass die entscheidende Behörde sich als gebunden betrachtet, obschon sie nach Gesetz berechtigt wäre, nach Ermessen zu handeln, oder dass sie auf Ermessensausübung ganz oder teilweise von vornherein verzichtet (<ref-ruling> E. 5.2 S. 73; <ref-ruling> E. 2 S. 310; je mit Hinweisen).
2.4. Im vorliegenden Verfahren unterlässt es die Vorinstanz, die gesamten Verhältnisse einzubeziehen und umfassend zu würdigen. Sie hält fest, der Beschwerdegegner habe sich im Vollzug - mit Ausnahme zweier Disziplinierungen - tadellos verhalten. Die Rückfallgefahr für Gewaltstrafen oder Tötungsdelikte sei als gering eingeschätzt worden. Der Vorinstanz ist sodann zuzustimmen, dass es angesichts der Unterhaltspflichten für seinen Sohn nicht sehr negativ ins Gewicht fällt, dass der Beschwerdegegner noch keine Wiedergutmachtungszahlungen geleistet hat. Das von der Beschwerdeführerin vorgebrachte Argument der beträchtlichen Schuldensumme des Beschwerdegegners als zusätzlicher Anreiz zu einer Flucht ist in der vorliegenden Konstellation kein allzu wesentliches Element bei der Prüfung der Urlaubsgewährung, aber dennoch eines, das es einzubeziehen gilt. Der Beschwerdegegner wird die Schweiz unabhängig von einer allfälligen Flucht verlassen (müssen), wodurch es ohnehin schwieriger wird, von ihm nicht bezahlte Schulden zu vollstrecken. Die Beschwerdeführerin weist allerdings zu Recht darauf hin, dass die Vorinstanz ausser Acht lässt, dass der Beschwerdegegner zu 13 Jahre Freiheitsstrafe verurteilt wurde. Er würde frühestens in ca. zwei Jahren bedingt entlassen werden. Dies ist eine hinreichend lange Zeit, um ein starkes Indiz daran zu begründen, der weiteren Strafverbüssung auszuweichen und die ohnehin bevorstehende Ausreise aus der Schweiz vorzuverschieben. Der Beschwerdegegner beabsichtigt, nach Deutschland zurückzukehren (wie im Fall, der BGE <ref-ruling> zugrunde lag), wo seine Eltern und sein siebenjähriger Sohn leben. Er hat weder ein Interesse am weiteren Verbleib in der Schweiz noch verfügt er über ein tragfähiges Beziehungsnetz hier in diesem Land. Schliesslich würdigt die Vorinstanz nicht, dass die dem ursprünglichen Gesuch um Urlaub zugrunde liegende Gedenkfeier in Rheinau, nahe der deutschen Grenze, stattfinden sollte und sich der Beschwerdegegner weder bereit erklärte, begleitet zu werden noch in eine Verschiebung der Feier in die Vollzugsanstalt einwilligte. Dadurch wird zusätzlich der Anschein erweckt, dass es ihm entgegen seinen Beteuerungen nicht nur um das Gedenken an seine verstorbene Tochter und das Verbringen dieses Moments mit den Familienangehörigen ging. Im Lichte aller Umstände liegen damit insgesamt konkrete Gründe vor, die eine Flucht als wahrscheinlich erscheinen lassen. Ausserdem ist zum jetzigen Zeitpunkt das öffentliche Interesse an einer Wiedereingliederung des Beschwerdegegners in die Gesellschaft und dessen Resozialisierung noch nicht als gewichtig zu bezeichnen. Die Beschwerde erweist sich als begründet.
3.
Die Beschwerde ist gutzuheissen, der angefochtene Entscheid aufzuheben und die Sache zur neuen Beurteilung an die Vorinstanz zurückzuweisen.
Das Gesuch des Beschwerdegegners um unentgeltliche Rechtspflege ist gutzuheissen, da dessen Bedürftigkeit erstellt scheint. Dieser trägt daher keine Gerichtskosten und seine Rechtsanwältin ist für ihre Aufwendungen im bundesgerichtlichen Verfahren aus der Bundesgerichtskasse zu entschädigen.

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird gutgeheissen, das Urteil des Verwaltungsgerichts des Kantons Zürich vom 18. Dezember 2018 aufgehoben und die Sache zu neuer Beurteilung an die Vorinstanz zurückgewiesen.
2.
Das Gesuch des Beschwerdegegners um unentgeltliche Rechtspflege wird gutgeheissen.
3.
Es werden keine Kosten erhoben.
4.
Rechtsanwältin Denise Kramer-Oswald wird für das bundesgerichtliche Verfahren aus der Gerichtskasse eine Entschädigung von Fr. 3'000.-- ausgerichtet.
5.
Dieses Urteil wird den Parteien und dem Verwaltungsgericht des Kantons Zürich, 3. Abteilung, Einzelrichterin, schriftlich mitgeteilt.
Lausanne, 12. Dezember 2019
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Denys
Die Gerichtsschreiberin: Pasquini