Add all non-edges of $G[B_1,B_2]$ incident to $w$ to $\hat{G}$.
Set $e=(v_1,u_2)$.
Return that no  of $G$ contains $e$.
Return set $A=B_2$.
Return all 's $H$ of $G$ such that $V_1(H)\subseteq B_1$ and $V_2(H)\subseteq B_2$. find them by inspecting $\hat{G}$

Finding all 's of $G$ which contain given edge $e=(v_1,v_2)$ such that $\Gamma(v_1)\cap\Gamma(v_2)=\varnothing$.

To implement Step <ref> we check two arbitrary vertices of $B_1\setminus\{v_1\}$ in $\mathcal{O}(t)$ time as the candidates for $u_1$. If each of them is incident to at least two non-edges of $G[B_1,B_2]$, then we stop Algorithm <ref> immediately and we return that no  of $G$ contains $e$. Similarly, we check three arbitrary vertices of $B_2\setminus\{v_2\}$ as the candidates for $u_2$. It guarantees that at least two of them are adjacent to $u_1$ in $G$.

Notice that the operation of adding non-edge $e'$ of $G[B_1,B_2]$ in Step <ref> does nothing if $e'$ belongs to $E(\hat{G})$ already.

If Algorithm <ref> returns set $A$ in Step <ref>, then it works in $\mathcal{O}(t|A|)$ time. Moreover, no vertex of $A$ belongs to any  of $G$.

Let $E'$ be a set of any three vertex-disjoint non-edges of $G[B_1,B_2]$. Such three non-edges exist because the condition in Step <ref> of Algorithm <ref> was true. Notice that from the definition of $B_1$ and $B_2$, no edge of $E'$ is incident to $v_1$ or $v_2$.

At the beginning we claim that both $v_1$ and $v_2$ do maybe define some term for a vertex which do not belong to any forbidden subgraph? not belong to any  of $G$. We prove it only for $v_1$ since the proof for $v_2$ is symmetric.
Suppose that $v_1$ belongs to some  $H$ of $G$. Assume that $v_1\in V_1(H)$. By Observation <ref>, $e$ does not belong to any  of $G$, so $v_2$ does not belong to $H$. Since $H$ is $t$-regular and $\deg_G(v_1)=t+1$, all other neighbours of $v_1$ belong to $H$, i.e. $B_2\setminus\{v_2\}=V_2(H)$. Therefore, every non-edge of $E'$ has an endpoint in $V_2(H)$. Since $u_2\in V_2(H)$, at most one neighbour of $u_2$ does not belong to $V_1(H)$. From the choice of $u_2$, an endpoint of some edge of $E'$ belongs to $V_1(H)$ – a contradiction since some non-edge of $E'$ (and $G$) belongs to $E(H)$.

Now we claim that both $u_1$ and $u_2$ do not belong to any  of $G$. Suppose that $u_1\in V_1(H)$ for some  $H$ of $G$. Since $v_2$ does not belong to any  of $G$, all other neighbours of $u_1$ belong to $V_2(H)$, including $u_2$. Hence, at least two non-edges of $E'$ have an endpoint in $V_2(H)$. By repeating the same argument for $u_2$ we conclude that all neighbours of $u_2$ except $v_1$ belong to $V_1(H)$. Therefore, at least two non-edges of $E'$ have an endpoint in $V_1(H)$. Since $|E'|=3$ it means that some non-edge of $E'$ belongs to $H$ – a contradiction.

In the end, we claim that no other element of $A$ belongs to any  of $G$. It follows easily from the fact that every other element of $A$ is incident to both $v_1$ and $u_1$, both of which cannot belong to any  of $G$. The claimed running time of Algorithm <ref> follows from the fact that at most one vertex processed in Step <ref> does not belong to $A$ – another endpoint of possible non-edge of $G[B_1,B_2]$ incident to $u_1$.

If Algorithm <ref> executed Step <ref> and its condition turned out to be true, no  of $G$ contains $e=(v_1,v_2)$ by Observation <ref>. Nevertheless, it may happen that there exists a  of $G$ which contains either $v_1$ or $v_2$ in this case. The following observation describes the complement of $G[B_1,B_2]$ in such case.

Let $B_1$ does this observation need a proof? It can be proven by considering the maximum matching of the complement of $G[B_1,B_2]$ which has to consists of exactly two edges and $B_2$ be any two vertex-disjoint subsets of the vertices of $G$, each of size exactly $t+1$. If both of the following conditions are true:

* there are no three vertex-disjoint edges in the complement of $G[B_1,B_2]$, and

* the edge set of the complement of $G[B_1,B_2]$ cannot be divided into two (possibly empty) stars whose one center belongs to $B_1$ and the other one to $B_2$,

then the edge set of the complement of $G[B_1,B_2]$ can be divided into two non-empty stars of degree at least two whose both centers belong either to $B_1$ or both to $B_2$.

If Algorithm

TODO (analyze Algorithm <ref> similarly to the analysis of Algorithm <ref>)

If $v_1$ and $v_2$ have exactly one common neighbour $z$, we will use the following claim.

Assume that $|\Gamma(v_1)\cap\Gamma(v_2)|=1$. There exists a procedure which works in $\mathcal{O}(t)$ time and it either

* finds $e'=(v_1',v_2')\in E(G)$ such that $|\Gamma(v_1')\cap\Gamma(v_2')|\neq 1$, or

* concludes that no  of $G$ contains $e$.

We incorporate the procedure from the statement of Claim <ref> in the implementation of procedure FIND in the following way. If it finds $e'$, the we run procedure FIND parametrized by edge $e'$ instead of $e$. Otherwise, we return that no  of $G$ contains $e$. We give the proof of Claim <ref> below.

Let $z$ be a unique common neighbour of $v_1$ and $v_2$. Consider an edge $(v_1,z)$ as the candidate for $e'$. Of course, $v_1$ and $z$ have at least one common neighbour, namely, $v_2$. If $z$ is adjacent to some vertex of $\Gamma(v_1)\setminus\{v_2,z\}$, then $v_1$ and $z$ have at least two common neighbours and we return $e'=(v_1,z)$ in this case. Symmetrically, if $z$ is adjacent to some vertex of $\Gamma(v_2)\setminus\{v_1,z\}$, we return $(v_2,z)$ as $e'$.

From now we assume that $z$ is not adjacent to any vertex of $(\Gamma(v_1)\sum\Gamma(v_2))\setminus\{v_1,v_2\}$. Therefore, $z$ do not belong to any  of $G$ which contains $e$. Let $u_2$ be any vertex of $\Gamma(v_1)$ different than $v_2$ and $z$. It is easy to check that if $u_2$ is not adjacent to some vertex of $\Gamma(v_2)\setminus\{z\}$, then

check if $z$ can belong to some  of $G$ which contains $e$. We do it by checking if $z$ is a common neighbour of all vertices of $\Gamma(v_i)$, for some $i\in\{1,2\}$. Since $t\geq 2$, $z$ cannot be a common neighbour of both of these vertex sets. If $z$ is not a common neighbour of any of $\Gamma(v_i)$, then it is easy to check that $z$ cannot belong to any  of $G$ which contains $e$.

TODO (if $z$ is not a common neighbour of any of $\Gamma(v_i)$, we proceed similarly to Algorithm <ref> for $B_1=\Gamma(v_2)\setminus\{z\}$ and $B_2=\Gamma(v_1)\setminus\{z\}$; we can assume that $u_1$ and $u_2$ are not incident to any non-edge of $G[B_1,B_2]$; we search for two vertex-disjoint non-edges in $G[B_1,B_2]$ – if found, we return $A$ as the set of all processed vertices of degree at most one in $\hat{G}$; if only one non-edge is found and $z$ is not incident to all but one vertices of $B_1$ and a remaining neighbour of $u_2$, return $A$ as all vertices of $B_1$ and $B_2$ which are isolated in $\hat{G}$; otherwise, add the remaining neighbour of $u_2$ to $B_1$, add $z$ to $B_2$ and we search for a  which contains an edge $(v_1,u_2)$; if not found, we return $A$ as the set of all vertices of $B_1$ and $B_2$ which are isolated in $\hat{G}$)

TODO (if $z$ is a common neighbour of, say, $\Gamma(v_2)$, we proceed similarly to Algorithm <ref> for $B_1=\Gamma(v_2)$ and $B_2=\Gamma(v_1)\setminus\{z\}$; we have to check if the complement of $G[B_1,B_2]$ is a star whose the center belongs to $B_1$; if not, $e$ does not belong to any  of $G$; in this case it is enough to consider any edge of $\hat{G}$ and to prove that $v_1$, $v_2$ and $z$ cannot belong to any  of $G$, using the fact that $z$ is incident to $v_1$ and every vertex of $B_2$)

If $v_1$ and $v_2$ have exactly two common neighbours $z_1$ and $z_2$, then it is easy to notice that if some  $H$ of $G$ contains $e$, then $V_1(H)=\Gamma(v_i)\setminus\{z_j\}$ and $V_2(H)=\Gamma(v_{3-i})\setminus\{z_{3-j}\}$ for some $i,j\in\{1,2\}$. Therefore, we check in $\mathcal{O}(t)$ time if $z_1$ and $z_2$ are common neighbours of, respectively, $\Gamma(v_2)$ and $\Gamma(v_1)$, or vice versa. If not, we return that no  of $G$ contains $e$.

TODO (Otherwise, we proceed similarly to Algorithm <ref>, but we set $B_1=\Gamma(v_1)\setminus\{z_j\}$ and $B_2=\Gamma(v_2)\setminus\{z_{3-j}\}$ for some $j\in\{1,2\}$; search for any non-edge in $G[B_1,B_2]$; if found, return $A$ as the set of all processed vertices (they are isolated in $\hat{G}$); describe analysis of Algorithm <ref> in this case)

Procedure FIND in this case can be seen as a generalization of procedure FIND for 's. It is parametrized by an edge $e=(v_1,v_2)$. We assume that $\deg_G(v_1)=\deg_G(v_2)=t+1$ by adding artificial vertices if neccessary. We use the following generalization of Observation <ref> to 's.

For any edge $(u_1,u_2)$ of some  of $G$, $(p-2)q\leq|\Gamma(u_1)\cap\Gamma(u_2)|\leq (p-2)q+2$.

We check at the beginning if the number of common neighbours of $v_1$ and $v_2$ is between $(p-2)q$ and $(p-2)q+2$. If not, we return that there is no  of $G$ which contains $e$ in $\Theta(t)$ time. Otherwise, we construct a partition of the neighbours of $v_1$ and $v_2$ which roughly corresponds to the partition of any  of $G$ which contains $e$ into its color classes. The details are given in the following lemma.

Assume that the number of the common neighbours of $v_1$ and $v_2$ is between $(p-2)q$ and $(p-2)q+2$. Then we can construct a procedure which works in $\mathcal{O}(t)$ time and it either finds out that no  of $G$ contains $e$, or it returns three pairwise disjoint subsets of the vertices of $G$, namely $B_0$, $B_1$ and $B_2$, such that for every  $H$ of $G$ which contains $e$, all of the following conditions are satisfied:

* $V_i(H) \subseteq B_i$ for every $i\in\{1,2\}$, and

* $V(H)\setminus (V_1(H)\cup V_2(H)) \subseteq B_0$.

Moreover, $B_0$, $B_1$ and $B_2$ satisfy all of the following conditions:

* $v_i\in B_i$ for every $i\in\{1,2\}$, and

* $|B_0|=(p-2)q+k$ and $q\leq |B_1|,|B_2|\leq q+(1-k)$ for some $k\in\{0,1\}$, and

* for every $i\in\{1,2\}$, $v_i$ is adjacent to every vertex of $B_0$ and $B_{3-i}$; an only other neighbour of $v_i$, if it exists, it belongs to $B_i$.

We consider three separate cases depending on the number of common neighbours of $v_1$ and $v_2$. We set $B_0=\Gamma(v_1)\cap\Gamma(v_2)$ and $B_i=\Gamma(v_{3-i})\setminus\Gamma(v_i)$ for $i\in\{1,2\}$ at the beginning. However, some common neighbours of $v_1$ and $v_2$ can belong to the same color class of some  of $G$ to which $e$ belongs as $v_1$ or $v_2$. Therefore, we have to possibly move some vertices from $B_0$ to $B_1$ or $B_2$. We use the following observation to find these vertices.

Let $H$ be any  of $G$. Then the edge set of a subgraph of $G$ induced on any color class of $H$ is a matching.

Therefore, if some vertex $v\in\Gamma(v_1)\cap\Gamma(v_2)$ belongs to the same color class of a  of $G$ which contains $e$ as $v_i$, for some $i\in\{1,2\}$, it cannot be adjacent to any other vertex of this color class.

TODO (for every $i\in\{1,2\}$, we consider a constant number of the vertices of $B_i$ and search for vertices of $\Gamma(v_1)\cap\Gamma(v_2)$ which are not adjacent to them; if there is more than a constant number of such vertices in $\Gamma(v_1)\cap\Gamma(v_2)$, then there is no ; otherwise, move these vertices from $B_0$ to $B_1$ or $B_2$ depending on the size of $B_0$)

TODO (search for 's in $B_0$, $B_1$ and $B_2$ from Lemma <ref> similarly to 's; check if almost all vertices of $B_i$ are adjacent to almost all vertices of $B_0$ and $B_{3-i}$, then run procedure FIND recursively on $B_0$; if it fails and returns $A$, return roughly $A\cup B_0\cup B_1$)

Procedure add proof of Lemma <ref> for  for $p\geq 3$ and $2<q\leq \Theta(1)$ FIND for this case is parametrized by a vertex $v$ and is similiar to procedure FIND for 's. We can assume that $\deg_G(v)=t+1$. We will use the following observation.

Let $H$ be any  of $G$. Then the complement of $G[V(H)]$ is a matching. Moreover, $G[V(H)]$ is a dense subgraph if and only if the complement of $G[V(H)]$ have at least four isolated vertices. In such case, these isolated vertices form a core of $G[V(H)]$.

A general idea to check if some  of $G$ contains $v$, is to search for all $K^{p-1}_2$'s of $G$ whose all vertices are the neighbours of $v$. If we find them, we check if it is possible to extend them to 's of $G$ which contain $v$. We give the details of procedure FIND below.

At the beginning we describe in details how to find $K^{p-1}_2$'s of $G$ in $\Gamma(v)$. We do it similarly to Algorithm <ref>. We process the neighbours of $v$ one by one and we add found non-edges of $G[\Gamma(v)]$ to an auxiliary graph $\hat{G}$. We stop this process if there is no vertex in $\hat{G}$ whose removal results in a graph whose edge set is a matching.

TODO (define set $A$)

If procedure FIND returns set $A$, then it works in $\mathcal{O}(t|A|)$ time and no vertex of $A$ belongs to any  of $G$.

TODO (similiar to the proof of Claim <ref>)

TODO (extend found $K^{p-1}_2$'s to 's which contain $v$ by searching for common neighbours of the vertex sets of found $K^{p-1}_2$'s)

TODO (write that it can be done similarly to procedure FIND for 's)

§.§ Finding the potential functions

In this subsection, we present how to find the potential function of any forbidden subgraph of $G$.
We use the following observations to do so.

Consider any triangle $t$ of $G$. Then there exists exactly one potential function of $t$.

The potential function of any  of $G$ can be calculated in $\mathcal{O}(t^2)$ time by covering the set of its vertices by triangles and by using Observation <ref>.

Consider any $H=\ktt{}$ of $G$ and let $r_H$ be any potential function of $H$. For any real number $\delta$, define the following potential function of $H$:

\[ r_H^\delta(v)=\left\{\begin{array}{ll}
r_H(v)+\delta & \textrm{if $v\in V_1(H)$,}\\
r_H(v)-\delta & \textrm{if $v\in V_2(H)$.}
\end{array}\right. \]

Then the set of all potential functions of $H$ is a set of all $r_H^\delta$ over all real numbers $\delta$.

We can find any potential function of any $H=\ktt{}$ of $G$ by defining the potential of some vertex of $H$ arbitrarily which determines potentials of all other vertices of $H$. It is easy to see that this procedure can be implemented to run in $\Theta(t)$ time.

For $p\geq 3$, we can find the potential function of any  of $G$ in $\mathcal{O}(t^2)$ time using Observation <ref> in the same way as for 's.

§ CONCLUSION

We  presented the first polynomial algorithms for the weighted versions of the bounded  restricted and -free $t$-matching problems in which the weight function is vertex-induced on every forbidden subgraph. Moreover, these algorithms for the unweighted versions are faster than those known previously.

It is imaginable that our algorithms can be adapted to find  maximum size or weight $t$-matchings which contain  no complete bipartite subgraphs consisting of $t+2$ vertices in the graphs of maximum degree at most $t+1$, possibly leading to a faster algorithm for the problem of increasing connectivity by one.

Based on our result, one can suspect that the degree sequences of maximum weight restricted $t$-matchings form an $M$-concave function on the constant-parity jump system in any graph of  maximum degree at most $t+1$ if the weight function is vertex-induced on every forbidden subgraph.

We were able to generalize our method to the new $k$-restricted $t$-matching problem.
We do not know if its weighted variant in which the weight function is vertex-induced  on every subgraph from $\mathcal{K}$  can be solved in  polynomial time and we were not able to generalize our algorithm for the unweighted version to the weighted  one.
Another generalization of the $k$-restricted $t$-matching problem arises when we drop the assumption that the subgraphs from $\mathcal{K}$ are pairwise edge-disjoint. We do not know if this version is solvable in polynomial time and generalizing our algorithm to this case can be quite tedious. However, it can be quite interesting to consider a variant when all subgraphs from  $\mathcal{K}$ are isomorphic to the same $t$-regular  and the values of $k_H$ are I think that this variant should be easy the same for all $H\in\mathcal{K}$.

[1]
K. Bérczi and Y. Kobayashi.
An algorithm for $(n-3)$-connectivity augmentation problem: Jump
system approach.
Journal of Combinatorial Theory, Series B, 102(3):565–587,

[2]
K. Bérczi and L. Végh.
Restricted b-matchings in degree-bounded graphs.
In Integer Programming and Combinatorial Optimization, pages
43–56, 2010.

[3]
C. Berge.
Graphs and Hypergraphs.
North-Holland Publishing Company, 1973.

[4]
G. Cornuéjols and W. Pulleyblank.
A matching problem with side conditions.
Discrete Mathematics, 29(2):135–159, 1980.

[5]
W. Cunningham.
Matching, matroids, and extensions.
Mathematical Programming, 91:515–542, 2002.

[6]
J. Edmonds.
Maximum matching and a polyhedron with $0,1$-vertices.
Journal of Research of the National Bureau of Standards Section
B Mathematics and Mathematical Physics, pages 125–130, 1965.

[7]
M. Fisher, G. Nemhauser, and L. Wolsey.
An analysis of approximations for finding a maximum weight
hamiltonian circuit.
Operations Research, 27(4):799–809, 1979.

[8]
H. Gabow.
An efficient implementation of Edmonds' algorithm for maximum
weight matching on graphs.
Technical report, University of Colorado, 1975.

[9]
H. Gabow.
An efficient reduction technique for degree-constrained subgraph and
bidirected network flow problems.
In Proceedings of the Fifteenth Annual ACM Symposium on Theory
of Computing, pages 448–456, 1983.

[10]
Z. Galil, S. Micali, and H. Gabow.
An $O(EV\log V)$ algorithm for finding a maximal weighted matching
in general graphs.
SIAM Journal on Computing, 15:120–130, 1986.

[11]
D. Hartvigsen.
Finding maximum square-free $2$-matchings in bipartite graphs.
Journal of Combinatorial Theory, Series B, 96(5):693–705,

[12]
D. Hartvigsen and Y. Li.
Maximum cardinality simple 2-matchings in subcubic graphs.
SIAM Journal on Optimization, 21(3):1027–1045, 2011.

[13]
D. Hartvigsen and Y. Li.
Polyhedron of triangle-free simple 2-matchings in subcubic graphs.
Mathematical Programming, 138:43–82, 2013.

[14]
Y. Kobayashi.
A simple algorithm for finding a maximum triangle-free $2$-matching
in subcubic graphs.
Discrete Optimization, 7:197–202, 2010.

[15]
Y. Kobayashi.
Triangle-free $2$-matchings and $M$-concave functions on jump
Discrete Applied Mathematics, 175:35–42, 2014.

[16]
Y. Kobayashi.
Weighted triangle-free $2$-matching problem with edge-disjoint
forbidden triangles.
In Integer Programming and Combinatorial Optimization, pages
280–293, 2020.

[17]
Y. Kobayashi, J. Szabo, and K. Takazawa.
A proof of Cunningham's conjecture on restricted subgraphs and jump
Journal of Combinatorial Theory, Series B, 102:948–966, 2012.

[18]
Y. Kobayashi and X. Yin.
An algorithm for finding a maximum t-matching excluding complete
partite subgraphs.
Discrete Optimization, 9(2):98–108, 2012.

[19]
M. Makai.
On maximum cost $K_{t,t}$-free $t$-matchings of bipartite graphs.
SIAM Journal on Discrete Mathematics, 21:349–360, 2007.

[20]
Y. Nam.
Matching Theory: Subgraphs with Degree Constraints and other
PhD thesis, University of British Columbia, 1994.

[21]
K. Paluch, K. Elbassioni, and A. van Zuylen.
Simpler approximation of the maximum asymmetric traveling salesman
In 29th International Symposium on Theoretical Aspects of
Computer Science, pages 501–506, 2012.

[22]
K. Paluch and M. Wasylkiewicz.
Restricted $t$-matchings via half-edges.
In 29th Annual European Symposium on Algorithms, pages
73:1–73:17, 2021.

[23]
K. Paluch and M. Wasylkiewicz.
A simple combinatorial algorithm for restricted 2-matchings in
subcubic graphs - via half-edges.
Information Processing Letters, 171, 2021.

[24]
G. Pap.
Combinatorial algorithms for matchings, even factors and square-free
Mathematical Programming, 110:57–69, 2007.

[25]
K. Takazawa.
A weighted $K_{t,t}$-free $t$-factor algorithm for bipartite
Mathematics of Operations Research, 34(2):351–362, 2009.

[26]
L. Végh.
Augmenting undirected node-connectivity by one.
SIAM Journal on Discrete Mathematics, 25(2):695–718, 2011.

[27]
O. Vornberger.
Easy and hard cycle covers.
Technical report, Universität Paderborn, 1980.