A General Reduction Theorem with Applications to Pathwidth and the Complexity of MAX 2-CSP

Keith Edwards (Lead / Corresponding author), Eric McDermid

    Research output: Contribution to journalArticlepeer-review

    4 Citations (Scopus)
    373 Downloads (Pure)

    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 languageEnglish
    Pages (from-to)940-968
    Number of pages29
    JournalAlgorithmica
    Volume72
    Issue number4
    Early online date3 May 2014
    DOIs
    Publication statusPublished - 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.

    Cite this