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 2012: teaching assistance for INF 236 Parallelle algoritmer course.
| Lecturer | prof. Fredrik Manne |
| Lectures | Monday 14:15, Thursday 10:15, Room 2103 |
| Exercises | Wednesday 12:15, Room 2103 |
If you have any troubles or questions regarding the course, send me an e-mail or drop by at the office 3146. I will put some stuff from the exercise sessions here.
Spring 2012: random lectures on ACM stuff. Subpage here.
Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk,
Known algorithms for Edge Clique Cover are probably optimal,
unpublished, available at [arxiv]
Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk, Jakub Onufry Wojtaszczyk,
Sitting closer to friends than enemies, revisited,
unpublished, available at [arxiv]
Fedor V. Fomin, Stefan Kratsch, Marcin Pilipczuk, Michał Pilipczuk, Yngve Villanger,
Subexponential fixed-parameter tractability of cluster editing,
unpublished, available at [arxiv]
Fedor V. Fomin, Michał Pilipczuk,
Jungles, bundles, and fixed parameter tractability,
unpublished, available at [arxiv]
Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk,
On group feedback vertex set parameterized by the size of the cutset,
accepted to 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,
accepted to WG 2012
Marek Cygan, Stefan Kratsch, Marcin Pilipczuk, Michał Pilipczuk, Magnus Wahlström,
Clique cover and graph separation: New incompressibility results,
accepted to 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,
accepted to ICALP 2012 (track A), available at [arxiv]
Fedor V. Fomin, Petr Golovach, Jesper Nederlof, Michał Pilipczuk,
Minimizing Rosenthal potential in multicast games,
accepted to ICALP 2012 (track C)
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, 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
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, available at [arxiv], journal version accepted to SICOMP
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 in Algorithmica
Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk, Jakub Onufry Wojtaszczyk,
Kernelization hardness of connectivity problems in d-degenerate graphs,
WG 2010, journal version accepted to DAM
Here you can find a random subset of my presentations, which by some chance I have found in the final version. Description in Polish means that the content is also in Polish.
| 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 |