Tight Approximation Ratio for Minimum Maximal Matching

Abstract

We study a combinatorial problem called Minimum Maximal Matching, where we are asked to find in a general graph the smallest matching that can not be extended. We show that this problem is hard to approximate with a constant smaller than 2, assuming the Unique Games Conjecture.

As a corollary we show, that Minimum Maximal Matching in bipartite graphs is hard to approximate with constant smaller than $\frac{4}{3}$, with the same assumption. With a stronger variant of the Unique Games Conjecture—that is Small Set Expansion Hypothesis—we are able to improve the hardness result up to the factor of $\frac{3}{2}$.

S. Dudycz—Supported by the Polish National Science Centre grant 2013/11/B/ST6/01748.

M. Lewandowski and J. Marcinkowski—Supported by the Polish National Science Centre grant 2015/18/E/ST6/00456.

1 Introduction

Matchings are some of the most central combinatorial structures in theory of algorithms. A routine computing them is a basic puzzle used in numerous results in Computer Science (like Christofides algorithm). Various variants of matchings are studied extensively. Their computation complexity status is usually well-known and some techniques discovered when studying matchings are afterwards employed in other problems.

As we know since 1961, many natural variants of perfect matchings and maximum matchings can be found in polynomial time, even in general graphs. Here we study a different problem—Minimum Maximal Matching (). The task is—given graph $G$, to find an inclusion-wise maximal matching $M$ with the smallest cardinality (or weight in the weighted version).

1.1 Related Work

The problem was studied as early as 1980, when Yannakakis and Gavril showed that it is NP-hard even in some restricted cases [20]. Their paper also presents an equivalence of and Minimum Edge Dominating Set () problem, where the goal is to find minimum cardinality subset of edges $F$, such that every edge in the graph is adjacent to some edge in $F$. Every maximal matching is already an edge dominating set, and any edge dominating set can be easily transformed to a maximal matching of no larger size. This equivalence does not hold for the weighted variants of the problem.

It is a well known, simple combinatorial fact, that one maximal matching in any graph can not be more than twice as large as another maximal matching. This immediately gives a trivial 2-approximation algorithm for . Coming up with 2-approximation in the weighted variant of either of the problems is more challenging. In 2003, Carr, Fujito, Konjevod and Parekh presented a $2\frac{1}{10}$-approximation algorithm for a weighted problem [3]. Later the approximation was improved to 2 by Fujito and Nagamochi [8].

Some algorithms aiming at approximation ratio better then 2 were also developed for the unweighted problem. Gotthilf, Lewenstein and Rainschmidt came up with a $2-c\frac{\log n}{n}$-approximation for the general case [9]. Schmied and Viehmann have a better-than-two constant ratio for dense graphs [19].

Finally, hardness results need to be mentioned. In 2006 Chlebík and Chlebíková proved, that it is NP-hard to approximate the problem within factor better than $\frac{7}{6}$ [4]. The result was later improved to $1.207$¹ by Escoffier, Monnot, Paschos, and Xiao [7]. $\frac{3}{2}$-hardness results depending on ugc were also obtained [7, 19].

1.2 Unique Games Conjecture

Unique Games Conjecture, since being formulated by Khot in 2002 [11], has been used to prove hardness of approximation of many problems. For the survey on ugc results see [12].

Many hardness results obtained from Unique Games Conjecture match previously known algorithms, as is the case, for example, of Vertex Cover, Max Cut or Maximum Acyclic Subgraph. Therefore, it is appealing to use it to obtain new results. While ugc is still open, recently a related 2–2-Games Conjecture has been proved [14], in consequence proving Unique Games Conjecture with partial completeness. This result provides some evidence towards validity of Unique Games Conjecture.

Basing on Unique Games Conjecture we are able to prove the main result of our paper.

Theorem 1

Assuming Unique Games Conjecture, it is NP-hard to approximate Minimum Maximal Matching with constant better than 2.

The proof of this theorem relies on the UGC-hardness proof for Vertex Cover of Khot and Regev [15]. In essence, we endeavour to build a matching over the vertices of Vertex Cover.

The Minimum Maximal Matching problem does not seem to be easier on bipartite graphs. All the algorithms mentioned above are defined for general graphs and we are not aware of any ways to leverage the bipartition of the input graph. At the same time, our hardness proof only works for general graphs. With some observations we are able to achieve a hardness result for bipartite graphs, which, however, is not tight.

Theorem 2

Assuming Unique Games Conjecture, it is NP-hard to approximate bipartite Minimum Maximal Matching with constant better than $\frac{4}{3}$.

1.3 Obtaining a Stronger Result

The studies on Unique Games Conjecture and hardness of approximation of different problems have led to formulating different hypotheses strengthening upon ugc—among them the Small Set Expansion Hypothesis proposed by Raghavendra and Steurer [18], and another conjecture—whose name is not yet established and so far the name Strong UGC is used—formulated by Bansal and Khot [1]. A competent discussion on differences between the two conjectures can be found in [16, Appendix C].

To improve our result on bipartite graphs, we construct a reduction from a problem called Maximum Balanced Biclique (), where—given a bipartite graph—the goal is to find a maximum biclique with the same number of vertices on each side of the graph. Hardness of approximation results suitable for our reduction have been found starting from both the Small Set Expansion Hypothesis [16] and Strong UGC [2].

Theorem 3

Assuming Small Set Expansion Hypothesis (or Strong Unique Games Conjecture), it is NP-hard to approximate Bipartite Minimum Maximal Matching with a constant better than $\frac{3}{2}$.

Due to space limitations, this result is only presented in the full version of our paper (published on arXiv [6]).

2 Revisiting the Khot-Regev Reduction

In their paper [15] Khot and Regev prove the $\textsc {ugc}$-hardness of approximating Minimum Vertex Cover within a factor smaller than $2$. In this section we look at parts of their proof more closely.

Their reduction starts off with an alternative formulation of $\textsc {ugc}$², which, they show, is a consequence of the standard variant.

2.1 Khot-Regev Formulation of Unique Games Conjecture

This formulation talks about a variant of Unique Label Cover problem described by a tuple $\Phi = \left( X, R, \Psi , E\right)$. $X$ is a set of variables, $E$ are the edges and $\Psi _{x_1,x_2}$ defines a constraint for every pair of variables connected by an edge. A constraint is a permutation $\Psi _{x_1,x_2} \in R \leftrightarrow R$ meaning that if $x_1$ is labelled with a colour $r \in R$, $x_2$ must be labelled with $\Psi _{x_1,x_2}(r)$.

A $t$-labelling is an assignment of subsets $L(x)$ of size $|L(x)| = t$ to the variables. A constraint $\Psi _{x_1,x_2}$ is satisfied by the t-labelling $L$ if there exists a colour $r \in L(x_1)$ such that $\Psi _{x_1,x_2}(r) \in L(x_2)$.

Conjecture 1

(Unique Games Conjecture).

For any $\xi , \gamma > 0$ and $t \in \mathbb {N}$ there exists some $|R|$ such that it is NP-hard to distinguish, given an instance $\Phi = \left( X, R, \Psi , E\right)$ which category it falls into:

• (yes instance): There exists a labelling (1-labelling) $L$ and a set $X_0 \subseteq X$, $|X_0| \geqslant (1 - \xi )|X|$, such that $L$ satisfies all constraints between vertices of $X_0$.

• (no instance): For any t-labelling $L$ and any set $X_0 \subseteq X$, $|X_0| \geqslant \gamma |X|$, not all constraints between variables of $X_0$ are satisfied by $L$.

2.2 Weighted Vertex Cover

The next step is a reduction from the $\textsc {ugc}$ to the Minimum Vertex Cover problem. Given an instance $\Phi = \left( X, R, \Psi , E\right)$ of Unique Label Cover problem, as described above, we build a graph $G_{\Phi }$.

For every variable in $x \in X$ we create a cloud $\mathscr {C}_x$ of $2^{|R|}$ vertices. Each vertex corresponds to a subset of labels and is denoted by $\left( x, S\right) \in |X| \times \mathcal {P}(R)$³. The weight of a new vertex $(x, S)$, denoted as $w(x, S)$, is equal to

$$ \mu (|S|) = \frac{1}{|X|} \cdot p^{|S|}{(1-p)}^{|R \setminus S|} $$

where $p = \frac{1}{2}-\varepsilon$ (there is a bias towards smaller sets). The total weight of $G_{\Phi }$ is thus equal to $1$.

Next, we connect the vertices $(x_1, S_1)$ and $(x_2, S_2)$ if there is no pair of labels $s_1 \in S_1$ and $s_2 \in S_2$ satisfying the constraint $\Psi _{x_1,x_2}$. Two lemmas are proved.

Lemma 1

([15, Sec. 4.2]). If $\Phi$ was a yes instance, the graph $G_{\Phi }$ has an independent set of weight at least $\frac{1}{2} - 2\varepsilon$.

Proof

The instance $\Phi$, being a yes instance, has a labelling $L$ assigning one colour $r_x$ to each variable $x$. We know, that there is a large set $X_0$ of variables ($|X_0| \geqslant \left( 1 - \xi \right) |X|$), such that all constraints between variables of $X_0$ are satisfied by $L$.

We now define

$$ \mathcal {IS} = \big \{ (x, S)\ \big |\ x \in X_0,\, r_x \in S \big \} $$

and claim, that $\mathcal {IS}$ is an independent set in $G_{\Phi }$. For any two variables $x_1$ and $x_2$ of $X_0$ we know, that

$$ \Psi _{x_1,x_2}(r_{x_1}) = r_{x_2}. $$

Indeed, if we then take the sets of labels $S_1 \ni r_1$ and $S_2 \ni r_2$, they do satisfy the constraint for the variables $x_1$, $x_2$. Hence, there is no edge between $(x_1, S_1)$ and $(x_2, S_2)$.

Finally, the weight of $\mathcal {IS}$ is equal to

$$ \begin{aligned} w\left( \mathcal {IS}\right)&= \sum _{x \in X_0} \left( \sum _{S \subseteq R, S \ni r_x} w(x, S) \right) = \sum _{x \in X_0} \left( \frac{1}{|X|} \cdot \sum _{k=1}^{|R|} \left( {\begin{array}{c}|R|-1\\ k-1\end{array}}\right) \cdot p^k \cdot {\left( 1-p\right) }^{|R|-k} \right) \\&= \sum _{x \in X_0} \left( p \cdot \frac{1}{|X|} \cdot \sum _{k=0}^{|R|-1} \left( {\begin{array}{c}|R|-1 \\ k\end{array}}\right) \cdot p^k \cdot {\left( 1-p\right) }^{|R|-1-k} \right) \\&= \sum _{x \in X_0} \left( p \cdot \frac{1}{|X|} \cdot {\left( p + \left( 1-p\right) \right) }^{|R|-1}\right) \\&= \frac{|X_0|}{|X|} \cdot p \geqslant (1-\xi )(\frac{1}{2}-\varepsilon ) > \frac{1}{2} - 2\varepsilon . \end{aligned} $$

   $\square$

The most of their paper is dedicated to proving the following key lemma.

Lemma 2

([15, Sec. 4.3]). If $\Phi$ is a no instance, $G_{\Phi }$ does not have an independent set of weight larger than $2\gamma$.

Since the Minimum Vertex Cover is a complement of the Maximum Independent Set, we see that it is hard to distinguish between graphs with Minimum Vertex Cover of the weight $\frac{1}{2} + 2\varepsilon$ and those, where Minimum Vertex Cover weights $1 - 2\gamma$.

2.3 Notation

Throughout this paper we are going to use $\Phi$ as an instance of Unique Label Cover problem that we are translating to $G_{\Phi }$. The weight function $w$ on vertices and bias function $\mu$ is going to be referred to, as well as the constants $\varepsilon$ and $\gamma$. When $\Phi$ is a yes instance, we are going to refer to the set $X_0$ as in Conjecture 1, and use the independent set $\mathcal {IS}$ from Lemma 1.

3 Weighted Minimum Maximal Matching

Let us now modify their reduction. The graph ${G}^{\prime }_{\Phi }$ gets additional edges between vertices $(x, S_1)$, $(x, S_2)$ if $S_1 \cap S_2 = \varnothing$—they do not assign the same colour to the variable $x$. Clearly, the Lemmas 1 and 2 still hold for ${G}^{\prime }_{\Phi }$.

Moreover, we introduce the weight function on the edges.

This weight function is such that for any matching, the weight of matching edges is equal to the weight of matched vertices.

We will now show the similar statements are true for the Minimum Maximal Matching as for the independent set.

Lemma 3

If $\Phi$ was a yes instance, the Minimum Maximal Matching in $\left( {G}^{\prime }_\Phi , w_+\right)$ weights at most $\frac{1}{2} + 2\varepsilon$.

Lemma 4

If $\Phi$ was a no instance, the Minimum Maximal Matching in $\left( {G}^{\prime }_{\Phi }, w_+\right)$ weights at least $1 - 2\gamma$.

These lemmas altogether will give us the theorem.

Theorem 4

Assuming the Unique Games Conjecture, for any $\epsilon > 0$ it is NP-hard to distinguish between graphs with Maximal Matching of weight $\frac{1}{2} + \epsilon$ and those where every Maximal Matching weights at least $1 - \epsilon$.

This in turn means that—assuming UGC—a polynomial-time approximation algorithm with a factor better than $2$ can not be constructed.

Proof

(Proof of Lemma 3).

Let us construct a matching $M$ in $G^{\prime }_{\Phi }$. The matching will only consist of the edges between vertices corresponding to the same variable in ${\Phi }$. First we define the part of $M$ restricted to $X_0$⁴.

$$ M_0 = \Big \{{(x, S_1) \sim (x, S_2)\ \big |\ x \in X_0 \,\wedge \, S_1 \uplus S_2 = R\setminus \{r_x\}}\Big \} $$

For vertices in clouds corresponding to variables outside of $X_0$ we define

$$ M_1 = \Big \{{(x, S_1) \sim (x, S_2)\ \big |\ x \in X_0 \,\wedge \, S_1 \uplus S_2 = R}\Big \} $$

The matching $M$ will be the union of $M_0$ and $M_1$.

We can observe, that the vertices matched by $M$ are exactly those, that do not belong to $\mathcal {IS}$. Hence,

$$ \begin{aligned} w_+(M)&\leqslant w(V(G^{\prime }_{\Phi })) - w(\mathcal {IS}) \leqslant 1 - \left( \frac{1}{2} - 2\varepsilon \right) = \frac{1}{2} + 2\varepsilon \end{aligned} $$

Moreover, since the vertices of $M$ compose a vertex cover, $M$ is a maximal matching.    $\square$

Proof

(Proof of Lemma 4).

Let $M$ be any maximal matching. The vertices matched by $M$, $V(M)$ form a vertex cover. Hence, the weight of $M$ is going to be at least as large as the weight of the Minimum Vertex Cover. From Lemma 2 we know, that if ${\Phi }$ was a no instance, $G^{\prime }_{\Phi }$’s Minimum Vertex Cover weights at least $1 - 2\gamma$.    $\square$

4 Towards the Unweighted MMM: Fractional Matchings

A natural way to reduce a weighted variant of a problem to the unweighted would often be to assume that the weights are integral (that can be achieved by rounding them first at a negligible cost) and copying every vertex as many times, as its weight would suggest. This simple strategy will not however work with instances from previous section, where we were matching pairs of vertices of different weights. Such a matching does not easily translate to the graph with vertex copies. Thus, we want to create different, fractional matching, in which every vertex is matched proportionally to its weight. Then, we can use such matching after copying each vertex.

In order to extend our approximation hardness proof to Minimum Maximal Matching problem in unweighted graphs, we thus need first to modify our weighted reduction a bit. The structure remains the same, but the weight of each edge is now defined to be the minimum of the weights of its endpoints.

Similarly to the reasoning presented in the previous section, when $G^{\prime }_{\Phi }$ is a yes instance, we will want to construct a matching and argue that it is maximal using a known vertex cover.

Definition 1

A fractional matching is an assignment of values to variables $x_e$ corresponding to edges, such that for every edge $e$ $0 \leqslant x_e \leqslant w_{\min }(e)$ and for every vertex $v$, the sum $\sum _{(v,w) \in E} x_{(v, w)} \leqslant w(v)$.

Definition 2

A fractional matching $x$ saturates a vertex $v$ if $\sum _{(v,w) \in E} x_{(v, w)} = w(v)$. A vertex $v$ is unmatched if $\sum _{(v,w) \in E} x_{(v, w)} = 0$.

As we know already, when $\Phi$ is a yes instance, there is a vertex cover in $G^{\prime }_{\Phi }$ composed of all vertices except those in $\mathcal {IS}$.

Lemma 5

If $\Phi$ was a yes instance, a fractional matching exists that leaves all vertices in $\mathcal {IS}$ unmatched and saturates all the other vertices.

4.1 Proving Lemma 5

Our matching will again only match vertices in the same clouds. Let us first concentrate on vertices in the cloud $\mathscr {C}_x$ corresponding to a variable $x \not \in X_0$. The matching needs to saturate every vertex in $\mathscr {C}_x$.

The fractional matching $F$ can be viewed as a real-valued vector and will be a sum of three matchings. The first one is defined similarly to $M_1$ in Lemma 3.

$$ F^0\big ((x, S_1), (x, S_2)\big ) = {\left\{ \begin{array}{ll} w_{\min }\left( (x, S_1), (x, S_2)\right) , &{} \text{ if } S_1 \uplus S_2 = R \\ 0, &{} \text{ otherwise } \end{array}\right. } $$

Recalling, that the weight function $w$, defined on vertices, has a bias towards smaller sets, we can state the following.

Observation 5

$F^0$ saturates all vertices $(x, S)\in \mathscr {C}_x$ if $|S| \geqslant \frac{|R|}{2}$.

Let us now pick $0< k < \frac{|R|}{2}$ and look at the layer $\mathscr {C}_x^k = {\big \{ (x, S) \ \big | \ |S| = k \big \}}$. The graph is symmetric, and $F^0$ matches every vertex with the same weight—$\mu (|R|-k) = \frac{1}{|X|} p^{|R|-k} {(1-p)}^k$. In order to build a matching $F^1$, that saturates all vertices in the layer we build a bipartite graph $\mathcal {B}^k$ out of $\mathscr {C}_x^k$⁵.

Definition 3

For every set $S$ of size $k$, $\mathcal {B}^k$ has two vertices, $S^L$ and $S^R$. $S_1^L$ is connected with $S_2^R$ if $S_1 \cap S_2 = \varnothing$.

The graph $\mathcal {B}_k$ is in fact a Bipartite Kneser Graph. As proved in [17], it has a Hamiltonian cycle $\mathcal {H}_k$. We are using this cycle to define $F^1$—for every edge connecting the sets $S_1$ and $S_2$ in $\mathcal {H}_k$ we lay the weight of

$$ F^1\left( (x, S_1), (x, S_2)\right) = \frac{1}{4} \left( \mu (k) - \mu (|R|-k) \right) $$

on the edge connecting them in $\mathscr {C}_x^k$.

To saturate the vertices $(x, \varnothing )$ (for $x \not \in X_0$), we must realize that all these vertices form a clique in which we can find a Hamiltonian Cycle $\mathcal {H}_\emptyset$. Let us define $F^2$

$$ F^2\big ((x_1, \varnothing ), (x_2, \varnothing )\big ) = {\left\{ \begin{array}{ll} \frac{\mu (0) - \mu (|R|)}{2}, &{} \text{ for } \{x_1, x_2\} \in \mathcal {H}_\emptyset \\ 0, &{} \text{ otherwise } \end{array}\right. } $$

Lemma 6

$F^0 + F^1 + F^2$ saturates all vertices in $\mathscr {C}_x^k$.

Proof

We look at the vertex $(x, S)$. For $0< |S| < \frac{|R|}{2}$, the Hamiltonian Cycle $\mathcal {H}_k$ visits every set exactly twice (once $S^L$ and once $S^R$), using four edges incident to it. Hence, the total contribution of $F^0$ and $F^1$ is equal to

$$ \mu (|R|-k) + 4 \cdot \frac{1}{4} \left( \mu (k)-\mu (|R|-k) \right) = \mu (k) = w(x, S). $$

$F^0$ contributes $\mu (|R|)$ to the vertex $(x, \varnothing )$, while $F^2$ contributes $2 \cdot \frac{\mu (0) - \mu (|R|)}{2}$, hence that vertex is also saturated.

Finally, vertices with $S = \varnothing$ are saturated by $F^0 + F^2$.    $\square$

When ${{\varvec{x}}}\in {{\varvec{X}}}_{\mathbf {0}}{} \mathbf{.}$ We proceed similarly as for vertices not in $X_0$. For the cloud $\mathscr {C}_x$ when $x \in X_0$, our first matching $F^0$ is taking the labeling of the variable $x$ into account. Similarly to Lemma 3, we match $(x, S_1)$ and $(x, S_2)$ if $S_1 \uplus S_2 = R \setminus \{r_x\}$, thus saturating the larger of the sets.

Again, the layer $\mathscr {C}_x^k$ for $k < \frac{|R|-1}{2}$, composed of sets not containing $r_x$, is a Bipartite Kneser Graph, and we use its Hamiltonian cycle to define $F^1$.

Also the vertices $(x, \varnothing )$ for $x \in X_0$ form a clique. Once again, we can use the Hamiltonian Cycle in that clique to define $F^2$.

5 Unweighted MMM

Starting with a graph $G^{\prime }_{\Phi }$ with the weight function $w$ on the vertices, and any precision parameter $\rho > 0$, we are going to construct an unweighted graph $G_{\Phi }^{\rho } = \left( V^{\rho }, E^{\rho }\right)$. The resulting graph size is polynomial in $|\Phi |$ and $\frac{1}{\rho }$.

Definition 4

Let $n = |V(G^{\prime }_{\Phi })| \cdot \frac{1}{\rho }$. For every $v \in V(G^{\prime }_{\Phi })$ we set $n_v = \lceil n \cdot w(v) \rfloor$⁶6. The new set of vertices is going to consist of multiple copies of original vertices; for each vertex $v$, we add $4 \cdot n_v$ copies.

The edges are going to connect each pair of copies of vertices connected in $G^{\prime }_\Phi$.

This construction has been presented in [5]. It is shown that any vertex cover $C \subset G^{\prime }_{\Phi }$ yields a product vertex cover $C^{\rho } = \bigcup _{v \in C} \{v\}\times [4\cdot n_v]$ with $\Big |w(C) - \frac{|C^\rho |}{|V(G_{\Phi }^{\rho })|}\Big | < \rho$ (precision). Moreover, every minimal vertex cover in $G_{\Phi }^{\rho }$ is a product vertex cover [5, Proposition 8.1].

As before, we are now going to prove two lemmas witnessing the completeness and soundness of our reduction.

Lemma 7

(Soundness). If $\Phi$ was a no instance, for every maximal matching $M$ in $G_{\Phi }^{\rho }$

$$ 2\cdot |M| > |V(G_{\Phi }^{\rho })| \left( 1 - 2\gamma - \rho \right) . $$

Proof

Take any maximal matching $M$. The $2\cdot |M|$ vertices matched by it form a vertex cover $C$. Let $C_-$ be a minimal vertex cover obtained by removing unneeded vertices from $C$. As presented in [5], $C_-$ is a product vertex cover, which means, there is a vertex cover $C_w$ in $G^{\prime }_{\Phi }$ with weight

$$ w(C_w) < \frac{|C_-|}{V(G_{\Phi }^{\rho })} + \rho \leqslant \frac{|C|}{V(G_{\Phi }^{\rho })} + \rho . $$

On the other hand, from Lemma 2 we have, that $w(C_w) > 1 - 2\gamma$.    $\square$

Fig. 1.

A close-up look at the resulting matching in a cloud of vertices corresponding to the variable $x \in X_0$. The fractional matchings $F^0$ and $F^1$ constructed in Sect. 4 can be discretised to match all the copies of respective vertices.

Lemma 8

(Completeness). If $\Phi$ was a yes instance, a maximal matching $M$ exists in $G_{\Phi }^{\rho }$ with

$$ 2\cdot |M| < |V(G_{\Phi }^{\rho })| \left( \frac{1}{2} + 2\varepsilon + \rho \right) . $$

Proof

Take $F$, a fractional matching on $(G^{\prime }_{\Phi }, w_{\min })$ constructed in Lemma 5. When $F^0$ matches vertices $u = (x, S_1)$ and $v = (x, S_2)$ with some weight $F^0(u, v)$, we are going to match $4 \cdot n \cdot \lceil F^0(u, v) \rfloor$ copies of $u$ and $v$ using parallel edges.

Let us focus on a vertex $u = (x, S)\not \in \mathcal {IS}$ belonging to a vertex cover of $G^{\prime }_{\Phi }$, with $0< |S| < \frac{|R|}{2}$. It is matched by $F^0$ to $(x, S')$, which leaves $4\left( \lceil w(x, S) \rfloor - \lceil w(x, S') \rfloor \right)$ vertices in $G_{\Phi }^{\rho }$ unmatched. This number is divisible by 4, which allows us to match all the copies of vertices in the Bipartite Kneser Graph according to $F^1$ (see Fig. 1).

Finally, the number of unmatched copies of the $(x, \varnothing )$ vertices is divisible by 2. We can thus replicate $F^2$ to match all the remaining copies of these vertices.

Since we are matching every node in a vertex cover of the graph $G_{\Phi }^{\rho }$, our matching is maximal and its cardinality is half of the cardinality of the vertex cover.

$$ |M| = \frac{1}{2} \left( V(G_{\Phi }^{\rho }) - |IS|^{\rho }\right) < \frac{1}{2} V(G_{\Phi }^{\rho }) \left( 1 - \left( \frac{1}{2} - 2\varepsilon - \rho \right) \right) $$

   $\square$

6 Conclusion

We would like to finish by discussing potentially interesting open problems. Natural question following our result on is whether other hardness results for Vertex Cover also hold for . In particular, it is known that Vertex Cover on $k$-hypergraphs is hard to approximate with a constant better than $k$ [15]. Also, the best known NP-hardness of Vertex Cover is $\sqrt{2}$, following the reduction from 2–2 Games Conjecture [13], which has been recently proven [14].

Both of these reductions are very similar to Khot and Regev’s ugc-hardness of Vertex Cover. As such they can be used to prove corresponding hardnesses of weighted , by following similar approach as in Sect. 3. They differ, however, in the choice of the weight function of vertices, which turns out to be crucial in terms of unweighted . These weight functions have bias towards bigger sets, so construction described in Sect. 4 can not be used for these problems.

Still the best known NP-hardness of unweighted is $1.207$ by Escoffier, Monnot, Paschos, and Xiao [7] and it is an open problem, whether it can be improved to match hardness of Vertex Cover using 2–2 Games Conjecture.

In case of bipartite , there remains a gap between our $\frac{3}{2}$-hardness and best known constant approximation algorithm, which has ratio 2. Showing that bipartite is hard to approximate with a constant better than 2 would immediately imply tight hardness of Maximum Stable Matching with Ties [10]. On the other hand, there are no results for leveraging restriction to bipartite graphs. Thus, a potential better than 2 approximation algorithm for bipartite graphs would be interesting for showing structural difference between in bipartite and general graphs.

A Hardness of Bipartite MMM

In this section we will perform a natural reduction to prove the following theorem.

Theorem 6

Assuming the Unique Games Conjecture, for any $\epsilon > 0$ it is NP-hard to distinguish between balanced bipartite graphs of $2n$ vertices:

• (yes instance) with a Maximal Matching of size smaller than $n \left( \frac{1}{2} + \epsilon \right)$.

• (no instance) with no Maximal Matching of size smaller than $n \left( \frac{2}{3} - \epsilon \right)$.

We will start with the graph $G_{\Phi }^{\rho }$ defined in Sect. 5. The bipartite graph $H_{\Phi }$ has two copies $v^{l}$ and $v^{r}$ of every vertex $v \in G_\Phi ^\rho$. The vertices $u^{l}$ and $v^r$ are connected with an edge if there is an edge $(u, v)$ in $G_\Phi ^\rho$. $n$ is going to be equal to $|V(G_\Phi ^\rho )|$. We will call this construction bipartisation of an undirected graph.

It is easy to see, that if $\Phi$ is a yes instance of the Unique Label Cover problem, we can use the matching from Lemma 8 ($M$ in $G_\Phi ^\rho$) to produce a maximal matching in $H_\Phi$. For every edge $(u, v)\in M$ we will put its two copies, $(u^l, v^r)$ and $(v^l, u^r)$ into the matching. The resulting matching size is thus equal to $2 \cdot |M| < n (\frac{1}{2} + \epsilon )$.

1.1 A.1 Covering with Paths

In order to analyse the no case, we need to look at the bipartite instance and its matchings from another angle. For any matching in $H_{\Phi }$, we will view its edges as directed edges in $G_\Phi ^{\rho }$—the vertices on the left will be viewed as out vertices, and those on the right as in vertices. The graph $G_{\Phi }^{\rho }$ will thus be covered with directed edges. Every vertex will be incident to at most one outgoing and one incoming edge, which means that the edges will form a structure of directed paths and cycles. The set of these paths and cycles will be called $\mathscr {P}(M)$ for a matching $M$.

Observation 7

If $M$ is a maximal matching, every path $P \in \mathscr {P}(M)$ has a length $|P| \geqslant 2$.

Proof

Assume, that for a maximal matching $M$ in $H_\Phi$ there is a length-one path $P = {(u, v)} \in \mathscr {P}(M)$. This means, that the vertices $v^l$ and $u^r$ are unmatched in $M$—yet, they are connected with an edge, that can be added to the matching (that would form a length-2 cycle in $\mathscr {P}(M)$).    $\square$

We will now use this observation to prove the relation between maximal matchings in $H_\Phi$ and vertex covers in $G_\Phi ^\rho$.

Lemma 9

For any maximal matching $M$ in $H_\Phi$, there exists a vertex cover $C$ in $G_\Phi ^{\rho }$ of size $|C| \leqslant \frac{3}{2}|M|$.

Proof

We will construct the vertex cover using paths and cycles of $\mathscr {P}(M)$. For every $P \in \mathscr {P}(M)$ we add all the vertices of $P$ into $C$. When $P$ is a cycle, it contains as many vertices as edges. A path has at most $\frac{3}{2}$ as many vertices as edges, since its length is at least 2.    $\square$

As shown in Lemma 7, when $\Phi$ is a no instance, the Minimum Vertex Cover in $G_\Phi ^\rho$ has at least $n (1 - \epsilon )$ vertices. The Minimum Maximal Matching in $H_{\Phi }$ must in this case have at least $\frac{2}{3}n(1 - \epsilon ) > n(\frac{2}{3} - \epsilon )$ edges.

The hardness coming from Theorem 6 is, that assuming UGC, no polynomial-time algorithm will provide approximation for Minimum Maximal Matching with a factor $\frac{4}{3} - \epsilon$ for any $\epsilon > 0$.