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 ? Jul 31, 2011 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. Jul 31, 2011 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. Jul 31, 2011 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. Aug 1, 2011 at 13:35

1 Answer

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 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'})$.) Aug 1, 2011 at 16:19
• @Marcus: You are welcome, and thank you for pointing out the typo. Aug 1, 2011 at 17:24