Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

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

  • Published:
Journal of Combinatorial Optimization Aims and scope Submit manuscript

    We’re sorry, something doesn't seem to be working properly.

    Please try refreshing the page. If that doesn't work, please contact support so we can address the problem.

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9

Similar content being viewed by others

References

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

    Article  MathSciNet  MATH  Google Scholar 

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

    Book  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

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

    MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  • 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–316

    Article  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  • 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–51

    Article  MathSciNet  MATH  Google Scholar 

  • 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

    Google Scholar 

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

    Book  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  • 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):26

    Article  MathSciNet  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  Google Scholar 

  • 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–256

    Article  MathSciNet  MATH  Google Scholar 

  • 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–298

    Article  MathSciNet  MATH  Google Scholar 

  • 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–265

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  • 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–327

    Article  MathSciNet  MATH  Google Scholar 

Download references

Acknowledgments

This work was first presented at FAW 2014. The help of previous anonymous reviewers has improved our presentation greatly. The work of T. Liu was partially done during the program of Collective Dynamics in Information Systems (2014) in Kavli Institute for Theoretical Physics China at the Chinese Academy of Sciences. Partially supported by Natural Science Foundation of China (Grant Nos. 61370052 and 61370156).

Author information

Authors and Affiliations

  1. Key Laboratory of High Confidence Software Technologies, Ministry of Education, School of Electronic Engineering and Computer Science, Peking University, Beijing, 100871, China

    Hao Chen, Tian Liu, Ziyang Tang & Chaoyi Wang

  2. School of Mathematical Science, Peking University, Beijing, 100871, China

    Zihan Lei

  3. National Lab of Software Development Environment, Beihang University, Beijing, 100191, China

    Ke Xu

Authors
  1. Hao Chen
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Zihan Lei
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Tian Liu
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Ziyang Tang
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Chaoyi Wang
    View author publications

    You can also search for this author in PubMed Google Scholar

  6. Ke Xu
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding authors

Correspondence to Tian Liu or Ke Xu.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Chen, H., Lei, Z., Liu, T. et al. Complexity of domination, hamiltonicity and treewidth for tree convex bipartite graphs. J Comb Optim 32, 95–110 (2016). https://doi.org/10.1007/s10878-015-9917-3

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10878-015-9917-3

Keywords

Search

Navigation