Parameterized shifted combinatorial optimization

作者：

Highlights：

• Shifted Combinatorial Optimization is an optimization framework involving the choice of several feasible solutions at once.

• In this paper, we systematically study SCO, especially from the perspective of parameterized complexity. Our results are:

• Parameterized by the size of the feasible set, SCO is XP, FPT and in P for general, decreasing and increasing costs;

• For graph properties defined by MSO logic, SCO is in XP parameterized by the formula and the graph tree- or clique-width;

• There is an MSO definable partitioning property for which SCO is W[1]-hard over graphs of bounded tree-depth.

摘要

•Shifted Combinatorial Optimization is an optimization framework involving the choice of several feasible solutions at once.•In this paper, we systematically study SCO, especially from the perspective of parameterized complexity. Our results are:•Parameterized by the size of the feasible set, SCO is XP, FPT and in P for general, decreasing and increasing costs;•For graph properties defined by MSO logic, SCO is in XP parameterized by the formula and the graph tree- or clique-width;•There is an MSO definable partitioning property for which SCO is W[1]-hard over graphs of bounded tree-depth.

论文关键词：Combinatorial optimization,Shifted problem,Treewidth,MSO logic,MSO partitioning

论文评审过程：Received 24 August 2017, Revised 31 March 2018, Accepted 22 June 2018, Available online 14 August 2018, Version of Record 10 October 2018.

论文官网地址：https://doi.org/10.1016/j.jcss.2018.06.002