下载文档原格式
DNA计算在求解NP—完全问题的应用【摘要】基于生化反应的DNA计算模型越来越受到关注。
DNA计算的研究已经成为一个热点。
本文主要介绍了DNA计算在一些NP-完全问题中的应用。
并分析了DNA模型存在的问题。
指出未来国内DNA计算研究的重点可以在三个方面：解的检测，降低空间复杂度，生化实验研究。
【关键词】DNA计算；NP-完全问题；最大团；最小顶点覆盖0 引言电子计算机的快速发展，在很大程度上促进了优化计算问题的解决。
但是，电子计算机运算速度不够快，存贮容量不够大。
而且随着现代社会科学技术的不断进步发展，许多新的复杂疑难问题在不断出现，如一些非线性问题和NP-完全问题，特别是在一些工程领域内，电子计算机很难满足计算机发展的需要，为了可以更好的解决这类问题，一种新型的计算方法被受人们关注，即DNA计算。
近些年来，DNA很受科学领域的关注。
它的进步之处不仅仅在于其存储量和运算速度的改善，更重要的是他开发了本身潜在的计算能力。
实践证明，DNA计算机在计算速度和存储容量等方面确实有很大的进展。
DNA计算的基本思想是：利用DNA特殊的双螺旋结构和碱基互补配对规律进行信息编码，把要运算的对象映射成DNA分子链，在生物酶的作用下，生成各种数据池，然后按照一定的规则将原始问题的数据运算高度并行地映射成DNA分子链的可控的生化过程。
最后，利用分子生物技术如聚合链反应PCR、超声波降解、亲和层分析、克隆、诱变、分子纯化、电泳、磁珠分离等，检测所需的运算结果。
最早的计算机模式是由Alderman 博士在1994首先提出的。
而后，对于DNA计算机领域的研究引起了各科学等领域研究者的广泛关注。
DNA 计算研究的最终目的是构造出具有巨大并行性的DNA计算机。
国内开始DNA 计算的研究始于1996年。
到目前为止，我国关于DNA计算的研究大致可以分为3个阶段，学习阶段、理论研究阶段、理论与实验研究阶段[1]。
自2001年开始，国内关于DNA计算的研究基本上已经转入理论研究阶段。
算法----NP-难度和NP-完全的问题1、确定的算法算法运算的结果都是唯⼀确定的, 这样的算法叫做确定的算法(deterministic algorithm) 。
如加减乘除2、不确定的算法允许算法每种运算的结果不是唯⼀确定的, ⽽是受限于某个特定的可能性集合。
执⾏这些运算的机器可以根据终⽌条件选择可能性集合中的⼀个作为结果。
这就引出了所谓不确定的算法( nondeterministic algorithm)。
如求下⼀个⼤质数3、不确定机式执⾏不确定算法的机器称为不确定机(nondeterministic machine ) 。
然⽽, 这⾥所定义的不确定机实际上是不存在的, 因此通过直觉可以感到这类问题不可能⽤“快速的”确定算法求解。
4、P问题（Polynomial多项式问题）P 是所有可在多项式时间内⽤确定算法求解的判定问题的集合。
5、NP问题（Non-Deterministic Polynomial, ⾮确定多项式）NP是所有可在多项式时间内⽤不确定算法求解的判定问题的集合。
有些问题很难找到多项式时间的算法（或许根本不存在），例如“找出⽆向图中”问题。
但如果给了该问题的⼀个答案，可以在多项式时间内判断这个答案是否正确。
例如说对于哈密顿回路问题，给⼀个任意的回路，很容易判断它是否是哈密顿回路（只要看是不是所有的顶点都在回路中就可以了）。
这⾥给出NP问题的另⼀个定义,这种可以在多项式时间内验证⼀个解是否正确的问题称为NP问题，亦称为验证问题类（布尔判断问题）。
6、约化令 L1 和L2 是两个问题, 如果有⼀确定的多项式时间算法求解L1 , ⽽这个算法使⽤了⼀个在多项式时间内求解L2 的确定算法,则称L1 约化为L2 ( 也可以写作L1 ∝L2 )。
7、NP-完全问题如果可满⾜性约化为⼀个问题L,则称此问题L是NP-难度的。
如果L是NP难度的且L∈NP, 则称问题L是NP-完全的。
⼀切NP-完全的问题都是NP-难度的问题, 但⼀切NP-难度的问题并不都是NP-完全的。
电子科技大学研究生算法设计与分析拟考题及答案评分细则（3）一、Please answer T or F for each of the following statements to indicate whether the statement is true or false1. The knapsack problem can be solved in polynomial time by using dynamic programming.( F )2. Some problems in NP can be solved in polynomial time.( T )3. To show a problem is NP-hard, we can reduce it to a well-known NP-Complete problem.( F )4. In an undirected graph, the value of the maximum flow between two vertices is equivalent to the value of the minimum cut between them. ( T )5. . ( F )二、Arrange the following functions in ascending asymptotic order of growth rate:，，，，.参考答案：f2，f3，f1，f4，f5三、Please answer the following questions:(a) What are the main steps of designing a dynamic programming algorithm?参考答案：1.定义子问题；2根据子问题建立递归关系式；3用自底而上的方式求解（建立储存表）。
(b) What are the main steps of proving the NP-Completeness of a problem?参考答案：1.证明该问题属于NP；2.选一个已知的NPC问题B；3.将问题B归约到该问题上。
SUBSET-SUM is NP-Complete•The SUBSET-SUM problem:–Instance: We are given a set S of positive integers, and atarget integer t.–Question: does there exist a subset of S adding up to t?•Example: {1, 3, 5, 17, 42, 391}, target 50–The subset sum problem is a good problem to use when proving NP-completeness for problems defined on sets of integers.–We will show that 3-SAT <P SUBSET-SUM.•So: We are given an arbitrary 3-SAT formula and we wish toderive a set S of integers and a target integer t.–Then we prove that 3-SAT is satisfiable iff a subset of S adds up to t.SUBSET-SUM3-SAT =P•Idea: we use “bit descriptions” that essentiallydescribe the construction of the 3-SAT formula.–The integers in S will be derived from this description.–As before, we assume that there are m Boolean variables and n clauses.–Our description uses bit fields that represent differentaspects of the 3-SAT formula: it has two lines for eachlogic variable:•One line specifies which clauses use the true version of avariable.•Another line describes which clauses use the false version ofthe variable.–We will get the numbers for S by considering the rows to be integers.–When adding the integers we do not want anycomplicating carry-over into the next column so we consider the entries to be numbers in a higher base.•A base corresponding to a three bit integer would do (an octal number) but for simplicity, each number is considered to be a base-10 digit.–The selection of the required subset from S will designate a subset of lines from the description. –This selection must be forced to choose either a Ti line or an F i line (not both) for each value of i .•This means that the target integer t will start with m 1’s.–What about the sums of entries in the columns for the clauses?•Looking at the description lines we see that the sum in a column could be 1, 2, or 3.•We want the target number to have a specific value so we append more lines (integers) to the array to give the selection mechanism a chance to get a subset with a specific target sum.–We will show that this does not destroy our ability to do anappropriate selection from the T i , F i rows.•For every clause column, we need two more integers: one with a 1 and another with a 2 in that column and 0 everywhere else •Make the target have a 4 in the digits for the clause columns.–Note: For any column, the nonzero digits in all integers add up to at most 6 (so our base-10 simplification will never see a carry-over).–Going back to our example:()()134124u u u u u u ∨¬∨¬∧¬∨∨¬123412112233441122100010100001010001010*********0010100001000001111000010200002010000012000002Target :111144u u u u c c T F T F T F T F S S S S •Suppose the formula were satisfiable:–We need to show that there is a subset of S with target sum t.–Choose integer from the Ti ,F i rows corresponding to true literals, giving sums of 1 in the literal-digit positions.–Using only the Ti ,F i rows, we get sums that are 1, 2, or 3 in the clause columns.–Choose appropriate “slack integers” (from the S1i and S2i rows to make those sums equal to 4).–The final sum matches the target in all digits, as required.•Suppose a set of integers sum to the target:–We need to show that we can get a satisfyingassignment of the given 3-SAT formula.–There must be exactly one integer (i.e. row) selectedfrom each pair of the T i,F i rows, or there is no way to get a 1 in the initial columns of the target.–The selection thus defines the obvious assignment tovariables, but is it a satisfying assignment?–For each clause, the “slack integers” in the chosen set can only add up to at most 3 in that clause column.–There must be at least one 1 contributed from someinteger corresponding to the T i,F i rows.–That corresponds to a true literal in that clause and the formula is satisfied.•Finishing our Proof that SUBSET-SUM is NP-Complete:–Since 3-SAT is NP-complete, we have justdemonstrated that SUBSET-SUM is NP-hard.–But is it in NP? Yes, because:•We have a certificate: the subset achieving the target sum.•A verification algorithm would verify that the numbersspecify a subset and furthermore that they add up to thetarget.–Finally:•SUBSET-SUM is NP-hard + SUBSET-SUM in NP èSUBSET-SUM is NP-complete.Coin-Changing is NP-Hard•Prove by reduction from SUBSET-SUM.–We want to prove:SUBSET-SUM <P COIN-CHANGING.–We are given an arbitrary instance of subset-sum:•s 1, s 2,…, s n and a target t .–We want to create a particular coin changing problem by specifying:•the number of coin denominations, the value of eachdenomination and a payout value S.–Recall that each coin can be used more than once in the payout.–Let M be equal to max{s 1, s 2,…, s n }.–For every number s i create two coins C i and N i :•We use a strategy that is similar to our previous proof, but most of the numbers in the array are in “base-2n” instead of base-10.•The first column is special and will work in base-2nM.•Intuition:–Choosing coin C i means putting s i into the subset.–Choosing coin N i means not putting s i into the subset.–Our payout value S will be the target sum t .–The column sums will be: t for the first column with 1 for all the others.122...2...2...........................0...1 000...1 0.....................i ni i i base nM base n base n base ns s s C s N −−−−–Show:•If there exists a subset with sum t then it is possible to payout the sum with <n coins.–Proof:•If s i is chosen then take coin C i, otherwise take coin N i.•So, the sum in the first column is t as required and all othercolumns sum to 1.–Show:•If it is possible to pay out the sum S with <n coins, then there exists a subset with sum t.–Proof:•Since there are <n coins, there is never a carry-over into anadjacent column (consider the base of the entries).•So from every pair C i, N i exactly one is chosen.–This is the only possibility that will ensure that the column sums areall ones after the first column.•We construct a subset of the s1, s2,…,s n as follows: s i isselected to be in the subset iff C i was chosen.–We will get a first column sum of t.–Since SUBSET-SUM is NP-complete and since we have just shown that SUBSET-SUM <P COIN-CHANGING we can deduce that COIN-CHANGING is NP-hard.–As a certificate we can use the set of coins paying out the sum.–For verification we could:•Check to verify that the certificate contains only valid coins.•Check that the number of coins is <n.•Check the sum.–So:•COIN-CHANGING is in NP.–Finally:•COIN-CHANGING is NP-complete.。
Equitable colorings of bounded treewidth graphsHans L.BodlaenderFedor V.Fomininstitute of information and computing sciences,utrecht university technical report UU-CS-2004-010www.cs.uu.nlEquitable colorings of bounded treewidth graphsHans L.Bodlaender∗Fedor V.Fomin†AbstractA proper coloring of a graph G is equitable if the sizes of any two color classesare differ by at most one.The related notion isℓ-bounded coloring where each of thecolor classes is of cardinality≤ℓ.We consider the problems to determine for a givengraph G(and a given integerℓ)whether G has an equitable(ℓ-bounded)coloring.We prove that both problems can be solved in polynomial time on graphs of boundedtreewidth.1IntroductionThere is a wide believe that almost every natural hard problem can be solved efficiently on graphs of bounded treewidth.Of course this is not true,a nice example is the bandwidth minimization problem which is NP hard even on trees of degree three[11,25].Another part of’folklore’in Graph Algorithms community is that if some(natural)problem can be solved in polynomial time on trees,one should be able to solve it in polynomial time on graphs of bounded treewidth.However,there are some striking and frustrating examples, like L(2,1)-coloring,when efficient algorithm for trees can be constructed[7]and nothing is known about the complexity of the problem on graphs of treewidth≥2.For more than ten years,equitable coloring andℓ-bounded coloring were also examples of such problems.Both problems can be solved in polynomial time on trees and forests[9,2,17],i.e. graphs of treewidth1and existence of a polynomial time algorithm for graphs of treewidth ≥2was an open question.In this paper we introduce thefirst polynomial time algorithm on graphs of bounded treewidth for both versions of coloring.Due to enormous exponents in the running our algorithm is mainly of theoretical interest.Our main technique is quite far from the standard dynamic programming on graphs of bounded treewidth.To convince the reader(and ourselves)that the standard dynamic programming approach is unlikely to implemented for equitable coloring on graphs of bounded treewidth,we prove that a pre-colored version of the problem is NP hard on graphs of treewidth1,i.e.forests.Themain idea behind our polynomial time algorithm is to use recent combinatorial results of Kostochka et al.[21]that allow us to handle graphs with’large’vertex degrees separately.Previous results.The equitable coloring problem has a long history.The cel-ebrated theorem of Hajnal&Szemer´e di[13]says that any graph G has an equitable k-coloring for k≥∆(G)+1.This bound is sharp.One of the direction of research in this field was in obtaining better upper bounds than∆(G)+1for special graph classes.See the survey[23]for a review of the results in thisfield.The coloring problem can be trivially reduced to equitable coloring problem and thus equitable coloring is NP hard.Polynomial time algorithms are known for split graphs[8]and trees[9].ℓ-bounded coloring has a number of applications.It is also known as the mutual exclusion scheduling problem(MES)which is the problem of scheduling unit-time tasks non-preemptively on m processors subject to constraints,represented by a graph G, so that tasks represented by adjacent vertices in G must run in disjoint time intervals.This problem arises in load balancing the parallel solution of partial differential equations by domain decomposition.(See[2,26]for more information.)Also the problems of this form have been studied in the Operations Research literature[3,22].Other applications are in scheduling in communication systems[15]and in constructing school timetables[19].Theℓ-bounded k-coloring problem can be solved in polynomial time on split graphs, complements of interval graphs[24,8],forests and in linear time on trees[2,17].This is almost all what is known on graph classes where theℓ-bounded coloring problem is efficiently solvable.When one of the parametersℓor k isfixed the situation is different. For example,forfixedℓor k the problem is solved on cographs[4,24]and forfixedℓon bipartite graphs[4,14]and line graphs[1].Forℓ=2the problem is equivalent to the maximum matching problem on the complement graphs and is polynomial.Notice that forfixedℓthe problem can be expressed in the counting monadic second-order logic and for graphs of bounded treewidth linear time algorithm forfixedℓcan be constructed[18]. Whenℓis notfixed(i.e.ℓis part of the input)even for trees the situation is not simple and the question on existence of a polynomial time algorithm on trees[14]was open for several years.The problem remains NP-complete on cographs,bipartite and interval graphs[4],on cocomparability graphs andfixedℓ≥3[24],on complements of line graphs andfixedℓ≥3 [10],and on permutation graphs andℓ≥6[16].For k=3the problem is NP-complete on bipartite graphs[4].Almost all NP-completeness results forℓ-bounded k-coloring for different graph classes mentioned above can also be obtained for equitable k-coloring by making use of the following observation.Proposition1.1.A graph G on n vertices isℓ-bounded k-colored if and only if the graph G′obtained from G by adding an independent set of sizeℓk−n is equitable k-colorable. Our contribution.A standard dynamic programming approach for the coloring prob-lem needs to keep O(w k n)entries,where w is the treewidth of a graph and k is the number2of colors.Since the chromatic number of a graph is at most w+1this implies that the clas-sical coloring problem can be solved in polynomial time on graphs of bounded treewidth. Clearly such a technique does not work for equitable coloring because the number of colors in an equitable coloring is not bounded by a function of treewidth.For exam-ple,a star on n vertices has treewidth1and it can not be equitable k-colored for any k<(n−1)/2.One of the indications that the complexity of equitable coloring for graphs of bounded treewidth can be different from’classical’is that by Proposition1.1 and[4],the problem is NP hard on cographs and thus on graphs of bounded clique-width. (Note that chromatic number is polynomial on graphs of bounded clique-width[20].) However,one of the properties of equitable colorings making our approach possible is the phenomena observedfirst by Bollob´a s&Guy[5]for trees:’Most’trees can be equitable 3-colored.In other words,for almost all trees the difference between the numbers of colors in equitable coloring is not’far’from the chromatic number.Recently Kostochka et al.[21]succeed to generalize Bollob´a s&Guy result for degenerated graphs and our main contribution—the proof that equitable coloring can be solved in polynomial time on graphs of bounded treewidth(Section3)—strongly uses this result.Very roughly,we use the results of Kostochka et al.to establish the threshold when the problem is trivially solved and when it become to be solvable in polynomial time by dynamic programming developed in Section2.In Section4we show that such an approach can not be extended to pre-colored equitable coloring by showing that the pre-colored version of the problem is NP hard on graphs of treewidth1,i.e.,forests.1.1DefinitionsWe denote by G=(V,E)afinite undirected and simple graph.We usually use n to denote the number of vertices in G.For every nonempty W⊆V,the subgraph of G induced by W is denoted by G[W].The maximum degree of G is∆(G):=max v∈V d G(v).A graph G is d-degenerate if each of its nonempty subgraphs has a vertex of degree at most d.A nonempty subset of vertices I⊆V is independent in G if no two of its elements are adjacent in G.Definition1.2.A tree decomposition of a graph G=(V,E)is a pair({X i|i∈I},T= (I,F)),with{X i|i∈I}a family of subsets of V and T a tree,such that • i∈I X i=V.•For all{v,w}∈E,there is an i∈I with v,w∈X i.•For all i0,i1,i2∈I:if i1is on the path from i0to i2in T,then X i0∩X i2⊆X i1.The width of tree decomposition({X i|i∈I},T=(I,F))is max i∈I|X i|−1.The treewidth of a graph G is the minimum width of a tree decomposition of G.Lemma1.3(Folklore).Every graph on n vertices and of treewidth≤w has at most wn edges.3A k-coloring of the vertices of a graph G=(V,E)is a partition A1,A2,...,A k of V into independent sets(in which some of the A j may be empty);the k sets A j are called the color classes of the k-coloring.The chromatic numberχ(G)is the minimum value k for which a k-coloring exists.A k-coloring A1,A2,...,A k isℓ-bounded if|A i|≤l,1≤i≤k.A k-coloring A1,A2,...,A k is equitable if for any i,j∈{1,2,...,k},|A i−A j|≤1. Theorem1.4([21]).Every n-vertex d-degenerate graph G is equitably k-colorable for any k≥max{62d,31d n}.n−∆(G)+12Covering by equitable independent sets.Let S⊆V be a set of vertices of a graph G=(V,E).We say that S can be covered by independent sets of sizes[n/k]if there is a set of subsets A i⊆V,i∈{1,2,...,p},p≤|S|, such that(i)For every i∈{1,2,...,p},A i is an independent set;(ii)For every i,j∈{1,2,...,p},i=j,A i∩A j=∅;(iii)For every i∈{1,2,...,p},either|A i|=⌈n/k⌉,or|A i|=⌊n/k⌋;(iv)S⊆∪1≤i≤p A i.Covering by independent sets is a natural generalization of equitable coloring:A graph G has equitable k-coloring if and only if V can be covered by independent sets of sizes [n/k].We use the following observations in our proof.Lemma2.1.Let S⊆V be a vertex subset of a graph G.(a)If S can not be covered by independent sets of sizes[n/k],the graph G is not equitablek-colorable;(b)If S can be covered by p independent sets A1,...,A p of sizes[n/k]and the graphG′=G[V−∪1≤i≤p A i]is equitable(k−p)-colorable,the graph G is equitable k-colorable.Let G be a graph of treewidth w.The next theorem implies that when the cardinality of S⊆V or the number k is at most f(w),where f is a function of w,the question if S can be covered by independent sets of sizes[n/k]can be answered in polynomial time.Because there are graphs that needΩ(n)colors in an equitable coloring,Theorem2.2does not imply directly that for graphs of bounded treewidth the equitable coloring problem can be solved in polynomial time.4Theorem2.2.Let G=(V,E)be an n-vertex graph of treewidth≤w,let S be a subset of V,and let k be an integer.One can eitherfind a covering of S by independent sets of sizes [n/k],or conclude that there is no such a covering in polynomial time when k is bounded by a constant,or when|S|is bounded by a constant.Proof.This can be shown using standard dynamic programming techniques for graphs of bounded treewidth.Note that we can check for a covering of at most min{k,|S|} independent sets of sizes[n/k].An algorithm comparable to those e.g.shown in[6,27], that also has different table entries/homomorphism classes when sets have different sizes solves the problem in polynomial time on graphs of bounded treewidth.3Bounded treewidthThe main result of this paper is the following theorem.Theorem3.1.Equitable k-colorability problem can be solved in polynomial time on graphs of bounded treewidth.Proof.Let G=(V,E)be a graph of treewidth w and let k be an integer.To determine if G has an equitable k-coloring,we consider the following cases.Case1.∆(G)≤n/2+1and k≥62w.Sincenmax0≤∆(G)≤n/2+1}n−∆(G)+1and by Corollary1.5,G is equitably k-colorable.Case2.∆(G)≤n/2+1and k≤62w.In this case,it follows from Theorem2.2that the question whether G has an equitably k-coloring can be solved in polynomial time.Case3.∆(G)>n/2+1.Let S⊂V be the set of vertices in G of degree≥n/2+2. By Lemma1.3,G has at most wn edges,so|S|≤4w.Thus by Theorem2.2,it can be checked in polynomial time whether S can be covered by independent sets of sizes[n/k]. If S cannot be covered,by part(a)of Lemma2.1,G has no equitable k-coloring.Let A i⊂V,i∈{1,2,...,p},p≤|S|,be an equitable covering of S by independent sets of sizes[n/k].We define a new graph G′=G[V−∪1≤i≤p A i].The maximum vertex degree in G′is at most n/2+1and the treewidth of G′is≤w.Graph G′hasn′=|V−∪1≤i≤p A i|≥n−p n k−1)>(1−4wLet k′=k−p.We need again case distinction. Case A.k′≥max{62w,31w n′n′−n/2}≥max{62w,31wn′n′−n/2}and k′<62w.Since p≤4w,we have that k=k′+p<66w.Then by Theorem2.2,the question whether G has an equitably k-coloring, can be solved in polynomial time.Case C.k′<max{62w,31w n′n′−n(1−4w2=31w2−4wk ≤4w31and1k ≥2727<72wand we conclude that k=k′+p≤76w.Again,by Theorem2.2the question if G has an equitably k-coloring,can be solved in polynomial time.By Proposition1.1,Theorem3.1implies directly that there is a polynomial time algo-rithm for theℓ-bounded coloring problem restricted to graphs of bounded treewidth. 4Equitable coloring with pre-coloringFor a graph G,a pre-coloring p of a subset V′⊂V in k colors is a mappingπ:V′→{1,2,...,p}.We say that a coloring A1,A2,...,A m of G extends the pre-coloringπif u∈Aπ(u)for every u∈V′.We consider the following problem:Equitable coloring with pre-coloring:For a given graph G,integer k and a given pre-coloringπof G,determine the smallest integer k for which there exists an equitable k-coloring of G extendingπ. Theorem4.1.Equitable coloring with pre-coloring is NP hard on forests.6Proof.We use a reduction from the problem3-partitionInstance:A set A of non-negative integers a1,...,a3m,and a bound B,suchthat for all i with1≤i≤3m,(B+1)/4<a i<B/2and 1≤i≤3m a i=mB.Question:Can A be partitioned into m disjoint sets A1,A2,...,A m such thata i∈A j a i=B for every j with1≤j≤m?3-partition is NP-complete in the strong sense(Problem SP15in Garey&Johnson[12]).Let the set A={a1,...,a3m}and the bound B be an instance of3-partition.We construct a forest G and pre-coloring of G such that G is equitable(m+1)-colorable if and only if A can be3-partitioned.For every i∈{1,2,...,m}we define the set N i={1,2,...,m}−{i}and pre-colored star S i as a star with one non-pre-colored central vertex v adjacent to m−1leaves which are pre-colored in all colors from N i.Thus vertex v can be colored only in color i or m+1. For every i∈{1,2,...,m}and j∈{1,2,...,3m},we define the pre-colored tree G i,j as a tree obtained by taking the disjoint union of a j+1pre-colored stars S i and by making the central vertex v of one of them to be adjacent to the central vertices of the others a j stars. We call the vertex v the central vertex of G i,j.Thus G i,j has m(a j+1)vertices;for every colorℓ∈N i there are(a j+1)vertices of G i,j pre-colored byℓ.Every(m+1)-coloring of G i,j either colors v in m+1and remaining a j non-pre-colored vertices in i,or it colors v in i and remaining a j non-pre-colored vertices in m+1.(See Fig.1.)134v134134134Figure1:Tree G i,j.Here a j=3,m=4,i=2and N2={1,3,4}.In any5-coloring of G i,j,either v should be colored by5and all its non pre-colored neighbors by2,or v should be colored by2and the neighbors by5.For every j∈{1,2,...,3m},we define a pre-colored tree G j as follows:We take the disjoint union of pre-colored trees G i,j,i∈{1,2,...,m},add one vertex c j adjacent to all central vertices of trees G i,j and add one leaf adjacent to c j pre-colored in m+1.Thus G j has m2(a j+1)+2vertices;for every colorℓ∈{1,2,...,m}−{i}there are(m−1)(a j+1) vertices of G j pre-colored byℓand there is1vertex pre-colored by m+1.Also in any coloring of G j vertex c j can not be colored in m+1.Thus for every(m+1)-coloring of G j the spectra of colors used on neighbors of c j does not contain all colors from{1,2,...,m}.7Finally,the forest G is the disjoint union of pre-colored trees G1,G2,...,G3m and independent set of cardinality3m(m−2)+B pre-colored in color m+1.Thus G has 1≤j≤3m m2(a j+1)+3(m−2)+B=m2(mB+3m)+3(m−2)+Bvertices.For every colorℓ∈{1,2,...,m}−{i}there are1≤j≤3m(m−1)(a j+1)=(m−1)(mB+3m)vertices of G pre-colored byℓand3m(m−1)+B vertex are pre-colored by m+1.Suppose that A can be partitioned into m disjoint sets A1,A2,...,A m such that a i∈A j a i=B.We define an extension of pre-coloring of G as follows.For everyfixed j∈{1,2,...,3m},we choose i such that a j∈A i.We color central vertex of G i,j in color m+1and the remaining noncolored a j vertices of G i,j in color i.In each graph Gℓ,j,ℓ=i, a j vertices are colored by m+1and one vertex byℓ.Also we color vertex c j with i.Thus in every graph G j on the set of non-pre-colored vertices color i is used a j+1times.Any colorℓ∈{1,2,...,m}−{i}is used one time and color m+1is useda j(m−1)+1times on non-pre-colored vertices.Thus in graph G the number of vertices colored by color ℓ∈{1,2,...,m}is1=(m−1)(mB+3m)+B+3m. (m−1)(mB+3m)+ a j∈Aℓ(a j+1)+{1≤j≤3m|a j∈Aℓ}The number of vertices colored in m+1is3m(m−2)+B+ 1≤j≤3m(a j(m−1)+1)=(m−1)(mB+3m)+B+3mand we conclude that the obtained coloring is equitable(m+1)-coloring.Suppose now that G is equitable(m+1)-colorable.The main observation here is that for every j∈{1,2,...,3m}at most a j(m−1)+1vertices of a graph G j are colored by m+1. (Otherwise coloring of central vertices of graphs G i,j,i∈{1,2,...,m},uses the whole spectra{1,2,...,m}thus leaving no space for color of c j.)If for some j∈{1,2,...,3m} less than a j(m−1)+1vertices of a graph G j are colored with color m+1then(the coloring is equitable)for some j′∈{1,2,...,3m}at least a j m vertices of graph G j′are colored by m+1,which is a contradiction.Thus we can conclude that for every j∈{1,2,...,3m}there is exactly one subgraph G i,j such that a j non-pre-colored vertices of G i,j are colored with i.For all other i′∈{1,2,...,m},i=i′,a j non-pre-colored vertices of G i′,j are colored with m+1.We defineA i={a j:a j non-pre-colored vertices of G i,j are colored with i}.8In G the number of vertices colored by color i∈{1,2,...,m}is1. (m−1)(mB+3m)+B+3m=(m−1)(mB+3m)+ a j∈A i(a j+1)+{1≤j≤3m|a j∈A i} Thus for every i∈{1,2,...,m}a j∈A i(a j+1)=Band A1,A2,...,A m is a3-partition of A.So we have a polynomial reduction from3-partition to equitable coloring with pre-coloring.As equitable coloring with pre-coloring trivially belongs to NP, we can conclude it is NP-complete.References[1]N.Alon,A note on the decomposition of graphs into isomorphic matchings,ActaMath.Hungar.,42(1983),pp.221–223.[2]B.S.Baker and E.G.Coffman,Jr.,Mutual exclusion scheduling,Theoret.Comput.Sci.,162(1996),pp.225–243.[3]J.Blazewicz,K.H.Ecker,E.Pesch,G.Schmidt,and J.Weglarz,Schedul-ing Computer and Manufacturing Processes,Springer,Berlin,2001.2nd ed.[4]H.L.Bodlaender and K.Jansen,Restrictions of graph partition problems.I,put.Sci.,148(1995),pp.93–109.[5]B.Bollob´a s and R.K.Guy,Equitable and proportional coloring of trees,J.Combin.Theory Ser.B,34(1983),pp.177–186.[6]R.B.Borie,Generation of polynomial-time algorithms for some optimization prob-lems on tree-decomposable graphs,Algorithmica,14(1995),pp.123–137.[7]G.J.Chang and D.Kuo,The L(2,1)-labeling problem on graphs,SIAM J.DiscreteMath.,9(1996),pp.309–316.[8]B.-L.Chen,M.-T.Ko,and K.-W.Lih,Equitable and m-bounded coloring of splitgraphs,in Combinatorics and computer science(Brest,1995),vol.1120of Lecture Notes in Comput.Sci.,Springer,Berlin,1996,pp.1–5.[9]B.-L.Chen and K.-W.Lih,Equitable coloring of trees,bin.Theory Ser.B,61(1994),pp.83–87.9[10]E.Cohen and M.Tarsi,NP-completeness of graph decomposition problems,J.Complexity,7(1991),pp.200–212.[11]M.R.Garey,R.L.Graham,D.S.Johnson,and D.E.Knuth,Complexityresults for bandwidth minimization,SIAM J.Appl.Math.,34(1978),pp.477–495.[12]M.R.Garey and D.S.Johnson,Computers and Intractability,A guide to thetheory of NP-completeness,W.H.Freeman and Co.,San Francisco,Calif.,1979. [13]A.Hajnal and E.Szemer´e di,Proof of a conjecture of P.Erd˝o s,in Combinatorialtheory and its applications,II(Proc.Colloq.,Balatonf¨u red,1969),North-Holland, Amsterdam,1970,pp.601–623.[14]P.Hansen,A.Hertz,and J.Kuplinsky,Bounded vertex colorings of graphs,Discrete Math.,111(1993),pp.305–312.Graph theory and combinatorics(Marseille-Luminy,1990).[15]S.Irani and V.Leung,Scheduling with conflicts,and applications to traffic signalcontrol,in Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms(Atlanta,GA,1996),New York,1996,ACM,pp.85–94.[16]K.Jansen,The mutual exclusion scheduling problem for permutation and compara-bility graphs,Information and Computation,180(2003),pp.71–81.[17]M.Jarvis and B.Zhou,Bounded vertex coloring of trees,Discrete Math.,232(2001),pp.145–151.[18]D.Kaller,A.Gupta,and T.Shermer,Theχt-coloring problem,in Symp.onTheoretical Aspects of Comp.Sc.,STACS’95(Munich,1995),vol.900of Lecture Notes in Comput.Sci.,Springer,Berlin,1995,pp.409–420.[19]F.Kitagawa and H.Ikeda,An existential problem of a weight-controlled subsetand its application to school timetable construction,Proceedings of the First Japan Conference on Graph Theory and Applications(Hakone,1986),Discrete Math.,72 (1988),pp.195–211.[20]D.Kobler and U.Rotics,Edge dominating set and colorings on graphs withfixedclique-width,Discrete Appl.Math.,126(2003),pp.197–221.[21]A.V.Kostochka,K.Nakprasit,and S.V.Pemmaraju,Coloring d-degenarategraphs equitable.Manuscript,2003.[22]J.Krarup and D.de Werra,Chromatic optimisation:limitations,objectives,uses,references,European J.Oper.Res.,11(1982),pp.1–19.[23]K.-W.Lih,The equitable coloring of graphs,in Handbook of Combinatorial Opti-mization,Vol.3,Kluwer Acad.Publ.,Boston,MA,1998,pp.543–566.10[24]Z.Lonc,On complexity of some chain and antichain partition problems,in Graph-theoretic concepts in computer science WG’91(Fischbachau,1991),vol.570of Lecture Notes in Comput.Sci.,Springer,Berlin,1992,pp.97–104.[25]B.Monien,The bandwidth minimization problem for caterpillars with hair length3is NP-complete,SIAM J.Algebraic Discrete Methods,7(1986),pp.505–512. [26]B.F.Smith,P.E.Bjørstad,and W.D.Gropp,Domain Decomposition.Paral-lel multilevel methods for elliptic partial differential equations,Cambridge University Press,Cambridge,1996.[27]J.A.Telle and A.Proskurowski,Algorithms for vertex partitioning problemson partial k-trees,SIAM J.Discrete Math.,10(1997),pp.529–550.11。
