Marcin Wrochna

Publication Activity (10 Years)

Years Active: 2014-2023
Publications (10 Years): 51

Top Topics

Tree Decompositions

Constraint Graph

Top Venues

ACM Trans. Comput. Theory

SIAM J. Discret. Math.

Publications

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