Scholarlink

<p>In this paper, we analyze the weighted partial vertex cover problem on undirected, vertex-weighted, edge-weighted trees (WPVCT). This problem has been studied in the literature from the perspectives of exact and approximation algorithms. We investigate this problem from the perspectives of parameterization and kernelization. The WPVCT problem finds applications in a number of domains including communications, logistics and data science. This problem is defined by a number of parameters (input, output and structural). We focus on the number of vertices in the optimal cover as the parameter of interest (output parameter). One of our results is a lower bound for parameterized algorithms for the WPVCT problem. A second result is a lower bound on the number of bits in a kernel for the same problem. Both these results are based on the Exponential Time Hypothesis (ETH).</p>

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

Parameterized lower bounds for the weighted vertex cover problem in trees

  • 期刊论文

  • 发表日期：

    2025年8月30日

查看全文
  • P. Wojciechowski,
  • K. Subramani

摘要

In this paper, we analyze the weighted partial vertex cover problem on undirected, vertex-weighted, edge-weighted trees (WPVCT). This problem has been studied in the literature from the perspectives of exact and approximation algorithms. We investigate this problem from the perspectives of parameterization and kernelization. The WPVCT problem finds applications in a number of domains including communications, logistics and data science. This problem is defined by a number of parameters (input, output and structural). We focus on the number of vertices in the optimal cover as the parameter of interest (output parameter). One of our results is a lower bound for parameterized algorithms for the WPVCT problem. A second result is a lower bound on the number of bits in a kernel for the same problem. Both these results are based on the Exponential Time Hypothesis (ETH).