Optimal Solution is of length 8:

cabababc

Greedy Hierarchical Solution is of length 10:

cababcbaba

initial hierarchical graph

we first process input strings

ababc is an input string hence we add two bottom edges to it: abab->ababc->babc

baba is an input string hence we add two bottom edges to it: bab->baba->aba

cabab is an input string hence we add two bottom edges to it: caba->cabab->abab

we now process nodes from top to bottom in lexicographical ordering

consider node abab

abab is balanced, skip it

consider node baba

baba is balanced, skip it

consider node babc

to balance babc, add edge babc->abc

consider node caba

to balance caba, add edge cab->caba

consider node aba

to balance aba, add edge aba->ba

consider node abc

to balance abc, add edge abc->bc

consider node bab

to balance bab, add edge ba->bab

consider node cab

to balance cab, add edge ca->cab

consider node ba

adding edges b->ba->a to connect the component to eps

consider node bc

to balance bc, add edge bc->c

consider node ca

to balance ca, add edge c->ca

consider node a

to balance a, add edge a->eps

consider node b

to balance b, add edge eps->b

consider node c

adding edges eps->c->eps to connect the component to eps

Done!

this is the greedy hierarchical solution: cababcbaba

this is the initial solution: cabababc

we now double every edge of the initial solution

we now start collapsing

process ababc

we will now collapse the edges abab->ababc->babc

ababc is an input node so we cannot collapse its pair of edges

process cabab

we will now collapse the edges caba->cabab->abab

cabab is an input node so we cannot collapse its pair of edges

process abab

we will now collapse the edges aba->abab->bab

there no lower edges, skip this node

process baba

we will now collapse the edges bab->baba->aba

baba is an input node so we cannot collapse its pair of edges

process babc

we will now collapse the edges bab->babc->abc

process caba

we will now collapse the edges cab->caba->aba

process aba

we will now collapse the edges ab->aba->ba

process abc

we will now collapse the edges ab->abc->bc

process bab

we will now collapse the edges ba->bab->ab

process cab

we will now collapse the edges ca->cab->ab

process ab

we will now collapse the edges a->ab->b

process ba

we will now collapse the edges b->ba->a

the pair of edges b->ba->a cannot be mirrored as it would break connectivity

process bc

we will now collapse the edges b->bc->c

process ca

we will now collapse the edges c->ca->a

process a

we will now collapse the edges eps->a->eps

process b

we will now collapse the edges eps->b->eps

process c

we will now collapse the edges eps->c->eps

the pair of edges eps->c->eps cannot be mirrored as it would break connectivity

this is the initial solution: babacababc