Marcin Wrochna

65 papers A* 7A 4B 8Journal 45Unranked 1

Year	Rank	Type	Title / Venue / Authors
2025	A*	`conf`	Complexity of Approximate Conflict-Free, Linearly-Ordered, and Nonmonochromatic Hypergraph Colourings. ICALP Tamio-Vesa Nakajima, Zephyr Verwimp, Marcin Wrochna, Stanislav Zivný
2025	J	`jnl`	Complexity of approximate conflict-free, linearly-ordered, and nonmonochromatic hypergraph colourings. CoRR Tamio-Vesa Nakajima, Zephyr Verwimp, Marcin Wrochna, Stanislav Zivný
2023	J	`jnl`	PTAS for Sparse General-valued CSPs. ACM Trans. Algorithms Balázs F. Mezei, Marcin Wrochna, Stanislav Zivný
2023	J	`jnl`	Pliability and Approximating Max-CSPs. J. ACM Miguel Romero, Marcin Wrochna, Stanislav Zivný
2023	J	`jnl`	Topology and Adjunction in Promise Constraint Satisfaction. SIAM J. Comput. Andrei A. Krokhin, Jakub Oprsal, Marcin Wrochna, Stanislav Zivný
2022	J	`jnl`	A note on hardness of promise hypergraph colouring. CoRR Marcin Wrochna
2021	J	`jnl`	Linear Kernels for Edge Deletion Problems to Immersion-Closed Graph Classes. SIAM J. Discret. Math. Archontia C. Giannopoulou, Michal Pilipczuk, Jean-Florent Raymond, Dimitrios M. Thilikos, Marcin Wrochna
2021	A*	`conf`	PTAS for Sparse General-Valued CSPs. LICS Balázs F. Mezei, Marcin Wrochna, Stanislav Zivný
2021	J	`jnl`	The Complexity of Promise SAT on Non-Boolean Domains. ACM Trans. Comput. Theory Alex Brandts, Marcin Wrochna, Stanislav Zivný
2021	A*	`conf`	Treewidth-Pliability and PTAS for Max-CSPs. SODA Miguel Romero, Marcin Wrochna, Stanislav Zivný
2020	J	`jnl`	Homomorphism Reconfiguration via Homotopy. SIAM J. Discret. Math. Marcin Wrochna
2020	A*	`conf`	Improved hardness for SODA Marcin Wrochna, Stanislav Zivný
2020	J	`jnl`	Integer Programming and Incidence Treedepth. CoRR Eduard Eiben, Robert Ganian, Dusan Knop, Sebastian Ordyniak, Michal Pilipczuk, Marcin Wrochna
2020	B	`conf`	PACE Solver Description: Sallow: A Heuristic Algorithm for Treedepth Decompositions. IPEC Marcin Wrochna
2020	J	`jnl`	PTAS for Sparse General-Valued CSPs. CoRR Balázs F. Mezei, Marcin Wrochna, Stanislav Zivný
2020	J	`jnl`	Sallow: a heuristic algorithm for treedepth decompositions. CoRR Marcin Wrochna
2020	A*	`conf`	The Complexity of Promise SAT on Non-Boolean Domains. ICALP Alex Brandts, Marcin Wrochna, Stanislav Zivný
2020	J	`jnl`	The Power of the Combined Basic LP and Affine Relaxation for Promise CSPs. Electron. Colloquium Comput. Complex. Joshua Brakensiek, Venkatesan Guruswami, Marcin Wrochna, Stanislav Zivný
2020	J	`jnl`	The Power of the Combined Basic Linear Programming and Affine Relaxation for Promise Constraint Satisfaction Problems. SIAM J. Comput. Joshua Brakensiek, Venkatesan Guruswami, Marcin Wrochna, Stanislav Zivný
2020	J	`jnl`	Tight Complexity Lower Bounds for Integer Linear Programming with Few Constraints. ACM Trans. Comput. Theory Dusan Knop, Michal Pilipczuk, Marcin Wrochna
2020	J	`jnl`	Topology and adjunction in promise constraint satisfaction. CoRR Andrei A. Krokhin, Jakub Oprsal, Marcin Wrochna, Stanislav Zivný
2020	J	`jnl`	Topology and adjunction in promise constraint satisfaction. Electron. Colloquium Comput. Complex. Andrei A. Krokhin, Jakub Oprsal, Marcin Wrochna, Stanislav Zivný
2019	J	`jnl`	Cutwidth: Obstructions and Algorithmic Aspects. Algorithmica Archontia C. Giannopoulou, Michal Pilipczuk, Jean-Florent Raymond, Dimitrios M. Thilikos, Marcin Wrochna
2019	J	`jnl`	Edge Bipartization Faster than $$2^k$$ 2 k. Algorithmica Marcin Pilipczuk, Michal Pilipczuk, Marcin Wrochna
2019	J	`jnl`	Hedetniemi's Conjecture and Strongly Multiplicative Graphs. SIAM J. Discret. Math. Claude Tardif, Marcin Wrochna
2019	J	`jnl`	Improved hardness for H-colourings of G-colourable graphs. CoRR Marcin Wrochna, Stanislav Zivný
2019	B	`conf`	Integer Programming and Incidence Treedepth. IPCO Eduard Eiben, Robert Ganian, Dusan Knop, Sebastian Ordyniak, Michal Pilipczuk, Marcin Wrochna
2019	J	`jnl`	On inverse powers of graphs and topological implications of Hedetniemi's conjecture. J. Comb. Theory B Marcin Wrochna
2019	J	`jnl`	The complexity of promise SAT on non-Boolean domains. CoRR Alex Brandts, Marcin Wrochna, Stanislav Zivný
2019	J	`jnl`	The step Sidorenko property and non-norming edge-transitive graphs. J. Comb. Theory A Daniel Král', Taísa L. Martins, Péter Pál Pach, Marcin Wrochna
2019	A	`conf`	Tight Complexity Lower Bounds for Integer Linear Programming with Few Constraints. STACS Dusan Knop, Michal Pilipczuk, Marcin Wrochna
2019	J	`jnl`	Tight Lower Bounds for the Complexity of Multicoloring. ACM Trans. Comput. Theory Marthe Bonamy, Lukasz Kowalik, Michal Pilipczuk, Arkadiusz Socala, Marcin Wrochna
2019	J	`jnl`	Treewidth-Pliability and PTAS for Max-CSPs. CoRR Miguel Romero, Marcin Wrochna, Stanislav Zivný
2019	J	`jnl`	Turing Kernelization for Finding Long Paths in Graph Classes Excluding a Topological Minor. Algorithmica Bart M. P. Jansen, Marcin Pilipczuk, Marcin Wrochna
2018	J	`jnl`	Fully Polynomial-Time Parameterized Computations for Graphs and Matrices of Low Treewidth. ACM Trans. Algorithms Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, Michal Pilipczuk, Marcin Wrochna
2018	B	`conf`	On Directed Feedback Vertex Set Parameterized by Treewidth. WG Marthe Bonamy, Lukasz Kowalik, Jesper Nederlof, Michal Pilipczuk, Arkadiusz Socala, Marcin Wrochna
2018	J	`jnl`	On Space Efficiency of Algorithms Working on Structural Decompositions of Graphs. ACM Trans. Comput. Theory Michal Pilipczuk, Marcin Wrochna
2018	J	`jnl`	Reconfiguration in bounded bandwidth and tree-depth. J. Comput. Syst. Sci. Marcin Wrochna
2018	J	`jnl`	Tight complexity lower bounds for integer linear programming with few constraints. CoRR Dusan Knop, Michal Pilipczuk, Marcin Wrochna
2017	A*	`conf`	Fully polynomial-time parameterized computations for graphs and matrices of low treewidth. SODA Fedor V. Fomin, Daniel Lokshtanov, Michal Pilipczuk, Saket Saurabh, Marcin Wrochna
2017	A*	`conf`	Linear Kernels for Edge Deletion Problems to Immersion-Closed Graph Classes. ICALP Archontia C. Giannopoulou, Michal Pilipczuk, Jean-Florent Raymond, Dimitrios M. Thilikos, Marcin Wrochna
2017	J	`jnl`	On Directed Feedback Vertex Set parameterized by treewidth. CoRR Marthe Bonamy, Lukasz Kowalik, Jesper Nederlof, Michal Pilipczuk, Arkadiusz Socala, Marcin Wrochna
2017	J	`jnl`	Polynomial Kernelization for Removing Induced Claws and Diamonds. Theory Comput. Syst. Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, Erik Jan van Leeuwen, Marcin Wrochna
2017	J	`jnl`	Square-free graphs are multiplicative. J. Comb. Theory B Marcin Wrochna
2017	A	`conf`	Tight Lower Bounds for the Complexity of Multicoloring. ESA Marthe Bonamy, Lukasz Kowalik, Michal Pilipczuk, Arkadiusz Socala, Marcin Wrochna
2017	J	`jnl`	Turing Kernelization for Finding Long Paths in Graph Classes Excluding a Topological Minor. CoRR Bart M. P. Jansen, Marcin Pilipczuk, Marcin Wrochna
2017	B	`conf`	Turing Kernelization for Finding Long Paths in Graphs Excluding a Topological Minor. IPEC Bart M. P. Jansen, Marcin Pilipczuk, Marcin Wrochna
2016	B	`conf`	Cutwidth: Obstructions and Algorithmic Aspects. IPEC Archontia C. Giannopoulou, Michal Pilipczuk, Jean-Florent Raymond, Dimitrios M. Thilikos, Marcin Wrochna
2016	J	`jnl`	Cutwidth: obstructions and algorithmic aspects. CoRR Archontia C. Giannopoulou, Michal Pilipczuk, Jean-Florent Raymond, Dimitrios M. Thilikos, Marcin Wrochna
2016	B	`conf`	Edge Bipartization Faster Than 2^k. IPEC Marcin Pilipczuk, Michal Pilipczuk, Marcin Wrochna
2016	J	`jnl`	Linear kernels for edge deletion problems to immersion-closed graph classes. CoRR Archontia C. Giannopoulou, Michal Pilipczuk, Dimitrios M. Thilikos, Jean-Florent Raymond, Marcin Wrochna
2016	A	`conf`	On Space Efficiency of Algorithms Working on Structural Decompositions of Graphs. STACS Michal Pilipczuk, Marcin Wrochna
2016	J	`jnl`	Tight lower bounds for the complexity of multicoloring. CoRR Marthe Bonamy, Lukasz Kowalik, Michal Pilipczuk, Arkadiusz Socala, Marcin Wrochna
2015	J	`jnl`	Edge Bipartization faster than 2 CoRR Marcin Pilipczuk, Michal Pilipczuk, Marcin Wrochna
2015	J	`jnl`	Fully polynomial-time parameterized computations for graphs and matrices of low treewidth. CoRR Fedor V. Fomin, Daniel Lokshtanov, Michal Pilipczuk, Saket Saurabh, Marcin Wrochna
2015	A	`conf`	Homomorphism Reconfiguration via Homotopy. STACS Marcin Wrochna
2015	J	`jnl`	On space efficiency of algorithms working on structural decompositions of graphs. CoRR Michal Pilipczuk, Marcin Wrochna
2015	B	`conf`	Polynomial Kernelization for Removing Induced Claws and Diamonds. WG Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, Erik Jan van Leeuwen, Marcin Wrochna
2015	J	`jnl`	Polynomial kernelization for removing induced claws and diamonds. CoRR Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, Erik Jan van Leeuwen, Marcin Wrochna
2014	J	`jnl`	Homomorphism reconfiguration via homotopy. CoRR Marcin Wrochna
2014	J	`jnl`	Reconfiguration in bounded bandwidth and treedepth. CoRR Marcin Wrochna
2014	B	`conf`	Reconfiguration over Tree Decompositions. IPEC Amer E. Mouawad, Naomi Nishimura, Venkatesh Raman, Marcin Wrochna
2014	J	`jnl`	Reconfiguration over tree decompositions. CoRR Amer E. Mouawad, Naomi Nishimura, Venkatesh Raman, Marcin Wrochna
2014	—	`conf`	Reconfiguring Independent Sets in Claw-Free Graphs. SWAT Paul S. Bonsma, Marcin Kaminski, Marcin Wrochna
2014	J	`jnl`	Reconfiguring Independent Sets in Claw-Free Graphs. CoRR Paul S. Bonsma, Marcin Kaminski, Marcin Wrochna