[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

Parameterized Algorithms for Finding Square Roots

  • Published:
Algorithmica Aims and scope Submit manuscript

Abstract

We show that the following two problems are fixed-parameter tractable with parameter \(k\): testing whether a connected \(n\)-vertex graph with \(m\) edges has a square root with at most \(n-1+k\) edges and testing whether such a graph has a square root with at least \(m-k\) edges. Our first result implies that squares of graphs obtained from trees by adding at most \(k\) edges can be recognized in polynomial time for every fixed \(k\ge 0\); previously this result was known only for \(k=0\). Our second result is equivalent to stating that deciding whether a graph can be modified into a square root of itself by at most \(k\) edge deletions is fixed-parameter tractable with parameter \(k\).

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
£29.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 (United Kingdom)

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

Notes

  1. We restrict ourselves to connected graphs for simplicity. We may do this for the following reason. For disconnected \(n\)-vertex graphs with \(\ell \ge 2\) connected components the natural parameter is \(k=s-(n-\ell )\) instead of \(k=s-(n-1)\). Our FPT result for connected graphs immediately carries over to disconnected graphs if we choose as parameter \(k=s-(n-\ell )\) instead.

References

  1. Adamaszek, A., Adamaszek, M.: Uniqueness of graph square roots of girth six. Electron. J. Comb. 18, 139 (2011)

    MathSciNet  Google Scholar 

  2. Aingworth, D., Motwani, R., Harary, F.: The difference between a graph and its square. Utilitas Math. 54, 223–228 (1998)

    MathSciNet  MATH  Google Scholar 

  3. Alon, N., Gutin, G., Kim, E.J., Szeider, S., Yeo, A.: Solving max- r-sat above a tight lower bound. Algorithmica 61, 638–655 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  4. Cochefert, M., Couturier, J.-F., Golovach, P.A., Kratsch, D., Paulusma, D.: Sparse square roots. In: WG, Lecture Notes Computer Science, vol. 8165. Springer, pp. 177–188 (2013)

  5. Diestel, R.: Graph Theory, Graduate Texts in Mathematics, vol. 173, 4th edn. Springer, Heidelberg (2010)

    Google Scholar 

  6. Downey, R.G., Fellows, M.R.: Fundamentals of Parameterized Complexity, Texts in Computer Science. Springer, (2013)

    Book  Google Scholar 

  7. Farzad, B., Karimi, M.: Square-root finding problem in graphs, a complete dichotomy theorem. CoRR, abs/1210.7684 (2012)

  8. Farzad, B., Lau, L.C., Le, V.B., Tuy, N.N.: Complexity of finding graph roots with girth conditions. Algorithmica 62, 38–53 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  9. Flum, J., Grohe, M.: Parameterized Complexity Theory, Texts in Theoretical Computer Science. An EATCS Series. Springer, Berlin (2006)

    Google Scholar 

  10. Lau, L.C.: Bipartite roots of graphs. ACM Trans. Algorithms 2, 178–208 (2006)

    Article  MathSciNet  Google Scholar 

  11. Lau, L.C., Corneil, D.G.: Recognizing powers of proper interval, split, and chordal graph. SIAM J. Discrete Math. 18, 83–102 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  12. Le, V.B., Oversberg, A., Schaudt, O.: Polynomial time recognition of squares of ptolemaic graphs and 3-sun-free split graphs. CoRR, abs/1402.0024 (2014)

  13. Le, V.B., Tuy, N.N.: The square of a block graph. Discrete Math. 310, 734–741 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  14. Le, V.B., Tuy, N.N.: A good characterization of squares of strongly chordal split graphs. Inf. Process. Lett. 111, 120–123 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  15. Lin, Y.-L., Skiena, S.: Algorithms for square roots of graphs. SIAM J. Discrete Math. 8, 99–118 (1995)

    Article  MathSciNet  MATH  Google Scholar 

  16. Milanic, M., Schaudt, O.: Computing square roots of trivially perfect and threshold graphs. Discrete Appl. Math. 161, 1538–1545 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  17. Moon, J.W., Moser, L.: On cliques in graphs. Israel J. Math. 3, 23–28 (1965)

    Article  MathSciNet  MATH  Google Scholar 

  18. Motwani, R., Sudan, M.: Computing roots of graphs is hard. Discrete Appl. Math. 54, 81–88 (1994)

    Article  MathSciNet  MATH  Google Scholar 

  19. Mukhopadhyay, A.: The square root of a graph. J. Comb. Theory 2, 290–295 (1967)

    Article  MATH  Google Scholar 

  20. Niedermeier, R.: Invitation to Fixed-Parameter Algorithms, Oxford Lecture Series in Mathematics and its Applications, vol. 31. Oxford University Press, Oxford (2006)

    Book  Google Scholar 

  21. Ross, I.C., Harary, F.: The square of a tree. Bell Syst. Tech. J. 39, 641–647 (1960)

    Article  MathSciNet  Google Scholar 

  22. Tsukiyama, S., Ide, M., Ariyoshi, H., Shirakawa, I.: A new algorithm for generating all the maximal independent sets. SIAM J. Comput. 6, 505–517 (1977)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Acknowledgments

We would like to thank two anonymous reviewers for a number of helpful comments that improved our presentation.

Author information

Authors and Affiliations

  1. Laboratoire d’Informatique Théorique et Appliquée, Université de Lorraine, 57045, Metz Cedex 01, France

    Manfred Cochefert & Dieter Kratsch

  2. CReSTIC, Université de Reims Champagne-Ardenne, 7 Boulevard Jean Delautre, 08005, Charleville-Méziéres, France

    Jean-François Couturier

  3. Department of Informatics, University of Bergen, PB 7803, 5020, Bergen, Norway

    Petr A. Golovach

  4. Science Laboratories, School of Engineering and Computing Sciences, Durham University, South Road, Durham, DH1 3LE, UK

    Daniël Paulusma

Authors
  1. Manfred Cochefert
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Jean-François Couturier
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Petr A. Golovach
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Dieter Kratsch
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Daniël Paulusma
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Petr A. Golovach.

Additional information

The research leading to these results has received funding from the European Research Council under the European Union’s Seventh Framework Programme (FP/2007-2013)/ERC Grant Agreement no. 267959. The research also has been supported by EPSRC (EP/G043434/1) and ANR Blanc AGAPE (ANR-09-BLAN-0159-03). A preliminary version of this paper appeared as an extended abstract in the proceedings of WG 2013 [4].

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Cochefert, M., Couturier, JF., Golovach, P.A. et al. Parameterized Algorithms for Finding Square Roots. Algorithmica 74, 602–629 (2016). https://doi.org/10.1007/s00453-014-9967-4

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00453-014-9967-4

Keywords

Search

Navigation