Given a mixed graph $G=(V,E,A)$ with edges $E$ and arcs $A$, find a matching in $E$ that minimizes the number of arcs in $G/M$, where $G/M$ is obtained from $G$ by contracting matched vertices and removing parallel arcs.
Is (the decision version of) this problem NP-complete? Has it been studied in the literature?
I do not know if your intent is to allow undirected edges in E and arcs in A to be parallel or not, but it does not matter in the end. In this answer, we assume that you do not allow edges and arcs to be parallel.
Consider a special case where for each arc in A, A also contains the arc in the opposite direction. In this case, we can ignore the orientation of arcs and consider them to be undirected. We call edges in E black edges and edges in A red edges.
Even under these two restrictions, the problem is NP-complete by a reduction from Max-2SAT. Let φ be a 2CNF formula in n variables $x_1,\dots,x_n$ with m clauses. Construct a graph G with 3n vertices $v_1,\dots,v_n,x_1,\dots,x_n,\bar{x}_1,\dots,\bar{x}_n$ as follows. G has 2n black edges: $(v_i,x_i)$ and $(v_i,\bar{x}_i)$ for i=1,…,n. G has $5\binom{n}{2}-m$ red edges. First, connect $v_i$ and $v_j$ for i≠j by a red edge. Next, for every distinct variables $x_i$ and $x_j$, consider four pairs of literals $(l,l')=(x_i,x_j),(x_i,\bar{x}_j),(\bar{x}_i,x_j),(\bar{x}_i,\bar{x}_j)$. Connect literals $l$ and $l'$ by a red edge if and only if clause $(\bar{l}\vee\bar{l}')$ does not appear in φ.
It is clear that we only have to consider maximal matchings in black edges in order to minimize the number of red edges after contraction. It is also clear that every maximal matching M in black edges consists of n edges connecting $v_i$ to $l_i\in\{x_i,\bar{x}_i\}$ for i=1,…,n. Identify this maximal matching M with truth assignment $\{l_1,\dots,l_n\}$. It is easy to verify that after contracting M and removing parallel edges, the graph has exactly $4\binom{n}{2}-k$ red edges, where k is the number of clauses satisfied by this truth assignment. Therefore, minimizing the number of red edges after contracting a matching in black edges is equivalent to maximizing the number of satisfied clauses.
