2025/06/30 by Sipra Singh, Singh, Sipra
Computer Science · Engineering · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Vehicle Routing Optimization Methods
paper · pdf · doi:10.48550/arxiv.2506.24032
openalex publication_date 2025/06/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In a large-scale network, we want to choose some influential nodes to make a profit by paying some cost within a limited budget so that we do not have to spend more budget on some nodes adjacent to the chosen nodes; our problem is the graph-theoretic representation of it. We define our problem, Dominating Set Knapsack, by attaching the knapsack problem with the dominating set on graphs. Each vertex v~(∈ V) is associated with a cost factor w(v) and a profit amount α(v). We aim to choose some vertices within a fixed budget (s) that give maximum profit so that we do not need to choose their 1-hop neighbors. We show that the Dominating Set Knapsack problem is strongly NPC even when restricted to bipartite graphs, but weakly NPC for star graphs. We present a pseudo-polynomial time algorithm for trees in time O(n⋅ min\s2, (α(V))2\). We show that Dominating Set Knapsack is unlikely to be Fixed Parameter Tractable (FPT) by proving that it is W[2]-hard parameterized by the solution size. We developed FPT algorithms with running time O(4tw⋅ nO(1) min\s2,α(V)2\) and O(2vck-1⋅ nO(1) min\s2,α(V)2\), where tw represents the tw of the given graph G(V,E), vck is the solution size of the Vertex Cover Knapsack, s is the capacity or size of the knapsack and α(V)=∑v∈ Vα(v). We obtained similar results for other variants k-Dominating Set Knapsack and Minimal Dominating Set Knapsack, where k is the size of the dominating set.