Publications

Marek Cygan

Number of publications: 101

2024

• Michał Nauman, Michał Bortkiewicz, Piotr Miłoś , Tomasz Trzciński, Mateusz Ostaszewski, Marek Cygan , Overestimation, Overfitting, and Plasticity in Actor-Critic: the Bitter Lesson of Reinforcement Learning, 41st International Conference on Machine Learning, Vienna, Austria, 21 July 2024 - 27 July 2024. See in PBN
• Dominik Filipiak, Andrzej Zapała, Piotr Tempczyk , Anna Fensel, Marek Cygan , Polite Teacher: Semi-Supervised Instance Segmentation With Mutual Learning and Pseudo-Label Thresholding, IEEE Access, 12 2024, p. 37744-37756. See in PBN
• Jan Ludziejewski , Jakub Krajewski, Kamil Adamczewski, Maciej Pióro, Michał Krutul, Szymon Antoniak, Kamil Ciebiera, Krystian Król, Tomasz Odrzygóźdź, Piotr Sankowski , Marek Cygan , Sebastian Jaszczur, Scaling Laws for Fine-Grained Mixture of Experts, 41st International Conference on Machine Learning, Vienna, Austria, 21 July 2024 - 27 July 2024, 235 2024, p. 33270-33288. See in PBN

2023

• Michal Nauman, Marek Cygan , Michał Nauman, On Many-Actions Policy Gradient, 40th International Conference on Machine Learning, Honolulu, the United States of America, 23 July 2023 - 29 July 2023. See in PBN

2022

• Marek Cygan , Jesper Nederlof, Marcin Pilipczuk , Johan M. M. Van Rooij, Jakub Onufry Wojtaszczyk, Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time, ACM Transactions on Algorithms, 18 (2) 2022, p. 1-31. See in PBN
• Arkadev Chattopadhyay, Marek Cygan , Noga Ron-Zewi, Christian Wulff-Nilsen, Special Section on the Fifty-Second Annual ACM Symposium on the Theory of Computing (STOC 2020), SIAM Journal on Computing, 52nd ACM Symposium on Theory of Computing, Chicago, the United States of America, 22 June 2020 - 26 June 2020, 51 (3) 2022, p. STOC20-i-STOC20-i. See in PBN

2021

• Marek Cygan , Alexander Kulikov, Ivan Mihajlin, Maksim Nikolaev, Grigory Reznikov, Minimum Common String Partition: Exact Algorithms, 29th Annual European Symposium on Algorithms (ESA 2019), Lizbona, Portugal, 5 September 2021 - 7 September 2021. See in PBN
• Marek Cygan , Paweł Komosa, Daniel Lokshtanov, Marcin Pilipczuk , Michał Pilipczuk , Saket Saurabh, Magnus Wahlström, Randomized Contractions Meet Lean Decompositions, ACM Transactions on Algorithms, 17 (1) 2021, p. 1948-1964. See in PBN
• Magnús M. Halldórsson, Guy Kortsarz, Marek Cygan , Tight Bounds on Subexponential Time Approximation of Set Cover and Related Problems, 18th Workshop on Approximation and Online Algorithms, Pisa, Italy, 9 September 2020 - 10 September 2020. See in PBN

2020

• Parinya Chalermsook, Guy Kortsarz, Bundit Laekhanukit, Pasin Manurangsi, Danupon Nanongkai, Luca Trevisan, Marek Cygan , From Gap-Exponential Time Hypothesis to Fixed Parameter Tractable Inapproximability: Clique, Dominating Set, and More, SIAM Journal on Computing, 49 2020, p. 772--810. See in PBN
• Ivan Bliznets, Paweł Komosa, Lukáš Mach, Marek Cygan , Michał Pilipczuk , Lower Bounds for the Parameterized Complexity of Minimum Fill-in and Other Completion Problems, ACM Transactions on Algorithms, 16 (2) 2020, p. 1-31. See in PBN

2019

• Robert Bogucki, Marek Cygan , Christin Khan, Maciej Klimek, Jan Kanty Milczek, Marcin Mucha , Applying deep learning to right whale photo identification, Conservation Biology, 33 (3) 2019, p. 676-684. See in PBN
• Marek Cygan , Łukasz Kowalik , Arkadiusz Socała, Improving TSP Tours Using Dynamic Programming over Tree Decompositions, ACM Transactions on Algorithms, 15 (4) 2019, p. 1-19. See in PBN
• Marek Cygan , Daniel Lokshtanov, Marcin Pilipczuk , Michał Pilipczuk , Saket Saurabh, Minimum Bisection Is Fixed-Parameter Tractable, SIAM Journal on Computing, 48 (2) 2019, p. 417-450. See in PBN
• Marek Cygan , Marcin Mucha , Karol Węgrzycki, Michał Włodarczyk , On Problems Equivalent to (min,+)-Convolution, ACM Transactions on Algorithms, 15 (1) 2019, p. 1-25. See in PBN

2018

• Marek Cygan , Łukasz Kowalik , Arkadiusz Socała, Krzysztof Sornat, Approximation and Parameterized Complexity of Minimax Approval Voting, Journal of Artificial Intelligence Research, 63 2018, p. 495 - 513. See in PBN
• Marek Cygan , Stefan Kratsch, Jesper Nederlof, Fast Hamiltonicity Checking Via Bases of Perfect Matchings, JOURNAL OF THE ACM, 46 (3) 2018, p. 1-46. See in PBN
• Ivan Bliznets, Marek Cygan , Paweł Komosa, Michał Pilipczuk , Hardness of Approximation for H-free Edge Modification Problems, ACM Transactions on Computation Theory, 10 (2) 2018, p. 2018. See in PBN
• Marek Cygan , Artur Czumaj, Marcin Mucha , Piotr Sankowski , Online Facility Location with Deletions, 26th Annual European Symposium on Algorithms, Helsinki, Finland, 20 August 2018 - 22 August 2018. See in PBN

2017

• Marek Cygan , Łukasz Kowalik , Arkadiusz Socała, Krzysztof Sornat, Approximation and Parameterized Complexity of Minimax Approval Voting, 31st AAAI Conference on Artificial Intelligence, San Francisco, the United States of America, 4 February 2017 - 9 February 2017. See in PBN
• Parinya Chalermsook, Marek Cygan , Guy Kortsarz, Pasin Manurangsi, Bundit Laekhanukit, Danupon Nanongkai, Luca Trevisan, From Gap-ETH to FPT-Inapproximability: Clique, Dominating Set, and More, 58th Annual IEEE Symposium on Foundations of Computer Science, Berkeley, the United States of America, 15 October 2017 - 17 October 2017. See in PBN
• Marek Cygan , Daniel Marx, Marcin Pilipczuk , Michał Pilipczuk , Hitting forbidden subgraphs in graphs of bounded treewidth, Information and Computation, 256 2017, p. 62-82. See in PBN
• Marek Cygan , Łukasz Kowalik , Arkadiusz Socała, Improving TSP Tours Using Dynamic Programming over Tree Decompositions, 25th Annual European Symposium on Algorithms, Vienna, Austria, 4 September 2017 - 6 September 2017. See in PBN
• Marek Cygan , Marcin Mucha , Karol Węgrzycki, Michał Włodarczyk , On Problems Equivalent to (min, +)-Convolution, 44th International Colloquium on Automata, Languages, and Programming, Warszawa, Poland, 10 July 2017 - 14 July 2017. See in PBN
• Marek Cygan , Fabrizio Grandoni, Danny Hermelin, Tight Kernel Bounds for Problems on Graphs with Small Degeneracy, ACM Transactions on Algorithms, 2017. See in PBN
• Marek Cygan , Fedor V. Fomin, Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin, Jakub Pachocki, Arkadiusz Socała, Tight Lower Bounds on Graph Embedding Problems, JOURNAL OF THE ACM, 64 (3) 2017, p. 1-22. See in PBN

2016

• Anudhyan Boral, Marek Cygan , Tomasz Kociumaka, Marcin Pilipczuk , A Fast Branching Algorithm for Cluster Vertex Deletion, Theory of Computing Systems, 2016. See in PBN
• Paweł Brach, Marek Cygan , Piotr Sankowski , Jakub Łącki, Algorithmic Complexity of Power Law Networks, Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, 2016. See in PBN
• Rajesh Chitnis, Marek Cygan , MohammadTaghi Hajiaghayi, Marcin Pilipczuk , Michał Pilipczuk , Designing FPT Algorithms for Cut Problems Using Randomized Contractions, SIAM Journal on Computing, 2016. See in PBN
• Ivan Bliznets, Marek Cygan , Paweł Komosa, Michał Pilipczuk , Hardness of Approximation for H-Free Edge Modification Problems, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2016. See in PBN
• Marek Cygan , Marcin Pilipczuk , Michał Pilipczuk , Known Algorithms for Edge Clique Cover are Probably Optimal, SIAM Journal on Computing, 2016. See in PBN
• Marek Cygan , Daniel Lokshtanov, Marcin Pilipczuk , Michał Pilipczuk , Saket Saurabh, Lower Bounds for Approximation Schemes for Closest String, 15th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2016, June 22-24, 2016, Reykjavik, Iceland, 2016. See in PBN
• Ivan Bliznets, Marek Cygan , Paweł Komosa, Lukas Mach, Michał Pilipczuk , Lower bounds for the parameterized complexity of Minimum Fill-In and other completion problems, Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, the United States of America, 2016. See in PBN
• Marek Cygan , Marcin Pilipczuk , Michał Pilipczuk , On Group Feedback Vertex Set Parameterized by the Size of the Cutset, Algorithmica, 2016. See in PBN
• Marek Cygan , Holger Dell, Daniel Lokshtanov, D\'aniel Marx, Jesper Nederlof, Yoshio Okamoto, Ramamohan Paturi, Saket Saurabh, Magnus Wahlstr\öm, On Problems as Hard as CNF-SAT, ACM Transactions on Algorithms, 2016. See in PBN
• Marek Cygan , Lukasz Jez, Jiri Sgall, Online Knapsack Revisited, Theory of Computing Systems, 2016. See in PBN
• Marek Cygan , Marcin Mucha , Piotr Sankowski , Qiang Zhang, Online Pricing with Impatient Bidders, Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, the United States of America, 10 January 2016 - 12 January 2016. See in PBN
• Marek Cygan , Erik Jan van Leeuwen, Marcin Pilipczuk , Michał Pilipczuk , Marcin Wrochna , Polynomial Kernelization for Removing Induced Claws and Diamonds, 41st International Workshop on Graph-Theoretic Concepts in Computer Science, Garching, Germany, 17 June 2015 - 19 June 2015. See in PBN
• Marek Cygan , Marcin Pilipczuk , Michał Pilipczuk , Marcin Wrochna , Erik Jan van Leeuwen, Polynomial Kernelization for Removing Induced Claws and Diamonds, Theory of Computing Systems, 2016. See in PBN
• Marek Cygan , Marcin Kubica, Jakub Radoszewski , Wojciech Rytter , Tomasz Waleń , Polynomial-time approximation algorithms for weighted LCS problem, Discrete Applied Mathematics, 2016. See in PBN
• Marek Cygan , Fedor V. Fomin, Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin, Jakub Pachocki, Arkadiusz Socała, Tight Bounds for Graph Homomorphism and Subgraph Isomorphism, Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, 2016. See in PBN

2015

• Marek Cygan , Harold N. Gabow, Piotr Sankowski , Algorithmic Applications of Baur-Strassen's Theorem: Shortest Cycles, Diameter, and Matchings, JOURNAL OF THE ACM, 2015. See in PBN
• Marek Cygan , Tomasz Kociumaka, Approximating Upper Degree-Constrained Partial Orientations, 18th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, 19th International Workshop on Randomization and Computation, Princeton, the United States of America, 24 August 2015 - 26 August 2015. See in PBN
• Hans L. Bodlaender, Marek Cygan , Stefan Kratsch, Jesper Nederlof, Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth, Information and Computation, 2015. See in PBN
• Rajesh Hemant Chitnis, Marek Cygan , Mohammad Taghi Hajiaghayi, D\'aniel Marx, Directed Subset Feedback Vertex Set Is Fixed-Parameter Tractable, ACM Transactions on Algorithms, 2015. See in PBN
• Marek Cygan , Marcin Pilipczuk , Faster exponential-time algorithms in graphs of bounded average degree, Information and Computation, 2015. See in PBN
• Ivan Bliznets, Marek Cygan , Paweł Komosa, Luk\'as Mach, Kernelization lower bound for Permutation Pattern Matching, Information Processing Letters, 2015. See in PBN
• Marek Cygan , Fedor Fomin, Łukasz Kowalik , Daniel Lokshtanov, Daniel Marx, Marcin Pilipczuk , Michał Pilipczuk , Saket Saurabh, Parameterized Algorithms, 2015. See in PBN
• Marek Cygan , Marcin Pilipczuk , Michał Pilipczuk , Jakub Onufry Wojtaszczyk, Sitting Closer to Friends than Enemies, Revisited, Theory of Computing Systems, 2015. See in PBN

2014

• Marek Cygan , Pinar Heggernes, 9th International Symposium on Parameterized and Exact Computation (IPEC 2014), 2014. See in PBN
• Anudhyan Boral, Marek Cygan , Tomasz Kociumaka, Marcin Pilipczuk , A Fast Branching Algorithm for Cluster Vertex Deletion, 9th International Computer Science Symposium in Russia, Moscow, the Russian Federation, 7 June 2014 - 11 June 2014. See in PBN
• Marek Cygan , Stefan Kratsch, Marcin Pilipczuk , Michał Pilipczuk , Magnus Wahlström, Clique Cover and Graph Separation: New Incompressibility Results, ACM Transactions on Computation Theory, 2014. See in PBN
• Marek Cygan , Tomasz Kociumaka, Constant Factor Approximation for Capacitated k-Center with Outliers, Leibniz International Proceedings in Informatics, 31st Symposium on Theoretical Aspects of Computer Science, Lyon, France, 5 March 2014 - 8 April 2014. See in PBN
• Marek Cygan , Dániel Marx, Marcin Pilipczuk , Michał Pilipczuk , Hitting Forbidden Subgraphs in Graphs of Bounded Treewidth, Mathematical Foundations of Computer Science 2014 - 39th International Symposium, Budapest, Hungary, 25 August 2014 - 29 August 2014. See in PBN
• Marek Cygan , Daniel Lokshtanov, Marcin Pilipczuk , Michał Pilipczuk , Saket Saurabh, Minimum bisection is fixed parameter tractable, Symposium on Theory of Computing, STOC 2014, New York, the United States of America, 31 May 2014 - 3 June 2014. See in PBN
• Marek Cygan , Marcin Pilipczuk , Daniel Lokshtanov, Michał Pilipczuk , Saket Saurabh, On Cutwidth Parameterized by Vertex Cover, Algorithmica, 68 (4) 2014, p. 940-953. See in PBN
• Marek Cygan , Marcin Pilipczuk , Michał Pilipczuk , Daniel Lokshtanov, Saket Saurabh, On the Hardness of Losing Width, Theory of Computing Systems, 54 (1) 2014, p. 73-82. See in PBN
• Marek Cygan , Marcin Pilipczuk , Dániel Marx, Michał Pilipczuk , Ildikó Schlotter, Parameterized Complexity of Eulerian Deletion Problems, Algorithmica, 68 (1) 2014, p. 41-61. See in PBN
• Cristina Bazgan, Morgan Chopin, Marek Cygan , Michael R. Fellows, Fedor V. Fomin, Erik Jan van Leeuwen, Parameterized complexity of firefighting, Journal of Computer and System Sciences, 2014. See in PBN
• Marek Cygan , Marcin Pilipczuk , Michał Pilipczuk , Jakub Wojtaszczyk, Scheduling Partially Ordered Jobs Faster than 2^n, Algorithmica, 68 (3) 2014, p. 692-714. See in PBN
• Marek Cygan , Marcin Pilipczuk , Michał Pilipczuk , Jakub Wojtaszczyk, Solving the 2-Disjoint Connected Subgraphs Problem Faster than 2 n, Algorithmica, 2014. See in PBN

2013

• Marek Cygan , Marcin Pilipczuk , Riste Skrekovski, A bound on the number of perfect matchings in Klee-graphs, DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE, 15 (1) 2013, p. 37-54. See in PBN
• Marek Cygan , Marcin Mucha , Piotr Sankowski , Matthias Englert, Anupam Gupta, Catch them if you can: how to serve impatient users, Innovations in Theoretical Computer Science, Berkeley, the United States of America, 2013. See in PBN
• Marek Cygan , Marcin Pilipczuk , Faster Exponential-Time Algorithms in Graphs of Bounded Average Degree, Automata, Languages, and Programming - 40th International Colloquium, Riga, Latvia, 8 July 2013 - 12 July 2013. See in PBN
• Marek Cygan , Marcin Pilipczuk , Michał Pilipczuk , Known algorithms for EDGE CLIQUE COVER are probably optimal, Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, New Orleans, the United States of America, 6 January 2013 - 8 January 2013. See in PBN
• Marek Cygan , Marcin Pilipczuk , Michał Pilipczuk , Jakub Wojtaszczyk, On multiway cut parameterized above lower bounds, ACM Transactions on Computation Theory, 2013. See in PBN
• Marek Cygan , Marcin Pilipczuk , Split Vertex Deletion meets Vertex Cover: New fixed-parameter and exact exponential-time algorithms, Information Processing Letters, 113 (5-6) 2013, p. 179-182. See in PBN
• Marek Cygan , Guy Kortsarz, Zeev Nutov, Steiner Forest Orientation Problems, SIAM JOURNAL ON DISCRETE MATHEMATICS, 2013. See in PBN
• Marek Cygan , Marcin Pilipczuk , Michał Pilipczuk , Jakub Wojtaszczyk, Subset Feedback Vertex Set Is Fixed-Parameter Tractable, SIAM JOURNAL ON DISCRETE MATHEMATICS, 2013. See in PBN
• Marek Cygan , Dániel Marx, Marcin Pilipczuk , Michał Pilipczuk , The Planar Directed K-Vertex-Disjoint Paths Problem Is Fixed-Parameter Tractable, 54th Annual IEEE Symposium on Foundations of Computer Science, Berkeley, the United States of America, 26 October 2013 - 29 October 2013. See in PBN

2012

• Marek Cygan , Fabrizio Grandoni, Stefano Leonardi, Marcin Pilipczuk , Piotr Sankowski , A Path-Decomposition Theorem with Applications to Pricing and Covering on Trees, Algorithms - ESA 2012 - 20th Annual European Symposium, Ljubljana, Slovenia, 10 September 2012 - 12 September 2012. See in PBN
• Marek Cygan , Jian-Feng Hou, Łukasz Kowalik , Borut Luzar, Jian-Liang Wu, A Planar linear arboricity conjecture, Journal of Graph Theory, 2012. See in PBN
• Marek Cygan , Marcin Pilipczuk , Michał Pilipczuk , Jakub Wojtaszczyk, A Polynomial Algorithm for 3-Compatible Coloring and the Stubborn List Partition Problem (The Stubborn Problem Is Stubborn No More), SIAM Journal on Computing, 2012. See in PBN
• Marek Cygan , Harold N. Gabow, Piotr Sankowski , Algorithmic Applications of Baur-Strassen's Theorem: Shortest Cycles, Diameter and Matchings, 2012. See in PBN
• Marek Cygan , Marcin Pilipczuk , Michał Pilipczuk , Jakub Wojtaszczyk, An Improved FPT Algorithm and a Quadratic Kernel for Pathwidth One Vertex Deletion, Algorithmica, 2012. See in PBN
• Marek Cygan , Marcin Pilipczuk , Bandwidth and distortion revisited, Discrete Applied Mathematics, 2012. See in PBN
• Marek Cygan , Stefan Kratsch, Marcin Pilipczuk , Michał Pilipczuk , Magnus Wahlström, Clique Cover and Graph Separation: New Incompressibility Results, Automata, Languages, and Programming - 39th International Colloquium, Warwick, the United Kingdom of Great Britain and Northern Ireland, 9 July 2012 - 13 July 2012. See in PBN
• Rajesh Hemant Chitnis, Marek Cygan , MohammadTaghi Hajiaghayi, Marcin Pilipczuk , Michał Pilipczuk , Designing FPT Algorithms for Cut Problems Using Randomized Contractions, 53rd Annual IEEE Symposium on Foundations of Computer Science, New Brunswick, the United States of America, 20 October 2012 - 23 October 2012. See in PBN
• Marek Cygan , Deterministic Parameterized Connected Vertex Cover, 2012. See in PBN
• Rajesh Hemant Chitnis, Marek Cygan , Mohammad Taghi Hajiaghayi, Dániel Marx, Directed Subset Feedback Vertex Set Is Fixed-Parameter Tractable, 2012. See in PBN
• Marek Cygan , Marcin Pilipczuk , Even Faster Exact Bandwidth, ACM Transactions on Algorithms, 2012. See in PBN
• Marek Cygan , Marcin Pilipczuk , Michał Pilipczuk , Jakub Wojtaszczyk, Kernelization hardness of connectivity problems in d-degenerate graphs, Discrete Applied Mathematics, 2012. See in PBN
• Marek Cygan , Marcin Pilipczuk , Michał Pilipczuk , On Group Feedback Vertex Set Parameterized by the Size of the Cutset, Graph-Theoretic Concepts in Computer Science - 38th International Workshop, Jerusalem, Israel, 26 June 2012 - 28 June 2012. See in PBN
• Marek Cygan , Marcin Pilipczuk , Michał Pilipczuk , Jakub Wojtaszczyk, Sitting Closer to Friends Than Enemies, Revisited, Mathematical Foundations of Computer Science 2012 - 37th International Symposium, Bratislava, Slovakia, 27 August 2012 - 31 August 2012. See in PBN
• Marek Cygan , Marcin Pilipczuk , Michał Pilipczuk , Jakub Wojtaszczyk, Solving the 2-Disjoint Connected Subgraphs Problem Faster Than 2 n, LATIN 2012: Theoretical Informatics - 10th Latin American Symposium, Arequipa, Peru, 16 April 2012 - 20 April 2012. See in PBN

2011

• Marek Cygan , Fabrizio Grandoni, Stefano Leonardi, Marcin Mucha , Marcin Pilipczuk , Piotr Sankowski , Approximation Algorithms for Union and Intersection Covering Problems, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, Mumbai, India, 12 December 2011 - 14 December 2011. See in PBN
• Daniel Binkele-Raible, Ljiljana Brankovic, Marek Cygan , Henning Fernau, Joachim Kneis, Dieter Kratsch, Alexander Langer, Mathieu Liedloff, Marcin Pilipczuk , Peter Rossmanith, Jakub Wojtaszczyk, Breaking the 2^n-barrier for Irredundance: Two lines of attack, Journal of Discrete Algorithms, 2011. See in PBN
• Marek Cygan , Marcin Pilipczuk , Jakub Wojtaszczyk, Capacitated domination faster than O(2^n), Information Processing Letters, 2011. See in PBN
• Marek Cygan , Geevarghese Philip, Marcin Pilipczuk , Michał Pilipczuk , Jakub Wojtaszczyk, Dominating set is fixed parameter tractable in claw-free graphs, Theoretical Computer Science, 2011. See in PBN
• Marek Cygan , Marcin Pilipczuk , Michał Pilipczuk , Ildiko Schlotter, Parameterized Complexity of Eulerian Deletion Problems, Lecture Notes in Computer Science, 2011. See in PBN
• Marek Cygan , Marcin Kubica, Jakub Radoszewski , Wojciech Rytter , Tomasz Waleń , Polynomial-Time Approximation Algorithms for Weighted LCS Problem, Lecture Notes in Computer Science, Combinatorial Pattern Matching, 2011. See in PBN
• Marek Cygan , Marcin Pilipczuk , Michał Pilipczuk , Jakub Wojtaszczyk, Scheduling Partially Ordered Jobs Faster Than 2n, Lecture Notes in Computer Science, 2011. See in PBN
• Marek Cygan , Jesper Nederlof, Marcin Pilipczuk , Michał Pilipczuk , Jakub Wojtaszczyk, Johan van Rooij, Solving connectivity problems parameterized by treewidth in single exponential time, IEEE 52nd Annual Symposium on Foundations of Computer Science, Palm Springs, the United States of America, 22 October 2011 - 25 October 2011. See in PBN
• Marek Cygan , Marcin Pilipczuk , Michał Pilipczuk , Jakub Wojtaszczyk, Subset Feedback Vertex Set Is Fixed-Parameter Tractable, Lecture Notes in Computer Science, 2011. See in PBN
• Marek Cygan , Marcin Pilipczuk , Michał Pilipczuk , Jakub Wojtaszczyk, The stubborn problem is stubborn no more (a polynomial algorithm for 3-compatible colouring and the stubborn list partition problem), Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, San Francisco, the United States of America, 23 January 2011 - 25 January 2011. See in PBN

2010

• Maxime Crochemore, Marek Cygan , Costas S. Iliopoulos, Marcin Kubica, Jakub Radoszewski , Wojciech Rytter , Tomasz Waleń , Algorithms for Three Versions of the Shortest Common Superstring Problem, Lecture Notes in Computer Science, Combinatorial Pattern Matching, 2010. See in PBN
• Marek Cygan , Marcin Pilipczuk , Michał Pilipczuk , Jakub Wojtaszczyk, An improved FPT algorithm and quadratic kernel for pathwidth one vertex deletion, Lecture Notes in Computer Science, 2010. See in PBN
• Marek Cygan , Marcin Pilipczuk , Jakub Wojtaszczyk, Capacitated domination faster than O(2^n), Algorithm Theory - SWAT 2010, 12th Scandinavian Symposium and Workshops on Algorithm Theory, Bergen, Norway, 21 June 2010 - 23 June 2010. See in PBN
• Marek Cygan , Marcin Pilipczuk , Exact and approximate bandwidth, Theoretical Computer Science, 2010. See in PBN
• Marek Cygan , Marcin Pilipczuk , Jakub Wojtaszczyk, Irredundant set faster than O(2^n), Algorithms and Complexity, 7th International Conference, Rome, Italy, 26 May 2010 - 28 May 2010. See in PBN
• Marek Cygan , Marcin Pilipczuk , Michał Pilipczuk , Jakub Wojtaszczyk, Kernelization hardness of connectivity problems in d-degenerate graphs, Graph Theoretic Concepts in Computer Science - 36th International Workshop, Zaros, Greece, 28 June 2010 - 30 June 2010. See in PBN