Back

Marcin Pilipczuk: research


Papers

Journal articles

Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk, Erik Jan van Leeuwen, Marcin Wrochna. Polynomial kernelization for removing induced claws and diamonds. Theory of Computing Systems, to appear, 2016.
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, to appear.
Marcin Pilipczuk. A tight lower bound for Vertex Planarization on graphs of bounded treewidth. Discrete Applied Mathematics, to appear, 2016.
Rajesh Chitnis, Marek Cygan, MohammadTaghi Hajiaghayi, Marcin Pilipczuk, Michał Pilipczuk. Designing FPT algorithms for cut problems using randomized contractions. SIAM Journal of Computing, to appear, 2016.
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.
Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk. On Group Feedback Vertex Set Parameterized by the Size of the Cutset. Algorithmica 74(2), 630-642, 2016.
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.
Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk. Known algorithms for EDGE CLIQUE COVER are probably optimal. SIAM Journal of Computing 45(1), 67-83, 2016.
Conference version:
Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk. Known algorithms for EDGE CLIQUE COVER are probably optimal. Proceedings of SODA 2013, 1044-1053.
Daniel Lokshtanov, Marcin Pilipczuk, Michał Pilipczuk, Saket Saurabh. Fixed-parameter tractable canonization and isomorphism test for graphs of bounded treewidth. SIAM J. Computing, to appear, 2015.
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.
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.
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.
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.
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.
Marek Cygan, Marcin Pilipczuk. Faster exponential-time algorithms in graphs of bounded average degree. Inf. Comput. 243, 75--85, 2015.
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.
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.
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.
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.
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.
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.
Tomasz Kociumaka, Marcin Pilipczuk. Faster deterministic Feedback Vertex Set. Inf. Process. Lett. 114(10), 556--560, 2014.
Marek Cygan, Stefan Kratsch, Marcin Pilipczuk, Michał Pilipczuk, Magnus Wahlström. Clique Cover and Graph Separation: New Incompressibility Results. TOCT 6(2), 6, 2014.
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.
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.
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.
Marek Cygan, Daniel Lokshtanov, Marcin Pilipczuk, Michał Pilipczuk, Saket Saurabh. On Cutwidth Parameterized by Vertex Cover. Algorithmica 68(4), 940-953, 2014.
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.
Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk, Jakub Onufry Wojtaszczyk. Scheduling Partially Ordered Jobs Faster Than 2n. Algorithmica 68(3), 692-714, 2012.
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.
Marek Cygan, Daniel Lokshtanov, Marcin Pilipczuk, Michał Pilipczuk, Saket Saurabh. On the Hardness of Losing Width. Theory Comput. Syst. 54(1), 73-82, 2014.
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.
Marek Cygan, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, Ildikó Schlotter. Parameterized Complexity of Eulerian Deletion Problems. Algorithmica 68(1), 41-61, 2014.
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.
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.
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.
Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk, Jakub Onufry Wojtaszczyk. On multiway cut parameterized above lower bounds. TOCT 5(1), 3, 2013.
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.
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.
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.
Ł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.
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.
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.
Marcin Pilipczuk, Michał Pilipczuk, Riste Skrekovski. Some results on Vizing's conjecture and related problems. Discrete Applied Mathematics 160(16-17), 2484-2490, 2012.
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.
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.
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). SIAM Journal of Computing 41(4), 815-828, 2012.
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.
Marek Cygan, Marcin Pilipczuk. Bandwidth and distortion revisited. Discrete Applied Mathematics 160(4-5), 494-504, 2012.
Marek Cygan, Marcin Pilipczuk. Even Faster Exact Bandwidth. ACM Transactions on Algorithms 8(1), 8, 2012.
Conference version:
Marek Cygan, Marcin Pilipczuk. Faster Exact Bandwidth. Proceedings of WG 2008, Lecture Notes in Computer Science 5344, 101-109.
Marek Cygan, Marcin Pilipczuk, Jakub Onufry Wojtaszczyk. Capacitated Domination Faster Than O(2n). Information Processing Letters 111(23-24), 1099-1103, 2011.
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.
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.
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.
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.
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.
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.
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.
Marcin Pilipczuk. Characterization of compact subsets of curves with omega-continuous derivatives. Fundamenta Mathematicae 211(2), 175-195, 2011.
Marek Cygan, Marcin Pilipczuk. Exact and approximate bandwidth. Theor. Comput. Sci. 411(40-42), 3701-3713, 2010.
Conference version:
Marek Cygan, Marcin Pilipczuk. Exact and Approximate Bandwidth. Proceedings of ICALP (1) 2009, Lecture Notes in Computer Science 5555, 304-315.
Piotr Hofman, Marcin Pilipczuk. A few new facts about the EKG sequence. Journal of Integer Sequences 11, article 08.4.2, 2008.
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.

Conference articles (without journal versions)

Chandra Chekuri, Alina Ene, Marcin Pilipczuk. Constant Congestion Routing of Symmetric Demands in Planar Directed Graphs. Proceedings of ICALP 2016, to appear.
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, to appear.
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.
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.
Daniel Lokshtanov, Marcin Pilipczuk, Erik Jan van Leeuwen. Independence and Efficient Domination on P6-free Graph. Proceedings of SODA 2016, 1784-1803.
Marcin Pilipczuk, Magnus Wahlström. Directed multicut is W[1]-hard, even for four terminal pairs. Proceedings of SODA 2016, 1167-1178.
Ivan Bliznets, Fedor Fomin, Marcin Pilipczuk, Michał Pilipczuk. A subexponential parameterized algorithm for Interval Completion. Proceedings of SODA 2016, 1116-1131.
Jakub Łącki, Jakub Oćwieja, Marcin Pilipczuk, Piotr Sankowski, Anna Zych. The Power of Dynamic Distance Oracles: Efficient Dynamic Algorithms for the Steiner Tree. Proceedings of STOC 2015, 11--20.
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.
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.
Marek Cygan, Daniel Lokshtanov, Marcin Pilipczuk, Michał Pilipczuk, Saket Saurabh. Minimum bisection is fixed parameter tractable. Proceedings of STOC 2014, 323--332.
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.
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.
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.
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.
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.
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.
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.

Technical reports and unpublished manuscripts

Bart M.P. Jansen, Marcin Pilipczuk. Approximation and Kernelization for Chordal Vertex Deletion.

Contact me at malcin at mimuw edu pl.