条件G [M]との最大一致Mは2K_2フリーです

次の問題に近い文献がありますか?

均衡のとれた二分木$ {U、W } $を持つ二部グラフ$ G(V、E)$が与えられていると$ G $に完全に一致する$ M
$が存在するので、$ u_1w_1、u_2w_2 M $、$ G_1にエッジ$ u_1w_2 $またはエッジ$ u_2w_1
$(またはその両方)がありますか?

言い換えれば、誘導された部分グラフ$ G [M] $が$ 2K_2 $フリーであるように完全に一致する$ M
$があるかどうかです。 (バランスの取れた二分法を使って、私は$ | U | = | W | $を意味しました)

余分な条件は、誘導されたマッチングの問題で使用されるものとは反対の極端なものです。おそらく関連する別の1つは、$ M
$におけるエッジの収縮がグラフに残っているエッジの数を最小にするような、バイパートグラフ$ G $における$ M
$と一致する最大サイズを見つける問題である。

私はマッチングと頂点パッキングで、Plummerによって与えられた関連する問題のリストをチェックしました。成功はありませんでしたか?

PS: This problem is a special case of this decision problem :-
For a given $kinmathbb{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.

ありがとうございました。

ベストアンサー

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’$).

これにより、余分な条件は、正確に距離2でペアワイズされた線グラフ$ L(G)$から$ G
$の頂点の部分集合を見つけることになる。したがって、お互いに距離のちょうど2
の頂点が候補問題(問題の問題に近いもの)です。最近の論文(M.A. Shalu、S。Vijayakumar、S。Devi
Yamini、およびT.P.
Sandhyaによる)強いサブカラーのアルゴリズム的側面では、この問題を強力なものと呼んでいます。

いくつかのグラフクラスでは、ストーンセットの問題はNP完全であることが知られています。私は二部グラフの折れ線グラフ上の状態を知らない。この論文では、二部グラフのNP完備であると述べています。ここでの興味は、二部グラフの線グラフのクラスにあります。

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です