TY - JOUR

T1 - willingness to pay

AU - Stöckel, Morten

AU - Vildhøj, Hjalte Wedel

AU - Bøg, Søren

PY - 2013

Y1 - 2013

N2 - 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ˆea 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.

AB - 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ˆea 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.

KW - Functional Orientation 2-Color problem

KW - Holographic algorithms

KW - Planar graph coloring

KW - Computational complexity

KW - NP-complete graphs

M3 - Journal article

SN - 1034-4942

VL - 56

JO - Australasian Journal of Combinatorics

JF - Australasian Journal of Combinatorics

ER -