Inclusion/Exclusion Meets Measure and Conquer

Inclusion/Exclusion Meets Measure and Conquer

0.00 Avg rating0 Votes
Article ID: iaor2014933
Volume: 69
Issue: 3
Start Page Number: 685
End Page Number: 740
Publication Date: Jul 2014
Journal: Algorithmica
Authors: , ,
Keywords: optimization, programming: branch and bound
Abstract:

Inclusion/exclusion and measure and conquer are two central techniques from the field of exact exponential‐time algorithms that recently received a lot of attention. In this paper, we show that both techniques can be used in a single algorithm. This is done by looking at the principle of inclusion/exclusion as a branching rule. This inclusion/exclusion‐based branching rule can be combined in a branch‐and‐reduce algorithm with traditional branching rules and reduction rules. The resulting algorithms can be analysed using measure and conquer allowing us to obtain good upper bounds on their running times. In this way, we obtain the currently fastest exact exponential‐time algorithms for a number of domination problems in graphs. Among these are faster polynomial‐space and exponential‐space algorithms for #Dominating Set and Minimum Weight Dominating Set (for the case where the set of possible weight sums is polynomially bounded), and a faster polynomial‐space algorithm for Domatic Number. This approach is also extended in this paper to the setting where not all requirements in a problem need to be satisfied. This results in faster polynomial‐space and exponential‐space algorithms for Partial Dominating Set, and faster polynomial‐space and exponential‐space algorithms for the well‐studied parameterised problem kSet Splitting and its generalisation kNot‐All‐Equal Satisfiability.

Reviews

Required fields are marked *. Your email address will not be published.