特殊图的图修正问题研究综述

doi:10.11896/j.issn.1002-137X.2018.03.002

摘要/Abstract

摘要： 图修正问题是指在一个图中进行删除点、删除边或加边操作,使这个图转变成另一个具有某种特殊性质的图。图修正问题一直被广泛研究,尤其对弦图、区间图以及单位区间图的图修正问题的研究更是如此。弦图是完美图中最重要的一类图,也是(单位)区间图的父类图,很多经典的NP难问题在弦图上都是多项式可解的。区间图以及单位区间图在生物计算上有着广泛的应用。对这几类图的图修正问题的研究对计算机理论和实践有很大的贡献。首先介绍并总结了关于弦图、区间图以及单位区间图的图修正问题的重要算法和技术,然后对这些问题的研究现状进行分析,并提出了今后研究中值得关注的问题。

关键词: 图修正问题,弦图,区间图,单位区间图

Abstract: Graph modification problems refer to deleting or adding edges or vertices in a graph to make a graph transform to another graph with a certain property.Graph modification problems have been widely studied for many years,especially on chordal graphs,interval graphs and unit interval graphs.Chordal graphs are the most important perfect graph class and supersets of (unit) interval graphs.There are many NP-hard problems which can be solved in polynomialtime on chordal graphs.Interval graphs and unit interval graphs have momentous application on computational biology.Research on graph modification problems of these graphs make a great contribution to both computer theory and applications.This survey first summarized important results for the graph modification problems on chordal graph,interval graph and unit interval graphs,then analyzed these problems,and provided some open problems to be worth studying.

Key words: Graph modification,Chordal graph,Interval graph,Unit interval graph

柯玉平,王建新. 特殊图的图修正问题研究综述[J]. 计算机科学, 2018, 45(3): 9-15. https://doi.org/10.11896/j.issn.1002-137X.2018.03.002

KE Yu-ping and WANG Jian-xin. Survey of Graph Modification Problems Related to Specific Graphs[J]. Computer Science, 2018, 45(3): 9-15. https://doi.org/10.11896/j.issn.1002-137X.2018.03.002

参考文献

[1] BODLAENDER H L,FLUITER B.On intervalizing k-coloredgraphs for DNA physical mapping[J].Discrete Applied Mathematics,1996,71(1):55-77.
[2] GOLUMBIC M C,KAPLAN H,SHAMIR R.On the complexity of DNA physical mapping[J].Advances in Applied Mathema-tics,1994,15(3):251-261.
[3] ROSE D J.A graph-theoretic study of the numerical solution of sparse positive definite systems of linear equations[C]∥Graph theory and Computing.1972:183-217.
[4] BAR-NOY A,BAR-YEHUDA R,FREUND A,et al.A unified approach to approximating resource allocation and scheduling[J].Journal of the ACM,2001,48(5):1069-1090.
[5] KRISHNAMOORTHY M S,DEO N.Node-deletion NP-com-plete problems[J].SIAM Journal on Computing,1979,8(4):619-625.
[6] LEWIS J M.On the complexity of the maximum subgraph prob-lem[C]∥Proceedings of the Tenth Annual ACM Symposium on Theory of Computing.ACM,1978:265-274.
[7] YANNAKAKIS M.Node-and edge-deletion NP-complete problems[C]∥Proceedings of the Tenth Annual ACM Symposium on Theory of Computing.ACM,1978:253-264.
[8] LEWIS J M,YANNAKAKIS M.The node-deletion problem for hereditary properties is NP-complete[J].Journal of Computer and SystemSciences,1980,20(2):219-230.
[9] YANNAKAKIS M.Computing the minimum fill-in is NP-complete[J].SIAM Journal on Algebraic Discrete Methods,1981,2(1):77-79.
[10] BURZYN P,BONOMO F,DURN G.NP-completeness results for edge modificationproblems[J].Discrete Applied Mathema-tics,2006,154(13):1824-1844.
[11] NATANZON A,SHAMIR R,SHARAN R.Complexity classification of some edge modificationproblems[J].Discrete Applied Mathematics,2001,113(1):109-128.
[12] DOWNEY R G,FELLOWS M R.Fixed-parameter tractability and completeness[C]∥Complexity Theory:Current Research,Dagstubl Workshop(DBLP).1992:191-225.
[13] DOWNEY R G,FELLOWS M R.Fixed-parameter tractability and completeness II:Oncompleteness for W [1][J].Theoretical Computer Science,1995,141(1):109-131.
[14] CHEN J N,KANJ I A,JIA W J.Vertex cover:further observations and further improvements[J].Journal of Algorithms,2001,41(2):280-301.
[15] TARJAN R E,TROJANOWSKI A E.Finding a maximum independent set[J].SIAM Journal on Computing,1977,6(3):537-546.
[16] ABRAHAMSON K A,DOWNEY R G,FELLOWS M R.Fixed-parameter intractability II[C]∥Annual Symposium on Theore-tical Aspects of Computer Science.Springer,1993:374-385.
[17] MCGEER P C,BRAYTON R K.Efficient algorithms for computing the longest viable pathin a combinational network[C]∥Proceedings of the 26th ACM/IEEE Design Automation Confe-rence.ACM,1989:561-567.
[18] CHEN J N,FOMIN F V,LIU Y,et al.Improved algorithms forfeedback vertex set problems[J].Journal of Computer and System Sciences,2008,74(7):1188-1198.
[19] DEHNE F,FELLOWS M,LANGSTON M,et al.An FPT algorithm for the undirected feedback vertex set problem[J].Theory of ComputingSystems,2007,41(3):479-492.
[20] GUO J,GRAMM J,HFFNER F,et al.Compression basedfixed-parameter algorithms for feedback vertex set and edge bipartization[J].Journal of Computer and System Sciences,2006,72(8):1386-1396.
[21] CAI L Z.Fixed-parameter tractability of graph modificationproblems for hereditary properties[J].Information Processing Letters,1996,58(4):171-176.
[22] MARX D.Chordal deletion is fixed-parameter tractable[J].Algorithmica,2010,57(4):747-768.
[23] CHEN J N,FOMIN F V,LIU Y,et al.Improved algorithms forfeedback vertex set problems[J].Journal of Computer and System Sciences,2008,74(7):1188-1198.
[24] CAO Y X,MARX D.Interval deletion is fixed-parameter tractable[J].ACM Transactions on Algorithms (TALG),2015,11(3):21.
[25] CAO Y X.Linear recognition of almost interval graphs[C]∥Proceedings of the Twenty-Seventh AnnualACM-SIAM Symposium on Discrete Algorithms.SIAM,2016:1096-1115.
[26] VILLANGER Y,HEGGERNES P,CHRISTOPHE P,et al.Interval completion is fixedparameter tractable[J].SIAM Journal on Computing,2009,38(5):2007-2020.
[27] BEVERN R,KOMUSIEWICZ C,HANNES M,et al.Measuring indifference:Unit interval vertex deletion[C]∥International Workshop on Graph-Theoretic Concepts in Computer Science.Springer,2010:232-243.
[28] CAO Y X.Unit interval editing is fixed-parameter tractable[M]∥Automata,Languages,and Programming.Springer,2015:306-317.
[29] KAPLAN H,SHAMIR R,TARJAN R E.Tractability of parameterized completion problemson chordal,strongly chordal,and proper interval graphs[J].SIAM Journal on Computing,1999,28(5):1906-1922.
[30] ROSE D J,TARJAN R E,LUEKER G S.Algorithmic aspects of vertex eliminationon graphs[J].SIAM Journal on Computing,1976,5(2):266-283.
[31] FULKERSON D,GROSS O.Incidence matrices and intervalgraphs[J].Pacific Journal of Mathematics,1965,15(3):835-855.
[32] DIRAC G A.On rigid circuit graphs[J].Abhandlungen Aus Dem Mathematischen Seminarder Universitt Hamburg,1961,25(1/2):71-76.
[33] CHAITIN G J.Register allocation & spilling via graph coloring[C]∥Sigplan Symposium on Computer Construction.ACM,1982:98-105.
[34] ROBERTSON N,SEYMOUR P D.Graph minors.III.planartree-width[J].Journal of Combinatorial Theory,Series B,1984,36(1):49-64.
[35] COURCELLE B.Graph rewriting:An algebraic and logic approach[M]∥Handbook of Theoretical Computer Science .1990:193-242.
[36] REED B,SMITH K,VETTA A.Finding odd cycle transversals[J].Operations Research Letters,2004,32(4):299-301.
[37] DOM M,GUO J,HFFNER F,et al.Fixed-parameter tract ability results for feedback set problems in tournaments[C]∥Italian Conference on Algorithms and Complexity.Springer,2006:320-331.
[38] GEORGE A,LIU J W.Computer solution of large sparse positive definite[M]∥ Computer Solution of Large Sparse Positive Definite Systems.Prentice-Hall,1981:1-177.
[39] PARTER S.The use of linear graphs in gauss elimination[J].SIAM Review,1961,3(2):119-130.
[40] OHTSUKI T,CHEUNGLAP K,FUJISAWA T.Minimal triangulation of a graph and optimalpivoting order in a sparse matrix[J].Journal of Mathematical Analysis and Applications,1976,54(3):622-633.
[41] BEERI C,FAGIN R,MAIER D,et al.On the desirability of acy-clicdatabase schemes[J].Journal of the ACM (JACM),1983,30(3):479-513.
[42] LAURITZEN S L,SPIEGELHALTER D J.Local computations with probabilities on graphicalstructures and their application to expert systems[J].Journal of the Royal Statistical Society.Series B (Methodological),1988,50(2):157-224.
[43] BODLAENDER H L,HEGGERNES P,VILLANGER Y.Faster parameterized algorithms forminimum fill-in[J].Algorithmica,2011,61(4):817-838.
[44] FOMIN F V,VILLANGER Y.Subexponential parameterizedalgorithm for minimum fill-in[J].SIAM Journal on Computing,2013,42(6):2197-2216.
[45] LEKKERKERKER C,BOLAND J.Representation of a finitegraph by a set of intervals on the realline[J].Fundamenta Mathematicae,1962,51(1):45-64.
[46] OLARIU S.An optimal greedy heuristic to color interval graphs[J].Information Processing Letters,1991,37(1):21-25.
[47] GILMORE P C,HOFFMAN A J.A characterization of comparability graphs and of interval graphs[J].Canadian Journal of Mathematics,2015,6(2):539-548.
[48] BRANDSTDT A,SPINRAD J P,LE V B.Graph classes:Asurvey[M].Philadelphia,1999:50-134.
[49] BENZER S.On the topology of the genetic fine structure[J].Proceedings of the National Academy of Sciences,1959,45(11):1607-1620.
[50] HAJS G.Ubereine art von graphen[J].International Mathe-matische Nachrichten,1957,11(3):11-65.
[51] BOOTH K S,LUEKER G S.Testing for the consecutive ones property,interval graphs,and graph planarity using PQ-tree algorithms[J].Journal of Computer and System Sciences,1976, 13(3):335-379.
[52] HABIB M,MCCONNELL R,PAUL C,et al.Lex-BFS and partition refinement,with applications to transitive orientation,interval graph recognition and consecutiveones testing[J].Theoretical Computer Science,2000,234(1):59-84.
[53] BERTSEKASD P,TSITSIKLIS J N.Neuro-dynamic progra-mming:an overview[C]∥Proceedings of the 34th IEEE Conference on Decisionand Control.1995:560-564.
[54] GALLAI.Transitiv orientierbare graphen[J].Acta Mathematica Hungarica,1967,18(1/2):25-66.
[55] GOLDBERG P W,GOLUMBIC M C,KAPLAN H,et al.Four strikes against physicalmapping of DNA[J].Journal of Computational Biology,1995,2(1):139-152.
[56] TARJAN R E.Graph theory and Gaussian elimination[M]∥Sparse Matrix Computations.1975:3-22.
[57] PENG H L,CHEN H K.On the interval completion of chordal graphs[J].Discrete Applied Mathematics,2006,154(6):1003-1010.
[58] BODLAENDER H L,KLOKS T,KRATSCH D.Treewidth and pathwidth of permutationgraphs[J].SIAM Journal on Discrete Mathematics,1995,8(4):606-616.
[59] SERNA M J,THILIKOSD M.Parameterized complexity forgraph layout problems[J].Bulletin of the EATCS,2005,86(41-65):272.
[60] VAN ’T HOF P,VILLANGER Y.Proper interval vertex deletion[J].Algorithmica,2013,65(4):845-867.
[61] GUTIN G,SZEIDER S,YEO A.Fixed-parameter complexity of minimum profileproblems[J].Algorithmica,2008,52(2):133-152.
[62] HEGGERNES P,PAUL C,TELLE J A,et al.Interval completion with fewedges[C]∥Proceedings of the Thirty-ninth Annual ACM Symposium on Theory of Computing.ACM,2007:374-381.
[63] BLIZNETS I,FOMIN F V,PILIPCZUK M,et al.Subexponential parameterizedalgorithm for interval completion[C]∥Proceedings of the Twenty-Seventh Annual ACM-SIAM Sympo-sium on Discrete Algorithms.SIAM,2016:1116-1131.
[64] ROBERTS F S.“Indifference graphs”.Proof techniques in graphtheory[C]∥Proceedings Second Ann Arbor Graph Theory Conference.1969:139-146.
[65] BOGART K P,WEST D B.A short proof that ‘proper= unit’[J].Discrete Mathematics,1999,201(1):21-23.
[66] WEGNER G.Eigenschaften der Nerven homologisch einfacher Familien in Rn[D].Dissertation,Gttingen,1967.
[67] ROSE D J,TARJANENDRE R,LUEKER G S.Algorithmic aspects of vertex eliminationon graphs[J].SIAM Journal on Computing,1976,5(2):266-283.
[68] BERTOSSI A A.Finding hamiltonian circuits in proper interval graphs[J].Information Processing Letters,1983,17(2):97-101.
[69] BLIZNETS I,FOMIN F V,PILIPCZUK M,et al.A subexponential parameterizedalgorithm for proper interval completion[C]∥European Symposium on Algorithms.Springer,2014:173-184.
[70] BESSY S,PEREZ A.Polynomial kernels for proper intervalcompletion and relatedproblems[C]∥International Symposium on Fundamentals of Computation Theory.Springer,2011:229-239.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed