vix.ing · top · new · best · stats · spec

Pilipczuk, Marcin

  1. Solving connectivity problems parameterized by treewidth in single exponential time
    2011/03/02 by Cygan, Marek, Nederlof, Jesper, Pilipczuk, Marcin +3 · 11 citations
    #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
  2. 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
  3. Directed multicut is W[1]-hard, even for four terminal pairs
    2015/07/08 by Pilipczuk, Marcin, Wahlström, Magnus · 3 citations
    #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
  4. Quasi-polynomial time approximation schemes for the Maximum Weight Independent Set Problem in H-free graphs
    2019/07/10 by Maria Chudnovsky, Marcin Pilipczuk, Chudnovsky, Maria +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
  5. On Multiway Cut parameterized above lower bounds
    2011/07/08 by Cygan, Marek, Pilipczuk, Marcin, Pilipczuk, Michał +1 · 2 citations
    #Data Structures and Algorithms (cs.DS) #F.2.2 #FOS: Computer and information sciences
  6. Fast branching algorithm for Cluster Vertex Deletion
    2013/06/17 by Boral, Anudhyan, Cygan, Marek, Kociumaka, Tomasz +1 · 2 citations
    #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
  7. Minimum Bisection is fixed parameter tractable
    2013/11/11 by Marek Cygan, Cygan, Marek, Daniel Lokshtanov +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
  8. Bounding twin-width for bounded-treewidth graphs, planar graphs, and bipartite graphs
    2022/01/24 by Hugo Jacob, Jacob, Hugo, Marcin Pilipczuk +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
  9. Randomized contractions meet lean decompositions
    2018/10/16 by Cygan, Marek, Komosa, Paweł, Lokshtanov, Daniel +4 · 2 citations
    #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
  10. Optimal Discretization is Fixed-parameter Tractable
    2020/03/05 by Kratsch, Stefan, Masařík, Tomáš, Muzi, Irene +2 · 2 citations
    #68Q25 #68R01 #68W40 #Computational Geometry (cs.CG) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences
  11. Maximum Weight Independent Set in Graphs with no Long Claws in Quasi-Polynomial Time
    2023/05/25 by Gartland, Peter, Lokshtanov, Daniel, Masařík, Tomáš +3 · 3 citations
    #05C69 #05C85 #Data Structures and Algorithms (cs.DS) #F.2.2 #FOS: Computer and information sciences #G.2.2
  12. Flow-augmentation III: Complexity dichotomy for Boolean CSPs parameterized by the number of unsatisfied constraints
    2022/07/15 by Eun Jung Kim, Stefan Kratsch, Kim, Eun Jung +5 · 3 citations
    Computer Science · #Constraint Satisfaction and Optimization #Formal Methods in Verification #semigroups and automata theory
  13. Hardness of Metric Dimension in Graphs of Constant Treewidth
    2021/02/19 by Li, Shaohua, Pilipczuk, Marcin · 2 citations
    #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences
  14. 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
  15. Known algorithms for EDGE CLIQUE COVER are probably optimal
    2012/03/08 by Cygan, Marek, Pilipczuk, Marcin, Pilipczuk, Michał · 1 citation
    #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #F.2.2 #FOS: Computer and information sciences
  16. Fixed-parameter tractability of multicut in directed acyclic graphs
    2012/02/26 by Kratsch, Stefan, Pilipczuk, Marcin, Pilipczuk, Michał +1 · 1 citation
    #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #F.2.2 #FOS: Computer and information sciences
  17. Finding a maximum induced degenerate subgraph faster than 2n
    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
  18. The planar directed k-Vertex-Disjoint Paths problem is fixed-parameter tractable
    2013/04/15 by Cygan, Marek, Marx, Dániel, Pilipczuk, Marcin +1 · 1 citation
    #Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
  19. The Power of Dynamic Distance Oracles: Efficient Dynamic Algorithms for the Steiner Tree
    2013/08/15 by Łącki, Jakub, Oćwieja, Jakub, Pilipczuk, Marcin +2 · 1 citation
    #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
  20. 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
  21. Fixed-parameter tractable canonization and isomorphism test for graphs of bounded treewidth
    2014/04/03 by Lokshtanov, Daniel, Pilipczuk, Marcin, Pilipczuk, Michał +1 · 1 citation
    #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
  22. Hitting forbidden subgraphs in graphs of bounded treewidth
    2014/11/15 by Cygan, Marek, Marx, Dániel, Pilipczuk, Marcin +1 · 1 citation
    #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
  23. Polynomial kernelization for removing induced claws and diamonds
    2015/03/02 by Cygan, Marek, Pilipczuk, Marcin, Pilipczuk, Michał +2 · 1 citation
    #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
  24. Edge Bipartization faster than 2k
    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
  25. Lower bounds for approximation schemes for Closest String
    2015/09/18 by Marek Cygan, Daniel Lokshtanov, Cygan, Marek +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
  26. Subexponential parameterized algorithms for planar and apex-minor-free graphs via low treewidth pattern covering
    2016/04/20 by Fomin, Fedor V., Lokshtanov, Daniel, Marx, Dániel +3 · 1 citation
    #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
  27. Subexponential parameterized algorithms for graphs of polynomial growth
    2016/10/25 by Marx, Dániel, Pilipczuk, Marcin · 1 citation
    #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
  28. A deterministic polynomial kernel for Odd Cycle Transversal and Vertex Multiway Cut in planar graphs
    2018/10/02 by Jansen, Bart M. P., Pilipczuk, Marcin, van Leeuwen, Erik Jan · 1 citation
    #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
  29. Finding large induced sparse subgraphs in C>t-free graphs in quasipolynomial time
    2020/07/21 by Gartland, Peter, Lokshtanov, Daniel, Pilipczuk, Marcin +2 · 1 citation
    #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
  30. Max Weight Independent Set in graphs with no long claws: An analog of the Gyárfás' path argument
    2022/03/09 by Majewski, Konrad, Masařík, Tomáš, Novotná, Jana +4 · 1 citation
    #Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
  31. Taming graphs with no large creatures and skinny ladders
    2022/05/02 by Gajarský, Jakub, Jaffke, Lars, Lima, Paloma T. +4 · 1 citation
    #Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
  32. On the Complexity of Problems on Tree-structured Graphs
    2022/06/23 by Bodlaender, Hans L., Groenland, Carla, Jacob, Hugo +2 · 1 citation
    #Computational Complexity (cs.CC) #FOS: Computer and information sciences
  33. Fixed-parameter tractability of Graph Isomorphism in graphs with an excluded minor
    2022/10/26 by Lokshtanov, Daniel, Pilipczuk, Marcin, Pilipczuk, Michał +1 · 1 citation
    #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences
  34. Flow-augmentation I: Directed graphs
    2021/11/05 by Kim, Eun Jung, Kratsch, Stefan, Pilipczuk, Marcin +1 · 1 citation
    #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences
  35. Max Weight Independent Set in sparse graphs with no long claws
    2023/09/29 by Abrishami, Tara, Chudnovsky, Maria, Dibek, Cemil +2 · 1 citation
    #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences
  36. Parameterized Complexity Classification for Interval Constraints
    2023/05/23 by Dabrowski, Konrad K., Jonsson, Peter, Ordyniak, Sebastian +3 · 2 citations
    #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
  37. Conditional lower bounds for sparse parameterized 2-CSP: A streamlined proof
    2023/11/10 by S., Karthik C., Marx, Dániel, Pilipczuk, Marcin +1 · 1 citation
    #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
  38. Parameterized Complexity of MinCSP over the Point Algebra
    2023/10/09 by Osipov, George, Pilipczuk, Marcin, Wahlström, Magnus · 2 citations
    #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
  39. The Influence of Dimensions on the Complexity of Computing Decision Trees
    2022/05/16 by Kobourov, Stephen G., Löffler, Maarten, Montecchiani, Fabrizio +5 · 1 citation
    #Computational Complexity (cs.CC) #FOS: Computer and information sciences
  40. On coarse tree decompositions and coarse balanced separators
    2025/02/27 by Abrishami, Tara, Czyżewska, Jadwiga, Kluk, Kacper +3 · 2 citations
    #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
  41. Planar and Minor-Free Metrics Embed into Metrics of Polylogarithmic Treewidth with Expected Multiplicative Distortion Arbitrarily Close to 1
    2023/04/14 by Cohen-Addad, Vincent, Le, Hung, Pilipczuk, Marcin +1 · 1 citation
    #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences
  42. Bounding ε-scatter dimension via metric sparsity
    2024/10/14 by Bourneuf, Romain, Pilipczuk, Marcin · 1 citation
    #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences
  43. Embedding Planar Graphs into Graphs of Treewidth O(log3 n)
    2024/10/31 by Hsien-Chih Chang, Vincent Cohen-Addad, Chang, Hsien-Chih +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