REVIEW 1 cited by
Parameterized Complexity of CSP for Infinite Constraint Languages
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
Signed reviews
read the original abstract
We study parameterized Constraint Satisfaction Problem for infinite constraint languages. The parameters that we study are weight of the satisfying assignment, number of constraints, maximum number of occurrences of a variable in the instance, and maximum number of occurrences of a variable in each constraint. A dichotomy theorem is already known for finite constraint languages with the weight parameter. We prove some general theorems that show, as new results, that some well-known problems are fixed-parameter tractable and some others are in W[1].
Forward citations
Cited by 1 Pith paper
-
Parameterized Intractability of Even Set and Shortest Vector Problem
For every constant gamma >= 1, k-Even Set is W[1]-hard to approximate under randomized reductions, and for every p > 1, k-SVP in the l_p norm is W[1]-hard to approximate to some constant factor.
Discussion (0). Continue with ORCID to comment.