Printer Friendly

On the complexity of vertex-coloring edge-weightings.

1 Introduction

For a given graph G = (V, E), let w : E [right arrow] R be a weight function. We say that w is proper if the coloring of the vertices xw (v) = [[summation].sup.e[contains as member]]w(e), v g V, is proper. In 2004, KaroHski, Luczak, and Thomason (2004) showed that any graph with no components isomorphic to K2 has a proper weighting from a finite set of reals. Furthermore, they conjectured that every graph with no components isomorphic to [K.sub.2] has a proper weighting from W = {1, 2, 3}. Addario-Berry, Dalal, McDiarmid, Reed, and Thomason (2007) showed that the above holds if W = {1,..., 30}. This result was improved by Addario-Berry, Dalal, and Reed (2008), who showed that one can take W = {1,..., 16}. Subsequently, Wang and Yu (2008) proved that W = {1,..., 13} suffices. A recent breakthrough by Kalkowski, Karoriski, and Pfender (2010) showed that the set of weights can be as small as W = {1,2,3,4,5}.

On the other hand, Addario-Berry, Dalal, and Reed (2008) showed that almost all graphs have a proper weighting from {1, 2}. In this paper, we show that determining whether a particular graph has a proper weighting of the edges from {1, 2} is NP-complete. Consequently, there is no simple characterization of graphs with proper weightings from {1,2}, unless P=NP. Formally, let

1-2WEIGHT = {G : G is a graph having a proper weighting from {1,2}} .

[FIGURE 1 OMITTED]

Theorem 1.1 1-2WEIGHT is NP-complete.

Before we prove this statement, we consider a similar theorem with a somewhat simpler proof, which we use as a template to prove Theorem 1.1. By analogy to 1-2WEIGHT we denote by 0-1WEIGHT the family of graphs with a proper weighting from {0,1} and show the following:

Theorem 1.2 0-1WEIGHT is NP-complete.

2 0-1WEIGHT is NP-complete

Here we prove Theorem 1.2.

First note that 0-1WEIGHT is clearly in NP, since one can verify in polynomial time for a given graph whether a weighting of its edges from {0, 1} is proper.

Next we consider the well-known NP-hard problem

3-COLOR = {G : G is a graph having a proper 3-vertex-coloring}.

In order to prove that 0-1WEIGHT is NP-hard (and hence NP-complete), we show a reduction from 3COLOR to 0-1WEIGHT. To this end, we define a polynomial time reduction h, such that G [member of] 3-COLOR if and only if h(G) [member of] 0-1WEIGHT. To achieve this, we need two auxiliary gadgets.

We refer to the first gadget as a triangle gadget. This consists of a triangle xab, with x referred to as the top and with a and b each having no other coinciding edges. Note that any proper weighting w from {0,1} of a graph with such a triangle must hold w(xa) = w(xb); otherwise xw (a) = w(ab) + w(ax) = w(ba) + w(bx) = xw (b). Hence, {w(xa), w(xb)} = {0,1} and so every such triangle gadget contributes exactly 1 to xw (x).

The second gadget, called a [kappa]-disallowing gadget, consists of a main triangle vxy with v referred to as the root and with x and y each constituting the top of k - 1 distinct triangle gadgets (see Figure 1(a)). Note that in any proper weighting w from {0,1}, w(vx) [not equal to] w(vy); otherwise, as both xw(x) and xw(y) have k - 1 contributed by x and y's triangles, xw(x) = w(xv) + w(xy) + k - 1 = w(yv) + w(yx) + k - 1 = xw(y). Therefore, if w(xy) = 0 then {xw(x),xw(y)} = {k - 1,k} and, if w(xy) = 1 then {xw(x),xw(y)} = {k, k + 1}. In either case, v has one neighbor z [member of] {x,y} with xw(z) = k, and consequently, xw (v) [not equal to] k in any proper weighting from {0,1}. Also {w(vx), w(vy)} = {0,1} and hence this gadget contributes exactly 1 to xw (v).

Now we are ready to show a reduction from 3-COLOR to 0-1WEIGHT, h, such that G g 3-COLOR if and only if h(G) g 0-1WEIGHT. Let G = (V, E) be a graph of order n. We may assume that n [greater than or equal to] 3. Otherwise, n [less than or equal to] 2 and G is in 3-COLOR and so it suffices to take as h(G) an empty graph which is trivially in 0-1WEIGHT. For n [greater than or equal to] 3 we construct the graph h(G) = (W, F) as follows (see Figure 1(c)). We start with G = (V, E). For each v [member of] V:

(i) connect v to two new vertices, s and t (distinct for each v);

(ii) add n - 1 new [kappa]-disallowing gadgets for all [kappa] [member of] {n + 2, n + 3,..., 2n} with v as their root.

Clearly, h(G) can be calculated in time polynomial in the size of G.

Fact 2.1 In h(G) the following holds: any proper weighting w from {0,1} satisfies xw (v) [member of] {n - 1, n, n + 1} for every v [member of] V.

Proof: Fix v g V. Since w(vs) + w(vt) g {0,1, 2}, v is the endpoint of deg(v) < n - 1 edges in V, and v is the root of (n - 1) [kappa]-disallowing gadgets (each contributing 1 to xw (v)), we have:

xw(v) g {0,1, 2} + {0,1, ..., deg(v)} + {n - 1} c {n - 1, n,..., 2n},

where by A + B we mean the set of all sums of an element from A with an element from B. Observing the above and the fact that v is the root of [kappa]-disallowing gadgets for all [kappa] [member of] {n + 2,..., 2n}, we find that any proper weighting w from {0,1} satisfies xw (v) [member of] {n - 1, n, n +1}, as claimed.

It remains to show that G [member of] 3-COLOR if and only if h(G) [member of] 0-1WEIGHT.

First let us assume that G [member of] 3-COLOR. That means there exists a proper 3-coloring of G, say x : V [right arrow] {n - 1, n, n +1}. We define a weighting of the edges of h(G), w : F [right arrow] {0,1} as follows. For all e g E let w(e) = 0. For all v g V, if x(v) = n - 1 then w(vs) = w(vt) = 0; otherwise, if x(v) = n then w(vs) = 1 and w(vt) = 0; and finally, if x(v) = n +1 then w(vs) = w(vt) = 1. All other edges (parts of gadgets) are weighted as follows: For a triangle gadget xab with root x, w(xa) = 1, w(xb) = w(ab) = 0. For a [kappa]-disallowing gadget with root v, and main triangle vxy, w(vx) = w(xy) = 1, w(vy) = 0, and the weighting of all other triangle gadgets as described above. Note that w is a proper weighting of h(G) (satisfying xw (v) = x(v) for all v [member of] V), as required.

Now let us assume that G [not member of] 3-COLOR. Therefore, for all x : V [right arrow] {n - 1, n, n +1}, x is not proper. But, from Fact 2.1, any proper weighting from {0,1} of h(G) satisfies xw (v) g {n - 1, n, n +1} for all v [member of] V. Thus, there is no such proper weighting and hence h(G) [not member of] 0-1WEIGHT.

This completes the proof of Theorem 1.2.

3 1-2WEIGHT is NP-complete

The proof of Theorem 1.1 extends the ideas introduced in the proof of Theorem 1.2. Since clearly 12WEIGHT is in NP, it remains to show that 1-2WEIGHT is NP-hard. As before, we show a reduction from 3-COLOR to 1-2WEIGHT. To this end, we define a polynomial time reduction f, such that G [member of] 3-COLOR if and only if f (G) [member of] 1-2WEIGHT. Below we define auxiliary gadgets.

As in Section 2, we will use a triangle gadget. Now note that every triangle xab, with only x having other adjacent edges (x is referred to as the top), contributes exactly 3 to xw (x) in any proper weighting w from {1 , 2}.

[FIGURE 2 OMITTED]

Now we define a 2-edge gadget consisting of the set of vertices {x, c, d, e, f} with x and c adjacent and {c, d, e, f} spanning a complete graph [K.sub.4]. One can check that every proper weighting w from {1,2} of a graph adjacent to such a gadget only at x requires w(xc) = 2. We refer to x as the endpoint.

We use the above gadgets to construct another gadget, called a [kappa]-disallowing gadget. As we will see, this gadget has similar properties as its namesake in Section 2. We therefore allow ourselves the re-use of the name for this new, slightly different, gadget. We assume that [kappa] [greater than or equal to] 8. The [kappa]- disallowing gadget contains a main triangle vxy with v referred to as the root. Moreover, if k is even, x and y each form the endpoint of ([kappa] - 6)/2 edge disjoint 2-edge gadgets and x and y are each tops of distinct triangle gadgets (see Figure 2(a)). If k is odd, x and y each form the endpoint of ([kappa] - 3)/2 edge disjoint 2-edge gadgets (see Figure 2(b)). Note that in any proper weighting w from {1,2}, w(vx) [not equal to] w(vy); otherwise, since the weight contributed by gadgets to xw (x) and xw (y) is [kappa] - 3, then xw (x) = w(xv) + w(xy) + [kappa] - 3 = w(yv) + w(yx) + [kappa] - 3 = xw (y). Therefore, for any [kappa], if w(xy) = 1 then {xw(x), xw (y)} = {[kappa] - 1, [kappa]} and, if w(xy) = 2 then {xw (x), xw (y)} = {k, [kappa] + 1}. In either case, v has one neighbor z g {x, y} with xw (z) = k, and consequently, xw(v) = k in any proper weighting from {1,2}. Also {w(vx), w(vy)} = {1,2}, and hence this gadget contributes exactly 3 to xw (v).

Now we are ready to show a polynomial time reduction from 3-COLOR to 1-2WEIGHT, f, such that G [member of] 3-COLOR if and only if f (G) [member of] 1-2WEIGHT. Let G = (V, E) be a graph of order n. As in Section 2, we may assume that n [greater than or equal to] 3. We construct the graph f (G) = (W, F) as follows (see Figure 2(d)). We start with G = (V, E). For each v g V:

(i) connect v to two new vertices s and t (distinct for each v);

(ii) connect v to all vertices from a new set [U.sub.v] (distinct for each v) with [absolute value of Uv] = n - 1 - deg(v);

(iii) add n - 1 new [kappa]-disallowing gadgets for all [kappa] [member of] {4n +1,4n + 2,..., 5n - 1} with v as their root. Clearly, f (G) can be calculated in time polynomial in the size of G.

Fact 3.1 In f (G) the following holds: any proper weighting w from {1,2} satisfies xw (v) [[member of] {4n - 2, 4n - 1 , 4n} for every v [member of] V.

Proof: Fix v [member of] V. Since w(vs) + w(vt) [member of] {2,3,4}, v is the endpoint of n - 1 edges with endpoints in V [union] Uv and v is the root of (n - 1) [kappa]-disallowing gadgets (each contributing 3 to xw(v)), we have:

xw(v) [member of] {2, 3, 4} + {n - 1,..., 2n - 2} + {3n - 3} = {4n - 2,..., 5n - 1}.

Observing the above and the fact that v is the root of [kappa]-disallowing gadgets for all [kappa] {4n + 1, 4n + 2,..., 5n - 1}, we find that any proper weighting w from {1, 2} satisfies xw (v) [member of] {4n - 2,4n - 1,4n}, as claimed.

Now we show that G G 3-COLOR if and only if f (G) G 1-2WEIGHT.

First let us assume that G 3-COLOR. That means there exists a proper 3-coloring of G, say x :

V [right arrow] {4n - 2,4n - 1,4n}. We define a weighting of the edges of f (G), w : F [right arrow] {1, 2} as follows. For all e G E let w(e) = 1. For all edges e = vu with v G V and u G [U.sub.v] we set w(e) = 1. For all v G V, if x(v) = 4n - 2 then w(vs) = w(vt) = 1; otherwise, if x(v) = 4n - 1 then w(vs) = 1 and w(vt) = 2; finally, if x(v) = 4n then w(vs) = w(vt) = 2. All other edges (parts of gadgets) are weighted as follows: For a triangle gadget xab with root x, w(xa) = 2, w(xb) = w(ab) = 1. For a 2-gadget defined by {x, c, d, e, f} with x adjacent to c, we have w(xc) = w(cd) = w(ce) = w(de) = w(df) = 2 and w(cf) = w(ef) = 1. For a [kappa]-disallowing gadget with root v and main triangle vxy, w(vx) = w(xy) = 2, w(vy) = 1, and the weighting of all other gadgets as described above. Note that w is a proper weighting of f (G) (satisfying xw (v) = x(v) for all v G V), as required.

Next let us assume that G [not member of] 3-COLOR. Therefore, for all x : V [right arrow] {4n - 2,4n - 1,4n}, x is not a proper vertex coloring. But, from Fact 3.1, any proper weighting from {1,2} of f (G) satisfies xw(v) [member of] {4n - 2, 4n - 1, 4n} for all v [member of] V. Thus, there is no such proper weighting and hence f (G) [not member of] 1-2WEIGHT.

This concludes the proof of Theorem 1.1.

4 Concluding remarks

In this paper we showed that determining whether a graph has a proper weighting from either {0, 1} or {1, 2} is NP-complete. As a matter of fact, these two problems are not the same, in the sense that the corresponding families of graphs 0-1WEIGHT and 1-2WEIGHT are not equal. For example, the graph consisting only of one 2-edge gadget is in 1-2WEIGHT, as seen before, but it is easy to check that it is not in 0-1WEIGHT. Furthermore, we believe that our approach can be generalized to show that determining whether a graph has a proper weighting from {a, b} is NP-complete for any different rational numbers a and b. It is not clear if the same would hold for any two distinct irrational numbers.

Acknowledgements

We would like to thank Michal Karomki, who introduced us to the 1-2-3 conjecture. We are also very grateful to the referees for their detailed comments on an earlier version of this paper.

received 18th March 2010, revised 24th February 2011, accepted 26th October 2011.

References

L. Addario-Berry, K. Dalal, C. McDiarmid, B. A. Reed, and A. Thomason. Vertex-colouring edge-weightings. Combinatorica, 27(1):1-12, 2007. ISSN 0209-9683. doi: http://dx.doi.org/10.1007/ s00493-007-0041-6.

L. Addario-Berry, K. Dalal, and B. A. Reed. Degree constrained subgraphs. Discrete Appl. Math., 156(7):1168-1174, 2008. ISSN 0166-218X. doi: DOI:10.1016/j.dam.2007.05. 059. URL http://www.sciencedirect.com/science/article/B6TYW-4PT2FK1-1/ 2/f3371b3c9c874a20 0bf561073f921e12.

M. Kalkowski, M. Karomki, and F. Pfender. Vertex-coloring edge-weightings: Towards the 1-2-3-conjecture. J. Comb. Theory, Ser. B, 100(3):347-349, 2010.

M. Karoniski, T. Luczak, and A. Thomason. Edge weights and vertex colours. J. Combin. Theory Ser. B, 91:151-157, 2004.

T. Wang and Q. Yu. On vertex-coloring 13-edge-weighting. Front. Math. China, 3(4):581-587, 2008. ISSN 1673-3452 (Print) 1673-3576 (Online). doi: 10.1007/s11464-008-0041-x.

Andrzej Dudek (1), ([dagger]) and David Wajc (2), ([double dagger])

(1) Department of Mathematics, Western Michigan University, Kalamazoo, MI 49008, USA

(2) Computer Science Department, Technion Israel Institute of Technology, Haifa 32000, Israel

([dagger]) Email: andrzej.dudek@wmich.edu.

([double dagger]) Email: sdavidwa@cs.technion.ac.il This work was performed while the author was visiting Carnegie Mellon University.

1365-8050 [C] 2011 Discrete Mathematics and Theoretical Computer Science (DMTCS), Nancy, France
COPYRIGHT 2011 DMTCS
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2011 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Author:Dudek, Andrzej; Wajc, David
Publication:Discrete Mathematics and Theoretical Computer Science
Article Type:Report
Geographic Code:7ISRA
Date:Nov 1, 2011
Words:2710
Previous Article:On the book thickness of k-trees.
Next Article:Combinatorics, groups, algorithms, and complexity: conference in honor of Laci Babai's 60th birthday.
Topics:

Terms of use | Privacy policy | Copyright © 2019 Farlex, Inc. | Feedback | For webmasters