Homepage: Michał Pilipczuk

About me

I work as a stipendiat (research fellow) in the ERC Grant Rigorous Theory of Preprocessing, led by prof. Fedor V. Fomin. The scope of my research includes (but is not limited to) fixed-parameter tractability, kernelization, and exact algorithms for NP-hard problems. I obtained my PhD degree in CS from the University of Bergen in November 2013, and I've done my masters in CS and in mathematics at the Faculty of Mathematics, Informatics and Mechanics, University of Warsaw.



Contact Info

E-mail michal[dot]pilipczuk[at]gmail[dot]com
AddressInstitutt for Informatikk, Universitetet i Bergen, PB 7803, 5020 Bergen, Norge

Phone+47 55 58 42 94
Fax+47 55 58 41 99


Thesis

PhD thesis, prepared under supervision of prof. Fedor V. Fomin, and defended on November 22nd, 2013 at the University of Bergen.

Original version
Revision 1Switched to A4 format, included comments of the opponents (in particular, Propositions got renamed to Theorems), fixed some other minor issues.


Papers

Unpublished

Daniel Lokshtanov, Marcin Pilipczuk, Michał Pilipczuk, Saket Saurabh,
Fixed-parameter tractable canonization and isomorphism test for graphs of bounded treewidth,
unpublished, available at [arxiv]

Ivan Bliznets, Fedor V. Fomin, Marcin Pilipczuk, Michał Pilipczuk,
A subexponential parameterized algorithm for Interval Completion,
unpublished, available at [arxiv]

Ivan Bliznets, Fedor V. Fomin, Marcin Pilipczuk, Michał Pilipczuk,
A subexponential parameterized algorithm for Proper Interval Completion ,
unpublished, available at [arxiv]

Marcin Pilipczuk, Michał Pilipczuk, Piotr Sankowski, Erik Jan van Leeuwen,
Network sparsification for Steiner problems on planar and bounded-genus graphs,
unpublished, available at [arxiv]

Accepted

Marek Cygan, Daniel Lokshtanov, Marcin Pilipczuk, Michał Pilipczuk, Saket Saurabh,
Minimum Bisection is fixed-parameter tractable,
accepted to STOC 2014, available at [arxiv]

Published

Claire David, Piotr Hofman, Filip Murlak, Michał Pilipczuk,
Synthesizing transformations from XML schema mappings,
ICDT 2014

Pål Grønås Drange, Fedor V. Fomin, Michał Pilipczuk, Yngve Villanger,
Exploring Subexponential Parameterized Complexity of Completion Problems,
STACS 2014, available at [arxiv]

Dániel Marx, Michał Pilipczuk,
Everything you always wanted to know about the parameterized complexity of Subgraph Isomorphism (but were afraid to ask),
STACS 2014, available at [arxiv]

Hans L. Bodlaender, Pål Grønås Drange, Markus Sortland Dregi, Fedor V. Fomin, Daniel Lokshtanov, Michał Pilipczuk,
A O(ck n) 5-approximation algorithm for treewidth,
FOCS 2013, available at [arxiv]

Marek Cygan, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk,
The planar directed k-Vertex-Disjoint Paths problem is fixed-parameter tractable,
FOCS 2013, available at [arxiv]

Fedor V. Fomin, Archontia C. Giannopoulou, Michał Pilipczuk,
Computing tree-depth faster than 2n,
IPEC 2013, available at [arxiv]

Ivan Bliznets, Fedor V. Fomin, Michał Pilipczuk, Yngve Villanger,
Largest chordal and interval subgraphs faster than 2n,
ESA 2013, revised version available at [arxiv]

Fedor V. Fomin, Michał Pilipczuk,
Subexponential parameterized algorithm for computing the cutwidth of a semi-complete digraph,
ESA 2013, available at [arxiv]

Marcin Pilipczuk, Michał Pilipczuk, Piotr Sankowski, Erik Jan van Leeuwen,
Subexponential-time parameterized algorithm for Steiner tree on planar graphs,
STACS 2013

Michał Pilipczuk,
Computing cutwidth and pathwidth of semi-complete digraphs via degree orderings,
STACS 2013, available at [arxiv]

Fedor V. Fomin, Stefan Kratsch, Marcin Pilipczuk, Michał Pilipczuk, Yngve Villanger,
Tight bounds for parameterized complexity of Cluster Editing,
STACS 2013, available at [arxiv]

Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk,
Known algorithms for Edge Clique Cover are probably optimal,
SODA 2013, available at [arxiv]

Fedor V. Fomin, Michał Pilipczuk,
Jungles, bundles, and fixed parameter tractability,
SODA 2013, available at [arxiv]

Rajesh Chitnis, Marek Cygan, MohammadTaghi Hajiaghayi, Marcin Pilipczuk, Michał Pilipczuk,
Designing FPT algorithms for cut problems using randomized contractions,
FOCS 2012, available at [arxiv]

Fedor V. Fomin, Bart M. P. Jansen, Michał Pilipczuk,
Preprocessing subgraph and minor problems: when does a small vertex cover help?,
IPEC 2012, journal version to appear in JCSS, available at [arxiv]

Marcin Pilipczuk, Michał Pilipczuk,
Finding a maximum induced degenerate subgraph faster than 2n,
IPEC 2012, available at [arxiv]

Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk, Jakub Onufry Wojtaszczyk,
Sitting closer to friends than enemies, revisited,
MFCS 2012, available at [arxiv]

Marcin Pilipczuk, Michał Pilipczuk, Riste Škrekovski,
Some results on Vizing's conjecture and related problems,
DAM 160(16-17)

Marek Cygan, Stefan Kratsch, Marcin Pilipczuk, Michał Pilipczuk, Magnus Wahlström,
Clique cover and graph separation: New incompressibility results,
ICALP 2012 (track A), available at [arxiv]

Stefan Kratsch, Marcin Pilipczuk, Michał Pilipczuk, Magnus Wahlström,
Fixed-parameter tractability of multicut in directed acyclic graphs,
ICALP 2012 (track A), available at [arxiv]

Fedor V. Fomin, Petr Golovach, Jesper Nederlof, Michał Pilipczuk,
Minimizing Rosenthal potential in multicast games,
ICALP 2012 (track C), available at [arxiv]

Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk,
On group feedback vertex set parameterized by the size of the cutset,
WG 2012 (best student paper award), available at [arxiv]

Petr Golovach, Pinar Heggernes, Pim van 't Hof, Fredrik Manne, Daniël Paulusma, Michał Pilipczuk,
How to eliminate a graph,
WG 2012, journal version in Algothmica online first (2013) under the name `Modifying a Graph Using Vertex Elimination'

Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk, Jakub Onufry Wojtaszczyk,
Solving the 2-Disjoint Connected Subgraphs problem faster than 2n,
LATIN 2012, journal version in Algorithmica online first (2013)

Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk, Jakub Onufry Wojtaszczyk,
Scheduling partially ordered jobs faster than 2n,
ESA 2011, journal version in Algorithmica online first (2012), available at [arxiv]

Marek Cygan, Daniel Lokshtanov, Marcin Pilipczuk, Michał Pilipczuk, Saket Saurabh,
On the hardness of losing width,
IPEC 2011, journal version in ToCS online first (2013)

Marek Cygan, Daniel Lokshtanov, Marcin Pilipczuk, Michał Pilipczuk, Saket Saurabh,
On cutwidth parameterized by vertex cover,
IPEC 2011, journal version in Algorithmica online first (2012)

Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk, Jakub Onufry Wojtaszczyk,
On Multiway Cut parameterized above lower bounds,
IPEC 2011, journal version in ACM TOCT 5(1):3, available at [arxiv]

Marek Cygan, Michał Pilipczuk, Riste Škrekovski,
On the inequality between radius and Randić index for graphs,
MATCH Commun. Math. Comput. Chem., Volume 67 (2012) number 2

Marek Cygan, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, Ildikó Schlotter,
Parameterized Complexity of Eulerian Deletion Problems,
WG 2011, journal version in Algorithmica online first

Michał Pilipczuk,
Problems parameterized by treewidth tractable in single exponential time: a logical approach,
MFCS 2011, available at [arxiv]

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,
FOCS 2011, full (really full) version available at [arxiv]

Marek Cygan, Geevarghese Philip, Marcin Pilipczuk, Michał Pilipczuk, Jakub Onufry Wojtaszczyk,
Dominating Set is fixed parameter tractable in claw-free Graphs,
TCS 412(50), available at [arxiv]

Marek Cygan, Michał Pilipczuk, Riste Škrekovski,
Relation between Randić index and average distance of trees,
MATCH Commun. Math. Comput. Chem., Volume 66 (2011) number 2

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),
SODA 2011, journal version in SICOMP 41(4), available at [arxiv]

Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk, Jakub Onufry Wojtaszczyk,
Subset feedback vertex set is fixed parameter tractable,
ICALP 2011 (track A), journal version in SIDMA 27(1), available at [arxiv]

Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk, Jakub Onufry Wojtaszczyk,
Improved FPT algorithm and quadratic kernel for Pathwidth One Vertex Deletion,
IPEC 2010, journal version in Algorithmica 64(1)

Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk, Jakub Onufry Wojtaszczyk,
Kernelization hardness of connectivity problems in d-degenerate graphs,
WG 2010, journal version: DAM 160(15)



Presentations

Here you can find a random subset of my presentations, which by some chance I have found in the final version. Description in language X means that the content is also in X.

SubIso@STACS2014Everything you ever wanted to know about the parameterized complexity of Subgraph Isomorphism; STACS 2014, March 2014
Subexp@Dagstuhl2014Subexponential parameterized algorithms for completion problems (Part 2); Dagstuhl seminar on graph modification problems, February 2014
Bisection@BertinoroMinimum Bisection is FPT; Third Bertinoro Workshop on Graphs, December 2013
PhD DefensePresentation from the PhD defense; UiB, November 2013
Tournaments@GROWOverview talk on containment problems in tournaments; GROW 2013, October 2013
ExpandersTrial lecture on expander graphs and their applications; UiB, September 2013
Treedepth@IPECComputing tree-depth faster than 2n; IPEC 2013, September 2013
Cutwidth@ESASubexponential parameterized algorithm for computing the cutwidth of a semi-complete digraph; ESA 2013, September 2013
RC@WORKERDesigning FPT algorithms for cut problems using randomized contractions; Workshop on Kernels 2013, April 2013
Tournaments@DagstuhlOverview talk on containment problems in tournaments; Dagstuhl seminar on bidimensional structures, March 2013
Tournaments@STACS2013Computing cutwidth and pathwidth of semi-complete digraphs via degree orderings; STACS 2013, March 2013
Clustering@STACS2013Tight bounds for parameterized complexity of Cluster Editing; STACS 2013, March 2013
J,B&FPT@SODA2013Jungles, bundles, and fixed-parameter tractability; SODA 2013, January 2013
ECC@SODA2013Known algorithms for Edge Clique Cover are probably optimal; SODA 2013, January 2013
Tutorial@IPEC2012Lower bounds for polynomial kernelization; tutorial during IPEC 2012, September 2012
J,B&FPTJungles, bundles and fixed-parameter tractability; Second Bertinoro Workshop on Graphs, December 2011
MinoryTeoria minorów; referat na XLVII Szkole Matematyki Poglądowej, Sierpień 2011
CC@YRFPresentation on 3-Compatible Colouring; YRF 2011, August 2011
ECML@MFCSPresentation on ECML; MFCS 2011, August 2011
PoznańPresentation about FPT on the seminar of DM group in Poznań, April 2011
ATGAlgebraiczna teoria grafów; referat na XLVI Szkole Matematyki Poglądowej, Luty 2011
d-deg@WorKerKernelization hardness in d-degenerate graphs; Workshop on Kernels 2010, November 2010


Problems

The list of problems in programming competitions I am a (co)author of.

TreesNCPC 2013
JuiceNCPC 2012
SticksXVIII OI, final round
GarbageXVIII OI, second round
Army trainingPA 2010, final round
RiddlePA 2010, round 6
EvacuationPA 2010, round 4
LightsXV OI, final round, practice day
TollXV OI, first round


Other

CV CV, March 2014
mipi@gpg My public key (Bergen)
pscOM@gpgPublic key of the PSC of the Polish MO (for sending problem propositions)