AG 1   Info

AG Audience

English

30 Minutes

Saarbrücken

Finding a small set of sufficiently good solutions for a given problem that are diverse, instead of just one best solution has recently become a notable topic in theoretical computer science. As in many cases even finding a single solution is computationally hard, we analyze the problems from the perspective of parameterized complexity. Recently it was shown that under a standard parameterization by treewidth, one can find diverse solutions for many problems with only a very small additional cost. We investigate a much stronger graph parameter, the clique-width, which can additionally describe some dense graph classes. We show that for almost any vertex problem if we are given a dynamic program solving that problem on clique-width decomposition, we can modify it to produce a few solutions that are as diverse as possible with as little overhead as in the above-mentioned treewidth paper. As a consequence, we prove that the diverse version of any MSO1 expressible vertex problem can be solved in FPT time parameterized by clique-width, the number of sought solutions, and the number of quantifiers in the formula. Moreover, our proof allows for a more general natural collection of diversity functions, contrary to the two measures mostly studied in the past. That might be of independent interest as a larger pool of different diversity functions can highlight various aspects of the solutions.

Nidhi Rathi

+49 681 9325 1134

--email hidden

Zoom

897 027 2575

passcode not visible

logged in users only