Marcin Wrochna

According to our database, Marcin Wrochna authored at least 36 papers between 2014 and 2025.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of three.

2025

Complexity of Approximate Conflict-Free, Linearly-Ordered, and Nonmonochromatic Hypergraph Colourings.

Tamio-Vesa Nakajima, Zephyr Verwimp, Marcin Wrochna, Stanislav Zivný

Proceedings of the 52nd International Colloquium on Automata, Languages, and Programming, 2025

2023

Pliability and Approximating Max-CSPs.

Miguel Romero, Marcin Wrochna, Stanislav Zivný

J. ACM, December, 2023

2022

A note on hardness of promise hypergraph colouring.

Marcin Wrochna

CoRR, 2022

2021

Treewidth-Pliability and PTAS for Max-CSPs.

Miguel Romero, Marcin Wrochna, Stanislav Zivný

Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

PTAS for Sparse General-Valued CSPs.

Balázs F. Mezei, Marcin Wrochna, Stanislav Zivný

Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science, 2021

2020

The Power of the Combined Basic Linear Programming and Affine Relaxation for Promise Constraint Satisfaction Problems.

Joshua Brakensiek, Venkatesan Guruswami, Marcin Wrochna, Stanislav Zivný

SIAM J. Comput., 2020

Topology and adjunction in promise constraint satisfaction.

Andrei A. Krokhin, Jakub Oprsal, Marcin Wrochna, Stanislav Zivný

Electron. Colloquium Comput. Complex., 2020

The Power of the Combined Basic LP and Affine Relaxation for Promise CSPs.

Joshua Brakensiek, Venkatesan Guruswami, Marcin Wrochna, Stanislav Zivný

Electron. Colloquium Comput. Complex., 2020

Sallow: a heuristic algorithm for treedepth decompositions.

Marcin Wrochna

CoRR, 2020

Improved hardness for <i>H</i>-colourings of <i>G</i>-colourable graphs.

Marcin Wrochna, Stanislav Zivný

Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

PACE Solver Description: Sallow: A Heuristic Algorithm for Treedepth Decompositions.

Marcin Wrochna

Proceedings of the 15th International Symposium on Parameterized and Exact Computation, 2020

The Complexity of Promise SAT on Non-Boolean Domains.

Alex Brandts, Marcin Wrochna, Stanislav Zivný

Proceedings of the 47th International Colloquium on Automata, Languages, and Programming, 2020

2019

Hedetniemi's Conjecture and Strongly Multiplicative Graphs.

Claude Tardif, Marcin Wrochna

SIAM J. Discret. Math., 2019

On inverse powers of graphs and topological implications of Hedetniemi's conjecture.

Marcin Wrochna

J. Comb. Theory B, 2019

The step Sidorenko property and non-norming edge-transitive graphs.

Daniel Král', Taísa L. Martins, Péter Pál Pach, Marcin Wrochna

J. Comb. Theory A, 2019

Improved hardness for H-colourings of G-colourable graphs.

Marcin Wrochna, Stanislav Zivný

CoRR, 2019

Edge Bipartization Faster than $$2^k$$ 2 k.

Marcin Pilipczuk, Michal Pilipczuk, Marcin Wrochna

Algorithmica, 2019

Turing Kernelization for Finding Long Paths in Graph Classes Excluding a Topological Minor.

Bart M. P. Jansen, Marcin Pilipczuk, Marcin Wrochna

Algorithmica, 2019

Tight Complexity Lower Bounds for Integer Linear Programming with Few Constraints.

Dusan Knop, Michal Pilipczuk, Marcin Wrochna

Proceedings of the 36th International Symposium on Theoretical Aspects of Computer Science, 2019

Integer Programming and Incidence Treedepth.

Eduard Eiben, Robert Ganian, Dusan Knop, Sebastian Ordyniak, Michal Pilipczuk, Marcin Wrochna

Proceedings of the Integer Programming and Combinatorial Optimization, 2019

2018

Reconfiguration in bounded bandwidth and tree-depth.

Marcin Wrochna

J. Comput. Syst. Sci., 2018

On Directed Feedback Vertex Set Parameterized by Treewidth.

Marthe Bonamy, Lukasz Kowalik, Jesper Nederlof, Michal Pilipczuk, Arkadiusz Socala, Marcin Wrochna

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2018

2017

Square-free graphs are multiplicative.

Marcin Wrochna

J. Comb. Theory B, 2017

Fully polynomial-time parameterized computations for graphs and matrices of low treewidth.

Fedor V. Fomin, Daniel Lokshtanov, Michal Pilipczuk, Saket Saurabh, Marcin Wrochna

Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

Turing Kernelization for Finding Long Paths in Graphs Excluding a Topological Minor.

Bart M. P. Jansen, Marcin Pilipczuk, Marcin Wrochna

Proceedings of the 12th International Symposium on Parameterized and Exact Computation, 2017

Linear Kernels for Edge Deletion Problems to Immersion-Closed Graph Classes.

Archontia C. Giannopoulou, Michal Pilipczuk, Jean-Florent Raymond, Dimitrios M. Thilikos, Marcin Wrochna

Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 2017

Tight Lower Bounds for the Complexity of Multicoloring.

Marthe Bonamy, Lukasz Kowalik, Michal Pilipczuk, Arkadiusz Socala, Marcin Wrochna

Proceedings of the 25th Annual European Symposium on Algorithms, 2017

2016

On Space Efficiency of Algorithms Working on Structural Decompositions of Graphs.

Michal Pilipczuk, Marcin Wrochna

Proceedings of the 33rd Symposium on Theoretical Aspects of Computer Science, 2016

Edge Bipartization Faster Than 2^k.

Marcin Pilipczuk, Michal Pilipczuk, Marcin Wrochna

Proceedings of the 11th International Symposium on Parameterized and Exact Computation, 2016

Cutwidth: Obstructions and Algorithmic Aspects.

Archontia C. Giannopoulou, Michal Pilipczuk, Jean-Florent Raymond, Dimitrios M. Thilikos, Marcin Wrochna

Proceedings of the 11th International Symposium on Parameterized and Exact Computation, 2016

2015

Edge Bipartization faster than 2^k.

Marcin Pilipczuk, Michal Pilipczuk, Marcin Wrochna

CoRR, 2015

Polynomial Kernelization for Removing Induced Claws and Diamonds.

Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, Erik Jan van Leeuwen, Marcin Wrochna

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2015

Homomorphism Reconfiguration via Homotopy.

Marcin Wrochna

Proceedings of the 32nd International Symposium on Theoretical Aspects of Computer Science, 2015

2014

Reconfiguration in bounded bandwidth and treedepth.

Marcin Wrochna

CoRR, 2014

Reconfiguring Independent Sets in Claw-Free Graphs.

Paul S. Bonsma, Marcin Kaminski, Marcin Wrochna

Proceedings of the Algorithm Theory - SWAT 2014, 2014

Reconfiguration over Tree Decompositions.

Amer E. Mouawad, Naomi Nishimura, Venkatesh Raman, Marcin Wrochna

Proceedings of the Parameterized and Exact Computation - 9th International Symposium, 2014