Scholarlink

For a graph G, a set \(S\subseteq V(G)\) is a cosecure dominating set if S is a dominating set of G and for each \(v \in S\) there exists a vertex \(v' \in N(v) \setminus S\) such that \((S \cup \{v'\}) \setminus \{v\}\) is also a dominating set. Given a graph G, Cosecure Domination  (Co-SDS, in short) asks to find a minimum cosecure dominating set for G. The problem is W[2]-hard parameterized by the solution size. Kusum and Pandey (Theor. Comput. Sci., 2024) showed that Co-SDS is linear time solvable on graphs of bounded treewidth and cliquewdith by using monadic second order logic. In this paper, we present explicit algorithms for the problem with respect to structural parameters like modular width, treewidth, distance to cluster, distance to co-cluster, and vertex cover number. Here, we want to emphasize that the running times of all our FPT algorithms are single exponential or only slightly super-exponential. We further show that Co-SDS when parameterized by vertex cover number, does not admit a polynomial kernel unless \(\mathsf{coNP \subseteq NP/poly}\) .

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

On the Parameterized Complexity of Cosecure Domination

  • 会议论文

  • 发表日期：

    2026年

查看全文
  • D. Karthika,
  • R. Muthucumaraswamy,
  • V. P. Abidha,
  • Pradeesha Ashok,
  • Sriram Bhyravarapu,
  • Sayani Das,
  • Saket Saurabh,
  • Ayush Sawlani,
  • Vikash Tripathi

摘要

For a graph G, a set \(S\subseteq V(G)\) is a cosecure dominating set if S is a dominating set of G and for each \(v \in S\) there exists a vertex \(v' \in N(v) \setminus S\) such that \((S \cup \{v'\}) \setminus \{v\}\) is also a dominating set. Given a graph G, Cosecure Domination  (Co-SDS, in short) asks to find a minimum cosecure dominating set for G. The problem is W[2]-hard parameterized by the solution size. Kusum and Pandey (Theor. Comput. Sci., 2024) showed that Co-SDS is linear time solvable on graphs of bounded treewidth and cliquewdith by using monadic second order logic. In this paper, we present explicit algorithms for the problem with respect to structural parameters like modular width, treewidth, distance to cluster, distance to co-cluster, and vertex cover number. Here, we want to emphasize that the running times of all our FPT algorithms are single exponential or only slightly super-exponential. We further show that Co-SDS when parameterized by vertex cover number, does not admit a polynomial kernel unless \(\mathsf{coNP \subseteq NP/poly}\) .