Sachverhalt:
A.
A._ und B.B._ sind die geschiedenen Eltern von C.B._ (geb. 1999).
B.
B.a. Am 19. November 2013 entzog die Kindes- und Erwachsenenschutzbehörde des Kantons Appenzell Ausserrhoden (im Folgenden KESB Appenzell Ausserrhoden) der Mutter die Obhut über die Tochter und platzierte diese nach einer vorübergehenden Unterbringung im Haus D._ beim Vater. Weiter wurde für C.B._ eine Beistandschaft errichtet und die elterliche Sorge der Mutter im Bereich Ausbildung beschränkt. Mit der Beistandschaft wurde E._, Berufsbeiständin bei den Sozialen Diensten Vorderland, betraut.
B.b. Gegen diesen Entscheid liess A._ am 14. Dezember 2013 Beschwerde beim Obergericht Appenzell Ausserrhoden erheben.
B.c. Am 12. August 2014 sagte das Obergericht die auf den 18. August 2014 angesetzte mündliche Verhandlung ab, weil zwischen der KESB Appenzell Ausserrhoden und der Beschwerdeführerin ein Gespräch stattgefunden hatte und Erstere eine neue Verfügung in Aussicht stellte. In der Folge wurde das Verfahren beim Obergericht vorläufig ausgesetzt, weil B.B._ in der Zwischenzeit beim Kantonsgericht Appenzell Ausserrhoden eine Klage auf Abänderung des Unterhalts anhängig gemacht hatte. In diesem Verfahren genehmigte die Einzelrichterin des Kantonsgerichts Appenzell Ausserrhoden eine Vereinbarung, in der sich B.B._ und A._ darauf verständigten, dass die Tochter künftig beim Vater wohnen und die Mutter an den Unterhalt der Tochter monatlich Fr. 250.-- bezahlen sollte. Der diesbezügliche Entscheid des Kantonsgerichts erwuchs am 14. Juli 2015 in Rechtskraft.
B.d. Mit Schreiben vom 23. Juli 2015 orientierte das Obergericht die Parteien über die geplante Abschreibung des vor ihm hängigen Beschwerdeverfahrens. Die Parteien erhielten Gelegenheit, sich innert einer Frist von vierzehn Tagen zur Kostenverlegung zu äussern und ihre Kostennoten einzureichen. Die Anwälte beider Parteier nutzten diese Gelegenheit (Eingaben vom 7. und 11. August 2015). Die KESB Appenzell Ausserrhoden verzichtete auf eine Stellungnahme.
B.e. Mit Entscheid vom 23. September 2015 schrieb das Obergericht die Beschwerde von A._ zufolge Gegenstandslosigkeit ab (Ziffer 1) und auferlegte der Beschwerdeführerin die Verfahrenskosten von Fr. 800.-- (Ziffer 2). A._ wurde keine Entschädigung zugesprochen (Ziffer 3.1) und sie wurde verpflichtet, B.B._ für seine Vertretungskosten mit Fr. 6'105.-- (inklusive Barauslagen und Mehrwertsteuer) zu entschädigen (Ziffer 3.2).
C.
C.a. Mit Beschwerde vom 26. Oktober 2015 wendet sich A._ (Beschwerdeführerin) an das Bundesgericht. Sie verlangt, die Ziffern 2, 3.1 und 3.2 des vorinstanzlichen Urteils aufzuheben und ihr zu Lasten der KESB Appenzell Ausserrhoden eine Parteientschädigung von Fr. 4'800.-- zuzusprechen. Eventualiter sei die Angelegenheit zur Neubeurteilung im Sinne der Erwägungen an die Vorinstanz zurückzuweisen. Für das bundesgerichtliche Verfahren ersucht die Beschwerdeführerin um unentgeltliche Rechtspflege.
C.b. Das Bundesgericht hat mit Schreiben vom 27. Oktober 2015 dem Gesuch um aufschiebende Wirkung nicht entsprochen, weil die drohende Vollstreckung von Geldforderungen keine die aufschiebende Wirkung rechtlich geschützter Interessen darstellt.
C.c. Zur Vernehmlassung eingeladen, erklärt das Verwaltungsgericht unter Hinweis auf die Ausführungen im angefochtenen Urteil, auf Gegenbemerkungen zu verzichten (Eingabe vom 18. Februar 2016). Die KESB Appenzell Ausserrhoden beantragt in ihrer Vernehmlassung vom 9. März 2016, die Beschwerde vollumfänglich abzuweisen. Der Beschwerdegegner verzichtet auf ein Rechtsbegehren mit der Erklärung, von den Rechtsbegehren der Beschwerdeführerin nicht direkt betroffen zu sein (Vernehmlassung vom 4. April 2016). Für das Verfahren vor dem Bundesgericht beantragt der Beschwerdegegner die unentgeltliche Rechtspflege. Die Eingaben wurden der Beschwerdeführerin zur Wahrung des rechtlichen Gehörs zur Kenntnis gebracht.
C.d. Am 31. März 2016 hat die Beschwerdeführerin persönlich diverse weitere Dokumente eingereicht, die ihrer Einschätzung nach für die Beurteilung des Falls wichtig und bisher nicht berücksichtigt worden seien.
Erwägungen:
1.
Das Bundesgericht prüft von Amtes wegen und mit freier Kognition, ob die Eintretensvoraussetzungen gegeben sind (BGE 141 II 113 E. 1 S. 116).
2.
Die Beschwerdeführerin wehrt sich dagegen, dass ihr die Vorinstanz für einen Abschreibungsbeschluss in einem Verfahren, das einen Obhutsentzug zum Gegenstand hatte, sowohl die Gerichtskosten als auch eine Entschädigung für den Beschwerdegegner auferlegt hat. Beim Entzug der Obhut geht es um einen nicht vermögensrechtlichen Entscheid auf dem Gebiet des Kindes- und Erwachsenenschutzes (Art. 72 Abs. 1 Bst. b Ziff. 6 BGG). Das Obergericht hat als letzte kantonale Instanz entschieden (Art. 75 BGG; Urteil 5A_852/2013 vom 20. März 2014 E. 1). Der Abschreibungsbeschluss ist ein Endentscheid (Art. 90 BGG). Die Beschwerdeführerin, die am vorinstanzlichen Verfahren teilgenommen hat, weist sich über ein schützenswertes Interesse aus (Art. 76 BGG). Auf die rechtzeitige Beschwerde ist grundsätzlich einzutreten (Art. 100 Abs. 1 i.V.m. Art. 45 Abs. 1 BGG).
3.
Das Bundesgericht legt seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat (Art. 105 Abs. 1 BGG). Neue Tatsachen und Beweismittel dürfen nur so weit vorgebracht werden, als erst der Entscheid der Vorinstanz dazu Anlass gibt (Art. 99 Abs. 1 BGG). Bei den Unterlagen, welche die Beschwerdeführerin nachträglich eingereicht hat, ist dies nicht der Fall. Sie müssen daher unberücksichtigt bleiben.
4.
Das Bundesrecht enthält keine Regel darüber, wie in Streitigkeiten um Kindesschutzmassnahmen die Gerichtskosten und Parteientschädigungen des kantonalen Beschwerdeverfahrens zu verlegen sind. Diese Frage beantwortet sich aufgrund des in Art. 450f ZGB enthaltenen Verweises nach kantonalem Recht (BGE 140 III 167 E. 2.3 S. 169; 140 III 385 E. 2.3 S. 386 f.). Dessen korrekte Anwendung überprüft das Bundesgericht nur auf Willkür hin (BGE 140 III 385 E. 2.3 S. 387; 138 IV 13 E. 2 S. 15; 134 III 379 E. 1.2 S. 382 f.). Die Beschwerdeführerin hat in der Beschwerde klar und detailliert aufzuzeigen, inwiefern die Anwendung des einschlägigen kantonalen Rechts durch die Vorinstanz im konkreten Fall geradezu willkürlich sein soll.
5.
5.1. Die Vorinstanz hat im Zusammenhang mit der Kostenverteilung das Folgende erwogen: Nach Art. 64 Abs. 1 des Gesetzes über die Einführung des Schweizerischen Zivilgesetzbuches des Kantons Appenzell Ausserrhoden vom 27. April 1969 (EG zum ZGB; bGS 211.1) sei auf Verfahren vor der Kindes- und Erwachsenenschutzbehörde und vor Obergericht - unter Vorbehalt abweichender Bestimmungen - das ausserrhodische Gesetz über die Verwaltungsrechtspflege vom 9. September 2002 (VRPG, bGS 143.1) anwendbar. Abweichende Regelungen lägen keine vor. Art. 53 VRPG verweise im 3. Abschnitt "Die Verwaltungsgerichtsbarkeit" generell auf Art. 19 ff. VRPG in den allgemeinen Bestimmungen des 1. Abschnitts. Dabei habe die obsiegende Partei Anspruch auf eine Entschädigung für ihre notwendigen Kosten und Auslagen.
Wer eine Amtshandlung verlange oder veranlasse, habe die Verfahrenskosten zu entrichten. Diese bestünden in einer Gebühr und den Auslagen (Art. 19 Abs. 1 VRPG). Im Rechtsmittelverfahren sei gebühren- und kostenpflichtig, wer ganz oder teilweise unterliege oder auf dessen Rechtsmittel nicht eingetreten werde (Art. 19 Abs. 3 VRPG). Der obsiegenden Partei könnten Gebühren und Kosten ganz oder teilweise auferlegt werden, wenn sie die Voraussetzungen des Obsiegens erst im Rechtsmittelverfahren geschaffen habe (Art. 19 Abs. 4 VRPG). Dem Bund, dem Kanton und den Gemeinden sowie anderen öffentlich-rechtlichen Körperschaften und Anstalten im Kanton würden keine Verfahrenskosten auferlegt (Art. 22 Abs. 1 VRPG). Sei eine Amtshandlung nur mit geringem Aufwand verbunden, bei Nichteintretens- und Abschreibungsbeschlüssen sowie aus Gründen der Billigkeit könne von der Erhebung von Verfahrenskosten ganz oder teilweise abgesehen werden (Art. 22 Abs. 4 VRPG).
Im Rekursverfahren (Art. 30 ff. VRPG) könne der ganz oder teilweise obsiegenden Partei auf Antrag eine angemessene Entschädigung für ihre Kosten und Auslagen zugesprochen werden (Art. 24 Abs. 1 VRPG). Die Parteientschädigung gehe zulasten der unterliegenden Partei. Aus Billigkeitsgründen könne sie auch der Staats- oder Gemeindekasse auferlegt werden (Art. 24 Abs. 2 VRPG). Keine Parteientschädigung werde ausgerichtet an Behörden, ausser im Klageverfahren nach Art. 57 f. VRPG oder bei mutwilliger Prozessführung sowie wenn die Voraussetzungen des Obsiegens erst im Rechtsmittelverfahren geschaffen würden und im Einspracheverfahren (Art. 24 Abs. 3 VRPG).
Werde eine Streitsache zufolge Gegenstandslosigkeit abgeschrieben, so habe nach der Praxis des Verwaltungsgerichtes des Kantons St. Gallen derjenige Beteiligte die Kosten zu tragen, der die Gegenstandslosigkeit verursacht habe. So seien die Kosten im Fall der Gegenstandslosigkeit aufgrund eines Widerrufs der angefochtenen Verfügung oder des angefochtenen Entscheids oder bei einer Wiedererwägung derselben dem entsprechenden Gemeinwesen zu überbinden. Im Fall eines Rückzugs des Baugesuchs im Laufe des Rechtsmittelverfahrens seien die Kosten dem Gesuchsteller aufzuerlegen. Dabei sei nicht auf die Begründung der Gegenstandslosigkeit abzustellen, sondern ausschliesslich darauf, in welchem Mass dem Begehren der Beteiligten infolge der Gegenstandslosigkeit gefolgt werde. Das Verwaltungsgericht habe zudem die in Art. 266 des alten sanktgallischen Zivilprozessgesetzes vom 20. Dezember 1990 (in Kraft bis 31. Dezember 2010) verankerte Regelung, wonach der Richter in gewissen Fällen Prozesskosten nach Ermessen auferlegen könne, auch für den Verwaltungsprozess als anwendbar erklärt. Lasse die Art des Streitfalles die Anwendung des Verursacherprinzips als unverhältnismässig erscheinen, so könnten die Kosten demjenigen auferlegt werden, der den Prozess veranlasst habe. Lasse sich nicht mehr feststellen, wer den Grund für die Gegenstandslosigkeit gesetzt habe, oder könne sie keiner am Verfahren beteiligten Partei zugerechnet werden, seien die Verfahrenskosten nach Billigkeit zu verlegen. Dabei könne insbesondere auf den mutmasslichen Prozessausgang vor Eintritt der Gegenstandslosigkeit abgestellt werden, oder die amtlichen Kosten könnten demjenigen auferlegt werden, der den Prozess veranlasst habe.
5.2. Bezug nehmend auf den konkreten Fall hält die Vorinstanz fest, dass das vorliegende Beschwerdeverfahren durch den Entscheid der Einzelrichterin des Kantonsgerichts vom 29. Juni 2015 gegenstandslos geworden sei, wobei das Abänderungsverfahren vom Beschwerdegegner eingeleitet worden sei. Letztlich habe er mit seiner Abänderungsklage die Gegenstandslosigkeit des vorliegenden Prozesses bewirkt. Veranlasst worden sei das Beschwerdeverfahren hingegen von der Beschwerdeführerin. Wenn man die Vereinbarung zwischen der Beschwerdeführerin und dem Beschwerdegegner im Abänderungsprozess inhaltlich mit den Anträgen im Beschwerdeverfahren vergleiche, ergebe sich, dass die Beschwerdeführerin mit ihren Begehren praktisch vollständig unterlegen sei. Lediglich die Beschränkung der elterlichen Sorge im Bereich Ausbildung sei in der Vereinbarung nicht enthalten. Dafür hätten sich die Eltern anstelle der bisherigen alleinigen elterlichen Sorge der Mutter auf die gemeinsame elterliche Sorge geeinigt.
Richtig sei, dass die Anhörung der Beschwerdeführerin durch die KESB Appenzell Ausserrhoden - zumindest was schriftlich dokumentiert sei - tatsächlich knapp ausgefallen sei. Der Beschwerdeführerin sei aber vor Erlass des angefochtenen Entscheids die Möglichkeit gegeben worden, ihren Standpunkt darzulegen. Dass die KESB Appenzell Ausserrhoden nicht zuerst eine superprovisorische Massnahme im Sinne von Art. 445 Abs. 2 ZGB angeordnet und anschliessend einen vorsorglichen Massnahmeentscheid im Sinne von Art. 445 Abs. 1 ZGB getroffen habe, in dessen Rahmen den Parteien die vollen Parteirechte gewährt worden seien, treffe zu. Es sei allerdings daran zu erinnern, dass das neue Kindes- und Erwachsenenschutzrecht erst per 1. Januar 2013 in Kraft getreten sei, die Kindes- und Erwachsenenbehörden in der Anfangsphase allgemein stark gefordert gewesen seien und sich die Bedeutung verschiedener Bestimmungen in der Übergangszeit noch nicht klar herauskristallisiert hätte. So seien auch die vom Anwalt der Beschwerdeführerin zitierten Entscheide BGE 140 III 289 und 5A_827/2013 des Bundesgerichts erst im März bzw. Juni 2014, das heisst lange nach dem angefochtenen Entscheid der KESB gefällt worden. Schliesslich habe das letztgenannte Urteil ein unverheiratetes Elternpaar betroffen.
Der mutmassliche Ausgang des Beschwerdeverfahrens sei ein mögliches Kriterium für die Verlegung der Kosten bei Gegenstandslosigkeit. Wie oben erwähnt, sei die Beschwerdeführerin materiell als unterliegende Partei anzusehen. Ob ihrer Beschwerde aus formellen Gründen Erfolg beschieden gewesen wäre, stehe demgegenüber nicht fest. Die Beurteilung des mutmasslichen Prozessausganges erfolge auf Grund einer lediglich summarischen Prüfung, bei der nicht auf alle Rügen einzeln und detailliert einzugehen sei, und mit bloss summarischer Begründung, weil nicht auf dem Weg über den Kostenentscheid ein materielles Urteil gefällt oder vorweggenommen werden dürfe. Lasse sich der mutmassliche Ausgang des Verfahrens nicht ohne weiteres feststellen, sei auf allgemeine prozessrechtliche Kriterien zurückzugreifen. Danach werde in erster Linie jene Partei kosten- und entschädigungspflichtig, die das gegenstandslos gewordene Verfahren veranlasst habe oder bei der die Gründe eingetreten seien, die zur Gegenstandslosigkeit des Verfahrens geführt hätten. Die Regelung bezwecke, denjenigen, der in guten Treuen Beschwerde erhoben habe, nicht im Kostenpunkt dafür zu bestrafen, dass die Beschwerde infolge nachträglicher Änderung der Umstände abzuschreiben sei, ohne dass ihm dies anzulasten wäre.
Zusammenfassend sei festzustellen, dass die Gegenstandslosigkeit des vorliegenden Beschwerdeverfahrens auf das Abänderungsbegehren des Beschwerdegegners beim Kantonsgericht zurückzuführen sei. Mit der Anpassung des Scheidungsurteils werde allerdings nur der Veränderung der tatsächlichen Verhältnisse, konkret der Tatsache, dass die Tochter aufgrund des Zerwürfnisses mit der Mutter künftig beim Vater leben werde, in rechtlicher Hinsicht Rechnung getragen. Zu diesem Schritt sei der Vater aufgrund der fehlenden Regelung der Unterhaltskosten quasi gezwungen gewesen. Veranlasst worden sei das Beschwerdeverfahren durch die Beschwerdeführerin. Wenn man die im Beschwerdeverfahren gestellten Anträge mit der Vereinbarung der Eltern im Abänderungsverfahren vergleiche, die von der Einzelrichterin auch genehmigt worden seien, sei die Beschwerdeführerin materiell als unterliegende Partei anzusehen. In formeller Hinsicht bestünden gegenüber dem Vorgehen der KESB zwar gewisse Vorbehalte. Letztlich hätten diese Rügen aber nicht detailliert geprüft werden müssen und es sei offen, ob der Entscheid der KESB vom 19. November 2013 vom Obergericht aus formellen Gründen aufgehoben worden wäre, wenn es zu einer entsprechenden Beurteilung gekommen wäre. Bei dieser Ausgangslage wäre es unbillig, in erster Linie darauf abzustellen, wer die Gegenstandslosigkeit verursacht habe. Vielmehr erscheine es angemessen, die amtlichen Kosten vollumfänglich der Beschwerdeführerin, die das Verfahren veranlasst habe und - zumindest materiell - vollumfänglich unterlegen sei, aufzuerlegen und diese auch zu verpflichten, den Beschwerdegegner für seine Vertretungskosten im Beschwerdeverfahren zu entschädigen (Art. 53 Abs. 3 in Verbindung mit Art. 24 Abs. 2 VRPG).
6.
6.1. Die Beschwerdeführerin rügt eine Verletzung des rechtlichen Gehörs (Art. 29 Abs. 2 BV, Art. 6 Ziff. 1 EMRK) und begründet dies damit, dass die Vorinstanz in ihrem Entscheid gerade einmal mit einem Nebensatz auf das - für die materielle Ausgangslage des Beschwerdeverfahrens - entscheidende bundesgerichtliche Urteil 5A_827/2013 eingegangen sei.
6.2. Die Begründungspflicht, wie sie sich aus dem verfassungsmässigen Gehörsanspruch (Art. 29 Abs. 2 BV) ergibt, bedeutet nicht, dass sich die Behörde zu allen Punkten einlässlich äussern und jedes einzelne Vorbringen widerlegen muss (vgl. zum Ganzen BGE 134 I 83 E. 4.1 S. 88; 133 III 439 E. 3.3 S. 445). Zu begründen ist das Ergebnis des Entscheides, das im Urteilsdispositiv zum Ausdruck kommt und das allein die Rechtsstellung der betroffenen Person berührt. Über dessen Tragweite - und nicht über ihm zugrunde liegende Erwägungen - soll sich die betroffene Person Rechenschaft geben können (Urteil 5A_382/2013 vom 12. September 2013 E. 3.1). Eingedenk dessen erweist sich der Tadel der Beschwerdeführerin als unbegründet.
7.
7.1. In der Sache macht die Beschwerdeführerin geltend, dass die Vorinstanz ihre Prozessaussichten im Beschwerdeverfahren vor Obergericht falsch eingeschätzt habe. Die KESB Appenzell Ausserrhoden habe ihr am 19. November 2013 die Obhut sowie die alleinige elterliche Sorge im Bereich Ausbildung über ihre Tochter C.B._ von einem Tag auf den andern entzogen. Diesen Entscheid habe sie fristgerecht angefochten. Mit Entscheid vom 3. Februar 2014 habe das Obergericht Appenzell Ausserrhoden den Antrag auf Wiederherstellung der aufschiebenden Wirkung abgewiesen. Das rechtliche Gehör vor dem Obhutsentzug und dem partiellen Entzug der elterlichen Sorge habe in einer kurzen telefonischen Mitteilung der zuständigen Sachbearbeiterin der KESB Appenzell Ausserrhoden bestanden. Eine richtige Anhörung von ihr, der Beschwerdeführerin und Kindsmutter, sei nicht erfolgt. Auch nach Auffassung der Vorinstanz habe die KESB Appenzell Ausserrhoden beim Obhutsentzug ihren Anspruch auf rechtliches Gehör missachtet.
Spätestens mit Eingang der Stellungnahme der Beiständin vom 28. Mai 2014 sei der einfache Schriftenwechsel vor der Vorinstanz abgeschlossen gewesen. Die Eingabe des Vertreters des Kindsvaters vom 11. April 2014 habe gerade einmal fünf Seiten umfasst. Weitere umfangreiche Eingaben des Kindsvaters habe es nicht gegeben.
Am 9. Juli 2014 habe die KESB Appenzell Ausserrhoden auf Anregung der Vorinstanz unter dem Titel "Wiedererwägung" eine Anhörung der Kindsmutter durchgeführt. In der Folge hätten die Kindseltern unter Federführung der KESB Appenzell Ausserrhoden Vergleichsverhandlungen aufgenommen, so dass die Vorinstanz schliesslich die auf den 18. August 2014 anberaumte Hauptverhandlung abgesagt habe. Die anschliessenden Vergleichsverhandlungen seien an der Höhe des Kindesunterhaltes und der elterlichen Sorge gescheitert. Der Kindsvater habe daraufhin Klage beim Kantonsgericht betreffend Abänderung des Scheidungsurteils eingereicht. Darin habe er u.a. die alleinige elterliche Sorge, einen Kindesunterhalt von Fr. 800.-- bzw. 900.-- pro Monat sowie die alleinige elterliche Obhut verlangt. Die Parteien hätten schliesslich unter Mitwirkung der zuständigen Einzelrichterineinen ausgewogenen Vergleich geschlossen (s. Sachverhalt Bst. B.c).
7.2. Ob die Vorinstanz die Aussichten der Beschwerdeführerin, im Beschwerdeverfahren zu obsiegen, richtig eingeschätzt hat, betrifft eine Rechtsfrage. Dabei ist zu beachten, dass sie sich im Fall eines Abschreibungsbeschlusses mit einer Prognose begnügen musste, aber auch durfte. Dies ist zu berücksichtigen, wenn vom Bundesgericht eine Überprüfung dieser Prognose erwartet wird. Das Bundesgericht schreitet nur ein, wenn sich die Prozessprognose bei summarischer Prüfung der Rechtslage als unhaltbar erweist. Im konkreten Fall hat die Vorinstanz die Schwächen des Entscheids der KESB Appenzell Ausserrhoden vom 19. November 2013 nicht verschwiegen, diese aber nicht als derart gravierend betrachtet, dass deswegen zwingend auf die Gutheissung der Beschwerde hätte geschlossen werden müssen. Was die Beschwerdeführerin dagegen vorträgt, stellt diese Prognose nicht in Frage. Den von der Beschwerdeführerin zitierten bundesgerichtlichen Urteilen 5A_827/2013 vom 7. März 2014 und BGE 140 III 289 ff. liegt ein Sachverhalt zugrunde, der sich nicht eins zu ein eins auf den vorliegenden Fall übertragen lässt. Die blosse Behauptung, die Vorinstanz hätte mit ihrem Kostenentscheid gegen den Grundsatz eines fairen Verfahrens, gegen Treu und Glauben sowie gegen das Verbot widersprüchlichen Verhaltens verstossen (Art. 5 Abs. 3 BV; Art. 9 BV, Art. 6 Ziff. 1 EMRK, Art. 52 ZPO i.V.m. Art. 450f ZGB), ersetzt keine dem Rügeprinzip genügende Auseinandersetzung mit dem vorinstanzlichen Entscheid. Dies gilt auch für die Behauptung der Beschwerdeführerin, die Vorinstanz verletze mit ihrem einseitigen Kostenentscheid Art. 8 und Art. 14 EMRK.
8.
8.1. Die Beschwerdeführerin stört sich weiter daran, dass die Vorinstanz sie als vollumfänglich unterlegene Partei betrachtet habe. Zu diesem (falschen) Schluss sei die Vorinstanz nur deshalb gekommen, weil sie es unterlassen habe, die Anträge der Parteien einem Gesamtvergleich der Anträge vor dem Obergericht und dem Kantonsgericht zu unterziehen. Insbesondere habe es die Vorinstanz unter Verletzung des rechtlichen Gehörs unterlassen zu prüfen, inwieweit der Beschwerdegegner mit seinen Anträgen vor Kantonsgericht mit seinen Vorstellungen punkto Kindesunterhalt und elterliche Sorge unterlegen sein könnte. Die Vorinstanz habe die entsprechende Klageschrift weder erwähnt noch gelesen. Die Klageschrift bzw. die Anträge des Beschwerdegegners seien für die Beurteilung, ob sie, die Beschwerdeführerin, trotz der aufgezeigten Mängel durch die KESB Appenzell Ausserrhoden als völlig unterlegen zu betrachten sei, von erheblicher Bedeutung. Aus diesem Grund würden die entsprechenden Passagen aus der Klage und dem Entscheid des Kantonsgerichts denn auch nochmals eingereicht.
Die Vorinstanz habe den vor dem Kantonsgericht abgeschlossenen Vergleich in Erwägung 9 nur unvollständig wiedergegeben. Insbesondere habe die Vorinstanz nicht erwähnt, dass die Kindseltern bezüglich der Kostentragung im Verfahren betreffend der Kindesbelange vor Kantonsgericht folgende Vereinbarung getroffen hätten: "Ziff. 9: Die Parteien übernehmen die Gerichtsgebühren je zur Hälfte - Ziff. 10: Jede Partei trägt ihre Anwalts- und Umtriebskosten selbst"
8.2. Fest steht, dass die Beschwerdeführerin im Abänderungsprozess die Obhut über ihre Tochter verloren hat. In diesem zentralen Punkt hat sich die Beschwerdeführerin als Beklagte im Streit um die Abänderung des Scheidungsurteils nicht durchgesetzt. Vor diesem Hintergrund ist es nicht zu beanstanden und schon gar nicht willkürlich, wenn die Vorinstanz die Beschwerdeführerin auch mit Blick auf den mutmasslichen Ausgang des Beschwerdeverfahrens als in der Sache unterliegende Partei betrachtet hat. Dass die Beschwerdeführerin im Abänderungsverfahren in einzelnen Punkten auch Erfolge verbuchen konnte, tut dieser Einschätzung keinen Abbruch. Im Übrigen scheitert die von der Beschwerdeführerin geforderte Gegenüberstellung von Abänderungsklage und Beschwerdeverfahren allein schon daran, dass die beiden Verfahren unterschiedliche Fragen zum Gegenstand haben. Während es im Beschwerdeverfahren vor dem Obergericht allein um den Entzug der Obhut über die Tochter und deren Unterbringung ging (s. Sachverhalt Bst. B.a), hatte das Abänderungsverfahren vor dem Kantonsgericht insbesondere auch den Kindesunterhalt zum Gegenstand. Bleibt es dabei, dass die Beschwerdeführerin auch im gegenstandslos gewordenen Beschwerdeverfahren als unterliegende Partei zu gelten hat, so erübrigen sich Erörterungen zum Begehren, mit dem die Beschwerdeführerin eine Parteientschädigung zu Lasten der KESB Appenzell Ausserrhoden fordert. Abgesehen davon tut die Beschwerdeführerin auch nicht in einer dem Rügeprinzip (E. 4) genügenden Art und Weise dar, weshalb die Anwendung des kantonalen Rechts ihr gegenüber der KESB Appenzell Ausserrhoden einen Entschädigungsanspruch verschaffen würde.
9.
Die Beschwerdeführerin wirft der Vorinstanz in einem weiteren Punkt vor, die Verfahrenskosten fälschlicherweise aufgrund des VRPG statt anhand der Grundsätze von Art. 106 ZPO verteilt zu haben. Wie es sich damit verhält, kann offen bleiben, tut die Beschwerdeführerin doch nicht dar, weshalb Art. 106 ZPO auf das Beschwerdeverfahren vor dem Obergericht überhaupt Anwendung finden sollte. Es mag denn auch zutreffen, dass sich die Parteien in ihrem gerichtlich genehmigten Unterhaltsvereinbarung dazu verpflichtet haben, die Gerichtskosten hälftig zu übernehmen und die Parteikosten wettzuschlagen. Bedeutung konnte diese Vereinbarung aber zum vorneherein nur im Abänderungsverfahren vor dem Kantonsgericht entfalten. Die Vorinstanz wurde durch diese gerichtlich homologierte Abmachung hingegen nicht gebunden. Daran ändert auch die Behauptung der Beschwerdeführerin nichts, dass das Vorgehen der Vorinstanz dem Gerechtigkeitsempfinden widerspreche.
10.
In einem letzten Punkt kritisiert die Beschwerdeführerin die Höhe der Parteientschädigung, die sie dem Beschwerdegegner zu bezahlen hat (s. Sachverhalt Bst. B.e).
10.1. Die Vorinstanz hält fest, die Kostennote des Anwalts des Beschwerdegegners, die auch das Verfahren ERV 13 127 vor dem Einzelrichter des Obergerichts abdecke, sei grundsätzlich tarifkonform. Allerdings sei anzumerken, dass das mittlere Stundenhonorar im Kanton Appenzell Ausserrhoden lediglich Fr. 200.-- und nicht Fr. 250.-- betrage. Die Vorinstanz verweist hierzu auf Art. 13 Abs. 2 i.V.m. Art. 19 Abs. 1 der kantonalen Verordnung über den Anwaltstarif vom 14. März 1995 (bGS 145.53). Daher habe die Beschwerdeführerin den Beschwerdegegner mit Fr. 6'105.-- (inklusive Barauslagen und Mehrwertsteuer) zu entschädigen.
10.2. Die Beschwerdeführerin klagt, die zugesprochene Entschädigung liege sogar über dem absoluten Maximum der im Kanton Appenzell Ausserrhoden zu beachtenden Honorarpauschale für familienrechtliche Angelegenheiten gemäss Art. 14 Abs. 1 i.V.m. Art. 21 Abs. 2 der erwähnten Tarifverordnung. Sie weist darauf hin, dass es im gegenstandslos gewordenen Verfahren nicht einmal zu einer Hauptverhandlung gekommen sei und der Beschwerdegegner gerade einmal eine rund fünfseitige Eingabe habe einreichen lassen. Mit den Vorschriften, auf die das Obergericht seinen Kostenspruch stützt (E. 10.1), setzt sich die Beschwerdeführerin jedoch in keiner Weise auseinander. Dies aber müsste sie tun, um der Vorinstanz eine verfassungswidrige Anwendung des kantonalen Rechts nachzuweisen. Hierzu genügt es nicht, wenn sie dem angefochtenen Entscheid mit Blick auf die gesetzliche Grundlage einfach ihre eigenen Vorstellungen entgegenhält.
10.3. Weiter beteuert die Beschwerdeführerin, der Schriftenwechsel im kantonalen Beschwerdeverfahren sei bereits im Mai 2014 abgeschlossen gewesen und die Hauptverhandlung abgesagt worden. Ab Juli 2014 hätten die Parteien nur noch Vergleichsgespräche geführt, dies auf Anregung der Vorinstanz via die KESB Appenzell Ausserrhoden, die "ihren formell als klar fehlerhaft bezeichneten Obhutsentzug" habe ausbügeln und eine umfassende Einigung habe erzielen wollen. Trotzdem bürde ihr die Vorinstanz die Aufwendungen des Rechtsvertreters des Beschwerdegegners auch ab Mai/Juni 2014 bis zum Abschluss des Verfahrens zufolge Gegenstandslosigkeit in vollem Umfang auf. Es sei im höchsten Masse willkürlich, wenn die Vorinstanz dem gegnerischen Anwalt trotz umfassender Einigung den Ersatz von Aufwendungen im Zusammenhang mit Vergleichsverhandlungen mit dem Argument zuspreche, dass sie, die Beschwerdeführerin, trotz der von ihr abgeschlossenen, fairen und umfassenden Einigung in vollem Umfang unterlegen sei. Hinzu komme noch, dass das Beschwerdeverfahren auf die formell fehlerhafte Vorgehensweise der KESB Appenzell Ausserrhoden zurückzuführen gewesen sei, was die Vorinstanz sogar zugestehe. Auch diese Einwände sind zum Scheitern verurteilt. Denn die Beschwerdeführerin liefert keinerlei Erklärung dafür, weshalb es ihr trotz der Angaben in der Honorarnote des Beschwerdegegners nicht möglich gewesen wäre, die ab Mitte 2014 angeblich nicht zur Entschädigung berechtigten Aufwandpositionen des Beschwerdegegners zu identifizieren, vom Rechnungsbetrag in Abzug zu bringen und gestützt darauf ein reformatorisches und beziffertes (Eventual-) Begehren zu stellen, das ihre Beanstandungen konkret zum Ausdruck bringt. Allein mit ihren pauschalen Reklamationen vermag sie vor Bundesgericht nichts auszurichten. Daran ändern auch ihre appellatorischen Beteuerungen nichts, wonach das Obergericht sie für ihre Vergleichsbereitschaft bestrafe, indem es ihr die gesamten Kosten des durch die umfassende Einigung gegenstandslos gewordenen Kindesschutzverfahrens auferlege, und damit die Grundsätze der Kostenverteilung im Familienrecht verkenne.
11.
Im Ergebnis erweist sich die Beschwerde als unbegründet. Sie ist abzuweisen. Die Beschwerdeführerin unterliegt. Sie hat deshalb für die Gerichtskosten aufzukommen (Art. 66 Abs. 1 BGG) und den Beschwerdegegner zu entschädigen (Art. 68 Abs.1 und 2 BGG). Die Gesuche der Parteien um unentgeltliche Rechtspflege für das bundesgerichtliche Verfahren können gutgeheissen werden (Art. 64 BGG). Der Rechtsanwalt des Beschwerdegegners ist direkt aus der Bundesgerichtskasse zu entschädigen. Die Parteien haben der Gerichtskasse Ersatz zu leisten, wenn sie später dazu in der Lage sind (Art. 64 Abs. 4 BGG). Der KESB Appenzell Ausserrhoden ist keine Entschädigung geschuldet (Art. 68 Abs. 3 BGG).
Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2.
2.1. Das Gesuch der Beschwerdeführerin um unentgeltliche Rechtspflege für das bundesgerichtliche Verfahren wird gutgeheissen und es wird der Beschwerdeführerin Rechtsanwalt Boris Züst als Rechtsbeistand beigegeben.
2.2. Das Gesuch des Beschwerdegegners um unentgeltliche Verbeiständung für das bundesgerichtliche Verfahren wird gutgeheissen und es wird dem Beschwerdegegner Rechtsanwalt Philip Schneider als Rechtsbeistand beigegeben.
3.
Die Gerichtskosten von Fr. 1'000.-- werden der Beschwerdeführerin auferlegt, indes vorläufig auf die Gerichtskasse genommen.
4.
Die Beschwerdeführerin hat Rechtsanwalt Philip Schneider für das bundesgerichtliche Verfahren mit Fr. 1'500.-- zu entschädigen. Die Entschädigung wird indes vorläufig auf die Gerichtskasse genommen und Rechtsanwalt Philip Schneider aus der Gerichtskasse mit Fr. 1'500.-- entschädigt.
5.
Rechtsanwalt Boris Züst wird aus der Bundesgerichtskasse mit Fr. 1'500.-- entschädigt.
6.
Dieses Urteil wird den Parteien, der Kindes- und Erwachsenenschutzbehörde KESB Appenzell Ausserrhoden und dem Obergericht Appenzell Ausserrhoden, Einzelrichter, schriftlich mitgeteilt.
Lausanne, 17. Mai 2016
Im Namen der II. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: von Werdt
Der Gerichtsschreiber: V. Monn