10
$\begingroup$

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?

|cite|improve this question
$\endgroup$
  • 2
    $\begingroup$ Does it matter whether you have arcs or not ? $\endgroup$ – Suresh Venkat Jul 31 '11 at 19:54
  • $\begingroup$ @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. $\endgroup$ – Marcus Ritt Jul 31 '11 at 20:47
  • 2
    $\begingroup$ ah ok. so really the question could be simplified to just have an undirected graph G, without two sets E and A. $\endgroup$ – Suresh Venkat Jul 31 '11 at 21:49
  • $\begingroup$ 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. $\endgroup$ – Marcus Ritt Aug 1 '11 at 13:35
8
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Thanks! (Typo: the clause should be $(\bar{l}\lor\bar{l'})$.) $\endgroup$ – Marcus Ritt Aug 1 '11 at 16:19
  • $\begingroup$ @Marcus: You are welcome, and thank you for pointing out the typo. $\endgroup$ – Tsuyoshi Ito Aug 1 '11 at 17:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.