<p>Given $G$, $C$ and $M$, where $G$ is a graph with maximum degree $3$, $C$ is a hamiltonian cycle of $G$, and $M$ is a matching of $G$.</p>

<p>Let $\mathcal{N}$ be the set of all matching of $C$ with size $|M|$. We want to pick a $N\in \mathcal{N}$, such that the number of cycles in $M\cup N$ is maximized. Here we also define edges in $M\cap N$ to be cycles.</p>

<p>Is this problem NP-hard?</p>

<p>A cool way to visualize the problem is consider $n$ points on a circle and some endpoint disjoint chords between the points. We want to connect adjacent points with disjoint arcs to maximize the number of cycles. </p>

CC BY-SA 3.0
2014-01-31T13:52:51.993Z
A clarification: I tried to visualize the problem, but I don't find a way to build two distinct cycles (using edges in $M \cup N$) that share a common edge (all resulting cycles must be disjoint). Indeed suppose that a node has degree 3 and $e_1,e_2$ are the edges on $C$, and $e_3$ is the chord. Then the matching $M$ contains at most one edge of the three, and the matching $N$ at most one of the three, so all nodes in $M \cup N$ must have degree $\leq 2$. Is it true?
Marzio De Biasi
CC BY-SA 3.0
2014-01-31T14:20:47.630Z
Yes. The structure of $M\cup N$ is very simple.
Chao Xu
CC BY-SA 3.0
2014-01-31T14:34:25.977Z
Ok! So all nodes adjacent to an edge in $M \cap N$ must have degree 1, right?
Marzio De Biasi
CC BY-SA 3.0
2014-01-31T14:42:11.063Z
Yes. If a node adjacent to an edge in $M\cap N$, then the component in $M\cup N$ that contains it is a $K_2$.
Chao Xu
CC BY-SA 3.0
2014-01-31T20:33:27.130Z
Is it true that $M \cap C \subseteq N$ in any optimal solution?
Vinicius dos Santos
CC BY-SA 3.0
2014-02-01T04:28:21.380Z
No. [See this graph](http://i.imgur.com/vSIEMaz.png). The black chords are $M$, and the red arcs are $N$, we can get $3$ cycles. However if we make $M\cap C\subseteq N$, we can't get $3$ cycles. This is caused by the restriction that $|N|=|M|$.
Chao Xu
<ds.algorithms><graph-algorithms>
Union of two matching to maximize the number of cycles
Chao Xu
# Union of two matching to maximize the number of cycles

(Asked by: username_0 on 2014-01-31)

Given $G$, $C$ and $M$, where $G$ is a graph with maximum degree $3$, $C$ is a hamiltonian cycle of $G$, and $M$ is a matching of $G$.

Let $\mathcal{N}$ be the set of all matching of $C$ with size $|M|$. We want to pick a $N\in \mathcal{N}$, such that the number of cycles in $M\cup N$ is maximized. Here we also define edges in $M\cap N$ to be cycles.

Is this problem NP-hard?

A cool way to visualize the problem is consider $n$ points on a circle and some endpoint disjoint chords between the points. We want to connect adjacent points with disjoint arcs to maximize the number of cycles.

**Tags:** ds.algorithms, graph-algorithms

> **Comments:**
> **username_1**: A clarification: I tried to visualize the problem, but I don't find a way to build two distinct cycles (using edges in $M \cup N$) that share a common edge (all resulting cycles must be disjoint). Indeed suppose that a node has degree 3 and $e_1,e_2$ are the edges on $C$, and $e_3$ is the chord. Then the matching $M$ contains at most one edge of the three, and the matching $N$ at most one of the three, so all nodes in $M \cup N$ must have degree $\leq 2$. Is it true?  
> **username_0**: Yes. The structure of $M\cup N$ is very simple.  
> **username_1**: Ok! So all nodes adjacent to an edge in $M \cap N$ must have degree 1, right?  
> **username_0**: Yes. If a node adjacent to an edge in $M\cap N$, then the component in $M\cup N$ that contains it is a $K_2$.  
> **username_2**: Is it true that $M \cap C \subseteq N$ in any optimal solution?  
> **username_0**: No. [See this graph](http://i.imgur.com/vSIEMaz.png). The black chords are $M$, and the red arcs are $N$, we can get $3$ cycles. However if we make $M\cap C\subseteq N$, we can't get $3$ cycles. This is caused by the restriction that $|N|=|M|$.  

---

## 0 answers

