SpringerLink
Log in

Not-All-Equal and 1-in-Degree Decompositions: Algorithmic Complexity and Applications

  • Published:
Algorithmica Aims and scope Submit manuscript

Abstract

A Not-All-Equal decomposition of a graph G is a decomposition of the vertices of G into two parts such that each vertex in G has at least one neighbor in each part. Also, a 1-in-Degree decomposition of a graph G is a decomposition of the vertices of G into two parts A and B such that each vertex in the graph G has exactly one neighbor in part A. Among our results, we show that for a given graph G, if G does not have any cycle of length congruent to 2 mod 4, then there is a polynomial time algorithm to decide whether G has a 1-in-Degree decomposition. In sharp contrast, we prove that for every r, \(r\ge 3\), for a given r-regular bipartite graph G determining whether G has a 1-in-Degree decomposition is \( \mathbf {NP} \)-complete. These complexity results have been especially useful in proving \( \mathbf {NP} \)-completeness of various graph related problems for restricted classes of graphs. In consequence of these results we show that for a given bipartite 3-regular graph G determining whether there is a vector in the null-space of the 0,1-adjacency matrix of G such that its entries belong to \(\{ \pm \, 1,\pm \,2\}\) is \(\mathbf {NP} \)-complete. Among other results, we introduce a new version of Planar 1-in-3 SAT and we prove that this version is also \( \mathbf {NP} \)-complete. In consequence of this result, we show that for a given planar (3, 4)-semiregular graph G determining whether there is a vector in the null-space of the 0,1-incidence matrix of G such that its entries belong to \(\{ \pm \,1,\pm \,2\}\) is \(\mathbf {NP} \)-complete.

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
EUR 32.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 includes VAT (Germany)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6

Similar content being viewed by others

References

  1. Akbari, S., Daemi, A., Hatami, O., Javanmard, A., Mehrabian, A.: Zero-sum flows in regular graphs. Gr. Comb. 26, 603–615 (2010)

    Article  MathSciNet  Google Scholar 

  2. Akbari, S., Ghareghani, N., Khosrovshahi, G.B., Mahmoody, A.: On zero-sum 6-flows of graphs. Linear Algebra Appl. 430(11–12), 3047–3052 (2009)

    Article  MathSciNet  Google Scholar 

  3. Alon, N., Berke, R., Buchin, K., Buchin, M., Csorba, P., Shannigrahi, S., Speckmann, B., Zumstein, P.: Polychromatic colorings of plane graphs. Discrete Comput. Geom. 42, 421–442 (2009)

    Article  MathSciNet  Google Scholar 

  4. Alon, N., Bregman, Z.: Every \(8\)-uniform \(8\)-regular hypergraph is \(2\)-colorable. Gr. Comb. 4(4), 303–305 (1988)

    Article  MathSciNet  Google Scholar 

  5. Bazgan, C., Tuza, Z., Vanderpooten, D.: The satisfactory partition problem. Discrete Appl. Math. 154(8), 1236–1245 (2006)

    Article  MathSciNet  Google Scholar 

  6. Bondy, J.A., Murty, U.S.R.: Introduction to Graph Theory. American Eisevier Publ. Co., New York (1976)

    MATH  Google Scholar 

  7. Bouchet, A.: Nowhere-zero integral flows on a bidirected graph. J. Comb. Theory Ser. B 34, 279–292 (1983)

    Article  MathSciNet  Google Scholar 

  8. Brandstädt, A., Fivcur, P., Leitert, A., Milaniv c, M.: Polynomial-time algorithms for weighted efficient domination problems in AT-free graphs and dually chordal graphs. Inf. Process. Lett. 115(2), 256–262 (2015)

    Article  MathSciNet  Google Scholar 

  9. Brandstädt, A., Leitert, A., Rautenbach, D.: Efficient dominating and edge dominating sets for graphs and hypergraphs. In: Chao, K.M., Hsu, T., Lee, D.T. (eds.) Algorithms and Computation. ISAAC 2012. Lecture Notes in Computer Science, vol. 7676, pp. 267–277. Springer, Berlin, Heidelberg (2012)

    Chapter  Google Scholar 

  10. Calkin, N., Dankelmann, P.: The domatic number of regular graphs. Ars Comb. 73, 247–255 (2004)

    MathSciNet  MATH  Google Scholar 

  11. Cattanéo, D., Perdrix, S.: The parameterized complexity of domination-type problems and application to linear codes. In: Gopal, T.V., Agrawal, M., Li, A., Cooper, S.B. (eds.) Theory and Applications of Models of Computation. TAMC 2014. Lecture Notes in Computer Science, vol. 8402, pp. 86–103. Springer, Cham (2014)

    Google Scholar 

  12. Choi, J.-O., Georges, J.P., Mauro, D.: On zero-sum \(\mathbb{Z}_k\)-magic labelings of 3-regular graphs. Gr. Comb. 29(3), 387–398 (2013)

    Article  Google Scholar 

  13. Choi, J.-O., Georges, J.P., Mauro, D.: Relating edge-coverings to the classification of Z2-magic graphs. Discrete Math. 312(9), 2938–2945 (2012)

    Article  MathSciNet  Google Scholar 

  14. Commoner, F.G.: A sufficient condition for a matrix to be totally unimodular. Networks 3, 351–365 (1973)

    Article  MathSciNet  Google Scholar 

  15. Cvetković, D.M., Gutman, I.M.: The algebraic multiplicity of the number zero in the spectrum of a bipartite graph. Mat. Vesn. 9(24), 141–150 (1972)

    MathSciNet  MATH  Google Scholar 

  16. Dehghan, A.: On strongly planar not-all-equal 3SAT. J. Comb. Optim. 32(3), 721–724 (2016)

    Article  MathSciNet  Google Scholar 

  17. Dehghan, A., Sadeghi, M.-R.: The complexity of the zero-sum 3-flows. Inf. Process. Lett. 115(2), 316–320 (2015)

    Article  MathSciNet  Google Scholar 

  18. Dehghan, A., Sadeghi, M.-R.: On the algorithmic complexity of zero-sum edge-coloring. Inf. Process. Lett. 116(11), 660–667 (2016)

    Article  MathSciNet  Google Scholar 

  19. Dehghan, A., Sadeghi, M.-R., Ahadi, A.: Algorithmic complexity of proper labeling problems. Theor. Comput. Sci. 495, 25–36 (2013)

    Article  MathSciNet  Google Scholar 

  20. Feder, T., Subi, C.: Maximum gap labelings of graphs. Inf. Process. Lett. 111(4), 169–173 (2011)

    Article  MathSciNet  Google Scholar 

  21. Feige, U., Halldórsson, M.M., Kortsarz, G., Srinivasan, A.: Approximating the domatic number. SIAM J. Comput. 32, 72–195 (2002)

    Article  MathSciNet  Google Scholar 

  22. Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of \(NP\)-Completeness. W. H. Freeman, San Francisco (1979)

    MATH  Google Scholar 

  23. Gerber, M.U., Kobler, D.: Algorithmic approach to the satisfactory graph partitioning problem. European J. Oper. Res. 125(2), 283–291 (2000). Combinatorial optimization (Copenhagen, 1998)

  24. Gerber, M.U., Kobler, D.: Algorithms for vertex-partitioning problems on graphs with fixed clique-width. Theor. Comput. Sci. 299(1–3), 719–734 (2003)

    Article  MathSciNet  Google Scholar 

  25. Golovach, P.A., Kratochvíl, J., Suchý, O.: Parameterized complexity of generalized domination problems. Discrete Appl. Math. 160(6), 780–792 (2012)

    Article  MathSciNet  Google Scholar 

  26. Hazama, Fumio: On the kernels of the incidence matrices of graphs. Discrete Math. 254(1), 165–174 (2002)

    Article  MathSciNet  Google Scholar 

  27. Heggernes, P., Telle, J.A.: Partitioning graphs into generalized dominating sets. Nord. J. Comput. 5, 128–142 (1998)

    MathSciNet  MATH  Google Scholar 

  28. Máčajová, E., Rollová, E.: Nowhere-zero flows on signed complete and complete bipartite graphs. J. Gr. Theory 78(2), 108–130 (2015)

    Article  MathSciNet  Google Scholar 

  29. Marino, M.C., Sciriha, I., Simić, S.K., Tošić, D.V.: More about singular line graphs of trees. Publ. Inst. Math. Nouv. Sér. 79(93), 1–12 (2006)

    Article  MathSciNet  Google Scholar 

  30. Moore, C., Robson, J.M.: Hard tiling problems with simple tiles. Discrete Comput. Geom. 26(4), 573–590 (2001)

    Article  MathSciNet  Google Scholar 

  31. Moret, B.M.: Planar NAE3SAT is in P. SIGACT News 19(2), 51–54 (1988)

    Article  Google Scholar 

  32. Mulzer, W., Rote, G.: Minimum-weight triangulation is NP-hard. J. ACM 55(2), 11 (2008)

    Article  MathSciNet  Google Scholar 

  33. Nath, M., Sarma, B.K.: On the null-spaces of acyclic and unicyclic singular graphs. Linear Algebra Appl. 427(1), 42–54 (2007)

    Article  MathSciNet  Google Scholar 

  34. Nemhauser, G.L., Wolsey, L.A.: Integer and Combinatorial Optimization. Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley, New York (1988)

    Book  Google Scholar 

  35. Sander, J.W., Sander, T.: On simply structured bases of tree kernels. AKCE J. Gr. Comb. 2(1), 45–56 (2005)

    MathSciNet  MATH  Google Scholar 

  36. Sander, J.W., Sander, T.: On the eigenvalues of distance powers of circuits. Linear Algebra Appl. 432(12), 3132–3140 (2010)

    Article  MathSciNet  Google Scholar 

  37. Sander, T.: On certain eigenspaces of cographs. Electron. J. Comb. 15(1):Research Paper 140, 8, (2008)

  38. Sander, T.: Sudoku graphs are integral. Electron. J. Comb. 16(1):Note 25, 7 (2009)

  39. Sander, T., Sander, J.W.: On simply structured kernel bases of unicyclic graphs. AKCE Int. J. Gr. Comb. 4(1), 61–82 (2007)

    MathSciNet  MATH  Google Scholar 

  40. Sander, T., Sander, J.W.: Tree decomposition by eigenvectors. Linear Algebra Appl. 430(1), 133–144 (2009)

    Article  MathSciNet  Google Scholar 

  41. Sarkis, G., Shahriari, S.: Zero-sum flows of the linear lattice. Finite Fields Appl. 31, 108–120 (2015)

    Article  MathSciNet  Google Scholar 

  42. Sciriha, I.: The two classes of singular line graphs of trees. Rend. Sem. Mat. Messina Ser. II, 5(21)(suppl.):167–180 (2000), 1999. 5th Workshop on Combinatorics (Messina, 1999)

  43. Shafique, K., Dutton, R.D.: Partitioning a graph into alliance free sets. Discrete Math. 309(10), 3102–3105 (2009)

    Article  MathSciNet  Google Scholar 

  44. Telle, J.A.: Complexity of domination-type problems in graphs. Nord. J. Comput. 1(1), 157–171 (1994)

    MathSciNet  Google Scholar 

  45. Thomassen, C.: Group flow, complex flow, unit vector flow, and the \((2+\epsilon )\)-flow conjecture. J. Comb. Theory Ser. B 108, 81–91 (2014)

    Article  MathSciNet  Google Scholar 

  46. Thomassen, Carsten: The even cycle problem for directed graphs. J. Am. Math. Soc. 5(2), 217–229 (1992)

    Article  MathSciNet  Google Scholar 

  47. Tutte, W.T.: A contribution to the theory of chromatic polynomials. Can. J. Math. 6, 80–91 (1954)

    Article  MathSciNet  Google Scholar 

  48. Villarreal, R.H.: Rees algebras of edge ideals. Commun. Algebra 23(9), 3513–3524 (1995)

    Article  MathSciNet  Google Scholar 

  49. Wang, T.-M., Hu, S.-W., Zhang, G.-H.: Zero-sum flow numbers of triangular grids. In: Frontiers in Algorithmics, pp. 264–275. Springer (2014)

  50. Wang, T.-M., Zhang, G.-H.: Zero-sum flow numbers of hexagonal grids. In: Fellows, M., Tan, X., Zhu, B. (eds.) Frontiers in Algorithmics and Algorithmic Aspects in Information and Management. Lecture Notes in Computer Science, vol. 7924, pp. 339–349. Springer, Berlin, Heidelberg (2013)

    Chapter  Google Scholar 

  51. Wang, T.-M., Hu, S.-W.: Constant sum flows in regular graphs. In: Atallah, M., Li, X.Y., Zhu, B. (eds.) Frontiers in Algorithmics and Algorithmic Aspects in Information and Management. Lecture Notes in Computer Science, vol. 6681, pp. 168–175. Springer, Berlin, Heidelberg (2011)

    Chapter  Google Scholar 

  52. Wang, T.-M., Hu, S.-W.: Zero-sum flow numbers of regular graphs. In: Lecture Notes in Computer Science, vol. 7285, pp. 269–278 (2012)

    Chapter  Google Scholar 

  53. Wang, X., Zhang, C.-Q., Zhang, T.: Nowhere-zero 4-flow in almost petersen-minor free graphs. Discrete Math. 309(5), 1025–1032 (2009)

    Article  MathSciNet  Google Scholar 

  54. Wei, E.L., Tang, W.L., Ye, D.: Nowhere-zero 15-flow in 3-edge-connected bidirected graphs. Acta Math. Sin. (Engl. Ser.) 30(4), 649–660 (2014)

    Article  MathSciNet  Google Scholar 

  55. West, Douglas B.: Introduction to Graph Theory. Prentice Hall Inc., Upper Saddle River (1996)

    MATH  Google Scholar 

  56. Yan, J.: Nowhere-zero 3-flows and \(\text{ z }_3\)-connectivity of a family of graphs. Discrete Math. 311(17), 1988–1994 (2011)

    Article  MathSciNet  Google Scholar 

  57. Zelinka, B.: Total domatic number and degrees of vertices of a graph. Math. Slov. 39, 7–11 (1989)

    MathSciNet  MATH  Google Scholar 

  58. Zhang, C.Q.: Nowhere-zero 4-flows and cycle double covers. Discrete Math. 154(1–3), 245–253 (1996)

    Article  MathSciNet  Google Scholar 

Download references

Acknowledgements

The authors would like to thank the anonymous referees for their useful comments which helped to improve the presentation of this paper.

Author information

Authors and Affiliations

  1. Department of Mathematics and Computer Science, Amirkabir University of Technology, Tehran, Iran

    Ali Dehghan & Mohammad-Reza Sadeghi

  2. Systems and Computer Engineering Department, Carleton University, Ottawa, Canada

    Ali Dehghan

  3. Department of Mathematical Sciences, Sharif University of Technology, Tehran, Iran

    Arash Ahadi

Authors
  1. Ali Dehghan
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Mohammad-Reza Sadeghi
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Arash Ahadi
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Mohammad-Reza Sadeghi.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Dehghan, A., Sadeghi, MR. & Ahadi, A. Not-All-Equal and 1-in-Degree Decompositions: Algorithmic Complexity and Applications. Algorithmica 80, 3704–3727 (2018). https://doi.org/10.1007/s00453-018-0412-y

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00453-018-0412-y

Keywords

Mathematics Subject Classification

Search

Navigation