Conditional lower bounds for sparse parameterized 2-CSP: a streamlined proof

DOI10.1137/1.9781611977936.35MaRDI QIDQ6545136zbMATH OpenFDO

Authors C. S. Karthik, Dániel Marx, Marcin Pilipczuk, Uéverton S. Souza

Publication date 29 May 2024

Full work available at URL https://doi.org/10.1137/1.9781611977936.35

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cited in

(6)

• On the tractability landscape of the conditional minisum approval voting rule
• Can you link up with treewidth?
• Minimizing the weighted number of tardy jobs is W[1]-hard
• From Chinese postman to salesman and beyond. II: Inapproximability and parameterized complexity
• Monotone bounded-depth complexity of homomorphism polynomials
• Can you link up with treewidth?

This page was built for publication: Conditional lower bounds for sparse parameterized 2-CSP: a streamlined proof

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6545136)