11
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • $\begingroup$ perfect matching may not be correct word. We are basically asking whether there is a maximum matching having size $|U|$ with the property mentioned. $\endgroup$
    – Cyriac Antony
    Mar 13, 2018 at 10:38
  • $\begingroup$ 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$ $\endgroup$
    – Cyriac Antony
    Jun 4, 2019 at 7:14
  • $\begingroup$ Sorry, by $G[M]$, I meant the subgraph of $G$ induced by vertices 'in' $M$ $\endgroup$
    – Cyriac Antony
    Jan 25, 2020 at 8:47

2 Answers 2

Reset to default
5
$\begingroup$

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" 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" by Jobson et al. (doi:https://doi.org/10.1016/j.disopt.2014.06.003) and "Connected matchings in special families of graphs" by Caragianis (thesis) are two notable references.

Improve this answer
$\endgroup$
1
$\begingroup$

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.

Improve this answer
$\endgroup$
7
  • $\begingroup$ edited to correct a mistake; I thought line graphs of bipartite graphs are bipartite. :) $\endgroup$
    – Cyriac Antony
    Mar 13, 2018 at 3:42
  • $\begingroup$ 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). $\endgroup$
    – Florent Foucaud
    Mar 13, 2018 at 9:42
  • $\begingroup$ corrected it as " edges ... are at distance 1 from each other". Thank you @Florent Foucaud $\endgroup$
    – Cyriac Antony
    Mar 13, 2018 at 9:56
  • $\begingroup$ That works, but now sadly your "distance of edges" does not correspond to the vertex-distance of the corresponding vertices in the line graph. $\endgroup$
    – Florent Foucaud
    Mar 13, 2018 at 10:01
  • 1
    $\begingroup$ 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). $\endgroup$
    – Florent Foucaud
    Mar 13, 2018 at 10:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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