# Finding a matching whose contraction minimizes the number of arcs in a graph

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?

• Does it matter whether you have arcs or not ? – Suresh Venkat Jul 31 '11 at 19:54
• @Suresh: Actually not, $A$ could be undirected. The point is that one set of edges defines what vertices can be matched and the matching minimizes the number of edges after contraction in the other set of edges. – Marcus Ritt Jul 31 '11 at 20:47
• ah ok. so really the question could be simplified to just have an undirected graph G, without two sets E and A. – Suresh Venkat Jul 31 '11 at 21:49
• I'm not sure. When the edges are undirected, we can reduce the problem to the directed case by substituting each edge by two directed ones; but in the directed case, the number of arcs after contraction depends on their direction, since two arcs between the same vertices need not be parallel. So simply disregarding the direction of the arcs, the optimal matching may be different. – Marcus Ritt Aug 1 '11 at 13:35

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 ij 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.
• Thanks! (Typo: the clause should be $(\bar{l}\lor\bar{l'})$.) – Marcus Ritt Aug 1 '11 at 16:19