I think it is a little bit tricky, because of the different node sets of your both polygons (green polygon A, red different segments of polyon B). Comparing the segments of both polygons give a clue which segments of polygon B will be modified.
Nodes polygon A

Nodes of the "different" segments polygon B

Unfortunally this show only the difference in segment structure, but I hope it is a starting point and it works like this:
After a download and unzip process I've imported the data set using PostgrSQL 9.46, PostGIS 2.1 under Debian Linux Jessie with the commands.
$ createdb gis-se
$ psql gis-se < /usr/share/postgis-2.1/postgis.sql
$ psql gis-se < /usr/share/postgis-2.1/spatial_ref_sys.sql
$ shp2pgsql -S polygon_a | psql gis-se
$ shp2pgsql -S polygon_b | psql gis-se
Assuming that the segments of polygon A are not in B and vice vera, I try to build the difference between the segments of both polygon sets, neglecting the segment membership to the polygons in each group (A or B).
For didactic reasons I formulate the SQL stuff in several views.
Corresponding to this GIS-SE post, I decompose the both polygons into segment tables segments_a
and segments_b
-- Segments of the polygon A
CREATE VIEW segments_a AS SELECT sp, ep
FROM
-- extract the endpoints for every 2-point line segment for each linestring
(SELECT
ST_PointN(geom, generate_series(1, ST_NPoints(geom)-1)) as sp,
ST_PointN(geom, generate_series(2, ST_NPoints(geom) )) as ep
FROM
-- extract the individual linestrings
(SELECT (ST_Dump(ST_Boundary(geom))).geom
FROM polygon_a
) AS linestrings
-- be sure that nothing is scrambled
ORDER BY sp, ep
) AS segments;
The segment table polygon A:
SELECT
st_astext(sp) AS sp,
st_astext(ep) AS ep
FROM segments_a
LIMIT 3;
sp | ep
-------------------------------------------+--------------------------------------------
POINT(-292.268907321861 95.0342877387557) | POINT(-287.118411917425 99.4165242769195)
POINT(-287.118411917425 99.4165242769195) | POINT(-264.62129248575 93.2470010145007)
POINT(-277.459563916327 -44.5629543976138) | POINT(-292.268907321861 95.03428773875
The same procedure was applied to polygon B.
-- Segments of the polygon B
CREATE VIEW segments_b AS SELECT sp, ep
FROM
-- extract the endpoints for every 2-point line segment for each linestring
(SELECT
ST_PointN(geom, generate_series(1, ST_NPoints(geom)-1)) as sp,
ST_PointN(geom, generate_series(2, ST_NPoints(geom) )) as ep
FROM
-- extract the individual linestrings
(SELECT (ST_Dump(ST_Boundary(geom))).geom
FROM polygon_b
) AS linestrings
-- be sure that nothing is scrambled
ORDER BY sp, ep
) AS segments;
The segment table polygon B
SELECT
st_astext(sp) AS sp,
st_astext(ep) AS ep
FROM segments_b
LIMIT 3;
sp | ep
-------------------------------------------+-------------------------------------------
POINT(-292.268907321861 95.0342877387557) | POINT(-287.118411917425 99.4165242769195)
POINT(-287.118411917425 99.4165242769195) | POINT(-264.62129248575 93.2470010145007)
POINT(-277.459563916327 -44.5629543976138) | POINT(-292.268907321861 95.0342877387557)
...
I can build a difference table view named segments_diff_{a,b}
. The difference is given by the non occurence of sorted start or end points in the segment set A and B.
CREATE VIEW segments_diff_a AS
SELECT st_makeline(b.sp, b.ep) as geom
FROM segments_b as b
LEFT JOIN segments_a as a ON (a.sp=b.sp and a.ep = b.ep)
-- filter segments without corresponding stuff in polygon A
WHERE a.sp IS NULL;

And the complemental stuff:
CREATE VIEW segments_diff_b AS
SELECT st_makeline(a.sp, a.ep) as geom
FROM segments_a as a
LEFT JOIN segments_b as b ON (a.sp=b.sp and a.ep = b.ep)
-- filter segments without corresponding stuff in polygon B
WHERE b.sp IS NULL;

Conclusion: To get a proper result for the small little segments you marked with the red arrow, both polygons must have same the node strucure and a intersection step on a node level (inserting vertexes of polygon A in B) is required. The Intersection could be done by:
CREATE VIEW segments_bi AS
SELECT distinct sp, ep
FROM (
SELECT
ST_PointN(geom, generate_series(1, ST_NPoints(geom)-1)) as sp,
ST_PointN(geom, generate_series(2, ST_NPoints(geom) )) as ep
FROM (
SELECT st_difference(b.seg, a.seg) as geom FROM
segments_diff_a as a, segments_diff_b as b
WHERE st_intersects(a.seg, b.seg)
) as cut
) as segments
WHERE sp IS NOT NULL AND ep IS NOT NULL
ORDER BY sp, ep;
But with strange results...
