Top

Journal of Combinatorial Optimization

Published in:

01-07-2016

Complexity of domination, hamiltonicity and treewidth for tree convex bipartite graphs

Authors: Hao Chen, Zihan Lei, Tian Liu, Ziyang Tang, Chaoyi Wang, Ke Xu

Published in: Journal of Combinatorial Optimization | Issue 1/2016

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Tree convex bipartite graphs generalize convex bipartite graphs by associating a tree, instead of a path, with one set of the vertices, such that for every vertex in another set, the neighborhood of this vertex induces a subtree. There are seven graph problems, grouped into three classes of domination, Hamiltonicity and treewidth, which are known to be \(\mathcal {NP}\)-complete for bipartite graphs, but tractable for convex bipartite graphs. We show \(\mathcal {NP}\)-completeness of these problems for tree convex bipartite graphs, even when the associated trees are stars or combs respectively.

previous article Constrained pairwise and center-star sequences alignment problems

next article Improved approximation algorithm for maximum agreement forest of two rooted binary phylogenetic trees

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Arnborg S, Corneil DG, Proskurowski A (1987) Complexity of finding embeddings in a k-tree. SIAM J Algebr Discret Methods 8:277–284MathSciNetCrossRefMATH

Brandstäd A, Le VB, Spinrad JP (1999) Graph classes—a survey. Society for Industrial and Applied Mathematics, PhiladelphiaCrossRef

Chen L, Lu C, Zeng Z (2010) Labelling algorithms for paired-domination problems in block and interval graphs. J Comb Optim 19:457–470MathSciNetCrossRefMATH

Damaschke P, Muller H, Kratsch D (1990) Domination in convex and chordal bipartite graphs. Inform Proc Lett 36:231–236MathSciNetCrossRefMATH

Garey MR, Johnson DS (1979) Computers and intractability, a guide to the theory of NP-completeness. W.H. Freeman and Company, New YorkMATH

Golumbic MC, Goss CF (1978) Perfect elimination and chordal bipartite graphs. J Graph Theory 2:155–163MathSciNetCrossRefMATH

Golumbic MC (2004) Algorithmic graph theory and perfect graphs, Annals of discrete mathematics, vol 57, 2nd edn. Elsevier B.V., Amsterdam

Grover F (1967) Maximum matching in a convex bipartite graph. Nav Res Logist Q 14:313–316CrossRef

Hung R-W (2012) Linear-time algorithm for the paired-domination problem in convex bipartite graphs. Theory Comput Syst 50:721–738MathSciNetCrossRefMATH

Irving W (1991) On approximating the minimum independent dominating set. Inform Process Lett 37:197–200MathSciNetCrossRefMATH

Jiang W, Liu T, Ren T, Xu K (2011) Two hardness results on feedback vertex sets. Proceedings of FAW-AAIM 2011, pp 233–243

Jiang W, Liu T, Wang C, Xu K (2013) Feedback vertex sets on restricted bipartite graphs. Theory Comput Sci 507:41–51MathSciNetCrossRefMATH

Jiang W, Liu T, Xu K (2011) Tractable feedback vertex sets in restricted bipartite graphs. Proceedings of COCOA 2011, pp 424–434

Karp R (1972) Complexity of computer computations., Reducibility among combinatorial problemsPlenum Press, New York

Kloks T (1994) Treewidth: computations and approximations. Springer, BerlinCrossRefMATH

Kloks T, Kratsch D (1995) Treewidth of chordal bipartite graphs. J Algorithms 19:266–281MathSciNetCrossRefMATH

Kloks T, Liu CH, Pon SH (2011) Feedback vertex set on chordal bipartite graphs. arXiv:1104.3915

Kloks T,Wang YL (2013) Advances in graph slgorithms. Manuscript

Krishnamoorthy MS (1975) An NP-hard problem in bipartite graphs. SIGACT News 7(1):26MathSciNetCrossRef

Liang YD, Blum N (1995) Circular convex bipartite graphs: maximum matching and Hamiltonian circuits. Inf Process Lett 56:215–219MathSciNetCrossRefMATH

Liang YD, Chang MS (1997) Minimum feedback vertex sets in cocomparability graphs and convex bipartite graphs. Acta Informatica 34:337–346MathSciNetCrossRef

Liu T (2014) Restricted bipartite graphs: comparison and hardness results. Proceddings of AAIM, pp 241–252

Liu T, Lu Z, Xu K (2015) Tractable connected domination for restricted bipartite graphs. J Comb Optim 29:247–256MathSciNetCrossRefMATH

Lu M, Liu T, Xu K (2013) Independent domination: reductions from circular- and triad-convex bipartite graphs to convex bipartite graphs. Proceedings of FAW-AAIM, pp 142–152

Lu M, Liu T, Tong W, Lin G, Xu K (2014) Set cover, set packing and hitting set for tree convex and tree-like set systems. Proceedings of TAMC, pp 248–258

Liu T, Xu K (2015) Union-closed tree convex sets. Proceedings of FAW, to appear

Müller H (1996) Hamiltonian circuits in chordal bipartite graphs. Disc Math 156(1–3):291–298MathSciNetCrossRefMATH

Müller H, Brandstät A (1987) The NP-completeness of steiner tree and dominating set for chordal bipartite graphs. Theory Comput Sci 53(2–3):257–265MathSciNetCrossRefMATH

Panda BS, Prahan D (2013) Minimum paired-dominating set in chordal graphs and perfect elimination bipartite graphs. J Comb Optim 26:770–785MathSciNetCrossRefMATH

Pandey A, Panda BS (2015) Domination in some subclasses of bipartite graphs. Proceedings of CALDAM 2015, pp 169–180

Pfaff J, Laskar R, Hedetniemi ST (1983) NP-completeness of total and connected domination, and irredundance for bipartite graphs. Technical Report 428, Department Mathematical Sciences, Clemenson University

Song Y, Liu T, Xu K (2012) Independent domination on tree convex bipartite graphs. Proceedings of FAW-AAIM 2012, pp 129–138

Wang C, Liu T, Jiang W, Xu K (2012) Feedback vertex sets on tree convex bipartite graphs. Proceedings of COCOA 2012, pp 95–102

Yannakakis M (1981) Node-deletion problem on bipartite graphs. SIAM J Comput 10:310–327MathSciNetCrossRefMATH

Title: Complexity of domination, hamiltonicity and treewidth for tree convex bipartite graphs
Authors: Hao Chen
Zihan Lei
Tian Liu
Ziyang Tang
Chaoyi Wang
Ke Xu
Publication date: 01-07-2016
Publisher: Springer US
Published in: Journal of Combinatorial Optimization / Issue 1/2016
Print ISSN: 1382-6905
Electronic ISSN: 1573-2886
DOI: https://doi.org/10.1007/s10878-015-9917-3

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Other articles of this Issue 1/2016

Kernelization and randomized Parameterized algorithms for Co-path Set problem

Improved approximation algorithm for maximum agreement forest of two rooted binary phylogenetic trees

Algorithms for the workflow satisfiability problem engineered for counting constraints

Performances of pure random walk algorithms on constraint satisfaction problems with growing domains

Upper bounds for the total rainbow connection of graphs

Strong minimum energy hierarchical topology in wireless sensor networks

Premium Partner