<p>I do not know if your intent is to allow undirected edges in <i>E</i> and arcs in <i>A</i> 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.</p>

<p>Consider a special case where for each arc in <i>A</i>, <i>A</i> 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 <i>E</i> <em>black edges</em> and edges in <i>A</i> <em>red edges</em>.</p>

<p>Even under these two restrictions, the problem is NP-complete by a reduction from Max-2SAT.  Let <i>φ</i> be a 2CNF formula in <i>n</i> variables $x_1,\dots,x_n$ with <i>m</i> clauses.  Construct a graph <i>G</i> with 3<i>n</i> vertices $v_1,\dots,v_n,x_1,\dots,x_n,\bar{x}_1,\dots,\bar{x}_n$ as follows.  <i>G</i> has 2<i>n</i> black edges: $(v_i,x_i)$ and $(v_i,\bar{x}_i)$ for <i>i</i>=1,…,<i>n</i>.  <i>G</i> has $5\binom{n}{2}-m$ red edges.  First, connect $v_i$ and $v_j$ for <i>i</i>≠<i>j</i> by a red edge.  Next, for every distinct variables $x_i$ and $x_j$, consider four pairs of literals $(l,l&#39;)=(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&#39;$ by a red edge if and only if clause $(\bar{l}\vee\bar{l}&#39;)$ does not appear in <i>φ</i>.</p>

<p>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 <i>M</i> in black edges consists of <i>n</i> edges connecting $v_i$ to $l_i\in\{x_i,\bar{x}_i\}$ for <i>i</i>=1,…,<i>n</i>.  Identify this maximal matching <i>M</i> with truth assignment $\{l_1,\dots,l_n\}$.  It is easy to verify that after contracting <i>M</i> and removing parallel edges, the graph has exactly $4\binom{n}{2}-k$ red edges, where <i>k</i> 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.</p>

CC BY-SA 3.0
2011-08-01T16:19:04.667Z
Thanks! (Typo: the clause should be $(\bar{l}\lor\bar{l'})$.)
Marcus Ritt
CC BY-SA 3.0
2011-08-01T17:24:17.123Z
@Marcus: You are welcome, and thank you for pointing out the typo.
Tsuyoshi Ito
CC BY-SA 3.0
2011-08-01T13:59:18.197Z
2011-08-01T17:23:23.003Z
2011-08-01T17:23:23.003Z
Tsuyoshi Ito
<p>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.</p>

<p>Is (the decision version of) this problem NP-complete? Has it been studied in the literature?</p>

CC BY-SA 3.0
2011-07-31T19:54:00.453Z
Does it matter whether you have arcs or not ?
Suresh Venkat
CC BY-SA 3.0
2011-07-31T20:47:20.060Z
@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
CC BY-SA 3.0
2011-07-31T21:49:48.587Z
ah ok. so really the question could be simplified to just have an undirected graph G, without two sets E and A.
Suresh Venkat
CC BY-SA 3.0
2011-08-01T13:35:50.487Z
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
<cc.complexity-theory><reference-request><graph-theory>
Finding a matching whose contraction minimizes the number of arcs in a graph
Marcus Ritt
# Finding a matching whose contraction minimizes the number of arcs in a graph

(Asked by: username_0 on 2011-07-31)

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?

**Tags:** cc.complexity-theory, reference-request, graph-theory
> **Comments:**
> **username_1**: Does it matter whether you have arcs or not ?  
> **username_0**: @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.  
> **username_1**: ah ok. so really the question could be simplified to just have an undirected graph G, without two sets E and A.  
> **username_0**: 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.  

---

## 1 answers

### Answer by username_2 on 2011-08-01. Score: 8 | Accepted 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 3*n* vertices $v\_1,\dots,v\_n,x\_1,\dots,x\_n,\bar{x}\_1,\dots,\bar{x}\_n$ as follows. *G* has 2*n* 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.

> **Comments:**
> **username_0**: Thanks! (Typo: the clause should be $(\bar{l}\lor\bar{l'})$.)  
> **username_2**: @Marcus: You are welcome, and thank you for pointing out the typo.  

---

