Marek Cygan

IJCAI Conference 2025 Conference Paper

A Case for Validation Buffer in Pessimistic Actor-Critic

• Michał Nauman
• Mateusz Ostaszewski
• Marek Cygan

In this paper, we investigate the issue of error accumulation in critic networks updated via pessimistic temporal difference objectives. We show that the critic approximation error can be approximated via a recursive fixed-point model similar to that of the Bellman value. We use such recursive definition to retrieve the conditions under which the pessimistic critic is unbiased. Building on these insights, we propose Validation Pessimism Learning (VPL) algorithm. VPL uses a small validation buffer to adjust the levels of pessimism throughout the agent training, with the pessimism set such that the approximation error of the critic targets is minimized. We investigate the proposed approach on a variety of locomotion and manipulation tasks and report improvements in sample efficiency and performance.

NeurIPS Conference 2025 Conference Paper

Bigger, Regularized, Categorical: High-Capacity Value Functions are Efficient Multi-Task Learners

• Michal Nauman
• Marek Cygan
• Carmelo Sferrazza
• Aviral Kumar
• Pieter Abbeel

Recent advances in language modeling and vision stem from training large models on diverse, multi‑task data. This paradigm has had limited impact in value-based reinforcement learning (RL), where improvements are often driven by small models trained in a single-task context. This is because in multi-task RL sparse rewards and gradient conflicts make optimization of temporal difference brittle. Practical workflows for generalist policies therefore avoid online training, instead cloning expert trajectories or distilling collections of single‑task policies into one agent. In this work, we show that the use of high-capacity value models trained via cross-entropy and conditioned on learnable task embeddings addresses the problem of task interference in online RL, allowing for robust and scalable multi‑task training. We test our approach on 7 multi-task benchmarks with over 280 unique tasks, spanning high degree-of-freedom humanoid control and discrete vision-based RL. We find that, despite its simplicity, the proposed approach leads to state-of-the-art single and multi-task performance, as well as sample-efficient transfer to new tasks.

AAAI Conference 2025 Conference Paper

Decoupled Policy Actor-Critic: Bridging Pessimism and Risk Awareness in Reinforcement Learning

• Michal Nauman
• Marek Cygan

Actor-Critic (AC) algorithms like SAC and TD3 were shown to perform well in a variety of continuous-action tasks. However, the theoretical basis for the pessimistic objectives these algorithms employ remains unestablished, raising questions about the specific class of policies they are implementing. In this work, we apply the expected utility hypothesis, a fundamental concept in economics, to illustrate that both pessimistic and non-pessimistic RL objectives can be interpreted through expected utility maximization using an exponential utility function. This approach reveals that pessimistic policies effectively maximize value certainty equivalent, aligning them with the optimization of risk-aware objectives. Furthermore, we propose Decoupled Policy Actor-Critic (DAC). DAC is a model-free algorithm that features two distinct actor networks: a pessimistic actor for temporal-difference learning and an optimistic actor for exploration. Our evaluations of DAC across various locomotion and manipulation tasks demonstrate improvements in sample efficiency and final performance. Remarkably, DAC, while requiring significantly fewer computational resources, matches the performance of leading model-based methods in the complex dog and humanoid domains.

NeurIPS Conference 2025 Conference Paper

FlySearch: Exploring how vision-language models explore

• Adam Pardyl
• Dominik Matuszek
• Mateusz Przebieracz
• Marek Cygan
• Bartosz Zieliński
• Maciej Wolczyk

The real world is messy and unstructured. Uncovering critical information often requires active, goal-driven exploration. It remains to be seen whether Vision-Language Models (VLMs), which recently emerged as a popular zero-shot tool in many difficult tasks, can operate effectively in such conditions. In this paper, we answer this question by introducing FlySearch, a 3D, outdoor, photorealistic environment for searching and navigating to objects in complex scenes. We define three sets of scenarios with varying difficulty and observe that state-of-the-art VLMs cannot reliably solve even the simplest exploration tasks, with the gap to human performance increasing as the tasks get harder. We identify a set of central causes, ranging from vision hallucination, through context misunderstanding, to task planning failures, and we show that some of them can be addressed by finetuning. We publicly release the benchmark, scenarios, and the underlying codebase.

ICML Conference 2025 Conference Paper

Joint MoE Scaling Laws: Mixture of Experts Can Be Memory Efficient

• Jan Ludziejewski
• Maciej Pióro
• Jakub Krajewski
• Maciej Stefaniak
• Michal Krutul
• Jan Malasnicki
• Marek Cygan
• Piotr Sankowski

Mixture of Experts (MoE) architectures have significantly increased computational efficiency in both research and real-world applications of large-scale machine learning models. However, their scalability and efficiency under memory constraints remain relatively underexplored. In this work, we present joint scaling laws for dense and MoE models, incorporating key factors such as the number of active parameters, dataset size, and the number of experts. Our findings provide a principled framework for selecting the optimal MoE configuration under fixed memory and compute budgets. Surprisingly, we show that MoE models can be more memory-efficient than dense models, contradicting conventional wisdom. Extensive empirical validation confirms the theoretical predictions of our scaling laws. These results offer actionable insights for designing and deploying MoE models in practical large-scale training scenarios.

NeurIPS Conference 2024 Conference Paper

Bigger, Regularized, Optimistic: scaling for compute and sample efficient continuous control

• Michal Nauman
• Mateusz Ostaszewski
• Krzysztof Jankowski
• Piotr Miłoś
• Marek Cygan

Sample efficiency in Reinforcement Learning (RL) has traditionally been driven by algorithmic enhancements. In this work, we demonstrate that scaling can also lead to substantial improvements. We conduct a thorough investigation into the interplay of scaling model capacity and domain-specific RL enhancements. These empirical findings inform the design choices underlying our proposed BRO (Bigger, Regularized, Optimistic) algorithm. The key innovation behind BRO is that strong regularization allows for effective scaling of the critic networks, which, paired with optimistic exploration, leads to superior performance. BRO achieves state-of-the-art results, significantly outperforming the leading model-based and model-free algorithms across 40 complex tasks from the DeepMind Control, MetaWorld, and MyoSuite benchmarks. BRO is the first model-free algorithm to achieve near-optimal policies in the notoriously challenging Dog and Humanoid tasks.

NeurIPS Conference 2024 Conference Paper

Mixture of Tokens: Continuous MoE through Cross-Example Aggregation

• Szymon Antoniak
• Michał Krutul
• Maciej Pióro
• Jakub Krajewski
• Jan Ludziejewski
• Kamil Ciebiera
• Krystian Król
• Tomasz Odrzygóźdź

Mixture of Experts (MoE) models based on Transformer architecture are pushing the boundaries of language and vision tasks. The allure of these models lies in their ability to substantially increase the parameter count without a corresponding increase in FLOPs. Most widely adopted MoE models are discontinuous with respect to their parameters - often referred to as sparse. At the same time, existing continuous MoE designs either lag behind their sparse counterparts or are incompatible with autoregressive decoding. Motivated by the observation that the adaptation of fully continuous methods has been an overarching trend in Deep Learning, we develop Mixture of Tokens (MoT), a simple, continuous architecture that is capable of scaling the number of parameters similarly to sparse MoE models. Unlike conventional methods, MoT assigns mixtures of tokens from different examples to each expert. This architecture is fully compatible with autoregressive training and generation. Our best models not only achieve a 3x increase in training speed over dense Transformer models in language pretraining but also match the performance of state-of-the-art MoE architectures. Additionally, a close connection between MoT and MoE is demonstrated through a novel technique we call transition tuning.

ICML Conference 2024 Conference Paper

Overestimation, Overfitting, and Plasticity in Actor-Critic: the Bitter Lesson of Reinforcement Learning

• Michal Nauman
• Michal Bortkiewicz
• Piotr Milos
• Tomasz Trzcinski
• Mateusz Ostaszewski
• Marek Cygan

Recent advancements in off-policy Reinforcement Learning (RL) have significantly improved sample efficiency, primarily due to the incorporation of various forms of regularization that enable more gradient update steps than traditional agents. However, many of these techniques have been tested in limited settings, often on tasks from single simulation benchmarks and against well-known algorithms rather than a range of regularization approaches. This limits our understanding of the specific mechanisms driving RL improvements. To address this, we implemented over 60 different off-policy agents, each integrating established regularization techniques from recent state-of-the-art algorithms. We tested these agents across 14 diverse tasks from 2 simulation benchmarks, measuring training metrics related to overestimation, overfitting, and plasticity loss — issues that motivate the examined regularization techniques. Our findings reveal that while the effectiveness of a specific regularization setup varies with the task, certain combinations consistently demonstrate robust and superior performance. Notably, a simple Soft Actor-Critic agent, appropriately regularized, reliably finds a better-performing policy within the training regime, which previously was achieved mainly through model-based approaches.

ICML Conference 2024 Conference Paper

Scaling Laws for Fine-Grained Mixture of Experts

• Jan Ludziejewski
• Jakub Krajewski
• Kamil Adamczewski
• Maciej Pióro
• Michal Krutul
• Szymon Antoniak
• Kamil Ciebiera
• Krystian Król

Mixture of Experts (MoE) models have emerged as a primary solution for reducing the computational cost of Large Language Models. In this work, we analyze their scaling properties, highlighting certain arbitrary assumptions present in the existing literature. In particular, we introduce a new hyperparameter, granularity, the modification of which allows for the optimal adjustment of the size of experts. Subsequently, we present scaling laws for fine-grained MoE, taking into account the number of training tokens, model size, and granularity. Using these scaling laws, we derive the optimal training configuration for a given computational budget. Furthermore, in contrast with previous works, we demonstrate that the gap in efficiency between dense and MoE models grows as we scale up the model size and training budget.

ICML Conference 2023 Conference Paper

On Many-Actions Policy Gradient

• Michal Nauman
• Marek Cygan

We study the variance of stochastic policy gradients (SPGs) with many action samples per state. We derive a many-actions optimality condition, which determines when many-actions SPG yields lower variance as compared to a single-action agent with proportionally extended trajectory. We propose Model-Based Many-Actions (MBMA), an approach leveraging dynamics models for many-actions sampling in the context of SPG. MBMA addresses issues associated with existing implementations of many-actions SPG and yields lower bias and comparable variance to SPG estimated from states in model-simulated rollouts. We find that MBMA bias and variance structure matches that predicted by theory. As a result, MBMA achieves improved sample efficiency and higher returns on a range of continuous action environments as compared to model-free, many-actions, and model-based on-policy SPG baselines.

JAIR Journal 2018 Journal Article

Approximation and Parameterized Complexity of Minimax Approval Voting

• Marek Cygan
• Łukasz Kowalik
• Arkadiusz Socała
• Krzysztof Sornat

We present three results on the complexity of Minimax Approval Voting. First, we study Minimax Approval Voting parameterized by the Hamming distance d from the solution to the votes. We show Minimax Approval Voting admits no algorithm running in time O*(2o(d log d)), unless the Exponential Time Hypothesis (ETH) fails. This means that the O*(d2d) algorithm of Misra, Nabeel and Singh is essentially optimal. Motivated by this, we then show a parameterized approximation scheme, running in time O*((3/ε)2d), which is essentially tight assuming ETH. Finally, we get a new polynomial-time randomized approximation scheme for Minimax Approval Voting, which runs in time nO(1/ε2⋅log(1/ε))⋅poly(m), where n is a number of voters and m is a number of alternatives. It almost matches the running time of the fastest known PTAS for Closest String due to Ma and Sun.

AAAI Conference 2017 Conference Paper

Approximation and Parameterized Complexity of Minimax Approval Voting

• Marek Cygan
• _ukasz Kowalik
• Arkadiusz Soca_a
• Krzysztof Sornat

We present three results on the complexity of MINIMAX APPROVAL VOTING. First, we study MINIMAX APPROVAL VOTING parameterized by the Hamming distance d from the solution to the votes. We show MINIMAX APPROVAL VOTING admits no algorithm running in time O (2o(d log d) ), unless the Exponential Time Hypothesis (ETH) fails. This means that the O (d2d ) algorithm of Misra et al. [AAMAS 2015] is essentially optimal. Motivated by this, we then show a parameterized approximation scheme, running in time O ((3/ )2d ), which is essentially tight assuming ETH. Finally, we get a new polynomial-time randomized approximation scheme for MINIMAX APPROVAL VOTING, which runs in time nO(1/ 2 ·log(1/ )) · poly(m), almost matching the running time of the fastest known PTAS for CLOSEST STRING due to Ma and Sun [SIAM J. Comp. 2009].

FOCS Conference 2017 Conference Paper

From Gap-ETH to FPT-Inapproximability: Clique, Dominating Set, and More

• Parinya Chalermsook
• Marek Cygan
• Guy Kortsarz
• Bundit Laekhanukit
• Pasin Manurangsi
• Danupon Nanongkai
• Luca Trevisan 0001

We consider questions that arise from the intersection between the areas of approximation algorithms, subexponential-time algorithms, and fixed-parameter tractable algorithms. The questions, which have been asked several times (e. g. , [1], [2], [3]) are whether there is a non-trivial FPT-approximation algorithm for the Maximum Clique (Clique) and Minimum Dominating Set (DomSet) problems parameterized by the size of the optimal solution. In particular, letting OPT be the optimum and N be the size of the input, is there an algorithm that runs in t(OPT) poly(N) time and outputs a solution of size f(OPT), for any functions t and f that are independent of N (for Clique, we want f(OPT) = ω(1))? In this paper, we show that both Clique and DomSet admit no non-trivial FPT-approximation algorithm, i. e. , there is no o(OPT)-FPT-approximation algorithm for Clique and no f(OPT)-FPT-approximation algorithm for DomSet, for any function f (e. g. , this holds even if f is an exponential or the Ackermann function). In fact, our results imply something even stronger: The best way to solve Clique and DomSet, even approximately, is to essentially enumerate all possibilities. Our results hold under the Gap Exponential Time Hypothesis (GapETH) [4], [5], which states that no 2 o(n) -time algorithm can distinguish between a satisfiable 3SAT formula and one which is not even (1 - ε)-satisfiable for some constant ε > 0. Besides Clique and DomSet, we also rule out non-trivial FPT-approximation for Maximum Balanced Biclique, the problem of finding maximum subgraphs with hereditary properties (e. g. , Maximum Induced Planar Subgraph), and Maximum Induced Matching in bipartite graphs. Previously only exact versions of these problems were known to be W[1]-hard [6], [7], [8]. Additionally, we rule out k o(1) -FPT-approximation algorithm for Densest k-Subgraph although this ratio does not yet match the trivial O(k)-approximation algorithm. To the best of our knowledge, prior results only rule out constant factor approximation for Clique [9], [10] and log 1/4+ε (OPT) approximation for DomSet for any constant ε > 0 [11]. Our result on Clique significantly improves on [9], [10]. However, our result on DomSet is incomparable to [11] since their results hold under ETH while our results hold under Gap-ETH, which is a stronger assumption.

I&C Journal 2017 Journal Article

Hitting forbidden subgraphs in graphs of bounded treewidth

• Marek Cygan
• Dániel Marx
• Marcin Pilipczuk
• Michał Pilipczuk

We study the complexity of a generic hitting problem H-Subgraph Hitting, where given a fixed pattern graph H and an input graph G, the task is to find a set X ⊆ V ( G ) of minimum size that hits all subgraphs of G isomorphic to H. In the colorful variant of the problem, each vertex of G is precolored with some color from V ( H ) and we require to hit only H-subgraphs with matching colors. Standard techniques shows that for every fixed H, the problem is fixed-parameter tractable parameterized by the treewidth of G; however, it is not clear how exactly the running time should depend on treewidth. For the colorful variant, we demonstrate matching upper and lower bounds showing that the dependence of the running time on treewidth of G is tightly governed by μ ( H ), the maximum size of a minimal vertex separator in H. That is, we show for every fixed H that, on a graph of treewidth t, the colorful problem can be solved in time 2 O ( t μ ( H ) ) ⋅ | V ( G ) |, but cannot be solved in time 2 o ( t μ ( H ) ) ⋅ | V ( G ) | O ( 1 ), assuming the Exponential Time Hypothesis (ETH). Furthermore, we give some preliminary results showing that, in the absence of colors, the parameterized complexity landscape of H-Subgraph Hitting is much richer.

SODA Conference 2016 Conference Paper

Algorithmic Complexity of Power Law Networks

• Pawel Brach
• Marek Cygan
• Jakub Lacki
• Piotr Sankowski

It was experimentally observed that the majority of real-world networks are scale-free and follow power law degree distribution. The aim of this paper is to study the algorithmic complexity of such “typical” networks. The contribution of this work is twofold. First, we define a deterministic condition for checking whether a graph has a power law degree distribution and experimentally validate it on real-world networks. This definition allows us to derive interesting properties of power law networks. We observe that for exponents of the degree distribution in the range [1, 2] such networks exhibit double power law phenomenon that was observed for several real-world networks. Our observation indicates that this phenomenon could be explained by just pure graph theoretical properties. The second aim of our work is to give a novel theoretical explanation why many algorithms run faster on real-world data than what is predicted by algorithmic worst-case analysis. We show how to exploit the power law degree distribution to design faster algorithms for a number of classic P-time problems including transitive closure, maximum matching, determinant, PageRank and matrix inverse. Moreover, we deal with the problems of counting triangles and finding maximum clique. In contrast to previously done average-case analyses, we believe that this is the first “waterproof” argument that explains why many real-world networks are easier. Moreover, an interesting aspect of this study is the existence of structure oblivious algorithms, i. e. , algorithms that run faster on power law networks without explicit knowledge of this fact or explicit knowledge of the parameters of the degree distribution, e. g. , algorithms for maximum clique or triangle counting.

SODA Conference 2016 Conference Paper

Lower bounds for the parameterized complexity of Minimum Fill-In and other completion problems

• Ivan Bliznets
• Marek Cygan
• Pawel Komosa
• Lukás Mach
• Michal Pilipczuk

SODA Conference 2016 Conference Paper

Online Pricing with Impatient Bidders

• Marek Cygan
• Marcin Mucha
• Piotr Sankowski
• Qiang Zhang

SODA Conference 2016 Conference Paper

Tight Bounds for Graph Homomorphism and Subgraph Isomorphism

• Marek Cygan
• Fedor V. Fomin
• Alexander Golovnev
• Alexander S. Kulikov
• Ivan Mihajlin
• Jakub Pachocki
• Arkadiusz Socala

We prove that unless Exponential Time Hypothesis (ETH) fails, deciding if there is a homomorphism from graph G to graph H cannot be done in time | V ( H )| o (| V ( G )|). We also show an exponential-time reduction from G raph H omomorphism to S ubgraph I somorphism. This rules out (subject to ETH) a possibility of | V ( H )| o (| V ( H )|) -time algorithm deciding if graph G is a subgraph of H. For both problems our lower bounds asymptotically match the running time of brute-force algorithms trying all possible mappings of one graph into another. Thus, our work closes the gap in the known complexity of these fundamental problems.

I&C Journal 2015 Journal Article

Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth

• Hans L. Bodlaender
• Marek Cygan
• Stefan Kratsch
• Jesper Nederlof

It is well known that many local graph problems, like Vertex Cover and Dominating Set, can be solved in time 2 O ( tw ) | V | O ( 1 ) for graphs G = ( V, E ) with a given tree decomposition of width tw. However, for nonlocal problems, like the fundamental class of connectivity problems, for a long time we did not know how to do this faster than tw O ( tw ) | V | O ( 1 ). Recently, Cygan et al. (FOCS 2011) presented Monte Carlo algorithms for a wide range of connectivity problems running in time c tw | V | O ( 1 ) for a small constant c, e. g. , for Hamiltonian Cycle and Steiner Tree. Naturally, this raises the question whether randomization is necessary to achieve this runtime; furthermore, it is desirable to also solve counting and weighted versions (the latter without incurring a pseudo-polynomial cost in the runtime in terms of the weights). We present two new approaches rooted in linear algebra, based on matrix rank and determinants, which provide deterministic c tw | V | O ( 1 ) time algorithms, also for weighted and counting versions. For example, in this time we can solve Traveling Salesman or count the number of Hamiltonian cycles. The rank based ideas provide a rather general approach for speeding up even straightforward dynamic programming formulations by identifying “small” sets of representative partial solutions; we focus on the case of expressing connectivity via sets of partitions, but the essential ideas should have further applications. The determinant-based approach uses the Matrix Tree Theorem for deriving closed formulas for counting versions of connectivity problems; we show how to evaluate those formulas via dynamic programming.

I&C Journal 2015 Journal Article

Faster exponential-time algorithms in graphs of bounded average degree

• Marek Cygan
• Marcin Pilipczuk

We present a number of exponential-time algorithms for problems in sparse matrices and graphs of bounded average degree. First, we obtain a simple algorithm that computes a permanent of an n × n matrix over an arbitrary commutative ring with at most dn non-zero entries using O ⋆ ( 2 ( 1 − 1 / ( 3. 55 d ) ) n ) time and ring operations, 1 improving and simplifying the recent result of Izumi and Wadayama [FOCS 2012]. Second, we present a simple algorithm for counting perfect matchings in an n-vertex graph in O ⋆ ( 2 n / 2 ) time and polynomial space; our algorithm matches the complexity bounds of the algorithm of Björklund [SODA 2012], but relies on inclusion–exclusion principle instead of algebraic transformations. Third, we show a combinatorial lemma that bounds the number of “Hamiltonian-like” structures in a graph of bounded average degree. Using this result, we show that 1. a minimum weight Hamiltonian cycle in an n-vertex graph with average degree bounded by d can be found in O ⋆ ( 2 ( 1 − ε d ) n ) time and exponential space for a constant ε d depending only on d; 2. the number of perfect matchings in an n-vertex graph with average degree bounded by d can be computed in O ⋆ ( 2 ( 1 − ε d ′ ) n / 2 ) time and exponential space, for a constant ε d ′ depending only on d. The algorithm for minimum weight Hamiltonian cycle generalizes the recent results of Björklund et al. [TALG 2012] on graphs of bounded degree.

STOC Conference 2014 Conference Paper

Minimum bisection is fixed parameter tractable

• Marek Cygan
• Daniel Lokshtanov
• Marcin Pilipczuk
• Michal Pilipczuk
• Saket Saurabh 0001

STOC Conference 2013 Conference Paper

Fast hamiltonicity checking via bases of perfect matchings

• Marek Cygan
• Stefan Kratsch
• Jesper Nederlof

For an even integer t ≥ 2, the Matching Connectivity matrix H t is a matrix that has rows and columns both labeled by all perfect matchings of the complete graph K t on t vertices; an entry H t [M 1 ,M 2 ] is 1 if M 1 ∪ M 2 is a Hamiltonian cycle and 0 otherwise. Motivated by the computational study of the Hamiltonicity problem, we present three results on the structure of H t : We first show that H t has rank exactly 2 t/2-1 over GF(2) via an appropriate factorization that explicitly provides families of matchings X t forming bases for H t . Second, we show how to quickly change representation between such bases. Third, we notice that the sets of matchings X t induce permutation matrices within H t . We use the factorization to derive an 1.888 n n O(1) time Monte Carlo algorithm that solves the Hamiltonicity problem in directed bipartite graphs. Our algorithm as well counts the number of Hamiltonian cycles modulo two in directed bipartite or undirected graphs in the same time bound. Moreover, we use the fast basis change algorithm from the second result to present a Monte Carlo algorithm that given an undirected graph on n vertices along with a path decomposition of width at most pw decides Hamiltonicity in (2+√2) pw n O(1) time. Finally, we use the third result to show that for every ε >0 this cannot be improved to (2+√2-ε) pw n O(1) time unless the Strong Exponential Time Hypothesis fails, i.e., a faster algorithm for this problem would imply the breakthrough result of an O((2-ε') n ) time algorithm for CNF-Sat.

SODA Conference 2013 Conference Paper

How to Sell Hyperedges: The Hypermatching Assignment Problem

• Marek Cygan
• Fabrizio Grandoni 0001
• Monaldo Mastrolilli

We are given a set of clients with budget constraints and a set of indivisible items. Each client is willing to buy one or more bundles of (at most) k items each (bundles can be seen as hyperedges in a k -hypergraph). If client i gets a bundle e, she pays b i, e and yields a net profit w i, e. The Hypermatching Assignment Problem (HAP) is to assign a set of pairwise disjoint bundles to clients so as to maximize the total profit while respecting the budgets. This problem has various applications in production planning and budget-constrained auctions and generalizes well-studied problems in combinatorial optimization: for example the weighted (unweighted) k -hypergraph matching problem is the special case of HAP with one client having unbounded budget and general (unit) profits; the Generalized Assignment Problem (GAP) is the special case of HAP with k = 1. Let ε > 0 denote an arbitrarily small constant. In this paper we obtain the following main results: • We give a randomized ( k + 1 + ∊) approximation algorithm for HAP, which is based on rounding the 1-round Lasserre strengthening of a novel LP. This is one of a few approximation results based on Lasserre hierarchies and our approach might be of independent interest. We remark that for weighted k -hypergraph matching no LP nor SDP relaxation is known to have integrality gap better than k − 1 + 1/ k for general k [Chan and Lau, SODA'10]. • For the relevant special case that one wants to maximize the total revenue (i. e. , b i, e = w i, e ), we present a local search based ( k + O (√ k ))/2 approximation algorithm for k = O (1). This almost matches the best known ( k + 1 + ∊)/2 approximation ratio by Berman [SWAT'00] for the (less general) weighted k -hypergraph matching problem. • For the unweighted k -hypergraph matching problem, we present a ( k + 1 + ∊)/3 approximation in quasipolynomial time. This improves over the ( k + 2)/3 approximation by Halldórsson [SODA'95] (also in quasipolynomial time). In particular this suggests that a 4/3 + ∊ approximation for 3-dimensional matching might exist, whereas the currently best known polynomial-time approximation ratio is 3/2.

FOCS Conference 2013 Conference Paper

Improved Approximation for 3-Dimensional Matching via Bounded Pathwidth Local Search

• Marek Cygan

One of the most natural optimization problems is the k-SET PACKING problem, where given a family of sets of size at most k one should select a maximum size subfamily of pairwise disjoint sets. A special case of 3-SET PACKING is the well known 3-DIMENSIONAL MATCHING problem, which is a maximum hypermatching problem in 3-uniform tripartite hypergraphs. Both problems belong to the Karp's list of 21 NP-complete problems. The best known polynomial time approximation ratio for k-SET PACKING is (k + ε)/2 and goes back to the work of Hurkens and Schrijver [SIDMA'89], which gives (1. 5+ε)-approximation for 3-DIMENSIONAL MATCHING. Those results are obtained by a simple local search algorithm, that uses constant size swaps. The main result of this paper is a new approach to local search for k-SET PACKING where only a special type of swaps is considered, which we call swaps of bounded pathwidth. We show that for a fixed value of k one can search the space of r-size swaps of constant pathwidth in c r poly(|F|) time. Moreover we present an analysis proving that a local search maximum with respect to O(log |F|)-size swaps of constant pathwidth yields a polynomial time (k+1+ε)/3-approximation algorithm, improving the best known approximation ratio for k-SET PACKING. In particular we improve the approximation ratio for 3-DIMENSIONAL MATCHING from 3/2+ε to 4/3+ε.

SODA Conference 2013 Conference Paper

Known algorithms for EDGE CLIQUE COVER are probably optimal

• Marek Cygan
• Marcin Pilipczuk
• Michal Pilipczuk

FOCS Conference 2013 Conference Paper

The Planar Directed K-Vertex-Disjoint Paths Problem Is Fixed-Parameter Tractable

• Marek Cygan
• Dániel Marx
• Marcin Pilipczuk
• Michal Pilipczuk

Given a graph G and k pairs of vertices (s 1, t 1 ), .. ., (s k, t k ), the k-Vertex-Disjoint Paths problem asks for pair wise vertex-disjoint paths P 1, .. ., Pk such that Pi goes from si to ti. Schrijver [SICOMP'94] proved that the k-Vertex-Disjoint Paths problem on planar directed graphs can be solved in time nO(k). We give an algorithm with running time 2 2O(k2) * n O(1) for the problem, that is, we show the fixed-parameter tractability of the problem.

FOCS Conference 2012 Conference Paper

Algorithmic Applications of Baur-Strassen's Theorem: Shortest Cycles, Diameter and Matchings

• Marek Cygan
• Harold N. Gabow
• Piotr Sankowski

Consider a directed or undirected graph with integral edge weights in [-W, W]. This paper introduces a general framework for solving problems on such graphs using matrix multiplication. The framework is based on the Baur-Strassen Theorem and Strojohann's determinant algorithm. For directed and undirected graphs without negative cycles we obtain simple Õ(Wn ω ) running time algorithms for finding a shortest cycle, computing the diameter or radius, and detecting a negative weight cycle. For each of these problems we unify and extend the class of graphs for which Õ(Wn ω ) time algorithms are known. In particular no such algorithms were known for any of these problems in undirected graphs with (potentially) negative weights. We also present an Õ(Wn ω ) time algorithm for minimum weight perfect matching. This resolves an open problem posed by Sankowski in 2006, who presented such an algorithm for bipartite graphs. Our algorithm uses a novel combinatorial interpretation of the linear program dual for minimum perfect matching. We believe this framework will find applications for finding larger spectra of related problems. As an example we give a simple Õ(Wn ω ) time algorithm to find all the vertices that lie on cycles of length at most t, for given t. This improves an Õ(Wn ω ) time algorithm of Yuster.

FOCS Conference 2012 Conference Paper

Designing FPT Algorithms for Cut Problems Using Randomized Contractions

• Rajesh Chitnis
• Marek Cygan
• MohammadTaghi Hajiaghayi
• Marcin Pilipczuk
• Michal Pilipczuk

We introduce a new technique for designing fixed-parameter algorithms for cut problems, namely randomized contractions. With our framework: (1) We obtain the first FPT algorithm for the parameterized version of the UNIQUE LABEL COVER problem, with single exponential dependency on the size of the cutset and the size of the alphabet. As a consequence, we extend the set of the polynomial time solvable instances of UNIQUE GAMES to those with at most O(√{log n}) violated constraints. (2) We obtain a new FPT algorithm for the STEINER CUT problem with exponential speed-up over the recent work of Kawarabayashi and Thorup (FOCS'11). (3) We show how to combine considering 'cut' and 'uncut' constraints at the same time. We define a robust problem NODE MULTIWAY CUT-UNCUT that can serve as an abstraction of introducing uncut constraints, and show that it admits an FPT algorithm with single exponential dependency on the size of the cutset. To the best of our knowledge, the only known way of tackling uncut constraints was via the approach of Marx, O'Sullivan and Razgon (STACS'10), which yields algorithms with double exponential running time. An interesting aspect of our algorithms is that they can handle real weights, to the best of our knowledge, the technique of important separators does not work in the weighted version.

FOCS Conference 2012 Conference Paper

LP Rounding for k-Centers with Non-uniform Hard Capacities

• Marek Cygan
• MohammadTaghi Hajiaghayi
• Samir Khuller

In this paper we consider a generalization of the classical k-center problem with capacities. Our goal is to select k centers in a graph, and assign each node to a nearby center, so that we respect the capacity constraints on centers. The objective is to minimize the maximum distance a node has to travel to get to its assigned center. This problem is NP-hard, even when centers have no capacity restrictions and optimal factor 2 approximation algorithms are known. With capacities, when all centers have identical capacities, a 6 approximation is known with no better lower bounds than for the infinite capacity version. While many generalizations and variations of this problem have been studied extensively, no progress was made on the capacitated version for a general capacity function. We develop the first constant factor approximation algorithm for this problem. Our algorithm uses an LP rounding approach to solve this problem, and works for the case of non-uniform hard capacities, when multiple copies of a node may not be chosen and can be extended to the case when there is a hard bound on the number of copies of a node that may be selected. Finally, for non-uniform soft capacities we present a much simpler 11-approximation algorithm, which we find as one more evidence that hard capacities are much harder to deal with.

MFCS Conference 2012 Conference Paper

Sitting Closer to Friends Than Enemies, Revisited

• Marek Cygan
• Marcin Pilipczuk
• Michal Pilipczuk
• Jakub Onufry Wojtaszczyk

Abstract Signed graphs, i. e. , undirected graphs with edges labelled with a plus or minus sign, are commonly used to model relationships in social networks. Recently, Kermarrec and Thraves [13] initiated the study of the problem of appropriately visualising the network: They asked whether any signed graph can be embedded into the metric space ℝ l in such a manner that every vertex is closer to all its friends (neighbours via positive edges) than to all its enemies (neighbours via negative edges). Interestingly, embeddability into ℝ 1 can be expressed as a purely combinatorial problem. In this paper we pursue a deeper study of this case, answering several questions posed by Kermarrec and Thraves. First, we refine the approach of Kermarrec and Thraves for the case of complete signed graphs by showing that the problem is closely related to the recognition of proper interval graphs. Second, we prove that the general case, whose polynomial-time tractability remained open, is in fact NP -complete. Finally, we provide lower and upper bounds for the time complexity of the general case: we prove that the existence of a subexponential time (in the number of vertices and edges of the input signed graph) algorithm would violate the Exponential Time Hypothesis, whereas a simple dynamic programming approach gives a running time single-exponential in the number of vertices.

TCS Journal 2011 Journal Article

Dominating set is fixed parameter tractable in claw-free graphs

• Marek Cygan
• Geevarghese Philip
• Marcin Pilipczuk
• Michał Pilipczuk
• Jakub Onufry Wojtaszczyk

We show that the Dominating Set problem parameterized by solution size is fixed-parameter tractable (FPT) in graphs that do not contain the claw ( K 1, 3, the complete bipartite graph on four vertices where the two parts have one and three vertices, respectively) as an induced subgraph. We present an algorithm that uses 2 O ( k 2 ) n O ( 1 ) time and polynomial space to decide whether a claw-free graph on n vertices has a dominating set of size at most k. Note that this parameterization of Dominating Set is W [ 2 ] -hard on the set of all graphs, and thus is unlikely to have an FPT algorithm for graphs in general. The most general class of graphs for which an FPT algorithm was previously known for this parameterization of Dominating Set is the class of K i, j -free graphs, which exclude, for some fixed i, j ∈ N, the complete bipartite graph K i, j as a subgraph. For i, j ≥ 2, the class of claw-free graphs and any class of K i, j -free graphs are not comparable with respect to set inclusion. We thus extend the range of graphs over which this parameterization of Dominating Set is known to be fixed-parameter tractable. We also show that, in some sense, it is the presence of the claw that makes this parameterization of the Dominating Set problem hard. More precisely, we show that for any t ≥ 4, the Dominating Set problem parameterized by the solution size is W [ 2 ] -hard in graphs that exclude the t -claw K 1, t as an induced subgraph. Our arguments also imply that the related Connected Dominating Set and Dominating Clique problems are W [ 2 ] -hard in these graph classes. Finally, we show that for any t ∈ N, the Clique problem parameterized by solution size, which is W [ 1 ] -hard on general graphs, is FPT in t -claw-free graphs. Our results add to the small and growing collection of FPT results for graph classes defined by excluded subgraphs, rather than by excluded minors.

FOCS Conference 2011 Conference Paper

Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time

• Marek Cygan
• Jesper Nederlof
• Marcin Pilipczuk
• Michal Pilipczuk
• Johan M. M. van Rooij
• Jakub Onufry Wojtaszczyk

For the vast majority of local problems on graphs of small tree width (where by local we mean that a solution can be verified by checking separately the neighbourhood of each vertex), standard dynamic programming techniques give c^tw |V|^O(1) time algorithms, where tw is the tree width of the input graph G = (V, E) and c is a constant. On the other hand, for problems with a global requirement (usually connectivity) the best -- known algorithms were naive dynamic programming schemes running in at least tw^tw time. We breach this gap by introducing a technique we named Cut&Count that allows to produce c^tw |V|^O(1) time Monte Carlo algorithms for most connectivity-type problems, including Hamiltonian Path, Steiner Tree, Feedback Vertex Set and Connected Dominating Set. These results have numerous consequences in various fields, like parameterized complexity, exact and approximate algorithms on planar and H-minor-free graphs and exact algorithms on graphs of bounded degree. The constant c in our algorithms is in all cases small, and in several cases we are able to show that improving those constants would cause the Strong Exponential Time Hypothesis to fail. In contrast to the problems aiming to minimize the number of connected components that we solve using Cut&Count as mentioned above, we show that, assuming the Exponential Time Hypothesis, the aforementioned gap cannot be breached for some problems that aim to maximize the number of connected components like Cycle Packing.

SODA Conference 2011 Conference Paper

The stubborn problem is stubborn no more (a polynomial algorithm for 3-compatible colouring and the stubborn list partition problem)

• Marek Cygan
• Marcin Pilipczuk
• Michal Pilipczuk
• Jakub Onufry Wojtaszczyk

TCS Journal 2010 Journal Article

Exact and approximate bandwidth

• Marek Cygan
• Marcin Pilipczuk

In this paper we gather several improvements in the field of exact and approximate exponential time algorithms for the Bandwidth problem. For graphs with treewidth t we present an O ( n O ( t ) 2 n ) exact algorithm. Moreover, for any two positive integers k ≥ 2, r ≥ 1, we present a ( 2 k r − 1 ) -approximation algorithm that solves Bandwidth for an arbitrary input graph in O ∗ ( k n ( k − 1 ) r ) time and polynomial space where by O ∗ we denote the standard big O notation but omitting polynomial factors. Finally, we improve the currently best known exact algorithm for arbitrary graphs with an O ( 4. 38 3 n ) time and space algorithm. In the algorithms for the small treewidth we develop a technique based on the Fast Fourier Transform, parallel to the Fast Subset Convolution techniques introduced by Björklund et al. This technique can be also used as a simple method of finding a chromatic number of all subgraphs of a given graph in O ∗ ( 2 n ) time and space, what matches the best known results.