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

On the Ordered List Subgraph Embedding Problems

  • Published:
Algorithmica 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

In the (parameterized) Ordered List Subgraph Embedding problem (p-OLSE) we are given two graphs \(G\) and \(H\), each with a linear order defined on its vertices, a function \(L\) that associates with every vertex in \(G\) a list of vertices in \(H\), and a parameter \(k\). The question is to decide if there is a subset \(S \subseteq V(G)\) of \(k\) vertices and a mapping/embedding from \(S\) to \(V(H)\) such that: (1) every vertex of \(S\) is mapped to a vertex from its associated list, (2) the linear orders inherited by \(S\) and its image under the mapping are respected, and (3) if there is an edge between two vertices in \(S\) then there is an edge between their images. If we change condition (3) to “there is an edge between two vertices in \(S\) if and only if there is an edge between their images”, we obtain the Ordered List Induced Subgraph Embedding problem (p-OLISE). The p-OLSE and p-OLISE problems model various problems in Bioinformatics related to structural comparison/alignment of proteins. We investigate the complexity of p-OLSE and p-OLISE with respect to the following structural parameters: the width \(\Delta _L\) of the function \(L\) (size of the largest list), and the maximum degree \(\Delta _H\) of \(H\) and \(\Delta _G\) of \(G\). In terms of the structural parameters under consideration, we draw a complete complexity landscape of p-OLSE and p-OLISE (and their optimization versions) with respect to the computational frameworks of classical complexity, parameterized complexity, and approximation.

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

Similar content being viewed by others

Notes

  1. The degree of a vertex in \(H_{split}\) may be unbounded.

  2. The class \(\mathcal{C}\) is closed under taking subgraphs; that is, every subgraph of a graph in \(\mathcal{C}\) is also in \(\mathcal{C}\).

References

  1. Alber, J., Gramm, J., Guo, J., Niedermeier, R.: Computing the similarity of two sequences with nested arc annotations. Theoret. Comput. Sci. 312(2–3), 337–358 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  2. Alon, N., Yuster, R., Zwick, U.: Color-coding. J. ACM 42, 844–856 (1995)

    Article  MathSciNet  MATH  Google Scholar 

  3. Ashby, C., Huang, X., Johnson, D., Kanj, I., Walker, K., Xia, G.: New algorithm for protein structure comparison and classification. BMC Genomics. 14, S2:S1 (2012)

  4. Cai, L., Chan, S.-M., Chan, S.-O.: Random separation: a new method for solving fixed-cardinality optimization problems. In: Proceedings of the Second International Workshop on Parameterized and Exact Computation, Volume 4169 of Lecture Notes in Computer Science, pp. 239–250. Springer, New York (2006)

  5. Chen, J., Kanj, I., Xia, G.: Improved upper bounds for vertex cover. Theoret. Comput. Sci. 411(40–42), 3736–3756 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  6. Downey, R., Fellows, M.: Parameterized computational feasibility. In: Clote, P., Remmel, J. (eds.) Feasible Mathematics II, pp. 219–244. Birkhauser, Boston (1995)

    Chapter  Google Scholar 

  7. Downey, R., Fellows, M.: Fundamentals of Parameterized Complexity. Springer, New York (2013)

    Book  MATH  Google Scholar 

  8. Evans, P.: Algorithms and complexity for annotated sequence analysis. Technical report, Ph.D. thesis, University of Victoria (1999)

  9. Evans, P.: Finding common subsequences with arcs and pseudoknots. In: Proceedings of the 10th Annual Symposium on Combinatorial Pattern Matching, Volume 1645 of Lecture Notes in Computer Science, pp. 270–280. Springer, New York (1999)

  10. Fagnot, I., Lelandais, G., Vialette, S.: Bounded list injective homomorphism for comparative analysis of protein-protein interaction graphs. J. Discrete Algorithms 6(2), 178–191 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  11. G. Fertin, R. Rizzi, S. Vialette: Finding exact and maximum occurrences of protein complexes in protein-protein interaction graphs. In: Proceedings of the 30th International Symposium on Mathematical Foundations of Computer Science, Volume 3618 of Lecture Notes in Computer Science, pp. 328–339. Springer, New York (2005)

  12. Fertin, G., Rizzi, R., Vialette, S.: Finding occurrences of protein complexes in protein-protein interaction graphs. J. Discrete Algorithms 7(1), 90–101 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  13. Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer, Berlin (2010)

    Google Scholar 

  14. Goldman, D., Istrail, S., Papadimitriou, C.: Algorithmic aspects of protein structure similarity. In: Proceedings of the 40th Annual Symposium on Foundations of Computer Science, pp. 512–522 (1999)

  15. Gramm, J., Guo, J., Niedermeier, R.: On exact and approximation algorithms for distinguishing substring selection. In: Proceedings of the 4th International Symposium on Fundamentals of Computation Theory, Volume 2751 of Lecture Notes in Computer Science, pp. 195–209 (2003)

  16. Gramm, J., Guo, J., Niedermeier, R.: Parameterized intractability of distinguishing substring selection. Theory Comput. Syst. 39(4), 545–560 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  17. Hartung, S., Niedermeier, R.: Incremental list coloring of graphs, parameterized by conservation. Theoret. Comput. Sci. 494, 86–98 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  18. Jiang, T., Lin, G., Ma, B., Zhang, K.: The longest common subsequence problem for arc-annotated sequences. J. Discrete Algorithms 2(2), 257–270 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  19. Kim, H.: Finding a maximum independent set in a permutation graph. Inf. Process. Lett. 36(1), 19–23 (1990)

    Article  MATH  Google Scholar 

  20. Lin, G.-H., Chen, Z.-Z., Jiang, T., Wen, J.: The longest common subsequence problem for sequences with nested arc annotations. J. Comput. Syst. Sci. 65(3), 465–480 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  21. Naor, M., Schulman, L., Srinivasan, A.: Splitters and near-optimal derandomization. In: Proceedings of the 36th Annual Symposium on Foundations of Computer Science, pp. 182–191 (1995)

  22. Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. Oxford University Press, Oxford (2006)

    Book  MATH  Google Scholar 

  23. Papadimitriou, C., Yannakakis, M.: Optimization, approximation, and complexity classes. J. Comput. Syst. Sci. 43, 425–440 (1991)

    Article  MathSciNet  MATH  Google Scholar 

  24. Song, Y., Liu, C., Huang, X., Malmberg, R., Xu, Y., Cai, L.: Efficient parameterized algorithms for biopolymer structure-sequence alignment. IEEE/ACM Trans. Comput. Biol. Bioinf. 3(4), 423–432 (2006)

    Article  Google Scholar 

  25. West, D.: Introduction to Graph Theory. Prentice Hall Inc, New Jersey (1996)

    MATH  Google Scholar 

  26. Zuckerman, D.: Linear degree extractors and the inapproximability of max clique and chromatic number. In: Proceedings of the 38th Annual ACM Symposium on Theory of Computing, pp. 681–690 (2006)

Download references

Author information

Authors and Affiliations

  1. School of Computing, DePaul University, 243 S. Wabash Avenue, Chicago, IL, 60604, USA

    Olawale Hassan, Iyad Kanj & Ljubomir Perković

  2. Department of Informatics, University of Bergen, Bergen, Norway

    Daniel Lokshtanov

Authors
  1. Olawale Hassan
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Iyad Kanj
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Daniel Lokshtanov
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Ljubomir Perković
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Iyad Kanj.

Additional information

A preliminary version of this paper appeared in proceedings of the 8th International Symposium on Parameterized and Exact Computation (IPEC), volume 8246 of Lecture Notes in Computer Science, pages 189–201, 2013.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Hassan, O., Kanj, I., Lokshtanov, D. et al. On the Ordered List Subgraph Embedding Problems. Algorithmica 74, 992–1018 (2016). https://doi.org/10.1007/s00453-015-9980-2

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00453-015-9980-2

Keywords

Search

Navigation