<p>Surprise! (for me).<br>
This type of matchings are already studied in the literature. They are called <strong>connected matchings</strong>.</p>

<p>They were introduced by Plummer, Stiebitz and Toft in their study on Hadwiger conjecture. See the chapter "Connected Matchings" by Cameron in the book "Combinatorial Optimization – Eureka, You Shrink!"</p>

<p>The status of connected matchings in bipartite graphs (not necessary balanced) is open to the best of my knowledge (<em>i shall update</em>). The weighted version of the problem is NP-complete for bipartite graphs. The problem is polynomial time solvable for chordal bipartite graphs.</p>

<p>Update: the problem is <strong>NP-complete for balanced bipartite graphs</strong> (i.e., the exact problem asked in the question). This is proved in the paper "<a href="https://arxiv.org/abs/1809.02835v1" rel="nofollow noreferrer">Multitasking Capacity: Hardness Results and Improved Constructions</a>" by Alon et al.  They also report that finding the size of a largest connected matching is hard to approximate within a factor of <span class="math-container">$n^{1-\epsilon}$</span> unless NP = co-RP.</p>

<p>Notes added earlier (kept for interested people):<br>
"<a href="https://www.sciencedirect.com/science/article/pii/S1572528614000322?via%3Dihub" rel="nofollow noreferrer">Connected matchings in chordal bipartite graphs</a>" by Jobson et al. (doi:<a href="https://doi.org/10.1016/j.disopt.2014.06.003" rel="nofollow noreferrer">https://doi.org/10.1016/j.disopt.2014.06.003</a>) and "<a href="https://ir.library.louisville.edu/etd/206/" rel="nofollow noreferrer">Connected matchings in special families of graphs</a>" by Caragianis (thesis) are two notable references.</p>

CC BY-SA 4.0
2019-11-29T16:46:50.443Z
2019-11-30T09:59:48.373Z
2019-11-30T09:59:48.373Z
Cyriac Antony
<p>There is another way to put this question. Is there a perfect matching $M$ of a balanced bipartite graph $G$ such that every pair of edges in $M$ is exactly at a distance 1 from each other in $G$ ?<br/>
( The distance between edges $e$ and $e’$ is the length of a shortest path from a vertex of $e$ to a vertex of $e’$).</p>

<p>Owing to this, the extra condition reduces to finding a subset of vertices from the line graph $L(G)$ of $G$ which are pairwise at a distance exactly 2. Thus the problem of <strong>finding a maximum size set of vertices at distance exactly 2</strong> from each other is a candidate problem (to be a close one to the problem in question). In the recent paper <em>On the algorithmic aspects of strong subcoloring</em> (by M.A. Shalu,S. Vijayakumar,S. Devi Yamini and T.P. Sandhya), they call this problem strong set.</p>

<p>Stong set problem is known to be NP-complete in some graph classes. I don't know its status on line graphs of bipartite graphs. The paper says it is NP-complete on bipartite graphs. Our interest here will be in the class of line graphs of bipartite graphs.</p>

CC BY-SA 3.0
2018-03-13T03:42:42.087Z
edited to correct a mistake; I thought line graphs of bipartite graphs are bipartite. :)
Cyriac Antony
CC BY-SA 3.0
2018-03-13T09:42:06.793Z
I think there should be a +1 in your definition of distance between edges (by the current definition the edges of M would be at distance 1 since there is an edge --- a path of length 1 --- connecting each pair of edges of M, but you actually mean distance 2).
Florent Foucaud
CC BY-SA 3.0
2018-03-13T09:56:18.247Z
corrected it as " edges ... are at distance 1 from each other". Thank you @Florent Foucaud
Cyriac Antony
CC BY-SA 3.0
2018-03-13T10:01:03.620Z
That works, but now sadly your "distance of edges" does not correspond to the vertex-distance of the corresponding vertices in the line graph.
Florent Foucaud
CC BY-SA 3.0
2018-03-13T10:15:55.067Z
To make the modeling closer to your problem, recall that a maximum matching in a graph corresponds to a maximum independent set in its line graph. Thus, in the line graph you are looking for a strong set that is also a maximum independent set (in particular, it must also be a dominating set).
Florent Foucaud
CC BY-SA 3.0
2018-03-13T10:16:17.370Z
Then, I'm not sure how to express that the matching must be perfect (not just maximum). Perhaps you can look at the conditions for having a perfect matching (see Hall's marriage theorem) and translate it in terms of the line graph. That should give you some conditions on the line graph, and then your problem will really be equivalent to the one of finding a maximum independent set that is also a strong set in the line graph.
Florent Foucaud
CC BY-SA 3.0
2018-03-13T10:21:01.830Z
finding a maximum matching will do. If it has size $|U|$, then it is perfect matching.
Cyriac Antony
CC BY-SA 3.0
2018-03-07T09:07:49.347Z
2018-03-13T09:54:39.300Z
2018-03-13T09:54:39.300Z
Cyriac Antony
<p>Is there anything in the literature close to the following problem:</p>

<p>Given a bipartite graph $G(V,E)$ with balanced bipartition $ \{U,W\}$ , does there exist a perfect matching $ M $ in $ G $ such that for every 2 edges $u_1w_1, u_2w_2\in M $, there is an edge $u_1w_2$ or edge $u_2w_1$ (or both) in $ G $?</p>

<p>In other words, is there a perfect matching $M$ such that the induced subgraph $G[M]$ is $ 2K_2 $-free.
(With balanced bipartition, I meant $|U|=|W|$.)</p>

<p>The extra condition is something like an opposite extreme of that used in induced matching problem. Another possibly related one is the problem of finding maximum size matching $M$ in bipartite graph $G$ such that contraction of edges in $M$ minimizes the number of edges left in the graph.</p>

<p>I checked the list of matching related problems given by Plummer in <em>Matching and vertex packing: how "hard" are they?</em> without success.</p>

<p>PS: This problem is a special case of this decision problem :- For a given $k\in\mathbb{N}$, is there a maximum matching $M$ of a bipartite graph $G$ such that $G[M]$ is $2K_2$-free and $|M|&gt;k$. If the input graph is balanced bipartite and $k=|U|$, we get the above problem.</p>

<p>Thank you.</p>

CC BY-SA 3.0
2018-03-13T10:38:32.187Z
perfect matching may not be correct word. We are basically asking whether there is a maximum matching having size $|U|$ with the property mentioned.
Cyriac Antony
CC BY-SA 4.0
2020-01-25T08:47:02.567Z
Sorry, by $G[M]$, I meant the subgraph of $G$ induced by vertices 'in' $M$
Cyriac Antony
CC BY-SA 4.0
2019-06-04T07:14:02.500Z
In a sense, we are asking for something opposite to what is called a strong matching. A strong matching $M$ in a graph $G$ is a matching $M$ such that there is no edge in $G$ connecting any two edges of $M$
Cyriac Antony
<matching>
Maximum matching M with the condition G[M] is 2K_2-free
Cyriac Antony
# Maximum matching M with the condition G[M] is 2K_2-free

(Asked by: username_0 on 2018-03-06)

Is there anything in the literature close to the following problem:

Given a bipartite graph $G(V,E)$ with balanced bipartition $ \{U,W\}$ , does there exist a perfect matching $ M $ in $ G $ such that for every 2 edges $u\_1w\_1, u\_2w\_2\in M $, there is an edge $u\_1w\_2$ or edge $u\_2w\_1$ (or both) in $ G $?

In other words, is there a perfect matching $M$ such that the induced subgraph $G[M]$ is $ 2K\_2 $-free.
(With balanced bipartition, I meant $|U|=|W|$.)

The extra condition is something like an opposite extreme of that used in induced matching problem. Another possibly related one is the problem of finding maximum size matching $M$ in bipartite graph $G$ such that contraction of edges in $M$ minimizes the number of edges left in the graph.

I checked the list of matching related problems given by Plummer in *Matching and vertex packing: how "hard" are they?* without success.

PS: This problem is a special case of this decision problem :- For a given $k\in\mathbb{N}$, is there a maximum matching $M$ of a bipartite graph $G$ such that $G[M]$ is $2K\_2$-free and $|M|>k$. If the input graph is balanced bipartite and $k=|U|$, we get the above problem.

Thank you.

**Tags:** matching
> **Comments:**
> **username_0**: perfect matching may not be correct word. We are basically asking whether there is a maximum matching having size $|U|$ with the property mentioned.  
> **username_0**: In a sense, we are asking for something opposite to what is called a strong matching. A strong matching $M$ in a graph $G$ is a matching $M$ such that there is no edge in $G$ connecting any two edges of $M$  
> **username_0**: Sorry, by $G[M]$, I meant the subgraph of $G$ induced by vertices 'in' $M$  

---

## 2 answers

### Answer by username_0 on 2019-11-29. Score: 5 | Accepted answer

Surprise! (for me).  
This type of matchings are already studied in the literature. They are called **connected matchings**.

They were introduced by Plummer, Stiebitz and Toft in their study on Hadwiger conjecture. See the chapter "Connected Matchings" by Cameron in the book "Combinatorial Optimization – Eureka, You Shrink!"

The status of connected matchings in bipartite graphs (not necessary balanced) is open to the best of my knowledge (*i shall update*). The weighted version of the problem is NP-complete for bipartite graphs. The problem is polynomial time solvable for chordal bipartite graphs.

Update: the problem is **NP-complete for balanced bipartite graphs** (i.e., the exact problem asked in the question). This is proved in the paper "[Multitasking Capacity: Hardness Results and Improved Constructions](https://arxiv.org/abs/1809.02835v1)" by Alon et al. They also report that finding the size of a largest connected matching is hard to approximate within a factor of $n^{1-\epsilon}$ unless NP = co-RP.

Notes added earlier (kept for interested people):  
"[Connected matchings in chordal bipartite graphs](https://www.sciencedirect.com/science/article/pii/S1572528614000322?via%3Dihub)" by Jobson et al. (doi:<https://doi.org/10.1016/j.disopt.2014.06.003>) and "[Connected matchings in special families of graphs](https://ir.library.louisville.edu/etd/206/)" by Caragianis (thesis) are two notable references.


---

### Answer by username_0 on 2018-03-07. Score: 1

There is another way to put this question. Is there a perfect matching $M$ of a balanced bipartite graph $G$ such that every pair of edges in $M$ is exactly at a distance 1 from each other in $G$ ?  
( The distance between edges $e$ and $e’$ is the length of a shortest path from a vertex of $e$ to a vertex of $e’$).

Owing to this, the extra condition reduces to finding a subset of vertices from the line graph $L(G)$ of $G$ which are pairwise at a distance exactly 2. Thus the problem of **finding a maximum size set of vertices at distance exactly 2** from each other is a candidate problem (to be a close one to the problem in question). In the recent paper *On the algorithmic aspects of strong subcoloring* (by M.A. Shalu,S. Vijayakumar,S. Devi Yamini and T.P. Sandhya), they call this problem strong set.

Stong set problem is known to be NP-complete in some graph classes. I don't know its status on line graphs of bipartite graphs. The paper says it is NP-complete on bipartite graphs. Our interest here will be in the class of line graphs of bipartite graphs.

> **Comments:**
> **username_0**: edited to correct a mistake; I thought line graphs of bipartite graphs are bipartite. :)  
> **username_1**: I think there should be a +1 in your definition of distance between edges (by the current definition the edges of M would be at distance 1 since there is an edge --- a path of length 1 --- connecting each pair of edges of M, but you actually mean distance 2).  
> **username_0**: corrected it as " edges ... are at distance 1 from each other". Thank you @Florent Foucaud  
> **username_1**: That works, but now sadly your "distance of edges" does not correspond to the vertex-distance of the corresponding vertices in the line graph.  
> **username_1**: To make the modeling closer to your problem, recall that a maximum matching in a graph corresponds to a maximum independent set in its line graph. Thus, in the line graph you are looking for a strong set that is also a maximum independent set (in particular, it must also be a dominating set).  
> **username_1**: Then, I'm not sure how to express that the matching must be perfect (not just maximum). Perhaps you can look at the conditions for having a perfect matching (see Hall's marriage theorem) and translate it in terms of the line graph. That should give you some conditions on the line graph, and then your problem will really be equivalent to the one of finding a maximum independent set that is also a strong set in the line graph.  
> **username_0**: finding a maximum matching will do. If it has size $|U|$, then it is perfect matching.  

---

