I am a PhD student of prof. Fedor Fomin at the University of Bergen; I started my studies in September 2011. The scope of my research consists of fixed-parameter tractability, kernelization, exact algorithms for NP-hard problems and, in fact, any nice combinatorial algorithmic problems that I encounter. I've done my masters in CS at the Faculty of Mathematics, Informatics and Mechanics of University of Warsaw, where I still pursue the master degree in mathematics.
Apart from this, I used to be involved in Polish Mathematical Olympiad. Despite moving to Norway, I still do some olympic stuff, including participation in selection of the problems and, occasionally, coaching some team for some international competition. I was working also as a jury member for Polish Olympiad in Informatics and a few times helped to prepare the collegiate algorithmic contest Potyczki Algorytmiczne (Algorithmic Engagements).
| michal[dot]pilipczuk[at]gmail[dot]com | |
| Address | Institutt for Informatikk, Universitetet i Bergen, PB 7803, 5020 Bergen, Norge |
| Phone | +47 55 58 42 94 |
| Fax | +47 55 58 41 99 |
Spring 2013: lecturing INF 237 Algoritme-engineering course.
| Lectures and exercises | Wednesday 12:15-16:00 |
| Materials | miside |
If you have any troubles or questions regarding the course, send me an e-mail or drop by at office 3146.
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,
unpublished, available at [arxiv]
Marek Cygan, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk,
The planar directed k-Vertex-Disjoint Paths problem is fixed-parameter tractable,
unpublished, available at [arxiv]
Ivan Bliznets, Fedor V. Fomin, Michał Pilipczuk, Yngve Villanger,
Largest chordal and interval subgraphs faster than 2n,
accepted to ESA 2013
Fedor V. Fomin, Michał Pilipczuk,
Subexponential parameterized algorithm for computing the cutwidth of a semi-complete digraph,
accepted to 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, 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)
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
Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk, Jakub Onufry Wojtaszczyk,
Solving the 2-Disjoint Connected Subgraphs problem faster than 2n,
LATIN 2012
Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk, Jakub Onufry Wojtaszczyk,
Scheduling partially ordered jobs faster than 2n,
ESA 2011, journal version accepted to Algorithmica, available at [arxiv]
Marek Cygan, Daniel Lokshtanov, Marcin Pilipczuk, Michał Pilipczuk, Saket Saurabh,
On the hardness of losing width,
IPEC 2011
Marek Cygan, Daniel Lokshtanov, Marcin Pilipczuk, Michał Pilipczuk, Saket Saurabh,
On cutwidth parameterized by vertex cover,
IPEC 2011
Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk, Jakub Onufry Wojtaszczyk,
On Multiway Cut parameterized above lower bounds,
IPEC 2011, 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
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: 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), 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: 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)
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.
| RC@WORKER | Designing FPT algorithms for cut problems using randomized contractions; Workshop on Kernels 2013, April 2013 |
| Tournaments@Dagstuhl | Overview talk on containment problems in tournaments; Dagstuhl Meeting on Bidimensional Structures, March 2013 |
| Tournaments@STACS2013 | Computing cutwidth and pathwidth of semi-complete digraphs via degree orderings; STACS 2013, March 2013 |
| Clustering@STACS2013 | Tight bounds for parameterized complexity of Cluster Editing; STACS 2013, March 2013 |
| J,B&FPT@SODA2013 | Jungles, bundles, and fixed-parameter tractability; SODA 2013, January 2013 |
| ECC@SODA2013 | Known algorithms for Edge Clique Cover are probably optimal; SODA 2013, January 2013 |
| Tutorial@IPEC2012 | Lower bounds for polynomial kernelization; tutorial during IPEC 2012, September 2012 |
| J,B&FPT | Jungles, bundles and fixed-parameter tractability; Second Bertinoro Workshop on Graphs, December 2011 |
| Minory | Teoria minorów; referat na XLVII Szkole Matematyki Poglądowej, Sierpień 2011 |
| CC@YRF | Presentation on 3-Compatible Colouring; YRF 2011, August 2011 |
| ECML@MFCS | Presentation on ECML; MFCS 2011, August 2011 |
| Poznań | Presentation about FPT on the seminar of DM group in Poznań, April 2011 |
| ATG | Algebraiczna teoria grafów; referat na XLVI Szkole Matematyki Poglądowej, Luty 2011 |
| d-deg@WorKer | Kernelization hardness in d-degenerate graphs; Workshop on Kernels 2010, November 2010 |
The list of problems in programming competitions I am a (co)author of.
| Sticks | XVIII OI, final round |
| Garbage | XVIII OI, second round |
| Army training | PA 2010, final round |
| Riddle | PA 2010, round 6 |
| Evacuation | PA 2010, round 4 |
| Lights | XV OI, final round, practice day |
| Toll | XV OI, first round |
| CV | CV, May 2012 |
| mipi@gpg | My public key (Bergen) |
| pscOM@gpg | Public key of the PSC of the Polish MO (for sending problem propositions) |
| norskU1 | Lists of words from the norwegian classes |
| norskU1-src | Sources of the above |