The hardness of the functional orientation 2-color problem

Morten Stöckel, Hjalte Wedel Vildhøj, Søren Bøg

Research output: Contribution to journalJournal articleResearchpeer-review

Abstract

We consider the Functional Orientation 2-Color problem, which was introduced by Valiant in his seminal paper on holographic algorithms [SIAM J. Comput. 37(5) (2008), 1565-1594]. For this decision problem, Valiant gave a polynomial time holographic algorithm for planar graphs of maximum degree 3, and showed that the problem is NP-complete for planar graphs of maximum degree 10. A recent result on defective graph coloring by Corrêa et al. [Australas. J. Combin. 43 (2009), 219-230] implies that the problem is already hard for planar graphs of maximum degree 8. Together, these results leave open the hardness question for graphs of maximum degree between 4 and 7. We close this gap by showing that the answer is always yes for arbitrary graphs of maximum degree 5, and that the problem is NP-complete for planar graphs of maximum degree 6. Moreover, for graphs of maximum degree 5, we note that a linear time algorithm for finding a solution exists.
Original languageEnglish
JournalAustralasian Journal of Combinatorics
Volume56
Pages (from-to)225-234
ISSN1034-4942
Publication statusPublished - 2013

Fingerprint

Dive into the research topics of 'The hardness of the functional orientation 2-color problem'. Together they form a unique fingerprint.

Cite this