Chudnovsky, Maria; Pilipczuk, Marcin; Pilipczuk, Michał; Thomassé, Stéphan Quasi-polynomial time approximation schemes for the maximum weight independent set problem in \(H\)-free graphs. (English) Zbl 07810343 SIAM J. Comput. 53, No. 1, 47-86 (2024). MSC: 68R10 05C69 05C85 PDFBibTeX XMLCite \textit{M. Chudnovsky} et al., SIAM J. Comput. 53, No. 1, 47--86 (2024; Zbl 07810343) Full Text: DOI
Nederlof, Jesper; Pilipczuk, Michał; Swennenhuis, Celine M. F.; Węgrzycki, Karol Hamiltonian cycle parameterized by treedepth in single exponential time and polynomial space. (English) Zbl 07725062 SIAM J. Discrete Math. 37, No. 3, 1566-1586 (2023). MSC: 68Q25 68R10 68W20 PDFBibTeX XMLCite \textit{J. Nederlof} et al., SIAM J. Discrete Math. 37, No. 3, 1566--1586 (2023; Zbl 07725062) Full Text: DOI
Bożyk, Łukasz; Pilipczuk, Michał On the Erdős-Pósa property for immersions and topological minors in tournaments. (English) Zbl 1515.05142 Discrete Math. Theor. Comput. Sci. 24, No. 1, Paper No. 12, 16 p. (2022). MSC: 05C70 05C20 05C83 PDFBibTeX XMLCite \textit{Ł. Bożyk} and \textit{M. Pilipczuk}, Discrete Math. Theor. Comput. Sci. 24, No. 1, Paper No. 12, 16 p. (2022; Zbl 1515.05142) Full Text: DOI arXiv
Fomin, Fedor V.; Lokshtanov, Daniel; Marx, Dániel; Pilipczuk, Marcin; Pilipczuk, Michał; Saurabh, Saket Subexponential parameterized algorithms for planar and apex-minor-free graphs via low treewidth pattern covering. (English) Zbl 1511.05222 SIAM J. Comput. 51, No. 6, 1866-1930 (2022). MSC: 05C85 05C10 05C75 68R10 PDFBibTeX XMLCite \textit{F. V. Fomin} et al., SIAM J. Comput. 51, No. 6, 1866--1930 (2022; Zbl 1511.05222) Full Text: DOI arXiv
Bożyk, Łukasz; Defrain, Oscar; Okrasa, Karolina; Pilipczuk, Michał On objects dual to tree-cut decompositions. (English) Zbl 1497.05181 J. Comb. Theory, Ser. B 157, 401-428 (2022). MSC: 05C60 05C70 05C57 91A43 91A24 PDFBibTeX XMLCite \textit{Ł. Bożyk} et al., J. Comb. Theory, Ser. B 157, 401--428 (2022; Zbl 1497.05181) Full Text: DOI arXiv
Bonamy, Marthe; Gavoille, Cyril; Pilipczuk, Michał Shorter labeling schemes for planar graphs. (English) Zbl 07589616 SIAM J. Discrete Math. 36, No. 3, 2082-2099 (2022). MSC: 68R10 05C85 PDFBibTeX XMLCite \textit{M. Bonamy} et al., SIAM J. Discrete Math. 36, No. 3, 2082--2099 (2022; Zbl 07589616) Full Text: DOI
Marx, Dániel; Pilipczuk, Marcin; Pilipczuk, Michal A subexponential parameterized algorithm for directed subset traveling salesman problem on planar graphs. (English) Zbl 1486.05294 SIAM J. Comput. 51, No. 2, 254-289 (2022). MSC: 05C85 05C10 68R10 90C35 90C27 PDFBibTeX XMLCite \textit{D. Marx} et al., SIAM J. Comput. 51, No. 2, 254--289 (2022; Zbl 1486.05294) Full Text: DOI arXiv
Bonamy, Marthe; Bousquet, Nicolas; Pilipczuk, Michał; Rzążewski, Paweł; Thomassé, Stéphan; Walczak, Bartosz Degeneracy of \(P_t\)-free and \(C_{\geq t}\)-free graphs with no large complete bipartite subgraphs. (English) Zbl 1478.05047 J. Comb. Theory, Ser. B 152, 353-378 (2022). MSC: 05C15 05C75 05C35 05C60 PDFBibTeX XMLCite \textit{M. Bonamy} et al., J. Comb. Theory, Ser. B 152, 353--378 (2022; Zbl 1478.05047) Full Text: DOI arXiv
Chudnovsky, Maria; King, Jason; Pilipczuk, Michał; Rzążewski, Paweł; Spirkl, Sophie Finding large \(H\)-colorable subgraphs in hereditary graph classes. (English) Zbl 1478.05048 SIAM J. Discrete Math. 35, No. 4, 2357-2386 (2021). Reviewer: Vahan Mkrtchyan (L’Aquila) MSC: 05C15 05C85 68Q25 PDFBibTeX XMLCite \textit{M. Chudnovsky} et al., SIAM J. Discrete Math. 35, No. 4, 2357--2386 (2021; Zbl 1478.05048) Full Text: DOI arXiv
Bonamy, Marthe; Dross, François; Masařík, Tomáš; Munaro, Andrea; Nadara, Wojciech; Pilipczuk, Marcin; Pilipczuk, Michał Jones’ conjecture in subcubic graphs. (English) Zbl 1476.05038 Electron. J. Comb. 28, No. 4, Research Paper P4.5, 12 p. (2021). MSC: 05C10 05C38 05C69 68R10 PDFBibTeX XMLCite \textit{M. Bonamy} et al., Electron. J. Comb. 28, No. 4, Research Paper P4.5, 12 p. (2021; Zbl 1476.05038) Full Text: DOI arXiv
Pilipczuk, Michał; Siebertz, Sebastian Polynomial bounds for centered colorings on proper minor-closed graph classes. (English) Zbl 1490.05082 J. Comb. Theory, Ser. B 151, 111-147 (2021). Reviewer: Sanming Zhou (Parkville) MSC: 05C15 05C83 05C85 05C75 05C60 PDFBibTeX XMLCite \textit{M. Pilipczuk} and \textit{S. Siebertz}, J. Comb. Theory, Ser. B 151, 111--147 (2021; Zbl 1490.05082) Full Text: DOI arXiv
Briański, Marcin; Micek, Piotr; Pilipczuk, Michał; Seweryn, Michał T. Erdös-Hajnal properties for powers of sparse graphs. (English) Zbl 1460.05103 SIAM J. Discrete Math. 35, No. 1, 447-464 (2021). MSC: 05C42 05C15 05C83 PDFBibTeX XMLCite \textit{M. Briański} et al., SIAM J. Discrete Math. 35, No. 1, 447--464 (2021; Zbl 1460.05103) Full Text: DOI arXiv
Bojańczyk, Mikołaj; Grohe, Martin; Pilipczuk, Michał Definable decompositions for graphs of bounded linear cliquewidth. (English) Zbl 1509.03119 Log. Methods Comput. Sci. 17, No. 1, Paper No. 5, 40 p. (2021). MSC: 03D05 03B16 05C70 68Q25 68Q45 PDFBibTeX XMLCite \textit{M. Bojańczyk} et al., Log. Methods Comput. Sci. 17, No. 1, Paper No. 5, 40 p. (2021; Zbl 1509.03119) Full Text: arXiv Link
Grzesik, Andrzej; Klimošová, Tereza; Pilipczuk, Marcin; Pilipczuk, Michał Covering minimal separators and potential maximal cliques in \(P_t\)-free graphs. (English) Zbl 1458.05194 Electron. J. Comb. 28, No. 1, Research Paper P1.29, 14 p. (2021). MSC: 05C69 05C70 05C75 05C85 68R10 PDFBibTeX XMLCite \textit{A. Grzesik} et al., Electron. J. Comb. 28, No. 1, Research Paper P1.29, 14 p. (2021; Zbl 1458.05194) Full Text: DOI arXiv
Giannopoulou, Archontia; Pilipczuk, Michał; Raymond, Jean-Florent; Thilikos, Dimitrios M.; Wrochna, Marcin Linear kernels for edge deletion problems to immersion-closed graph classes. (English) Zbl 1461.05164 SIAM J. Discrete Math. 35, No. 1, 105-151 (2021). Reviewer: Sizhong Zhou (Zhenjiang) MSC: 05C70 05C75 05C83 05C85 PDFBibTeX XMLCite \textit{A. Giannopoulou} et al., SIAM J. Discrete Math. 35, No. 1, 105--151 (2021; Zbl 1461.05164) Full Text: DOI arXiv
Chudnovsky, Maria; King, Jason; Pilipczuk, Michał; Rząėwski, Paweł; Spirkl, Sophie Finding large H-colorable subgraphs in hereditary graph classes. (English) Zbl 07651174 Grandoni, Fabrizio (ed.) et al., 28th annual European symposium on algorithms. ESA 2020, September 7–9, 2020, Pisa, Italy, virtual conference. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 173, Article 35, 17 p. (2020). MSC: 68Wxx PDFBibTeX XMLCite \textit{M. Chudnovsky} et al., LIPIcs -- Leibniz Int. Proc. Inform. 173, Article 35, 17 p. (2020; Zbl 07651174) Full Text: DOI
Pilipczuk, Michał Computing tree decompositions. (English) Zbl 07604213 Fomin, Fedor V. (ed.) et al., Treewidth, kernels, and algorithms. Essays dedicated to Hans L. Bodlaender on the occasion of his 60th birthday. Cham: Springer. Lect. Notes Comput. Sci. 12160, 189-213 (2020). MSC: 68-XX PDFBibTeX XMLCite \textit{M. Pilipczuk}, Lect. Notes Comput. Sci. 12160, 189--213 (2020; Zbl 07604213) Full Text: DOI
Paszke, Adam; Pilipczuk, Michał VC density of set systems definable in tree-like graphs. (English) Zbl 07559449 Esparza, Javier (ed.) et al., 45th international symposium on mathematical foundations of computer science, MFCS 2020, August 25–26, 2020, Prague, Czech Republic. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 170, Article 78, 13 p. (2020). MSC: 68Qxx PDFBibTeX XMLCite \textit{A. Paszke} and \textit{M. Pilipczuk}, LIPIcs -- Leibniz Int. Proc. Inform. 170, Article 78, 13 p. (2020; Zbl 07559449) Full Text: DOI arXiv
Chudnovsky, Maria; Pilipczuk, Marcin; Pilipczuk, Michał; Thomassé, Stéphan On the maximum weight independent set problem in graphs without induced cycles of length at least five. (English) Zbl 1459.05234 SIAM J. Discrete Math. 34, No. 2, 1472-1483 (2020). MSC: 05C69 05C75 05C85 05C17 05C12 PDFBibTeX XMLCite \textit{M. Chudnovsky} et al., SIAM J. Discrete Math. 34, No. 2, 1472--1483 (2020; Zbl 1459.05234) Full Text: DOI arXiv
Pilipczuk, Michał; van Leeuwen, Erik Jan; Wiese, Andreas Quasi-polynomial time approximation schemes for packing and covering problems in planar graphs. (English) Zbl 1433.68307 Algorithmica 82, No. 6, 1703-1739 (2020). MSC: 68R10 05C10 05C69 05C70 05C85 68U05 68W25 PDFBibTeX XMLCite \textit{M. Pilipczuk} et al., Algorithmica 82, No. 6, 1703--1739 (2020; Zbl 1433.68307) Full Text: DOI Link
Kwon, O-joung; Pilipczuk, Michał; Siebertz, Sebastian On low rank-width colorings. (English) Zbl 1428.05110 Eur. J. Comb. 83, Article ID 103002, 17 p. (2020). MSC: 05C15 PDFBibTeX XMLCite \textit{O-j. Kwon} et al., Eur. J. Comb. 83, Article ID 103002, 17 p. (2020; Zbl 1428.05110) Full Text: DOI
Fomin, Fedor V.; Pilipczuk, Michał On width measures and topological problems on semi-complete digraphs. (English) Zbl 1415.05063 J. Comb. Theory, Ser. B 138, 78-165 (2019). MSC: 05C20 05C12 PDFBibTeX XMLCite \textit{F. V. Fomin} and \textit{M. Pilipczuk}, J. Comb. Theory, Ser. B 138, 78--165 (2019; Zbl 1415.05063) Full Text: DOI Link
Cygan, Marek; Lokshtanov, Daniel; Pilipczuk, Marcin; Pilipczuk, Michał; Saurabh, Saket Minimum bisection is fixed-parameter tractable. (English) Zbl 1421.68069 SIAM J. Comput. 48, No. 2, 417-450 (2019). MSC: 68Q25 68R10 68W05 PDFBibTeX XMLCite \textit{M. Cygan} et al., SIAM J. Comput. 48, No. 2, 417--450 (2019; Zbl 1421.68069) Full Text: DOI Link
Giannopoulou, Archontia C.; Pilipczuk, Michał; Raymond, Jean-Florent; Thilikos, Dimitrios M.; Wrochna, Marcin Cutwidth: obstructions and algorithmic aspects. (English) Zbl 1414.68035 Algorithmica 81, No. 2, 557-588 (2019). MSC: 68Q25 05C85 68R10 PDFBibTeX XMLCite \textit{A. C. Giannopoulou} et al., Algorithmica 81, No. 2, 557--588 (2019; Zbl 1414.68035) Full Text: DOI
Pilipczuk, Michal; van Leeuwen, Erik Jan; Wiese, Andreas Quasi-polynomial time approximation schemes for packing and covering problems in planar graphs. (English) Zbl 1524.68239 Azar, Yossi (ed.) et al., 26th annual European symposium on algorithms, ESA 2018, August 20–22, 2018, Helsinki, Finland. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 112, Article 65, 13 p. (2018). MSC: 68R10 05C10 05C69 05C70 05C85 68U05 68W25 PDFBibTeX XMLCite \textit{M. Pilipczuk} et al., LIPIcs -- Leibniz Int. Proc. Inform. 112, Article 65, 13 p. (2018; Zbl 1524.68239) Full Text: DOI arXiv
Pilipczuk, Marcin; Pilipczuk, Michał Planar digraphs. (English) Zbl 1407.05114 Bang-Jensen, Jørgen (ed.) et al., Classes of directed graphs. Cham: Springer. Springer Monogr. Math., 207-243 (2018). MSC: 05C20 05C10 05C85 PDFBibTeX XMLCite \textit{M. Pilipczuk} and \textit{M. Pilipczuk}, in: Classes of directed graphs. Cham: Springer. 207--243 (2018; Zbl 1407.05114) Full Text: DOI
Cygan, Marek; Pilipczuk, Marcin; Pilipczuk, Michał; van Leeuwen, Erik Jan; Wrochna, Marcin Polynomial kernelization for removing induced claws and diamonds. (English) Zbl 1368.68222 Theory Comput. Syst. 60, No. 4, 615-636 (2017). MSC: 68Q25 68Q17 68R10 PDFBibTeX XMLCite \textit{M. Cygan} et al., Theory Comput. Syst. 60, No. 4, 615--636 (2017; Zbl 1368.68222) Full Text: DOI arXiv
Lokshtanov, Daniel; Pilipczuk, Marcin; Pilipczuk, Michał; Saurabh, Saket Fixed-parameter tractable canonization and isomorphism test for graphs of bounded treewidth. (English) Zbl 1358.05284 SIAM J. Comput. 46, No. 1, 161-189 (2017). MSC: 05C85 05C60 68W05 68W40 PDFBibTeX XMLCite \textit{D. Lokshtanov} et al., SIAM J. Comput. 46, No. 1, 161--189 (2017; Zbl 1358.05284) Full Text: DOI arXiv Link
Bliznets, Ivan; Fomin, Fedor V.; Pilipczuk, Michał; Villanger, Yngve Largest chordal and interval subgraphs faster than \(2^n\). (English) Zbl 1347.05236 Algorithmica 76, No. 2, 569-594 (2016). MSC: 05C85 05C35 05C60 68Q25 PDFBibTeX XMLCite \textit{I. Bliznets} et al., Algorithmica 76, No. 2, 569--594 (2016; Zbl 1347.05236) Full Text: DOI arXiv
Cygan, Marek; Pilipczuk, Marcin; Pilipczuk, Michał; van Leeuwen, Erik Jan; Wrochna, Marcin Polynomial kernelization for removing induced claws and diamonds. (English) Zbl 1362.68104 Mayr, Ernst W. (ed.), Graph-theoretic concepts in computer science. 41st international workshop, WG 2015, Garching, Germany, June 17–19, 2015. Revised papers. Berlin: Springer (ISBN 978-3-662-53173-0/pbk; 978-3-662-53174-7/ebook). Lecture Notes in Computer Science 9224, 440-455 (2016). MSC: 68Q25 68Q17 68R10 PDFBibTeX XMLCite \textit{M. Cygan} et al., Lect. Notes Comput. Sci. 9224, 440--455 (2016; Zbl 1362.68104) Full Text: DOI Link
Chitnis, Rajesh; Cygan, Marek; Hajiaghayi, MohammadTaghi; Pilipczuk, Marcin; Pilipczuk, Michał Designing FPT algorithms for cut problems using randomized contractions. (English) Zbl 1348.68063 SIAM J. Comput. 45, No. 4, 1171-1229 (2016). MSC: 68Q25 05C85 68W20 68W40 PDFBibTeX XMLCite \textit{R. Chitnis} et al., SIAM J. Comput. 45, No. 4, 1171--1229 (2016; Zbl 1348.68063) Full Text: DOI arXiv
Bodlaender, Hans L.; Drange, Pål Grønås; Dregi, Markus S.; Fomin, Fedor V.; Lokshtanov, Daniel; Pilipczuk, Michał A \(c^k n\) 5-approximation algorithm for treewidth. (English) Zbl 1333.05282 SIAM J. Comput. 45, No. 2, 317-378 (2016). MSC: 05C85 05C05 68R10 68W25 PDFBibTeX XMLCite \textit{H. L. Bodlaender} et al., SIAM J. Comput. 45, No. 2, 317--378 (2016; Zbl 1333.05282) Full Text: DOI arXiv
Cygan, Marek; Pilipczuk, Marcin; Pilipczuk, Michał On group feedback vertex set parameterized by the size of the cutset. (English) Zbl 1336.68121 Algorithmica 74, No. 2, 630-642 (2016). MSC: 68Q25 05C35 05C78 05C85 PDFBibTeX XMLCite \textit{M. Cygan} et al., Algorithmica 74, No. 2, 630--642 (2016; Zbl 1336.68121) Full Text: DOI arXiv
Fomin, Fedor V.; Giannopoulou, Archontia C.; Pilipczuk, Michał Computing tree-depth faster than \(2^n\). (English) Zbl 1337.68129 Algorithmica 73, No. 1, 202-216 (2015). MSC: 68Q25 05C85 PDFBibTeX XMLCite \textit{F. V. Fomin} et al., Algorithmica 73, No. 1, 202--216 (2015; Zbl 1337.68129) Full Text: DOI arXiv
Golovach, Petr A.; Heggernes, Pinar; van ’t Hof, Pim; Manne, Fredrik; Paulusma, Daniël; Pilipczuk, Michał Modifying a graph using vertex elimination. (English) Zbl 1314.68232 Algorithmica 72, No. 1, 99-125 (2015). MSC: 68R10 05C76 68Q17 68Q25 PDFBibTeX XMLCite \textit{P. A. Golovach} et al., Algorithmica 72, No. 1, 99--125 (2015; Zbl 1314.68232) Full Text: DOI Link
Cygan, Marek; Kratsch, Stefan; Pilipczuk, Marcin; Pilipczuk, Michał; Wahlström, Magnus Clique cover and graph separation: new incompressibility results. (English) Zbl 1321.68302 ACM Trans. Comput. Theory 6, No. 2, Article No. 6, 19 p. (2014). MSC: 68Q25 05C69 05C70 PDFBibTeX XMLCite \textit{M. Cygan} et al., ACM Trans. Comput. Theory 6, No. 2, Article No. 6, 19 p. (2014; Zbl 1321.68302) Full Text: DOI
Cygan, Marek; Pilipczuk, Marcin; Pilipczuk, Michał; Wojtaszczyk, Jakub Onufry Solving the 2-disjoint connected subgraphs problem faster than \(2^n\). (English) Zbl 1306.05125 Algorithmica 70, No. 2, 195-207 (2014). MSC: 05C40 05C60 05C85 68Q25 PDFBibTeX XMLCite \textit{M. Cygan} et al., Algorithmica 70, No. 2, 195--207 (2014; Zbl 1306.05125) Full Text: DOI
Fomin, Fedor V.; Jansen, Bart M. P.; Pilipczuk, Michał Preprocessing subgraph and minor problems: when does a small vertex cover help? (English) Zbl 1277.68095 J. Comput. Syst. Sci. 80, No. 2, 468-495 (2014). MSC: 68Q25 05C85 05C70 05C15 PDFBibTeX XMLCite \textit{F. V. Fomin} et al., J. Comput. Syst. Sci. 80, No. 2, 468--495 (2014; Zbl 1277.68095) Full Text: DOI arXiv
Cygan, Marek; Pilipczuk, Marcin; Pilipczuk, Michał; Wojtaszczyk, Jakub Onufry An improved FPT algorithm and a quadratic kernel for pathwidth one vertex deletion. (English) Zbl 1252.68150 Algorithmica 64, No. 1, 170-188 (2012). MSC: 68Q25 05C85 68Q17 PDFBibTeX XMLCite \textit{M. Cygan} et al., Algorithmica 64, No. 1, 170--188 (2012; Zbl 1252.68150) Full Text: DOI
Cygan, Marek; Pilipczuk, Marcin; Pilipczuk, Michał; Wojtaszczyk, Jakub Onufry On multiway cut parameterized above lower bounds. (English) Zbl 1352.68100 Marx, Dániel (ed.) et al., Parameterized and exact computation. 6th international symposium, IPEC 2011, Saarbrücken, Germany, September 6–8, 2011. Revised selected papers. Berlin: Springer (ISBN 978-3-642-28049-8/pbk). Lecture Notes in Computer Science 7112, 1-12 (2012). MSC: 68Q25 05C40 05C70 68Q17 90C27 PDFBibTeX XMLCite \textit{M. Cygan} et al., Lect. Notes Comput. Sci. 7112, 1--12 (2012; Zbl 1352.68100) Full Text: DOI arXiv
Cygan, Marek; Philip, Geevarghese; Pilipczuk, Marcin; Pilipczuk, Michał; Wojtaszczyk, Jakub Onufry Dominating set is fixed parameter tractable in claw-free graphs. (English) Zbl 1228.68030 Theor. Comput. Sci. 412, No. 50, 6982-7000 (2011). MSC: 68Q17 05C69 PDFBibTeX XMLCite \textit{M. Cygan} et al., Theor. Comput. Sci. 412, No. 50, 6982--7000 (2011; Zbl 1228.68030) Full Text: DOI arXiv
Cygan, Marek; Pilipczuk, Marcin; Pilipczuk, Michał; Wojtaszczyk, Jakub Onufry An improved FPT algorithm and quadratic kernel for pathwidth one vertex deletion. (English) Zbl 1309.68090 Raman, Venkatesh (ed.) et al., Parameterized and exact computation. 5th international symposium, IPEC 2010, Chennai, India, December 13–15, 2010. Proceedings. Berlin: Springer (ISBN 978-3-642-17492-6/pbk). Lecture Notes in Computer Science 6478, 95-106 (2010). MSC: 68Q25 05C85 PDFBibTeX XMLCite \textit{M. Cygan} et al., Lect. Notes Comput. Sci. 6478, 95--106 (2010; Zbl 1309.68090) Full Text: DOI