A distance- \( d \) independent set, for any integer \( d \ge 2 \) , in a simple unweighted graph \( G \) is defined as a subset of vertices \( S \) such that any two vertices \( u, v \in S \) are at least distance \( d \) apart in \( G \) . Given an unweighted graph G and a positive integer k, the Distance- \( d \) Independent Set Problem (D \( d \) IS) asks to determine whether, there exists a distance- \( d \) independent set \( S \) in \( G \) such that \( |S| \ge k \) . D2IS is equivalent to the well-known classical independent set problem. We denote the maximization version of DdIS as MaxDdIS and the parameterized version as ParaDdIS(k) where the parameter k is the size of a distance-d independent set. In this article, we study the computational complexity of DdIS, MaxDdIS, and ParaDdIS(k) for some popular graph classes: claw-free and bisplit graphs. We have shown that DdIS ( \(d\ge 3\) ) is NP-complete for claw-free graphs with maximum degree 12. Moreover, we prove that DdIS (for \(d= 3,4\) ) is NP-complete for triangle-free and \(C_6\) -free bisplit graphs. Furthermore, we have shown that, for any \(\epsilon > 0\) , it is NP-hard to approximate MaxD3IS within a factor \(n^{1/4-\epsilon }\) and MaxD4IS within a factor \(n^{1/2-\epsilon }\) for triangle-free bisplit graphs. Further, we have shown that ParaD3IS(k) and ParaD4IS(k) are W[1]-hard for triangle-free bisplit graphs.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

On Distance-d Independent Set Problems for Some Graph Classes

  • Sandip Das,
  • Soura Sena Das,
  • Sweta Das,
  • Sk Samim Islam

摘要

A distance- \( d \) independent set, for any integer \( d \ge 2 \) , in a simple unweighted graph \( G \) is defined as a subset of vertices \( S \) such that any two vertices \( u, v \in S \) are at least distance \( d \) apart in \( G \) . Given an unweighted graph G and a positive integer k, the Distance- \( d \) Independent Set Problem (D \( d \) IS) asks to determine whether, there exists a distance- \( d \) independent set \( S \) in \( G \) such that \( |S| \ge k \) . D2IS is equivalent to the well-known classical independent set problem. We denote the maximization version of DdIS as MaxDdIS and the parameterized version as ParaDdIS(k) where the parameter k is the size of a distance-d independent set. In this article, we study the computational complexity of DdIS, MaxDdIS, and ParaDdIS(k) for some popular graph classes: claw-free and bisplit graphs. We have shown that DdIS ( \(d\ge 3\) ) is NP-complete for claw-free graphs with maximum degree 12. Moreover, we prove that DdIS (for \(d= 3,4\) ) is NP-complete for triangle-free and \(C_6\) -free bisplit graphs. Furthermore, we have shown that, for any \(\epsilon > 0\) , it is NP-hard to approximate MaxD3IS within a factor \(n^{1/4-\epsilon }\) and MaxD4IS within a factor \(n^{1/2-\epsilon }\) for triangle-free bisplit graphs. Further, we have shown that ParaD3IS(k) and ParaD4IS(k) are W[1]-hard for triangle-free bisplit graphs.