Marek Cygan

207 papers A* 26A 11B 17C 2Misc 1Journal 133Unranked 14
YearRankTypeTitle / Venue / Authors
2026 J jnl
Reward-Conditioned Reinforcement Learning.
CoRR
Michal Nauman, Marek Cygan, Pieter Abbeel
2026 J jnl
Swim2Real: VLM-Guided System Identification for Sim-to-Real Transfer.
CoRR
Kevin Qiu, Kyle L. Walker, Mike Yan Michelis, Marek Cygan, Josie Hughes
2026 J jnl
Vid2Sid: Videos Can Help Close the Sim2Real Gap.
CoRR
Kevin Qiu, Yu Zhang, Marek Cygan, Josie Hughes
2025 A* conf
A Case for Validation Buffer in Pessimistic Actor-Critic.
IJCAI
Michal Nauman, Mateusz Ostaszewski, Marek Cygan
2025 J jnl
Bigger, Regularized, Categorical: High-Capacity Value Functions are Efficient Multi-Task Learners.
CoRR
Michal Nauman, Marek Cygan, Carmelo Sferrazza, Aviral Kumar, Pieter Abbeel
2025 J jnl
Debate2Create: Robot Co-design via Large Language Model Debates.
CoRR
Kevin Qiu, Marek Cygan
2025 A* conf
Decoupled Policy Actor-Critic: Bridging Pessimism and Risk Awareness in Reinforcement Learning.
AAAI
Michal Nauman, Marek Cygan
2025 J jnl
Decoupled Relative Learning Rate Schedules.
CoRR
Jan Ludziejewski, Jan Malasnicki, Maciej Pióro, Michal Krutul, Kamil Ciebiera, Maciej Stefaniak, Jakub Krajewski, Piotr Sankowski, Marek Cygan, Kamil Adamczewski, Sebastian Jaszczur
2025 J jnl
FlySearch: Exploring how vision-language models explore.
CoRR
Adam Pardyl, Dominik Matuszek, Mateusz Przebieracz, Marek Cygan, Bartosz Zielinski, Maciej Wolczyk
2025 A* conf
Joint MoE Scaling Laws: Mixture of Experts Can Be Memory Efficient.
ICML
Jan Ludziejewski, Maciej Pióro, Jakub Krajewski, Maciej Stefaniak, Michal Krutul, Jan Malasnicki, Marek Cygan, Piotr Sankowski, Kamil Adamczewski, Piotr Milos, Sebastian Jaszczur
2025 J jnl
Joint MoE Scaling Laws: Mixture of Experts Can Be Memory Efficient.
CoRR
Jan Ludziejewski, Maciej Pióro, Jakub Krajewski, Maciej Stefaniak, Michal Krutul, Jan Malasnicki, Marek Cygan, Piotr Sankowski, Kamil Adamczewski, Piotr Milos, Sebastian Jaszczur
2025 J jnl
Projected Compression: Trainable Projection for Efficient Transformer Compression.
CoRR
Maciej Stefaniak, Michal Krutul, Jan Malasnicki, Maciej Pióro, Jakub Krajewski, Sebastian Jaszczur, Marek Cygan, Kamil Adamczewski, Jan Ludziejewski
2025 J jnl
μ-Parametrization for Mixture of Experts.
CoRR
Jan Malasnicki, Kamil Ciebiera, Mateusz Borun, Maciej Pióro, Jan Ludziejewski, Maciej Stefaniak, Michal Krutul, Sebastian Jaszczur, Marek Cygan, Kamil Adamczewski, Jakub Krajewski
2024 J jnl
A Case for Validation Buffer in Pessimistic Actor-Critic.
CoRR
Michal Nauman, Mateusz Ostaszewski, Marek Cygan
2024 A* conf
Bigger, Regularized, Optimistic: scaling for compute and sample efficient continuous control.
NeurIPS
Michal Nauman, Mateusz Ostaszewski, Krzysztof Jankowski, Piotr Milos, Marek Cygan
2024 J jnl
Bigger, Regularized, Optimistic: scaling for compute and sample-efficient continuous control.
CoRR
Michal Nauman, Mateusz Ostaszewski, Krzysztof Jankowski, Piotr Milos, Marek Cygan
2024 A* conf
Mixture of Tokens: Continuous MoE through Cross-Example Aggregation.
NeurIPS
Szymon Antoniak, Michal Krutul, Maciej Pióro, Jakub Krajewski, Jan Ludziejewski, Kamil Ciebiera, Krystian Król, Tomasz Odrzygózdz, Marek Cygan, Sebastian Jaszczur
2024 A* conf
Overestimation, Overfitting, and Plasticity in Actor-Critic: the Bitter Lesson of Reinforcement Learning.
ICML
Michal Nauman, Michal Bortkiewicz, Piotr Milos, Tomasz Trzcinski, Mateusz Ostaszewski, Marek Cygan
2024 J jnl
Overestimation, Overfitting, and Plasticity in Actor-Critic: the Bitter Lesson of Reinforcement Learning.
CoRR
Michal Nauman, Michal Bortkiewicz, Mateusz Ostaszewski, Piotr Milos, Tomasz Trzcinski, Marek Cygan
2024 J jnl
Polite Teacher: Semi-Supervised Instance Segmentation With Mutual Learning and Pseudo-Label Thresholding.
IEEE Access
Dominik Filipiak, Andrzej Zapala, Piotr Tempczyk, Anna Fensel, Marek Cygan
2024 J jnl
RoboMorph: Evolving Robot Morphology using Large Language Models.
CoRR
Kevin Qiu, Krzysztof Ciebiera, Pawel Fijalkowski, Marek Cygan, Lukasz Kucinski
2024 A* conf
Scaling Laws for Fine-Grained Mixture of Experts.
ICML
Jan Ludziejewski, Jakub Krajewski, Kamil Adamczewski, Maciej Pióro, Michal Krutul, Szymon Antoniak, Kamil Ciebiera, Krystian Król, Tomasz Odrzygózdz, Piotr Sankowski, Marek Cygan, Sebastian Jaszczur
2024 J jnl
Scaling Laws for Fine-Grained Mixture of Experts.
CoRR
Jakub Krajewski, Jan Ludziejewski, Kamil Adamczewski, Maciej Pióro, Michal Krutul, Szymon Antoniak, Kamil Ciebiera, Krystian Król, Tomasz Odrzygózdz, Piotr Sankowski, Marek Cygan, Sebastian Jaszczur
2023 J jnl
Decoupled Actor-Critic.
CoRR
Michal Nauman, Marek Cygan
2023 J jnl
Grasping Student: semi-supervised learning for robotic manipulation.
CoRR
Piotr Krzywicki, Krzysztof Ciebiera, Rafal Michaluk, Inga Maziarz, Marek Cygan
2023 J jnl
Mixture of Tokens: Efficient LLMs through Cross-Example Aggregation.
CoRR
Szymon Antoniak, Sebastian Jaszczur, Michal Krutul, Maciej Pióro, Jakub Krajewski, Jan Ludziejewski, Tomasz Odrzygózdz, Marek Cygan
2023 A* conf
On Many-Actions Policy Gradient.
ICML
Michal Nauman, Marek Cygan
2022 J jnl
On All-Action Policy Gradients.
CoRR
Michal Nauman, Marek Cygan
2022 J jnl
One Simple Trick to Fix Your Bayesian Neural Network.
CoRR
Piotr Tempczyk, Ksawery Smoczynski, Philip Smolenski-Jensen, Marek Cygan
2022 J jnl
Polite Teacher: Semi-Supervised Instance Segmentation with Mutual Learning and Pseudo-Label Thresholding.
CoRR
Dominik Filipiak, Andrzej Zapala, Piotr Tempczyk, Anna Fensel, Marek Cygan
2022 J jnl
Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time.
ACM Trans. Algorithms
Marek Cygan, Jesper Nederlof, Marcin Pilipczuk, Michal Pilipczuk, Johan M. M. van Rooij, Jakub Onufry Wojtaszczyk
2022 J jnl
Special Section on the Fifty-Second Annual ACM Symposium on the Theory of Computing (STOC 2020).
SIAM J. Comput.
Arkadev Chattopadhyay, Marek Cygan, Noga Ron-Zewi, Christian Wulff-Nilsen
2021 A conf
Minimum Common String Partition: Exact Algorithms.
ESA
Marek Cygan, Alexander S. Kulikov, Ivan Mihajlin, Maksim Nikolaev, Grigory Reznikov
2021 J jnl
Randomized Contractions Meet Lean Decompositions.
ACM Trans. Algorithms
Marek Cygan, Pawel Komosa, Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh, Magnus Wahlström
2021 J jnl
n-CPS: Generalising Cross Pseudo Supervision to n networks for Semi-Supervised Semantic Segmentation.
CoRR
Dominik Filipiak, Piotr Tempczyk, Marek Cygan
2020 J jnl
From Gap-Exponential Time Hypothesis to Fixed Parameter Tractable Inapproximability: Clique, Dominating Set, and More.
SIAM J. Comput.
Parinya Chalermsook, Marek Cygan, Guy Kortsarz, Bundit Laekhanukit, Pasin Manurangsi, Danupon Nanongkai, Luca Trevisan
2020 J jnl
Lower Bounds for the Parameterized Complexity of Minimum Fill-in and Other Completion Problems.
ACM Trans. Algorithms
Ivan Bliznets, Marek Cygan, Pawel Komosa, Michal Pilipczuk, Lukás Mach
2020 B conf
Tight Bounds on Subexponential Time Approximation of Set Cover and Related Problems.
WAOA
Magnús M. Halldórsson, Guy Kortsarz, Marek Cygan
2020 J jnl
Tight Bounds on Subexponential Time Approximation of Set Cover and Related Problems.
CoRR
Marek Cygan, Magnús M. Halldórsson, Guy Kortsarz
2019 J jnl
Improving TSP Tours Using Dynamic Programming over Tree Decompositions.
ACM Trans. Algorithms
Marek Cygan, Lukasz Kowalik, Arkadiusz Socala
2019 J jnl
Minimum Bisection Is Fixed-Parameter Tractable.
SIAM J. Comput.
Marek Cygan, Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh
2019 J jnl
On Problems Equivalent to (min, +)-Convolution.
ACM Trans. Algorithms
Marek Cygan, Marcin Mucha, Karol Wegrzycki, Michal Wlodarczyk
2018 J jnl
Approximation and Parameterized Complexity of Minimax Approval Voting.
J. Artif. Intell. Res.
Marek Cygan, Lukasz Kowalik, Arkadiusz Socala, Krzysztof Sornat
2018 J jnl
Fast Hamiltonicity Checking Via Bases of Perfect Matchings.
J. ACM
Marek Cygan, Stefan Kratsch, Jesper Nederlof
2018 J jnl
Hardness of Approximation for
ACM Trans. Comput. Theory
Ivan Bliznets, Marek Cygan, Pawel Komosa, Michal Pilipczuk
2018 J jnl
Improved GQ-CNN: Deep Learning Model for Planning Robust Grasps.
CoRR
Maciej Jaskowski, Jakub Swiatkowski, Michal Zajac, Maciej Klimek, Jarek Potiuk, Piotr Rybicki, Piotr Polatowski, Przemyslaw Walczyk, Kacper Nowicki, Marek Cygan
2018 J jnl
On subexponential running times for approximating directed Steiner tree and related problems.
CoRR
Marek Cygan, Guy Kortsarz, Bundit Laekhanukit
2018 A conf
Online Facility Location with Deletions.
ESA
Marek Cygan, Artur Czumaj, Marcin Mucha, Piotr Sankowski
2018 J jnl
Online Facility Location with Deletions.
CoRR
Marek Cygan, Artur Czumaj, Marcin Mucha, Piotr Sankowski
2018 J jnl
Randomized contractions meet lean decompositions.
CoRR
Marek Cygan, Pawel Komosa, Daniel Lokshtanov, Michal Pilipczuk, Marcin Pilipczuk, Saket Saurabh
2017 A* conf
Approximation and Parameterized Complexity of Minimax Approval Voting.
AAAI
Marek Cygan, Lukasz Kowalik, Arkadiusz Socala, Krzysztof Sornat
2017 A* conf
From Gap-ETH to FPT-Inapproximability: Clique, Dominating Set, and More.
FOCS
Parinya Chalermsook, Marek Cygan, Guy Kortsarz, Bundit Laekhanukit, Pasin Manurangsi, Danupon Nanongkai, Luca Trevisan
2017 J jnl
From Gap-ETH to FPT-Inapproximability: Clique, Dominating Set, and More.
CoRR
Parinya Chalermsook, Marek Cygan, Guy Kortsarz, Bundit Laekhanukit, Pasin Manurangsi, Danupon Nanongkai, Luca Trevisan
2017 J jnl
Hitting forbidden subgraphs in graphs of bounded treewidth.
Inf. Comput.
Marek Cygan, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk
2017 A conf
Improving TSP Tours Using Dynamic Programming over Tree Decompositions.
ESA
Marek Cygan, Lukasz Kowalik, Arkadiusz Socala
2017 J jnl
Improving TSP tours using dynamic programming over tree decomposition.
CoRR
Marek Cygan, Lukasz Kowalik, Arkadiusz Socala
2017 A* conf
On Problems Equivalent to (min, +)-Convolution.
ICALP
Marek Cygan, Marcin Mucha, Karol Wegrzycki, Michal Wlodarczyk
2017 J jnl
On problems equivalent to (min, +)-convolution.
CoRR
Marek Cygan, Marcin Mucha, Karol Wegrzycki, Michal Wlodarczyk
2017 J jnl
Polynomial Kernelization for Removing Induced Claws and Diamonds.
Theory Comput. Syst.
Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, Erik Jan van Leeuwen, Marcin Wrochna
2017 J jnl
Randomization in Parameterized Complexity (Dagstuhl Seminar 17041).
Dagstuhl Reports
Marek Cygan, Fedor V. Fomin, Danny Hermelin, Magnus Wahlström
2017 J jnl
Tight Kernel Bounds for Problems on Graphs with Small Degeneracy.
ACM Trans. Algorithms
Marek Cygan, Fabrizio Grandoni, Danny Hermelin
2017 J jnl
Tight Lower Bounds on Graph Embedding Problems.
J. ACM
Marek Cygan, Fedor V. Fomin, Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin, Jakub Pachocki, Arkadiusz Socala
2016 J jnl
A Fast Branching Algorithm for Cluster Vertex Deletion.
Theory Comput. Syst.
Anudhyan Boral, Marek Cygan, Tomasz Kociumaka, Marcin Pilipczuk
2016 A* conf
Algorithmic Complexity of Power Law Networks.
SODA
Pawel Brach, Marek Cygan, Jakub Lacki, Piotr Sankowski
2016 J jnl
Approximation and Parameterized Complexity of Minimax Approval Voting.
CoRR
Marek Cygan, Lukasz Kowalik, Arkadiusz Socala, Krzysztof Sornat
2016 J jnl
Designing FPT Algorithms for Cut Problems Using Randomized Contractions.
SIAM J. Comput.
Rajesh Chitnis, Marek Cygan, MohammadTaghi Hajiaghayi, Marcin Pilipczuk, Michal Pilipczuk
2016 J jnl
Erratum to: Foreword: Special Issue on IPEC 2014.
Algorithmica
Marek Cygan, Pinar Heggernes
2016 — ch.
Exact Algorithms for Bandwidth.
Encyclopedia of Algorithms
Marek Cygan
2016 J jnl
Foreword: Special Issue on IPEC 2014.
Algorithmica
Marek Cygan, Pinar Heggernes
2016 — conf
Hardness of Approximation for H-Free Edge Modification Problems.
APPROX-RANDOM
Ivan Bliznets, Marek Cygan, Pawel Komosa, Michal Pilipczuk
2016 J jnl
Hardness of approximation for H-free edge modification problems.
CoRR
Ivan Bliznets, Marek Cygan, Pawel Komosa, Michal Pilipczuk
2016 J jnl
Known Algorithms for Edge Clique Cover are Probably Optimal.
SIAM J. Comput.
Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk
2016 — conf
Lower Bounds for Approximation Schemes for Closest String.
SWAT
Marek Cygan, Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh
2016 A* conf
Lower bounds for the parameterized complexity of Minimum Fill-In and other completion problems.
SODA
Ivan Bliznets, Marek Cygan, Pawel Komosa, Lukás Mach, Michal Pilipczuk
2016 J jnl
On Group Feedback Vertex Set Parameterized by the Size of the Cutset.
Algorithmica
Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk
2016 J jnl
On Problems as Hard as CNF-SAT.
ACM Trans. Algorithms
Marek Cygan, Holger Dell, Daniel Lokshtanov, Dániel Marx, Jesper Nederlof, Yoshio Okamoto, Ramamohan Paturi, Saket Saurabh, Magnus Wahlström
2016 J jnl
Online Knapsack Revisited.
Theory Comput. Syst.
Marek Cygan, Lukasz Jez, Jirí Sgall
2016 A* conf
Online Pricing with Impatient Bidders.
SODA
Marek Cygan, Marcin Mucha, Piotr Sankowski, Qiang Zhang
2016 J jnl
Polynomial-time approximation algorithms for weighted LCS problem.
Discret. Appl. Math.
Marek Cygan, Marcin Kubica, Jakub Radoszewski, Wojciech Rytter, Tomasz Walen
2016 — ch.
Randomized Contraction.
Encyclopedia of Algorithms
Marek Cygan
2016 A* conf
Tight Bounds for Graph Homomorphism and Subgraph Isomorphism.
SODA
Marek Cygan, Fedor V. Fomin, Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin, Jakub Pachocki, Arkadiusz Socala
2016 J jnl
Tight Lower Bounds on Graph Embedding Problems.
CoRR
Marek Cygan, Fedor V. Fomin, Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin, Jakub Pachocki, Arkadiusz Socala
2015 J jnl
Algorithmic Applications of Baur-Strassen's Theorem: Shortest Cycles, Diameter, and Matchings.
J. ACM
Marek Cygan, Harold N. Gabow, Piotr Sankowski
2015 J jnl
Algorithmic Complexity of Power Law Networks.
CoRR
Pawel Brach, Marek Cygan, Jakub Lacki, Piotr Sankowski
2015 — conf
Approximating Upper Degree-Constrained Partial Orientations.
APPROX-RANDOM
Marek Cygan, Tomasz Kociumaka
2015 J jnl
Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth.
Inf. Comput.
Hans L. Bodlaender, Marek Cygan, Stefan Kratsch, Jesper Nederlof
2015 J jnl
Directed Subset Feedback Vertex Set Is Fixed-Parameter Tractable.
ACM Trans. Algorithms
Rajesh Hemant Chitnis, Marek Cygan, Mohammad Taghi Hajiaghayi, Dániel Marx
2015 J jnl
Faster exponential-time algorithms in graphs of bounded average degree.
Inf. Comput.
Marek Cygan, Marcin Pilipczuk
2015 J jnl
Kernelization lower bound for Permutation Pattern Matching.
Inf. Process. Lett.
Ivan Bliznets, Marek Cygan, Pawel Komosa, Lukás Mach
2015 J jnl
Lower bounds for approximation schemes for Closest String.
CoRR
Marek Cygan, Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh
2015 J jnl
Lower bounds for the parameterized complexity of Minimum Fill-in and other completion problems.
CoRR
Ivan Bliznets, Marek Cygan, Pawel Komosa, Lukás Mach, Michal Pilipczuk
2015 — book
Parameterized Algorithms
Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh
2015 B conf
Polynomial Kernelization for Removing Induced Claws and Diamonds.
WG
Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, Erik Jan van Leeuwen, Marcin Wrochna
2015 J jnl
Polynomial kernelization for removing induced claws and diamonds.
CoRR
Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, Erik Jan van Leeuwen, Marcin Wrochna
2015 J jnl
Sitting Closer to Friends than Enemies, Revisited.
Theory Comput. Syst.
Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, Jakub Onufry Wojtaszczyk
2015 J jnl
The Hardness of Subgraph Isomorphism.
CoRR
Marek Cygan, Jakub Pachocki, Arkadiusz Socala
2014 Misc conf
A Fast Branching Algorithm for Cluster Vertex Deletion.
CSR
Anudhyan Boral, Marek Cygan, Tomasz Kociumaka, Marcin Pilipczuk
2014 J jnl
Approximating Upper Degree-Constrained Partial Orientations.
CoRR
Marek Cygan, Tomasz Kociumaka
2014 J jnl
Clique Cover and Graph Separation: New Incompressibility Results.
ACM Trans. Comput. Theory
Marek Cygan, Stefan Kratsch, Marcin Pilipczuk, Michal Pilipczuk, Magnus Wahlström
2014 A conf
Constant Factor Approximation for Capacitated k-Center with Outliers.
STACS
Marek Cygan, Tomasz Kociumaka
2014 J jnl
Constant Factor Approximation for Capacitated k-Center with Outliers.
CoRR
Tomasz Kociumaka, Marek Cygan
2014 — conf
Hitting Forbidden Subgraphs in Graphs of Bounded Treewidth.
MFCS (2)
Marek Cygan, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk
2014 J jnl
Hitting forbidden subgraphs in graphs of bounded treewidth.
CoRR
Marek Cygan, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk
2014 J jnl
Kernelization lower bound for Permutation Pattern Matching.
CoRR
Ivan Bliznets, Marek Cygan, Pawel Komosa, Lukás Mach
2014 A* conf
Minimum bisection is fixed parameter tractable.
STOC
Marek Cygan, Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh
2014 J jnl
On Cutwidth Parameterized by Vertex Cover.
Algorithmica
Marek Cygan, Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh
2014 J jnl
On the Hardness of Losing Width.
Theory Comput. Syst.
Marek Cygan, Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh
2014 J jnl
Parameterized Complexity of Eulerian Deletion Problems.
Algorithmica
Marek Cygan, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, Ildikó Schlotter
2014 B ed.
Parameterized and Exact Computation - 9th International Symposium, IPEC 2014, Wroclaw, Poland, September 10-12, 2014. Revised Selected Papers
IPEC
Marek Cygan, Pinar Heggernes
2014 J jnl
Parameterized complexity of firefighting.
J. Comput. Syst. Sci.
Cristina Bazgan, Morgan Chopin, Marek Cygan, Michael R. Fellows, Fedor V. Fomin, Erik Jan van Leeuwen
2014 J jnl
Scheduling Partially Ordered Jobs Faster than 2 n.
Algorithmica
Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, Jakub Onufry Wojtaszczyk
2014 J jnl
Solving the 2-Disjoint Connected Subgraphs Problem Faster than 2 n.
Algorithmica
Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, Jakub Onufry Wojtaszczyk
2013 J jnl
A bound on the number of perfect matchings in Klee-graphs.
Discret. Math. Theor. Comput. Sci.
Marek Cygan, Marcin Pilipczuk, Riste Skrekovski
2013 A conf
Catch them if you can: how to serve impatient users.
ITCS
Marek Cygan, Matthias Englert, Anupam Gupta, Marcin Mucha, Piotr Sankowski
2013 — conf
Deterministic Single Exponential Time Algorithms for Connectivity Problems Parameterized by Treewidth.
ICALP (1)
Hans L. Bodlaender, Marek Cygan, Stefan Kratsch, Jesper Nederlof
2013 J jnl
Fast branching algorithm for Cluster Vertex Deletion.
CoRR
Anudhyan Boral, Marek Cygan, Tomasz Kociumaka, Marcin Pilipczuk
2013 A* conf
Fast hamiltonicity checking via bases of perfect matchings.
STOC
Marek Cygan, Stefan Kratsch, Jesper Nederlof
2013 — conf
Faster Exponential-Time Algorithms in Graphs of Bounded Average Degree.
ICALP (1)
Marek Cygan, Marcin Pilipczuk
2013 J jnl
Faster exponential-time algorithms in graphs of bounded average degree
CoRR
Marek Cygan, Marcin Pilipczuk
2013 A* conf
How to Sell Hyperedges: The Hypermatching Assignment Problem.
SODA
Marek Cygan, Fabrizio Grandoni, Monaldo Mastrolilli
2013 A* conf
Improved Approximation for 3-Dimensional Matching via Bounded Pathwidth Local Search.
FOCS
Marek Cygan
2013 J jnl
Improved approximation for 3-dimensional matching via bounded pathwidth local search
CoRR
Marek Cygan
2013 A* conf
Known algorithms for EDGE CLIQUE COVER are probably optimal.
SODA
Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk
2013 J jnl
Minimum Bisection is fixed parameter tractable.
CoRR
Marek Cygan, Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh
2013 J jnl
On Pairwise Spanners
CoRR
Marek Cygan, Fabrizio Grandoni, Telikepalli Kavitha
2013 A conf
On Pairwise Spanners.
STACS
Marek Cygan, Fabrizio Grandoni, Telikepalli Kavitha
2013 J jnl
On multiway cut parameterized above lower bounds.
ACM Trans. Comput. Theory
Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, Jakub Onufry Wojtaszczyk
2013 B conf
Online Knapsack Revisited.
WAOA
Marek Cygan, Lukasz Jez
2013 J jnl
Split Vertex Deletion meets Vertex Cover: New fixed-parameter and exact exponential-time algorithms.
Inf. Process. Lett.
Marek Cygan, Marcin Pilipczuk
2013 J jnl
Steiner Forest Orientation Problems.
SIAM J. Discret. Math.
Marek Cygan, Guy Kortsarz, Zeev Nutov
2013 J jnl
Subset Feedback Vertex Set Is Fixed-Parameter Tractable.
SIAM J. Discret. Math.
Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, Jakub Onufry Wojtaszczyk
2013 A* conf
The Planar Directed K-Vertex-Disjoint Paths Problem Is Fixed-Parameter Tractable.
FOCS
Marek Cygan, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk
2013 J jnl
The planar directed k-Vertex-Disjoint Paths problem is fixed-parameter tractable
CoRR
Marek Cygan, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk
2013 J jnl
Tight Kernel Bounds for Problems on Graphs with Small Degeneracy
CoRR
Marek Cygan, Fabrizio Grandoni, Danny Hermelin
2013 A conf
Tight Kernel Bounds for Problems on Graphs with Small Degeneracy - (Extended Abstract).
ESA
Marek Cygan, Fabrizio Grandoni, Danny Hermelin
2012 A conf
A Path-Decomposition Theorem with Applications to Pricing and Covering on Trees.
ESA
Marek Cygan, Fabrizio Grandoni, Stefano Leonardi, Marcin Pilipczuk, Piotr Sankowski
2012 J jnl
A Planar linear arboricity conjecture.
J. Graph Theory
Marek Cygan, Jianfeng Hou, Lukasz Kowalik, Borut Luzar, Jian-Liang Wu
2012 J jnl
A Polynomial Algorithm for 3-Compatible Coloring and the Stubborn List Partition Problem (The Stubborn Problem Is Stubborn No More).
SIAM J. Comput.
Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, Jakub Onufry Wojtaszczyk
2012 J jnl
Algorithmic Applications of Baur-Strassen's Theorem: Shortest Cycles, Diameter and Matchings
CoRR
Marek Cygan, Harold N. Gabow, Piotr Sankowski
2012 A* conf
Algorithmic Applications of Baur-Strassen's Theorem: Shortest Cycles, Diameter and Matchings.
FOCS
Marek Cygan, Harold N. Gabow, Piotr Sankowski
2012 J jnl
An Improved FPT Algorithm and a Quadratic Kernel for Pathwidth One Vertex Deletion.
Algorithmica
Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, Jakub Onufry Wojtaszczyk
2012 J jnl
Bandwidth and distortion revisited.
Discret. Appl. Math.
Marek Cygan, Marcin Pilipczuk
2012 — conf
Clique Cover and Graph Separation: New Incompressibility Results.
ICALP (1)
Marek Cygan, Stefan Kratsch, Marcin Pilipczuk, Michal Pilipczuk, Magnus Wahlström
2012 A* conf
Designing FPT Algorithms for Cut Problems Using Randomized Contractions.
FOCS
Rajesh Hemant Chitnis, Marek Cygan, MohammadTaghi Hajiaghayi, Marcin Pilipczuk, Michal Pilipczuk
2012 J jnl
Designing FPT algorithms for cut problems using randomized contractions
CoRR
Rajesh Hemant Chitnis, Marek Cygan, MohammadTaghi Hajiaghayi, Marcin Pilipczuk, Michal Pilipczuk
2012 — conf
Deterministic Parameterized Connected Vertex Cover.
SWAT
Marek Cygan
2012 J jnl
Deterministic parameterized connected vertex cover
CoRR
Marek Cygan
2012 — conf
Directed Subset Feedback Vertex Set Is Fixed-Parameter Tractable.
ICALP (1)
Rajesh Hemant Chitnis, Marek Cygan, Mohammad Taghi Hajiaghayi, Dániel Marx
2012 J jnl
Directed Subset Feedback Vertex Set is Fixed-Parameter Tractable
CoRR
Rajesh Hemant Chitnis, Marek Cygan, MohammadTaghi Hajiaghayi, Dániel Marx
2012 J jnl
Even Faster Exact Bandwidth.
ACM Trans. Algorithms
Marek Cygan, Marcin Pilipczuk
2012 J jnl
Fast Hamiltonicity checking via bases of perfect matchings
CoRR
Marek Cygan, Stefan Kratsch, Jesper Nederlof
2012 J jnl
Kernelization hardness of connectivity problems in d-degenerate graphs.
Discret. Appl. Math.
Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, Jakub Onufry Wojtaszczyk
2012 J jnl
Known algorithms for EDGE CLIQUE COVER are probably optimal
CoRR
Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk
2012 J jnl
LP Rounding for k-Centers with Non-uniform Hard Capacities
CoRR
Marek Cygan, MohammadTaghi Hajiaghayi, Samir Khuller
2012 A* conf
LP Rounding for k-Centers with Non-uniform Hard Capacities.
FOCS
Marek Cygan, MohammadTaghi Hajiaghayi, Samir Khuller
2012 B conf
On Group Feedback Vertex Set Parameterized by the Size of the Cutset.
WG
Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk
2012 A conf
On Problems as Hard as CNF-SAT.
CCC
Marek Cygan, Holger Dell, Daniel Lokshtanov, Dániel Marx, Jesper Nederlof, Yoshio Okamoto, Ramamohan Paturi, Saket Saurabh, Magnus Wahlström
2012 J jnl
On fixed-parameter algorithms for Split Vertex Deletion
CoRR
Marek Cygan, Marcin Pilipczuk
2012 B conf
Sitting Closer to Friends Than Enemies, Revisited.
MFCS
Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, Jakub Onufry Wojtaszczyk
2012 J jnl
Sitting closer to friends than enemies, revisited
CoRR
Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, Jakub Onufry Wojtaszczyk
2012 B conf
Solving the 2-Disjoint Connected Subgraphs Problem Faster Than 2 n.
LATIN
Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, Jakub Onufry Wojtaszczyk
2012 J jnl
Solving weighted and counting variants of connectivity problems parameterized by treewidth deterministically in single exponential time
CoRR
Hans L. Bodlaender, Marek Cygan, Stefan Kratsch, Jesper Nederlof
2012 A conf
Steiner Forest Orientation Problems.
ESA
Marek Cygan, Guy Kortsarz, Zeev Nutov
2011 J jnl
Approximation Algorithms for Union and Intersection Covering Problems
CoRR
Marek Cygan, Fabrizio Grandoni, Stefano Leonardi, Marcin Mucha, Marcin Pilipczuk, Piotr Sankowski
2011 — conf
Approximation Algorithms for Union and Intersection Covering Problems.
FSTTCS
Marek Cygan, Fabrizio Grandoni, Stefano Leonardi, Marcin Mucha, Marcin Pilipczuk, Piotr Sankowski
2011 J jnl
Breaking the 2
J. Discrete Algorithms
Daniel Binkele-Raible, Ljiljana Brankovic, Marek Cygan, Henning Fernau, Joachim Kneis, Dieter Kratsch, Alexander Langer, Mathieu Liedloff, Marcin Pilipczuk, Peter Rossmanith, Jakub Onufry Wojtaszczyk
2011 J jnl
Capacitated domination faster than
Inf. Process. Lett.
Marek Cygan, Marcin Pilipczuk, Jakub Onufry Wojtaszczyk
2011 J jnl
Channel Assignment via Fast Zeta Transform
CoRR
Marek Cygan, Lukasz Kowalik
2011 J jnl
Channel assignment via fast zeta transform.
Inf. Process. Lett.
Marek Cygan, Lukasz Kowalik
2011 J jnl
Clique cover and graph separation: New incompressibility results
CoRR
Marek Cygan, Stefan Kratsch, Marcin Pilipczuk, Michal Pilipczuk, Magnus Wahlström
2011 J jnl
Dominating set is fixed parameter tractable in claw-free graphs.
Theor. Comput. Sci.
Marek Cygan, Geevarghese Philip, Marcin Pilipczuk, Michal Pilipczuk, Jakub Onufry Wojtaszczyk
2011 B conf
On Cutwidth Parameterized by Vertex Cover.
IPEC
Marek Cygan, Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh
2011 B conf
On Multiway Cut Parameterized above Lower Bounds.
IPEC
Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, Jakub Onufry Wojtaszczyk
2011 J jnl
On Multiway Cut parameterized above lower bounds
CoRR
Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, Jakub Onufry Wojtaszczyk
2011 J jnl
On Problems as Hard as CNFSAT
CoRR
Marek Cygan, Holger Dell, Daniel Lokshtanov, Dániel Marx, Jesper Nederlof, Yoshio Okamoto, Ramamohan Paturi, Saket Saurabh, Magnus Wahlström
2011 J jnl
On group feedback vertex set parameterized by the size of the cutset
CoRR
Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk
2011 B conf
On the Hardness of Losing Width.
IPEC
Marek Cygan, Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh
2011 B conf
Parameterized Complexity of Eulerian Deletion Problems.
WG
Marek Cygan, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, Ildikó Schlotter
2011 J jnl
Parameterized Complexity of Firefighting Revisited
CoRR
Marek Cygan, Fedor V. Fomin, Erik Jan van Leeuwen
2011 B conf
Parameterized Complexity of Firefighting Revisited.
IPEC
Marek Cygan, Fedor V. Fomin, Erik Jan van Leeuwen
2011 B conf
Polynomial-Time Approximation Algorithms for Weighted LCS Problem.
CPM
Marek Cygan, Marcin Kubica, Jakub Radoszewski, Wojciech Rytter, Tomasz Walen
2011 A conf
Scheduling Partially Ordered Jobs Faster Than 2 n.
ESA
Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, Jakub Onufry Wojtaszczyk
2011 J jnl
Scheduling partially ordered jobs faster than 2^n
CoRR
Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, Jakub Onufry Wojtaszczyk
2011 A* conf
Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time.
FOCS
Marek Cygan, Jesper Nederlof, Marcin Pilipczuk, Michal Pilipczuk, Johan M. M. van Rooij, Jakub Onufry Wojtaszczyk
2011 J jnl
Solving connectivity problems parameterized by treewidth in single exponential time
CoRR
Marek Cygan, Jesper Nederlof, Marcin Pilipczuk, Michal Pilipczuk, Johan M. M. van Rooij, Jakub Onufry Wojtaszczyk
2011 J jnl
Steiner Forest Orientation Problems
CoRR
Marek Cygan, Guy Kortsarz, Zeev Nutov
2011 — conf
Subset Feedback Vertex Set Is Fixed-Parameter Tractable.
ICALP (1)
Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, Jakub Onufry Wojtaszczyk
2011 A* conf
The stubborn problem is stubborn no more (a polynomial algorithm for 3-compatible colouring and the stubborn list partition problem).
SODA
Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, Jakub Onufry Wojtaszczyk
2010 C conf
A Planar Linear Arboricity Conjecture.
CIAC
Marek Cygan, Lukasz Kowalik, Borut Luzar
2010 B conf
Algorithms for Three Versions of the Shortest Common Superstring Problem.
CPM
Maxime Crochemore, Marek Cygan, Costas S. Iliopoulos, Marcin Kubica, Jakub Radoszewski, Wojciech Rytter, Tomasz Walen
2010 B conf
An Improved FPT Algorithm and Quadratic Kernel for Pathwidth One Vertex Deletion.
IPEC
Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, Jakub Onufry Wojtaszczyk
2010 J jnl
Bandwidth and Distortion Revisited
CoRR
Marek Cygan, Marcin Pilipczuk
2010 — conf
Capacitated Domination Faster Than
SWAT
Marek Cygan, Marcin Pilipczuk, Jakub Onufry Wojtaszczyk
2010 J jnl
Dominating Set is Fixed Parameter Tractable in Claw-free Graphs
CoRR
Marek Cygan, Geevarghese Philip, Marcin Pilipczuk, Michal Pilipczuk, Jakub Onufry Wojtaszczyk
2010 J jnl
Exact and approximate bandwidth.
Theor. Comput. Sci.
Marek Cygan, Marcin Pilipczuk
2010 — conf
Fast Approximation in Subspaces by Doubling Metric Decomposition.
ESA (1)
Marek Cygan, Lukasz Kowalik, Marcin Mucha, Marcin Pilipczuk, Piotr Sankowski
2010 C conf
Irredundant Set Faster Than
CIAC
Marek Cygan, Marcin Pilipczuk, Jakub Onufry Wojtaszczyk
2010 B conf
Kernelization Hardness of Connectivity Problems in
WG
Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, Jakub Onufry Wojtaszczyk
2010 J jnl
Subset feedback vertex set is fixed parameter tractable
CoRR
Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, Jakub Onufry Wojtaszczyk
2010 J jnl
The stubborn problem is stubborn no more (a polynomial algorithm for 3-compatible colouring and the stubborn list partition problem)
CoRR
Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, Jakub Onufry Wojtaszczyk
2009 J jnl
Beyond O*(2^n) in domination-type problems
CoRR
Marek Cygan, Marcin Pilipczuk, Jakub Onufry Wojtaszczyk
2009 J jnl
Even Faster Exact Bandwidth
CoRR
Marek Cygan, Marcin Pilipczuk
2009 — conf
Exact and Approximate Bandwidth.
ICALP (1)
Marek Cygan, Marcin Pilipczuk
2009 J jnl
Exponential-time approximation of weighted set cover.
Inf. Process. Lett.
Marek Cygan, Lukasz Kowalik, Mateusz Wykurz
2009 J jnl
Fast Approximation in Subspaces by Doubling Metric Decomposition
CoRR
Marek Cygan, Lukasz Kowalik, Marcin Mucha, Marcin Pilipczuk, Piotr Sankowski
2008 J jnl
Exponential-Time Approximation of Hard Problems
CoRR
Marek Cygan, Lukasz Kowalik, Marcin Pilipczuk, Mateusz Wykurz
2008 B conf
Faster Exact Bandwidth.
WG
Marek Cygan, Marcin Pilipczuk