论文标题
相关分离，独立性和匹配
Relating dissociation, independence, and matchings
论文作者
论文摘要
图中的解离集是一组顶点，最多$ 1 $诱导了最高学位的子图。计算给定图$ g $的分离数$ {\ rm diss}（g）$，定义为$ g $中的最大解离的顺序，即使$ g $被限制为二键，也很难。最近，Hosseinian和Butenko提出了一个简单的$ \ frac {4} {3} $ - 在两部分图中的分离数问题的近似算法。他们的结果依赖于不等式$ {\ rm diss}（g）\ leq \ frac {4} {3} {3}α（g-m）$隐含在其工作中，其中$ g $是两部分图形，$ m $是$ g $中的最大匹配，在$ g $中，$α（g-m）$ eyotes $ a $ a $ a $ liceotes。我们表明，对这种不平等的$（g，m）$可以有效地识别出这种不平等的$，并且可以有效地确定最大解离集。图$ g $的解离数满足$ \ max \ {α（g），2ν_s（g）\} \ leq {\ rm diss}（g）\leqα（g）+leqα（g）+ν_s（g）\ leq2α（g）$我们表明，确定$ {\ rm diss}（g）$是否等于下限和上限$ {\ rm diss}（g）$的四个项中的任何一个。
A dissociation set in a graph is a set of vertices inducing a subgraph of maximum degree at most $1$. Computing the dissociation number ${\rm diss}(G)$ of a given graph $G$, defined as the order of a maximum dissociation set in $G$, is algorithmically hard even when $G$ is restricted to be bipartite. Recently, Hosseinian and Butenko proposed a simple $\frac{4}{3}$-approximation algorithm for the dissociation number problem in bipartite graphs. Their result relies on the inequality ${\rm diss}(G)\leq\frac{4}{3}α(G-M)$ implicit in their work, where $G$ is a bipartite graph, $M$ is a maximum matching in $G$, and $α(G-M)$ denotes the independence number of $G-M$. We show that the pairs $(G,M)$ for which this inequality holds with equality can be recognized efficiently, and that a maximum dissociation set can be determined for them efficiently. The dissociation number of a graph $G$ satisfies $\max\{ α(G),2ν_s(G)\} \leq {\rm diss}(G)\leq α(G)+ν_s(G)\leq 2α(G)$, where $ν_s(G)$ denotes the induced matching number of $G$. We show that deciding whether ${\rm diss}(G)$ equals any of the four terms lower and upper bounding ${\rm diss}(G)$ is NP-hard.
