Sachverhalt: A. Mit Urteil des Strafgerichts Schwyz vom 8. Oktober 2013 wurde B._ wegen mehrfacher Vergewaltigung, begangen je einfach zum Nachteil von C._ und D._, sowie sexueller Nötigung und mehrfacher sexueller Belästigung zum Nachteil von C._ zu einer Freiheitsstrafe von 30 Monaten und einer Busse von Fr. 1'000.-- verurteilt. Mit Urteil vom 7. Oktober 2014 reduzierte das Kantonsgericht Schwyz das Strafmass auf 24 Monate Freiheitsstrafe. Eine dagegen erhobene Beschwerde hiess das Bundesgericht mit Urteil 6B_318/2015 vom 28. Oktober 2015 in Bezug auf den Schuldspruch wegen Vergewaltigung zum Nachteil von D._ gut, hob das Urteil des Kantonsgerichts Schwyz vom 7. Oktober 2014 auf und wies die Sache zu neuer Entscheidung an das Kantonsgericht Schwyz zurück. C._ war vom 18. Juli 2011 bis 13. März 2012 Patientin von Dr. med. A._, in deren Praxis zu jener Zeit auch E._ als medizinische Praxisassistentin tätig war. B. Am 20./28. Juli 2016 ersuchte A._ das Gesundheitsdepartement des Kantons St. Gallen für sich und E._ um Entbindung vom Berufsgeheimnis in Bezug auf ihre Patientin C._, um im Rahmen eines allfälligen Revisionsverfahrens gegen die Verurteilung von B._ wegen Vergewaltigung aussagen zu dürfen. Der Gesundheitsrat des Kantons St. Gallen wies das Gesuch mit Verfügung vom 4. November 2016 ab. Einer dagegen gerichteten Beschwerde an das Verwaltungsgericht des Kantons St. Gallen war kein Erfolg beschieden (Zirkulationsentscheid vom 20. Februar 2018). C. Gegen den Zirkulationsentscheid des Verwaltungsgerichts vom 20. Februar 2018 gelangen A._ (Beschwerdeführerin 1) und B._ (Beschwerdeführer 2) mit gemeinsamer Eingabe vom 20. März 2018 an das Bundesgericht. Sie beantragen, den vorinstanzlichen Entscheid aufzuheben und A._ sowie ihre ehemalige Praxisassistentin E._ von der beruflichen Schweigepflicht im Hinblick auf ihre frühere Patientin C._ zu befreien. Eventualiter sei das Verfahren zum neuen Entscheid an das Verwaltungsgericht des Kantons St. Gallen zurückzuweisen. Das Verwaltungsgericht beantragt die Abweisung der Beschwerde. Die zur Stellungnahme eingeladene C._ und der Gesundheitsrat des Kantons St. Gallen liessen sich nicht vernehmen.