### Abstract

We prove a general reduction theorem which allows us to extend bounds for certain graph parameters on cubic graphs to bounds for general graphs taking into account the individual vertex degrees. As applications, we give an algorithm for Max 2 -CSP whose complexity matches the algorithm of Scott and Sorkin in the case of d -regular graphs, d=5 , but is otherwise faster. It also improves on the previously fastest known algorithm in terms of the average degree, given by Golovnev and Kutzkov. Also from the general theorem, we derive a bound for the pathwidth of a general graph which equals that of Fomin et al. and Gaspers for graphs of degree at most 6 , but is smaller otherwise, and use this to give an improved exponential-space algorithm for Max 2 -CSP. Finally we use the general result to give a faster algorithm for Max 2 -CSP on claw-free graphs.

Original language | English |
---|---|

Pages (from-to) | 940-968 |

Number of pages | 29 |

Journal | Algorithmica |

Volume | 72 |

Issue number | 4 |

Early online date | 3 May 2014 |

DOIs | |

Publication status | Published - Aug 2015 |

### Keywords

- Constraint satisfaction problems
- Max 2-CSP
- Treewidth
- Pathwidth

## Fingerprint Dive into the research topics of 'A General Reduction Theorem with Applications to Pathwidth and the Complexity of MAX 2-CSP'. Together they form a unique fingerprint.

## Profiles

## Cite this

Edwards, K., & McDermid, E. (2015). A General Reduction Theorem with Applications to Pathwidth and the Complexity of MAX 2-CSP.

*Algorithmica*,*72*(4), 940-968. https://doi.org/10.1007/s00453-014-9883-7