Skip to main content
SpringerLink
Log in

The lexicographically first maximal subgraph problems:P-completeness andNC algorithms

  • Published:
Mathematical systems theory Aims and scope Submit manuscript

Abstract

The lexicographically first maximal (lfm) subgraph problem for a property π is to compute the lfm vertex set whose induced subgraph satisfies π. The main contribution of this paper is theP-completeness of the lfm subgraph problem for any nontrivial hereditary property. We also observe that most of the lfm subgraph problems are stillP-complete even if the instances are restricted to graphs with degree 3. However, some exceptions are found. For example, it is shown that the lfm 4-cycle free subgraph problem is inNC 2 for graphs with degree 3 but turns out to beP-complete for graphs with degree 4. Further, we analyze the complexity of the lfmedge-induced subgraph problem for some graph properties and show that it has a different complexity feature.

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

Access this article

Log in via an institution

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

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. R. Anderson and E. W. Mayr, Parallelism and greedy algorithms, STAN-CS-84-1003, April 1984.

  2. R. Anderson and E. W. Mayr, Parallelism and the maximal path problem,Inform. Process. Lett.,24 (1987), 121–126.

    Google Scholar 

  3. T. Asano and T. Hirata, Edge-deletion and edge-contraction problems,Proc. 14th ACM STOC, 1982, pp. 245–254.

  4. J. Avenhaus and K. Madlener, The Nielsen reduction andP-complete problems in free groups,Theoret. Comput. Sci.,32 (1984), 61–74.

    Google Scholar 

  5. K. S. Booth and G. S. Leuker, Testing for the consecutive ones property, interval graphs, and graph planarity usingPQ-tree algorithms,J. Comput. System Sci.,13 (1976), 335–379.

    Google Scholar 

  6. G. Chartrand and F. Harary, Planar permutation graphs,Ann. Inst. Henri Poincaré,4 (1967), 433–438.

    Google Scholar 

  7. S. A. Cook, An observation on time-storage trade off,J. Comput. System Sci.,9 (1974), 308–316.

    Google Scholar 

  8. S. A. Cook, A taxonomy of problems with fast parallel algorithms,Inform. and Control,64 (1985), 2–22.

    Google Scholar 

  9. D. Dobkin, R. J. Lipton, and S. Reiss, Linear programming is log-space hard forP, Inform. Process. Lett.,8 (1979), 96–97.

    Google Scholar 

  10. M. T. Garey and D. S. Johnson, The rectilinear Steiner tree problem isNP-complete,SIAM J. Appl. Math.,32 (1977), 826–834.

    Google Scholar 

  11. L. M. Goldschlager, The monotone and planar circuit value problems are log space complete forP, SIGACT News,9 (1977), 25–29.

    Google Scholar 

  12. L. M. Goldschlager, R. E. Shaw, and J. Staples, The maximum flow problem is log-space complete forP, Theoret. Comput. Sci.,21 (1982), 105–111.

    Google Scholar 

  13. F. Harary,Graph Theory, Addison-Wesley, Reading, MA, 1970.

    Google Scholar 

  14. J. E. Hopcroft and R. E. Tarjan, Efficient planarity testing,J. Assoc. Comput. Mach.,21 (1974), 549–568.

    Google Scholar 

  15. D. B. Johnson and S. M. Venkatesan, Parallel algorithm for minimum cuts and maximum flows in planar networks,Proc. 22nd IEEE FOCS, 1982, pp. 244–254.

  16. N. D. Jones and W. T. Laaser, Complete problems for deterministic polynomial time,Theoret. Comput. Sci.,3 (1977), 105–117.

    Google Scholar 

  17. R. M. Karp, E. Upfal, and A. Wigderson, Constructing a perfect matching is in randomNC, Proc. 17th ACM STOC, 1985, pp. 22–32.

  18. R. M. Karp, E. Upfal, and A. Wigderson, Are search and decision problems computationally equivalent?,Proc. 17th ACM STOC, 1985, pp. 464–475.

  19. R. M. Karp, E. Upfal, and A. Wigderson, The complexity of parallel computation on matroids,Proc. 26th IEEE FOCS, 1985, pp. 229–234.

  20. R. E. Ladner, The circuit value problem is log-space complete forP, SIGACT News,7 (1975), 18–21.

    Google Scholar 

  21. J. M. Lewis and M. Yannakakis, The node deletion problems for hereditary properties isNP-complete,J. Comput. System Sci.,20 (1980), 219–230.

    Google Scholar 

  22. M. Luby, A simple parallel algorithm for the maximal independent set problem,Proc. 17th ACM STOC, 1985, pp. 1–10.

  23. C. U. Martel, Lower bounds on parallel algorithms for finding the first maximal independent set,Inform. Process. Lett.,22 (1986), 81–85.

    Google Scholar 

  24. S. L. Mitchell, Linear algorithms recognize outerplanar and maximal outerplanar graphs,Inform. Process. Lett.,9 (1979), 229–232.

    Google Scholar 

  25. S. Miyano, A parallelizable lexicographically first maximal edge-induced subgraph problem,Inform. Process. Lett.,27 (1988), 75–78.

    Google Scholar 

  26. S. Miyano, Δ p2 -complete lexicographically first maximal subgraph problems,Proc. 13th MFCS, Lecture Notes in Computer Science, Vol. 324, Springer-Verlag, Berlin, 1988, pp. 454–462.

    Google Scholar 

  27. S. Miyano, Parallel complexity andP-complete problems,Proc. FGCS '88, 1988, pp. 532–541.

  28. N. Pippenger, On simultaneous resource bounds,Proc. 20th IEEE FOCS, 1979, pp. 307–311.

  29. J. H. Reif, Depth-first search is inherently sequential,Inform. Process. Lett.,20 (1985), 229–234.

    Google Scholar 

  30. W. L. Ruzzo, On uniform circuit complexity,J. Comput. System Sci.,22 (1981), 365–383.

    Google Scholar 

  31. E. Speckenmeyer, Untersuchungen zum Feedback Vertex Set Problem in ungerichteten Graphen, Ph.D. Thesis, Universität-GH-Paderborn, 1983.

  32. T. Watanabe, T. Ae, and A. Nakamura, On the removal of forbidden graphs by edge-deletion or by edge-contraction,Discrete Appl. Math.,3 (1981), 151–153.

    Google Scholar 

  33. M. Wiegers, Recognizing outerplanar graphs in linear time,Graph-Theoretic Concepts in Computer Science, Lecture Notes in Computer Science, Vol. 246, Springer-Verlag, Berlin, 1986, pp. 165–176.

    Google Scholar 

  34. M. Yannakakis, Node-deletion problems on bipartite graphs,SIAM J. Comput.,10 (1981), 310–327.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Research Institute of Fundamental Information Science, Kyushu University 33, 812, Fukuoka, Japan

    Satoru Miyano

Authors
  1. Satoru Miyano
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

This work was done while the author visited Universität-GH-Paderborn and a part of this paper was presented at the 14th ICALP, Karlsruhe, 1987.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Miyano, S. The lexicographically first maximal subgraph problems:P-completeness andNC algorithms. Math. Systems Theory 22, 47–73 (1989). https://doi.org/10.1007/BF02088292

Download citation

  • Received:

  • Revised:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF02088292

Keywords

Search

Navigation