Marcin Pilipczuk

1. Designing FPT algorithms for cut problems using randomized contractions
   2012/07/17 by Rajesh Chitnis, Marek Cygan, Chitnis, Rajesh +7 · 5 citations
   Computer Science · #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning and Algorithms #Optimization and Search Problems
2. Quasi-polynomial time approximation schemes for the Maximum Weight Independent Set Problem in H-free graphs
   2019/07/10 by Maria Chudnovsky, Chudnovsky, Maria, Marcin Pilipczuk +5 · 4 citations
   Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Optimization and Search Problems
3. Minimum Bisection is fixed parameter tractable
   2013/11/11 by Marek Cygan, Daniel Lokshtanov, Cygan, Marek +7 · 2 citations
   Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Search Problems
4. Bounding twin-width for bounded-treewidth graphs, planar graphs, and bipartite graphs
   2022/01/24 by Hugo Jacob, Marcin Pilipczuk, Jacob, Hugo +1 · 3 citations
   Computer Science · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Interconnection Networks and Systems
5. Flow-augmentation III: Complexity dichotomy for Boolean CSPs parameterized by the number of unsatisfied constraints
   2022/07/15 by Eun Jung Kim, Kim, Eun Jung, Stefan Kratsch +5 · 3 citations
   Computer Science · #Constraint Satisfaction and Optimization #Formal Methods in Verification #semigroups and automata theory
6. Clique cover and graph separation: New incompressibility results
   2011/11/02 by Marek Cygan, Stefan Kratsch, Cygan, Marek +7 · 1 citation
   Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #F.2.2 #FOS: Computer and information sciences #Optimization and Search Problems
7. Finding a maximum induced degenerate subgraph faster than 2ⁿ
   2012/08/22 by Marcin Pilipczuk, Pilipczuk, Marcin, Michał Pilipczuk +1 · 1 citation
   Computer Science · Mathematics · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Limits and Structures in Graph Theory
8. A subexponential parameterized algorithm for Proper Interval Completion
   2014/02/13 by Ivan Bliznets, Bliznets, Ivan, Fedor V. Fomin +5 · 1 citation
   Computer Science · #Advanced Graph Theory Research #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Formal Methods in Verification #semigroups and automata theory
9. Edge Bipartization faster than 2^k
   2015/07/08 by Marcin Pilipczuk, Michał Pilipczuk, Pilipczuk, Marcin +3 · 1 citation
   Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Interconnection Networks and Systems
10. Lower bounds for approximation schemes for Closest String
    2015/09/18 by Marek Cygan, Cygan, Marek, Daniel Lokshtanov +7 · 1 citation
    Computer Science · #Algorithms and Data Compression #Complexity and Algorithms in Graphs #Computational Geometry and Mesh Generation #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
11. Embedding Planar Graphs into Graphs of Treewidth O(log³ n)
    2024/10/31 by Hsien-Chih Chang, Chang, Hsien-Chih, Vincent Cohen-Addad +9 · 1 citation
    Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Interconnection Networks and Systems
12. Fatness and Flatness
    2026/07/23 by Arnold Filtser, Hung Le, Nikolas Mählmann +2
    #math.CO #cs.DM #cs.DS #math.MG