Back

Marcin Pilipczuk: research

Papers

Journal articles

Linda Cook, Tomáš Masařík, Marcin Pilipczuk, Amadeus Reinald, Uéverton Souza. Proving a Directed Analogue of the Gy{\'{a}}rf{\'{a}}s-Sumner Conjecture for Orientations of P4. Electron. J. Comb. 30(3), 2023.
Publisher's version.
Thomas Bellitto, Shaohua Li, Karolina Okrasa, Marcin Pilipczuk, Manuel Sorge. The Complexity of Routing Problems in Forbidden-Transition Graphs and Edge-Colored Graphs. Algorithmica 85(5), 1202--1250, 2023.
Publisher's version. Available as technical report arxiv:abs/2009.12892.
Conference version:
Thomas Bellitto, Shaohua Li, Karolina Okrasa, Marcin Pilipczuk, Manuel Sorge. The Complexity of Connectivity Problems in Forbidden-Transition Graphs And Edge-Colored Graphs. Proceedings of ISAAC 2020, 59:1--59:15.
Publisher's version.
Fedor Fomin, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, Saket Saurabh. Subexponential Parameterized Algorithms for Planar and Apex-Minor-Free Graphs via Low Treewidth Pattern Covering. SIAM J. Comput. 51(6), 1866--1930, 2022.
Publisher's version. Available as technical report arxiv:abs/1604.05999.
Conference version:
Fedor Fomin, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, Saket Saurabh. Subexponential parameterized algorithms for planar and apex-minor-free graphs via low treewidth pattern covering. Proceedings of FOCS 2016, 515-524.
Tomáš Masařík, Irene Muzi, Marcin Pilipczuk, Paweł Rzążewski, Manuel Sorge. Packing Directed Cycles Quarter- and Half-Integrally. Comb. 42(Supplement 2), 1409--1438, 2022.
Publisher's version. Available as technical report arxiv:abs/1907.02494.
Conference version:
Tomáš Masařík, Irene Muzi, Marcin Pilipczuk, Paweł Rzążewski, Manuel Sorge. Packing Directed Circuits Quarter-Integrally. Proceedings of ESA 2019, 72:1--72:13.
Publisher's version.
Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk. A Subexponential Parameterized Algorithm for Directed Subset Traveling Salesman Problem on Planar Graphs. SIAM J. Comput. 51(2), 254--289, 2022.
Publisher's version. Available as technical report arxiv:abs/1707.02190.
Conference version:
Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk. On Subexponential Parameterized Algorithms for Steiner Tree and Directed Subset TSP on Planar Graphs. Proceedings of FOCS 2018, 474--484.
Publisher's version.
Shaohua Li, Marcin Pilipczuk. Hardness of Metric Dimension in Graphs of Constant Treewidth. Algorithmica 84(11), 3110--3155, 2022.
Publisher's version.
Conference version:
Shaohua Li, Marcin Pilipczuk. Hardness of Metric Dimension in Graphs of Constant Treewidth. Proceedings of IPEC 2021, 24:1--24:13.
Publisher's version.
Tomáš Masařík, Marcin Pilipczuk, Paweł Rzążewski, Manuel Sorge. Constant Congestion Brambles in Directed Graphs. SIAM J. Discret. Math. 36(2), 922--938, 2022.
Publisher's version. Available as technical report arxiv:abs/2103.08445.
Marek Cygan, Jesper Nederlof, Marcin Pilipczuk, Michał Pilipczuk, Johan M. M. van Rooij, Jakub Onufry Wojtaszczyk. Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time. ACM Trans. Algorithms 18(2), 17:1--17:31, 2022.
Publisher's version. Available as technical report arxiv:abs/1201.1869.
Conference version:
Marek Cygan, Jesper Nederlof, Marcin Pilipczuk, Michał Pilipczuk, Johan M. M. van Rooij, Jakub Onufry Wojtaszczyk. Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time. Proceedings of FOCS 2011, 150-159.
Publisher's version.
Andrzej Grzesik, Tereza Klimošová, Marcin Pilipczuk, Michał Pilipczuk. Polynomial-time Algorithm for Maximum Weight Independent Set on P6-free Graphs. ACM Trans. Algorithms 18(1), 4:1--4:57, 2022.
Publisher's version. Available as technical report arxiv:abs/1707.05491.
Conference version:
Andrzej Grzesik, Tereza Klimošová, Marcin Pilipczuk, Michał Pilipczuk. Polynomial-time algorithm for Maximum Weight Independent Set on P6-free graphs. Proceedings of SODA 2019, 1257--1271.
Publisher's version.
Meike Hatzel, Pawel Komosa, Marcin Pilipczuk, Manuel Sorge. Constant Congestion Brambles. Discret. Math. Theor. Comput. Sci. 24(1), 2022.
Publisher's version. Available as technical report arxiv:abs/2008.02133.
Marthe Bonamy, Francois Dross, Tomáš Masařík, Andrea Munaro, Wojciech Nadara, Marcin Pilipczuk, Michał Pilipczuk. Jones' Conjecture in Subcubic Graphs. Electron. J. Comb. 28(4), 2021.
Publisher's version. Available as technical report arxiv:abs/1912.01570.
Wojciech Czerwinski, Wojciech Nadara, Marcin Pilipczuk. Improved Bounds for the Excluded-Minor Approximation of Treedepth. SIAM J. Discret. Math. 35(2), 934--947, 2021.
Publisher's version. Available as technical report arxiv:abs/1904.13077.
Conference version:
Wojciech Czerwinski, Wojciech Nadara, Marcin Pilipczuk. Improved Bounds for the Excluded-Minor Approximation of Treedepth. Proceedings of ESA 2019, 34:1--34:13.
Publisher's version.
Bart M.P. Jansen, Marcin Pilipczuk, Erik Jan van Leeuwen. A Deterministic Polynomial Kernel for Odd Cycle Transversal and Vertex Multiway Cut in Planar Graphs. SIAM J. Discret. Math. 35(4), 2387--2429, 2021.
Publisher's version. Available as technical report arxiv:abs/1810.01136.
Conference version:
Bart M.P. Jansen, Marcin Pilipczuk, Erik Jan van Leeuwen. A Deterministic Polynomial Kernel for Odd Cycle Transversal and Vertex Multiway Cut in Planar Graphs. Proceedings of STACS 2019, 39:1--39:18.
Publisher's version.
Andrzej Grzesik, Tereza Klimošová, Marcin Pilipczuk, Michał Pilipczuk. Covering Minimal Separators and Potential Maximal Cliques in Pt-Free Graphs. Electron. J. Comb. 28(1), 1, 2021.
Publisher's version. Available as technical report arxiv:abs/2003.12345.
Marek Cygan, Pawel Komosa, Daniel Lokshtanov, Marcin Pilipczuk, Michał Pilipczuk, Saket Saurabh, Magnus Wahlström. Randomized Contractions Meet Lean Decompositions. ACM Trans. Algorithms 17(1), 6:1--6:30, 2021.
Publisher's version. Available as technical report arxiv:abs/1810.06864.
Jeremy Kun, Michael P. O'Brien, Marcin Pilipczuk, Blair D. Sullivan. Polynomial Treedepth Bounds in Linear Colorings. Algorithmica 83(1), 361--386, 2021.
Publisher's version.
Marcin Pilipczuk, Ni Luh Dewi Sintiari, Stéphan Thomassé, Nicolas Trotignon. (Theta, triangle)-free and (even hole, K4)-free graphs. Part 2: Bounds on treewidth. J. Graph Theory 97(4), 624--641, 2021.
Publisher's version. Available as technical report arxiv:abs/2001.01607.
Marcin Pilipczuk, Manuel Sorge. A Double Exponential Lower Bound for the Distinct Vectors Problem. Discret. Math. Theor. Comput. Sci. 22(4), 2020.
Publisher's version. Available as technical report arxiv:abs/2002.01293.
Shaohua Li, Marcin Pilipczuk. An Improved FPT Algorithm for Independent Feedback Vertex Set. Theory Comput. Syst. 64(8), 1317--1330, 2020.
Publisher's version. Available as technical report arxiv:abs/1803.00937.
Conference version:
Shaohua Li, Marcin Pilipczuk. An Improved FPT Algorithm for Independent Feedback Vertex Set. Proceedings of WG 2018, 344--355.
Publisher's version.
Loic Dubois, Gwenael Joret, Guillem Perarnau, Marcin Pilipczuk, Francois Pitois. Two lower bounds for p-centered colorings. Discret. Math. Theor. Comput. Sci. 22(4), 2020.
Publisher's version. Available as technical report arxiv:abs/2006.04113.
Maria Chudnovsky, Marcin Pilipczuk, Michał Pilipczuk, Stéphan Thomassé. On the Maximum Weight Independent Set Problem in Graphs without Induced Cycles of Length at Least Five. SIAM J. Discret. Math. 34(2), 1472--1483, 2020.
Publisher's version. Available as technical report arxiv:abs/1903.04761.
Stefan Kratsch, Shaohua Li, Dániel Marx, Marcin Pilipczuk, Magnus Wahlström. Multi-budgeted Directed Cuts. Algorithmica 82(8), 2135--2155, 2020.
Publisher's version. Available as technical report arxiv:abs/1810.06848.
Conference version:
Stefan Kratsch, Shaohua Li, Dániel Marx, Marcin Pilipczuk, Magnus Wahlström. Multi-Budgeted Directed Cuts. Proceedings of IPEC 2018, 18:1--18:14.
Publisher's version.
Marek Cygan, Daniel Lokshtanov, Marcin Pilipczuk, Michał Pilipczuk, Saket Saurabh. Minimum Bisection Is Fixed-Parameter Tractable. SIAM J. Comput. 48(2), 417--450, 2019.
Publisher's version. Available as technical report arxiv:abs/1311.2563.
Conference version:
Marek Cygan, Daniel Lokshtanov, Marcin Pilipczuk, Michał Pilipczuk, Saket Saurabh. Minimum bisection is fixed parameter tractable. Proceedings of STOC 2014, 323--332.
Publisher's version.
Wojciech Nadara, Marcin Pilipczuk, Roman Rabinovich, Felix Reidl, Sebastian Siebertz. Empirical Evaluation of Approximation Algorithms for Generalized Graph Coloring and Uniform Quasi-wideness. {ACM} J. Exp. Algorithmics 24(1), 2.6:1--2.6:34, 2019.
Publisher's version. Available as technical report arxiv:abs/1802.09801.
Conference version:
Wojciech Nadara, Marcin Pilipczuk, Roman Rabinovich, Felix Reidl, Sebastian Siebertz. Empirical Evaluation of Approximation Algorithms for Generalized Graph Coloring and Uniform Quasi-Wideness. Proceedings of SEA 2018, 14:1--14:16.
Publisher's version.
Anita Liebenau, Marcin Pilipczuk, Paul D. Seymour, Sophie Spirkl. Caterpillars in Erdos-Hajnal. J. Comb. Theory, Ser. {B} 136, 33--43, 2019.
Publisher's version. Available as technical report arxiv:abs/1810.00811.
Bart M. P. Jansen, Marcin Pilipczuk, Marcin Wrochna. Turing Kernelization for Finding Long Paths in Graph Classes Excluding a Topological Minor. Algorithmica 81(10), 3936--3967, 2019.
Publisher's version. Available as technical report arxiv:abs/1707.01797.
Conference version:
Bart M.P. Jansen, Marcin Pilipczuk, Marcin Wrochna. Turing Kernelization for Finding Long Paths in Graphs Excluding a Topological Minor. Proceedings of IPEC 2017, 23:1--23:13.
Publisher's version.
Michal Ziobro, Marcin Pilipczuk. Finding Hamiltonian Cycle in Graphs of Bounded Treewidth: Experimental Evaluation. {ACM} J. Exp. Algorithmics 24(1), 2.7:1--2.7:18, 2019.
Publisher's version. Available as technical report arxiv:abs/1803.00927.
Conference version:
Michal Ziobro, Marcin Pilipczuk. Finding Hamiltonian Cycle in Graphs of Bounded Treewidth: Experimental Evaluation. Proceedings of SEA 2018, 29:1-29:14.
Tomasz Kociumaka, Marcin Pilipczuk. Deleting Vertices to Graphs of Bounded Genus. Algorithmica 81(9), 3655--3691, 2019.
Publisher's version. Available as technical report arxiv:abs/1706.04065.
Marcin Pilipczuk, Michał Pilipczuk, Piotr Sankowski, Erik Jan van Leeuwen. Network Sparsification for Steiner Problems on Planar and Bounded-Genus Graphs. ACM Transactions on Algorithms, to appear, 2018.
Available as technical report arxiv:abs/1306.6593.
Conference version:
Marcin Pilipczuk, Michał Pilipczuk, Piotr Sankowski, Erik Jan van Leeuwen. Network Sparsification for Steiner Problems on Planar and Bounded-Genus Graphs. Proceedings of FOCS 2014, 276-285.
Publisher's version.
Nikolai Karpov, Marcin Pilipczuk, Anna Zych-Pawlewicz. An Exponential Lower Bound for Cut Sparsifiers in Planar Graphs. Algorithmica 81(10), 4029--4042, 2019.
Publisher's version. Available as technical report arxiv:abs/1706.06086.
Conference version:
Nikolai Karpov, Marcin Pilipczuk, Anna Zych-Pawlewicz. An Exponential Lower Bound for Cut Sparsifiers in Planar Graphs. Proceedings of IPEC 2017, 24:1--24:11.
Publisher's version.
Krzysztof Choromanski, Dvir Falik, Anita Liebenau, Viresh Patel, Marcin Pilipczuk. Excluding Hooks and their Complements. Electr. J. Comb. 25(3), P3.27, 2018.
Publisher's version.
Gábor Bacsó, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Zsolt Tuza, Erik Jan van Leeuwen. Subexponential-time Algorithms for Maximum Independent Set in Pt-free and Broom-free Graphs. Algorithmica, to appear, 2018.
Available as technical report arxiv:abs/1804.04077.
Marcin Pilipczuk, Magnus Wahlström. Directed multicut is W[1]-hard, even for four terminal pairs. ACM Transactions on Computational Theory 10(3), 13:1-13:18, 2018.
Available as technical report arxiv:abs/1507.02178.
Conference version:
Marcin Pilipczuk, Magnus Wahlström. Directed multicut is W[1]-hard, even for four terminal pairs. Proceedings of SODA 2016, 1167-1178.
Publisher's version.
Chandra Chekuri, Alina Ene, Marcin Pilipczuk. Constant Congestion Routing of Symmetric Demands in Planar Directed Graphs. SIAM J. Discret. Math. 32(3), 2134--2160, 2018.
Publisher's version.
Conference version:
Chandra Chekuri, Alina Ene, Marcin Pilipczuk. Constant Congestion Routing of Symmetric Demands in Planar Directed Graphs. Proceedings of ICALP 2016, 7:1--7:14.
Bart M. P. Jansen, Marcin Pilipczuk. Approximation and Kernelization for Chordal Vertex Deletion. SIAM J. Discret. Math. 32(3), 2258--2301, 2018.
Publisher's version. Available as technical report arxiv:abs/1605.03001.
Conference version:
Bart M.P. Jansen, Marcin Pilipczuk. Approximation and Kernelization for Chordal Vertex Deletion. Proceedings of SODA 2017, 1399--1418.
Publisher's version.
Ivan Bliznets, Fedor Fomin, Marcin Pilipczuk, Michał Pilipczuk. Subexponential Parameterized Algorithm for Interval Completion. ACM Trans. Algorithms 14(3), 35:1--35:62, 2018.
Publisher's version.
Conference version:
Ivan Bliznets, Fedor Fomin, Marcin Pilipczuk, Michał Pilipczuk. Subexponential parameterized algorithm for Interval Completion. Proceedings of SODA 2016, 1116--1131.
Publisher's version.
Daniel Lokshtanov, Marcin Pilipczuk, Erik Jan van Leeuwen. Independence and Efficient Domination on P6-free Graph. ACM Transactions on Algorithms 14(1), 3:1-3:30, 2018.
Available as technical report arxiv:abs/1507.02163.
Conference version:
Daniel Lokshtanov, Marcin Pilipczuk, Erik Jan van Leeuwen. Independence and Efficient Domination on P6-free Graph. Proceedings of SODA 2016, 1784-1803.
Publisher's version.
Anna Adamaszek, Tomasz Kociumaka, Marcin Pilipczuk, Michał Pilipczuk. Hardness of approximation for strip packing. ACM Transactions on Computation Theory 9(3), 14:1-14:7, 2017.
Available as technical report arxiv:abs/1610.07766.
Marcin Pilipczuk, Michał Pilipczuk, Marcin Wrochna. Edge Bipartization faster than 2k. Algorithmica, to appear, 2017.
Available as technical report arxiv:abs/1507.02168.
Conference version:
Marcin Pilipczuk, Michał Pilipczuk, Marcin Wrochna. Edge Bipartization faster than 2k. Proceedings of IPEC 2016, 26:1-26:13.
Daniel Lokshtanov, Marcin Pilipczuk, Michał Pilipczuk, Saket Saurabh. Fixed-parameter tractable canonization and isomorphism test for graphs of bounded treewidth. SIAM J. Computing 46(1), 161-189, 2017.
Available as technical report arxiv:abs/1404.0818.
Conference version:
Daniel Lokshtanov, Marcin Pilipczuk, Michał Pilipczuk, Saket Saurabh. Fixed-parameter tractable canonization and isomorphism test for graphs of bounded treewidth. Proceedings of FOCS 2014, 186-195.
Publisher's version.
Marek Cygan, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk. Hitting Forbidden Subgraphs in Graphs of Bounded Treewidth. Information and Computation 256, 62-82, 2017.
Available as technical report arxiv:abs/1411.4184.
Conference version:
Marek Cygan, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk. Hitting Forbidden Subgraphs in Graphs of Bounded Treewidth. Proceedings of MFCS 2014, Lecture Notes in Computer Science 8635, 189--200.
Publisher's version.
Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk, Erik Jan van Leeuwen, Marcin Wrochna. Polynomial kernelization for removing induced claws and diamonds. Theory of Computing Systems 60(4), 615-636, 2016.
Available as technical report arxiv:abs/1503.00704.
Conference version:
Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk, Erik Jan van Leeuwen, Marcin Wrochna. Polynomial kernelization for removing induced claws and diamonds. Proceedings of WG 2015, 440-455.
Marcin Pilipczuk. A tight lower bound for Vertex Planarization on graphs of bounded treewidth. Discrete Applied Mathematics 231, 211-216, 2017.
Available as technical report arxiv:abs/1511.08283.
Rajesh Chitnis, Marek Cygan, MohammadTaghi Hajiaghayi, Marcin Pilipczuk, Michał Pilipczuk. Designing FPT algorithms for cut problems using randomized contractions. SIAM Journal of Computing 45(4), 1171-1229, 2016.
Available as technical report arxiv:abs/1207.4079.
Conference version:
Rajesh Chitnis, Marek Cygan, MohammadTaghi Hajiaghayi, Marcin Pilipczuk, Michał Pilipczuk. Designing FPT algorithms for cut problems using randomized contractions. Proceedings of FOCS 2012, 460-469.
Publisher's version.
Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk. On Group Feedback Vertex Set Parameterized by the Size of the Cutset. Algorithmica 74(2), 630-642, 2016.
Publisher's version. Available as technical report arxiv:abs/1112.6255.
Conference version:
Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk. On Group Feedback Vertex Set Parameterized by the Size of the Cutset. Proceedings of WG 2012, Lecture Notes in Computer Science 7551, 194-205.
Publisher's version.
Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk. Known algorithms for EDGE CLIQUE COVER are probably optimal. SIAM Journal of Computing 45(1), 67-83, 2016.
Publisher's version. Available as technical report arxiv:abs/1203.1754.
Conference version:
Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk. Known algorithms for EDGE CLIQUE COVER are probably optimal. Proceedings of SODA 2013, 1044-1053.
Publisher's version.
Ivan Bliznets, Fedor Fomin, Marcin Pilipczuk, Michał Pilipczuk. A Subexponential Parameterized Algorithm for Proper Interval Completion. SIAM J. Discrete Math. 29(4), 1961-1987, 2015.
Publisher's version. Available as technical report arxiv:abs/1402.3472.
Conference version:
Ivan Bliznets, Fedor Fomin, Marcin Pilipczuk, Michał Pilipczuk. A Subexponential Parameterized Algorithm for Proper Interval Completion. Proceedings of ESA 2014, Lecture Notes in Computer Science 8737, 173--184.
Publisher's version.
Anudhyan Boral, Marek Cygan, Tomasz Kociumaka, Marcin Pilipczuk. A Fast Branching Algorithm for Cluster Vertex Deletion. Theory of Computing Systems 58(2), 357-376, 2015.
Publisher's version. Available as technical report arxiv:abs/1306.3877.
Conference version:
Anudhyan Boral, Marek Cygan, Tomasz Kociumaka, Marcin Pilipczuk. A Fast Branching Algorithm for Cluster Vertex Deletion. Proceedings of CSR 2014, Lecture Notes in Computer Science 8476, 111--124.
Publisher's version.
Marek Cygan, Marcin Pilipczuk. Faster exponential-time algorithms in graphs of bounded average degree. Inf. Comput. 243, 75--85, 2015.
Publisher's version. Available as technical report arxiv:abs/1302.3763.
Conference version:
Marek Cygan, Marcin Pilipczuk. Faster Exponential-Time Algorithms in Graphs of Bounded Average Degree. Proceedings of ICALP (1) 2013, Lecture Notes in Computer Science 7965, 364-375.
Publisher's version.
Stefan Kratsch, Marcin Pilipczuk, Michał Pilipczuk, Magnus Wahlström. Fixed-Parameter Tractability of Multicut in Directed Acyclic Graphs. SIAM J. Discrete Math. 29(1), 122-144, 2015.
Publisher's version. Available as technical report arxiv:abs/1202.5749.
Conference version:
Stefan Kratsch, Marcin Pilipczuk, Michał Pilipczuk, Magnus Wahlström. Fixed-Parameter Tractability of Multicut in Directed Acyclic Graphs. Proceedings of ICALP (1) 2012, Lecture Notes in Computer Science 7391, 581-593.
Publisher's version.
Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk, Jakub Onufry Wojtaszczyk. Sitting Closer to Friends Than Enemies, Revisited. Theory of Computing Systems 56(2), 395-405, 2015.
Publisher's version. Available as technical report arxiv:abs/1201.1869.
Conference version:
Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk, Jakub Onufry Wojtaszczyk. Sitting Closer to Friends Than Enemies, Revisited. Proceedings of MFCS 2012, Lecture Notes in Computer Science 7464, 296-307.
Publisher's version.
Stefan Kratsch, Marcin Pilipczuk, Ashutosh Rai, Venkatesh Raman. Kernel Lower Bounds Using Co-nondeterminism: Finding Induced Hereditary Subgraphs. ACM Transactions on Computation Theory 7(1), 4, 2014.
Conference version:
Stefan Kratsch, Marcin Pilipczuk, Ashutosh Rai, Venkatesh Raman. Kernel Lower Bounds Using Co-nondeterminism: Finding Induced Hereditary Subgraphs. Proceedings of SWAT 2012, Lecture Notes in Computer Science 7357, 364-375.
Publisher's version.
Tomasz Kociumaka, Marcin Pilipczuk. Faster deterministic Feedback Vertex Set. Inf. Process. Lett. 114(10), 556--560, 2014.
Publisher's version. Available as technical report arxiv:abs/1306.3566.
Marek Cygan, Stefan Kratsch, Marcin Pilipczuk, Michał Pilipczuk, Magnus Wahlström. Clique Cover and Graph Separation: New Incompressibility Results. TOCT 6(2), 6, 2014.
Publisher's version. Available as technical report arxiv:abs/1111.0570.
Conference version:
Marek Cygan, Stefan Kratsch, Marcin Pilipczuk, Michał Pilipczuk, Magnus Wahlström. Clique Cover and Graph Separation: New Incompressibility Results. Proceedings of ICALP (1) 2012, Lecture Notes in Computer Science 7391, 254-265.
Publisher's version.
Fedor Fomin, Stefan Kratsch, Marcin Pilipczuk, Michał Pilipczuk, Yngve Villanger. Tight bounds for parameterized complexity of Cluster Editing with a small number of clusters. J. Comput. Syst. Sci. 80(7), 1430--1447, 2014.
Publisher's version. Available as technical report arxiv:abs/1112.4419.
Conference version:
Fedor Fomin, Stefan Kratsch, Marcin Pilipczuk, Michał Pilipczuk, Yngve Villanger. Tight bounds for Parameterized Complexity of Cluster Editing. Proceedings of STACS 2013, 32-43.
Publisher's version.
Marek Cygan, Daniel Lokshtanov, Marcin Pilipczuk, Michał Pilipczuk, Saket Saurabh. On Cutwidth Parameterized by Vertex Cover. Algorithmica 68(4), 940-953, 2014.
Publisher's version.
Conference version:
Marek Cygan, Daniel Lokshtanov, Marcin Pilipczuk, Michał Pilipczuk, Saket Saurabh. On Cutwidth Parameterized by Vertex Cover. Proceedings of IPEC 2011, Lecture Notes in Computer Science 7112, 246-258.
Publisher's version.
Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk, Jakub Onufry Wojtaszczyk. Scheduling Partially Ordered Jobs Faster Than 2n. Algorithmica 68(3), 692-714, 2012.
Publisher's version. Available as technical report arxiv:abs/1108.0810.
Conference version:
Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk, Jakub Onufry Wojtaszczyk. Scheduling Partially Ordered Jobs Faster Than 2n. Proceedings of ESA 2011, Lecture Notes in Computer Science 6942, 299-310.
Publisher's version.
Marek Cygan, Daniel Lokshtanov, Marcin Pilipczuk, Michał Pilipczuk, Saket Saurabh. On the Hardness of Losing Width. Theory Comput. Syst. 54(1), 73-82, 2014.
Publisher's version.
Conference version:
Marek Cygan, Daniel Lokshtanov, Marcin Pilipczuk, Michał Pilipczuk, Saket Saurabh. On the Hardness of Losing Width. Proceedings of IPEC 2011, Lecture Notes in Computer Science 7112, 159-168.
Publisher's version.
Marek Cygan, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, Ildikó Schlotter. Parameterized Complexity of Eulerian Deletion Problems. Algorithmica 68(1), 41-61, 2014.
Publisher's version.
Conference version:
Marek Cygan, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, Ildikó Schlotter. Parameterized Complexity of Eulerian Deletion Problems. Proceedings of WG 2011, Lecture Notes in Computer Science 6986, 131-142.
Publisher's version.
Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk, Jakub Onufry Wojtaszczyk. Solving the 2-Disjoint Connected Subgraphs Problem Faster Than 2n. Algorithmica 70(2), 195-207, 2013.
Publisher's version.
Conference version:
Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk, Jakub Onufry Wojtaszczyk. Solving the 2-Disjoint Connected Subgraphs Problem Faster Than 2n. Proceedings of LATIN 2012, Lecture Notes in Computer Science 7256, 195-206.
Publisher's version.
Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk, Jakub Onufry Wojtaszczyk. On multiway cut parameterized above lower bounds. TOCT 5(1), 3, 2013.
Publisher's version. Available as technical report arxiv:abs/1107.1585.
Conference version:
Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk, Jakub Onufry Wojtaszczyk. On Multiway Cut Parameterized above Lower Bounds. Proceedings of IPEC 2011, Lecture Notes in Computer Science 7112, 1-12.
Publisher's version.
Marek Cygan, Marcin Pilipczuk. Split Vertex Deletion meets Vertex Cover: New fixed-parameter and exact exponential-time algorithms. Information Processing Letters 113(5-6), 179-182, 2013.
Publisher's version. Available as technical report arxiv:abs/1208.1248.
Marek Cygan, Marcin Pilipczuk, Riste Skrekovski. A bound on the number of perfect matchings in klee-graphs. Discrete Mathematics & Theoretical Computer Science 15(1), 37-54, 2013.
Publisher's version. Manuscript PDF.
Łukasz Kowalik, Marcin Pilipczuk, Karol Suchan. Towards optimal kernel for connected vertex cover in planar graphs. Discrete Applied Mathematics 161(7-8), 1154-1161, 2012.
Publisher's version. Available as technical report arxiv:abs/1110.1964.
Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk, Jakub Onufry Wojtaszczyk. Subset Feedback Vertex Set Is Fixed-Parameter Tractable. SIAM Journal of Discrete Mathematics 27(1), 290-309, 2012.
Publisher's version. Available as technical report arxiv:abs/1004.2972.
Conference version:
Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk, Jakub Onufry Wojtaszczyk. Subset Feedback Vertex Set Is Fixed-Parameter Tractable. Proceedings of ICALP (1) 2011, Lecture Notes in Computer Science 6755, 449-461.
Publisher's version.
Marcin Pilipczuk, Michał Pilipczuk, Riste Skrekovski. Some results on Vizing's conjecture and related problems. Discrete Applied Mathematics 160(16-17), 2484-2490, 2012.
Publisher's version.
Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk, Jakub Onufry Wojtaszczyk. Kernelization Hardness of Connectivity Problems in d-Degenerate Graphs. Discrete Applied Mathematics 160(15), 2131-2141, 2012.
Publisher's version.
Conference version:
Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk, Jakub Onufry Wojtaszczyk. Kernelization Hardness of Connectivity Problems in d-Degenerate Graphs. Proceedings of WG 2010, Lecture Notes in Computer Science 6410, 147-158.
Publisher's version.
Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk, Jakub Onufry Wojtaszczyk. A Polynomial Algorithm for 3-Compatible Coloring and the Stubborn List Partition Problem (The Stubborn Problem Is Stubborn No More). SIAM J. Comput. 41(4), 815--828, 2012.
Publisher's version. Available as technical report arxiv:abs/1004.5010.
Conference version:
Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk, Jakub Onufry Wojtaszczyk. The stubborn problem is stubborn no more (a polynomial algorithm for 3-compatible colouring and the stubborn list partition problem). Proceedings of SODA 2011, 1666-1674.
Publisher's version.
Marek Cygan, Marcin Pilipczuk. Bandwidth and distortion revisited. Discrete Applied Mathematics 160(4-5), 494-504, 2012.
Publisher's version. Available as technical report arxiv:abs/1004.5012.
Marek Cygan, Marcin Pilipczuk. Even Faster Exact Bandwidth. ACM Transactions on Algorithms 8(1), 8, 2012.
Publisher's version. Available as technical report arxiv:abs/0902.1661.
Conference version:
Marek Cygan, Marcin Pilipczuk. Faster Exact Bandwidth. Proceedings of WG 2008, Lecture Notes in Computer Science 5344, 101-109.
Publisher's version.
Marek Cygan, Marcin Pilipczuk, Jakub Onufry Wojtaszczyk. Capacitated Domination Faster Than O(2n). Information Processing Letters 111(23-24), 1099-1103, 2011.
Publisher's version.
Conference version:
Marek Cygan, Marcin Pilipczuk, Jakub Onufry Wojtaszczyk. Capacitated Domination Faster Than O(2n). Proceedings of SWAT 2010, Lecture Notes in Computer Science 6139, 74-80.
Publisher's version.
Marek Cygan, Geevarghese Philip, Marcin Pilipczuk, Michał Pilipczuk, Jakub Onufry Wojtaszczyk. Dominating set is fixed parameter tractable in claw-free graphs. Theor. Comput. Sci. 412(50), 6982-7000, 2011.
Publisher's version. Available as technical report arxiv:abs/1011.6239.
Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk, Jakub Onufry Wojtaszczyk. An Improved FPT Algorithm and a Quadratic Kernel for Pathwidth One Vertex Deletion. Algorithmica 64(1), 170-188, 2012.
Publisher's version.
Conference version:
Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk, Jakub Onufry Wojtaszczyk. An Improved FPT Algorithm and Quadratic Kernel for Pathwidth One Vertex Deletion. Proceedings of IPEC 2010, Lecture Notes in Computer Science 6478, 95-106.
Publisher's version.
Daniel Binkele-Raible, Ljiljana Brankovic, Marek Cygan, Henning Fernau, Joachim Kneis, Dieter Kratsch, Alexander Langer, Mathieu Liedloff, Marcin Pilipczuk, Peter Rossmanith, Jakub Onufry Wojtaszczyk. Breaking the 2n-barrier for Irredundance: Two lines of attack. J. Discrete Algorithms 9(3), 214-230, 2011.
Publisher's version.
Conference version:
Marek Cygan, Marcin Pilipczuk, Jakub Onufry Wojtaszczyk. Irredundant Set Faster Than O(2n). Proceedings of CIAC 2010, Lecture Notes in Computer Science 6078, 288-298.
Publisher's version.
Vesna Andova, Saso Bogoev, Darko Dimitrov, Marcin Pilipczuk, Riste Skrekovski. On the Zagreb index inequality of graphs with prescribed vertex degrees. Discrete Applied Mathematics 159(8), 852-858, 2011.
Publisher's version.
Marcin Pilipczuk. Characterization of compact subsets of curves with omega-continuous derivatives. Fundamenta Mathematicae 211(2), 175-195, 2011.
Publisher's version.
Marek Cygan, Marcin Pilipczuk. Exact and approximate bandwidth. Theor. Comput. Sci. 411(40-42), 3701-3713, 2010.
Publisher's version.
Conference version:
Marek Cygan, Marcin Pilipczuk. Exact and Approximate Bandwidth. Proceedings of ICALP (1) 2009, Lecture Notes in Computer Science 5555, 304-315.
Publisher's version.
Piotr Hofman, Marcin Pilipczuk. A few new facts about the EKG sequence. Journal of Integer Sequences 11, article 08.4.2, 2008.
Publisher's version.
Marcin Pilipczuk, Jakub Onufry Wojtaszczyk. The negative association property for the absolute values of random variables equidistributed on a generalized Orlicz ball. Positivity 12(3), 421-474, 2008.
Publisher's version.

Conference articles (without journal versions)

Maria Chudnovsky, Rose McCarty, Marcin Pilipczuk, Michał Pilipczuk, Paweł Rzążewski. Sparse induced subgraphs in P6-free graphs. Proceedings of SODA 2024, to appear.
Available as technical report arxiv:abs/2307.07330.
Antonio Casares, Marcin Pilipczuk, Michał Pilipczuk, Uéverton Souza, K. S. Thejaswini. Simple and tight complexity lower bounds for solving Rabin games. Proceedings of SOSA 2024, to appear.
Available as technical report arxiv:abs/2310.20433.
Karthik C. S., Dániel Marx, Marcin Pilipczuk, Uéverton Souza. Conditional lower bounds for sparse parameterized 2-CSP: A streamlined proof. Proceedings of SOSA 2024, to appear.
Available as technical report arxiv:abs/2311.05913.
Vincent Cohen-Addad, Hung Le, Marcin Pilipczuk, Michał Pilipczuk. Planar and Minor-Free Metrics Embed into Metrics of Polylogarithmic Treewidth with Expected Multiplicative Distortion Arbitrarily Close to 1. Proceedings of FOCS 2023, to appear.
Available as technical report arxiv:abs/2304.07268.
Konrad K. Dabrowski, Peter Jonsson, Sebastian Ordyniak, George Osipov, Marcin Pilipczuk, Roohani Sharma. Parameterized Complexity Classification for Interval Constraints. Proceedings of IPEC 2023, to appear.
Available as technical report arxiv:abs/2305.13889.
Eun Jung Kim, Stefan Kratsch, Marcin Pilipczuk, Magnus Wahlström. Flow-augmentation III: Complexity dichotomy for Boolean CSPs parameterized by the number of unsatisfied constraints. Proceedings of SODA 2023, 3218--3228.
Publisher's version. Available as technical report arxiv:abs/2207.07422.
Meike Hatzel, Lars Jaffke, Paloma T. Lima, Tomáš Masařík, Marcin Pilipczuk, Roohani Sharma, Manuel Sorge. Fixed-parameter tractability of DIRECTED MULTICUT with three terminal pairs parameterized by the size of the cutset: twin-width meets flow-augmentation. Proceedings of SODA 2023, 3229--3244.
Publisher's version. Available as technical report arxiv:abs/2207.07425.
Lars Jaffke, Paloma T. Lima, Tomáš Masařík, Marcin Pilipczuk, Uéverton Souza. A tight quasi-polynomial bound for Global Label Min-Cut. Proceedings of SODA 2023, 290--303.
Publisher's version. Available as technical report arxiv:abs/2207.07426.
Konrad Majewski, Tomáš Masařík, Jana Novotná, Karolina Okrasa, Marcin Pilipczuk, Paweł Rzążewski, Marek Sokolowski. Max Weight Independent Set in Graphs with No Long Claws: An Analog of the Gyárfás' Path Argument. Proceedings of ICALP 2022, 93:1--93:19.
Publisher's version. Available as technical report arxiv:abs/2203.04836.
Daniel Lokshtanov, Marcin Pilipczuk, Michał Pilipczuk, Saket Saurabh. Fixed-parameter tractability of graph isomorphism in graphs with an excluded minor. Proceedings of STOC 2022, 914--923.
Publisher's version.
Eun Jung Kim, Stefan Kratsch, Marcin Pilipczuk, Magnus Wahlström. Directed flow-augmentation. Proceedings of STOC 2022, 938--947.
Publisher's version. Available as technical report arxiv:abs/2111.03450.
Shaohua Li, Marcin Pilipczuk, Manuel Sorge. Cluster Editing Parameterized Above Modification-Disjoint P3-Packings. Proceedings of STACS 2021, 49:1--49:16.
Publisher's version. Available as technical report arxiv:abs/1910.08517.
Hugo Jacob, Thomas Bellitto, Oscar Defrain, Marcin Pilipczuk. Close Relatives (Of Feedback Vertex Set), Revisited. Proceedings of IPEC 2021, 21:1--21:15.
Publisher's version. Available as technical report arxiv:abs/2106.16015.
Peter Gartland, Daniel Lokshtanov, Marcin Pilipczuk, Michał Pilipczuk, Paweł Rzążewski. Finding large induced sparse subgraphs in C\geq t-free graphs in quasipolynomial time. Proceedings of STOC 2021, 330--341.
Publisher's version.
Eun Jung Kim, Stefan Kratsch, Marcin Pilipczuk, Magnus Wahlström. Solving hard cut problems via flow-augmentation. Proceedings of SODA 2021, 149--168.
Publisher's version. Available as technical report arxiv:abs/2007.09018.
Marcin Pilipczuk, Michał Pilipczuk, Paweł Rzążewski. Quasi-polynomial-time algorithm for Independent Set in Pt-free graphs via shrinking the space of induced paths. Proceedings of SOSA 2021, 204--209.
Publisher's version. Available as technical report arxiv:abs/2009.13494.
Stefan Kratsch, Tomáš Masařík, Irene Muzi, Marcin Pilipczuk, Manuel Sorge. Optimal Discretization is Fixed-parameter Tractable. Proceedings of SODA 2021, 1702--1719.
Publisher's version. Available as technical report arxiv:abs/2003.02475.
Tara Abrishami, Maria Chudnovsky, Marcin Pilipczuk, Paweł Rzążewski, Paul D. Seymour. Induced subgraphs of bounded treewidth and the container method. Proceedings of SODA 2021, 1948--1964.
Publisher's version. Available as technical report arxiv:abs/2003.05185.
Jiehua Chen, Wojciech Czerwinski, Yann Disser, Andreas Emil Feldmann, Danny Hermelin, Wojciech Nadara, Marcin Pilipczuk, Michał Pilipczuk, Manuel Sorge, Bartlomiej Wróblewski, Anna Zych-Pawlewicz. Efficient fully dynamic elimination forests with applications to detecting long paths and cycles. Proceedings of SODA 2021, 796--809.
Publisher's version. Available as technical report arxiv:abs/2006.00571.
Maria Chudnovsky, Marcin Pilipczuk, Michał Pilipczuk, Stéphan Thomassé. Quasi-polynomial time approximation schemes for the Maximum Weight Independent Set Problem in H-free graphs. Proceedings of SODA 2020, 2260--2278.
Publisher's version. Available as technical report arxiv:abs/1907.04585.
Vincent Cohen-Addad, Michał Pilipczuk, Marcin Pilipczuk. A Polynomial-Time Approximation Scheme for Facility Location on Planar Graphs. Proceedings of FOCS 2019, 560--581.
Publisher's version. Available as technical report arxiv:abs/1904.10680.
Vincent Cohen-Addad, Marcin Pilipczuk, Michał Pilipczuk. Efficient Approximation Schemes for Uniform-Cost Clustering Problems in Planar Graphs. Proceedings of ESA 2019, 33:1--33:14.
Publisher's version. Available as technical report arxiv:abs/1905.00656.
Krzysztof Kiljan, Marcin Pilipczuk. Experimental Evaluation of Parameterized Algorithms for Feedback Vertex Set. Proceedings of SEA 2018, 12:1--12:12.
Publisher's version. Available as technical report arxiv:abs/1803.00925.
Dániel Marx, Marcin Pilipczuk. Subexponential parameterized algorithms for graphs of polynomial growth. Proceedings of ESA 2017, 59:1-59:15.
Available as technical report arxiv:abs/1610.07778.
Alina Ene, Matthias Mnich, Marcin Pilipczuk, Andrej Risteski. On Routing Disjoint Paths in Bounded Treewidth Graphs. Proceedings of SWAT 2016, LIPIcs 53, 15:1--15:15.
Publisher's version. Available as technical report arxiv:abs/1512.01829.
Marek Cygan, Daniel Lokshtanov, Marcin Pilipczuk, Michał Pilipczuk, Saket Saurabh. Lower Bounds for Approximation Schemes for Closest String. Proceedings of SWAT 2016, LIPIcs 53, 12:1--12:10.
Publisher's version. Available as technical report arxiv:abs/1509.05809.
Pål Grønås Drange, Markus Sortland Dregi, Fedor Fomin, Stephan Kreutzer, Daniel Lokshtanov, Marcin Pilipczuk, Michał Pilipczuk, Felix Reidl, Saket Saurabh, Fernando Sánchez Villaamil, Sebastian Siebertz, Somnath Sikdar. Kernelization and Sparseness: the case of Dominating Set. Proceedings of STACS 2016, 31:1-31:14.
Publisher's version. Available as technical report arxiv:abs/1411.4575.
Jakub Łącki, Jakub Oćwieja, Marcin Pilipczuk, Piotr Sankowski, Anna Zych-Pawlewicz. The Power of Dynamic Distance Oracles: Efficient Dynamic Algorithms for the Steiner Tree. Proceedings of STOC 2015, 11--20.
Publisher's version. Available as technical report arxiv:abs/1308.3336.
Marek Cygan, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk. The planar directed k-Vertex-Disjoint Paths problem is fixed-parameter tractable. Proceedings of FOCS 2013, 197-206.
Publisher's version. Available as technical report arxiv:abs/1304.4207.
Marcin Pilipczuk, Michał Pilipczuk, Piotr Sankowski, Erik Jan van Leeuwen. Subexponential-Time Parameterized Algorithm for Steiner Tree on Planar Graphs. Proceedings of STACS 2013, 353-364.
Publisher's version.
Marcin Pilipczuk, Michał Pilipczuk. Finding a maximum induced degenerate subgraph faster than 2n. Proceedings of IPEC 2012, Lecture Notes in Computer Science 7535, 3-12.
Publisher's version. Available as technical report arxiv:abs/1208.4449.
Marek Cygan, Fabrizio Grandoni, Stefano Leonardi, Marcin Pilipczuk, Piotr Sankowski. A Path-Decomposition Theorem with Applications to Pricing and Covering on Trees. Proceedings of ESA 2012, Lecture Notes in Computer Science 7501, 349-360.
Publisher's version.
Marek Cygan, Fabrizio Grandoni, Stefano Leonardi, Marcin Mucha, Marcin Pilipczuk, Piotr Sankowski. Approximation Algorithms for Union and Intersection Covering Problems. Proceedings of FSTTCS 2011, LIPIcs 13, 28-40.
Publisher's version. Available as technical report arxiv:abs/1102.5105.
Marek Cygan, Łukasz Kowalik, Marcin Mucha, Marcin Pilipczuk, Piotr Sankowski. Fast Approximation in Subspaces by Doubling Metric Decomposition. Proceedings of ESA (1) 2010, Lecture Notes in Computer Science 6346, 72-83.
Publisher's version. Available as technical report arxiv:abs/0911.1626.

Technical reports and unpublished manuscripts

Meike Hatzel, Gwenael Joret, Piotr Micek, Marcin Pilipczuk, Torsten Ueckerdt, Bartosz Walczak. Tight bound on treedepth in terms of pathwidth and longest path.
arxiv:abs/2302.02995.
Eun Jung Kim, Tomáš Masařík, Marcin Pilipczuk, Roohani Sharma, Magnus Wahlström. On weighted graph separation problems and flow-augmentation.
arxiv:abs/2208.14841.
Peter Gartland, Daniel Lokshtanov, Tomáš Masařík, Marcin Pilipczuk, Michał Pilipczuk, Paweł Rzążewski. Maximum Weight Independent Set in Graphs with no Long Claws in Quasi-Polynomial Time.
arxiv:abs/2305.15738.
Marek Cygan, Łukasz Kowalik, Marcin Pilipczuk, Mateusz Wykurz. Exponential-Time Approximation of Hard Problems.
arxiv:abs/0810.4934.
Marcin Pilipczuk, Michal Ziobro. Experimental Evaluation of Parameterized Algorithms for Graph Separation Problems: Half-Integral Relaxations and Matroid-based Kernelization.
arxiv:abs/1811.07779.
George Osipov, Marcin Pilipczuk. Directed Symmetric Multicut is W[1]-hard.
arxiv:abs/2310.05839.
Marek Cygan, Marcin Pilipczuk, Jakub Onufry Wojtaszczyk. Beyond O*(2n) in domination-type problems.
arxiv:abs/0909.4021.
Contact me at malcin at mimuw edu pl.