49 citations · 185 across the 18 of their papers we have counts for
5 papers · 1 filter
Continuous Computational Social Choice: A Case Study in Bribery
Martin Koutecký, Nikolaos Melissinos, Tung Anh Vu +1
Computational social choice seeks algorithmic answers to questions about preference aggregation, safety of elections, robustness of outcomes, stability, etc. It overwhelmingly mode…
Approximating Max-Cut under Graph-MSO Constraints
Martin Koutecký, Jon Lee, Viswanath Nagarajan +1
We consider the max-cut and max--cut problems under graph-based constraints. Our approach can handle any constraint specified using monadic second-order (MSO) logic on graphs of…
Simplified Algorithmic Metatheorems Beyond MSO: Treewidth and Neighborhood Diversity
Dušan Knop, Martin Koutecký, Tomáš Masařík +1
This paper settles the computational complexity of model checking of several extensions of the monadic second order (MSO) logic on two classes of graphs: graphs of bounded treewidt…
Parameterized Shifted Combinatorial Optimization
Jakub Gajarský, Petr Hliněný, Martin Koutecký +1
Shifted combinatorial optimization is a new nonlinear optimization framework which is a broad extension of standard combinatorial optimization, involving the choice of several feas…
Extended Formulation for CSP that is Compact for Instances of Bounded Treewidth
Petr Kolman, Martin Koutecký
In this paper we provide an extended formulation for the class of constraint satisfaction problems and prove that its size is polynomial for instances whose constraint graph has bo…