Combinatorial Problems With Closure Structures

摘要: We consider a specific class of combinatorial search respectively optimization problems where the space gives rise to closure operator and essentially hulls are only relevant subsets that must be checked in brute force approach. suggest such structure can help reduce time complexities. Moreover we propose two types (structural) parameterizations instance classes based on property outline how it could used achieve fixed-parameter tractability (FPT) characterizations. In this setting, three example described: covering problem from geometry, variant autarky propositional logic, graph finite forests.