Bribery and Control in Elections are a central theme in voting theory. In bribery problems, an external agent sometimes called a manipulator attempts to change the election outcome by paying selected voters to alter their preferences. The cost of a bribery depends on the voting rule and the way in which preferences are changed. We study the computational complexity of bribery and control under the lens of classical and parameterized complexity.
In the real world, many optimization problems involve selecting a subset of items of the universe to minimize the cost, risk, or budget and maximize the profit, gain or value. This is exactly the classical KNAPSACK problem. However, the items are often inter-connected in the real world and thus it makes sense to describe as a graph on them that models dependencies, structures and relationships between items. We look for the solution to problem that not only satisfies the knapsack constraints but also respects some structural constraints. To ground this to a practical application: In an Internet of Things (IoT) network, sensor deployment must ensure that all areas are covered while keeping the deployment cost within budget. A naive selection of sensors may lead to gaps in coverage or unnecessary redundancy, making the problem challenging. A Connected Knapsack can be the optimal choice to place the sensors.
Needless to say, such optimization problems are NP-hard. They are unlikely to admit polynomial-time algorithms unless P = NP. Given this inherent complexity, a fundamental question that arises is whether we can design algorithms that either provide approximate solutions or leverage additional information to find exact solutions in polynomial time?