In dem OFFIS Projekt Fahrgemeinschaften (Oldenburger Forschung- und Entwicklungsinstitut Für Informatik-Werkzeuge und -Systeme) hat sich gezeigt, daß die Einteilung einer gegebenen Personenmenge in Fahrgemeinschaften unter der Optimierung einer Zielfunktion äußerst schwierig sein kann. Im allgemeinen soll die Anzahl der Fahrgemeinschaften minimiert werden, wobei keine Fahrgemeinschaft eine bestimmte Umwegschranke (Zeit oder Weglänge) überschreiten darf. Wir haben diese Problemstellung und einige Abwandlungen formalisiert und die Problemkomplexität bestimmt. Wenn nur 2-er Fahrgemeinschaften zugelassen sind, lassen sich die Probleme effizient lösen. Dazu wird der Algorithmus zur Konstruktion eines maximalen Matchings eines Graphen verwendet. Bereits für 3-er Fahrgemeinschaften werden die Probleme NP-hart, auch wenn Nebenbedingungen an die zugrundeliegenden Straßengraphen gestellt werden. In den Reduktionen beziehen wir uns auf folgende Probleme: 3-dimensionales Matching, Exact Cover und Euklidischer Traveling Salesman. Offen geblieben ist, ob sich das Fahrgemeinschafts-Problem effizient lösen läßt, wenn die Start- und Zielorte aller Personen auf einer Geraden liegen