Skip to main content

2017 | OriginalPaper | Buchkapitel

On Structural Parameterizations of Graph Motif and Chromatic Number

verfasst von : Bireswar Das, Murali Krishna Enduri, Neeldhara Misra, I. Vinod Reddy

Erschienen in: Algorithms and Discrete Applied Mathematics

Verlag: Springer International Publishing

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

Structural parameterizations for hard problems have proven to be a promising venture for discovering scenarios where the problem is tractable. In particular, when a problem is already known to be polynomially solvable for some class of inputs, then it is natural to parameterize by the distance of a general instance to a tractable class. In the context of graph algorithms, parameters like vertex cover, twin cover, treewidth and treedepth modulators, and distances to various special graph classes are increasingly popular choices for hard problems.
Our main focus in this work is the Graph Motif problem, which involves finding a connected induced subgraph in a vertex colored graph that respects a given palette. This problem is known to be hard in the traditional setting even for fairly structured classes of graphs. In particular, Graph Motif is known to be \(\mathsf {W[1]}\)-hard when parameterized by the distance to split graphs, and para-\(\mathsf {NP}\)-hard when parameterized by the distance to co-graphs (which are the class of https://static-content.springer.com/image/chp%3A10.1007%2F978-3-319-53007-9_11/429667_1_En_11_IEq3_HTML.gif -free graphs). On the other hand, it is known to be \(\mathsf {FPT}\) when parameterized by the distance to a clique or the distance to an independent set (or equivalently, vertex cover). Towards finding the boundary of tractability, we consider parameterizing the problem by the distance to threshold graphs, which are graphs that are both split and https://static-content.springer.com/image/chp%3A10.1007%2F978-3-319-53007-9_11/429667_1_En_11_IEq5_HTML.gif -free. Note that this is a natural choice of an intermediate parameter in that it is larger than the parameters for which the problem is hard and smaller than the ones for which the problem is tractable. Our main contribution is an \(\mathsf {FPT}\) algorithm for the Graph Motif problem when parameterized by the distance to threshold graphs. We also address some related structural parameterizations for Chromatic Number. Here, we show that the problem admits a polynomial kernel when parameterized by the vertex deletion distance to a clique.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Literatur
1.
Zurück zum Zitat Ambalath, A.M., Balasundaram, R., Rao H., C., Koppula, V., Misra, N., Philip, G., Ramanujan, M.S.: On the kernelization complexity of colorful motifs. In: Raman, V., Saurabh, S. (eds.) IPEC 2010. LNCS, vol. 6478, pp. 14–25. Springer, Heidelberg (2010). doi:10.1007/978-3-642-17493-3_4 CrossRef Ambalath, A.M., Balasundaram, R., Rao H., C., Koppula, V., Misra, N., Philip, G., Ramanujan, M.S.: On the kernelization complexity of colorful motifs. In: Raman, V., Saurabh, S. (eds.) IPEC 2010. LNCS, vol. 6478, pp. 14–25. Springer, Heidelberg (2010). doi:10.​1007/​978-3-642-17493-3_​4 CrossRef
2.
Zurück zum Zitat Betzler, N., Van Bevern, R., Fellows, M.R., Komusiewicz, C., Niedermeier, R.: Parameterized algorithmics for finding connected motifs in biological networks. IEEE/ACM TCBB 8(5), 1296–1308 (2011) Betzler, N., Van Bevern, R., Fellows, M.R., Komusiewicz, C., Niedermeier, R.: Parameterized algorithmics for finding connected motifs in biological networks. IEEE/ACM TCBB 8(5), 1296–1308 (2011)
3.
Zurück zum Zitat Bodlaender, H.L., Jansen, B.M., Kratsch, S.: Cross-composition: a new technique for kernelization lower bounds (2010). arXiv preprint arXiv:1011.4224 Bodlaender, H.L., Jansen, B.M., Kratsch, S.: Cross-composition: a new technique for kernelization lower bounds (2010). arXiv preprint arXiv:​1011.​4224
4.
Zurück zum Zitat Bonnet, É., Sikora, F.: The graph motif problem parameterized by the structure of the input graph. In: LIPIcs-Leibniz International Proceedings in Informatics, vol. 43. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2015) Bonnet, É., Sikora, F.: The graph motif problem parameterized by the structure of the input graph. In: LIPIcs-Leibniz International Proceedings in Informatics, vol. 43. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2015)
6.
7.
Zurück zum Zitat Courcelle, B.: The monadic second-order logic of graphs. I. Recognizable sets of finite graphs. Inf. Comput. 85(1), 12–75 (1990)MathSciNetCrossRefMATH Courcelle, B.: The monadic second-order logic of graphs. I. Recognizable sets of finite graphs. Inf. Comput. 85(1), 12–75 (1990)MathSciNetCrossRefMATH
8.
Zurück zum Zitat Cygan, M., Fomin, F.V., Kowalik, Ł., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms, vol. 4. Springer, New York (2015)CrossRefMATH Cygan, M., Fomin, F.V., Kowalik, Ł., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms, vol. 4. Springer, New York (2015)CrossRefMATH
9.
Zurück zum Zitat Downey, R.G., Fellows, M.R.: Parameterized Complexity, vol. 3. Springer, Heidelberg (1999)CrossRefMATH Downey, R.G., Fellows, M.R.: Parameterized Complexity, vol. 3. Springer, Heidelberg (1999)CrossRefMATH
10.
Zurück zum Zitat Fellows, M.R., Fertin, G., Hermelin, D., Vialette, S.: Sharp tractability borderlines for finding connected motifs in vertex-colored graphs. In: Arge, L., Cachin, C., Jurdziński, T., Tarlecki, A. (eds.) ICALP 2007. LNCS, vol. 4596, pp. 340–351. Springer, Heidelberg (2007). doi:10.1007/978-3-540-73420-8_31 CrossRef Fellows, M.R., Fertin, G., Hermelin, D., Vialette, S.: Sharp tractability borderlines for finding connected motifs in vertex-colored graphs. In: Arge, L., Cachin, C., Jurdziński, T., Tarlecki, A. (eds.) ICALP 2007. LNCS, vol. 4596, pp. 340–351. Springer, Heidelberg (2007). doi:10.​1007/​978-3-540-73420-8_​31 CrossRef
11.
Zurück zum Zitat Foldes, S., Hammer, P.L.: Split graphs. Institut für Ökonometrie und Operations Research, Universität Bonn (1976) Foldes, S., Hammer, P.L.: Split graphs. Institut für Ökonometrie und Operations Research, Universität Bonn (1976)
12.
Zurück zum Zitat Fomin, F.V., Golovach, P.A., Lokshtanov, D., Saurabh, S.: Algorithmic lower bounds for problems parameterized by clique-width. In: Proceedings of 21st Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 493–502. SIAM (2010) Fomin, F.V., Golovach, P.A., Lokshtanov, D., Saurabh, S.: Algorithmic lower bounds for problems parameterized by clique-width. In: Proceedings of 21st Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 493–502. SIAM (2010)
15.
Zurück zum Zitat Ganian, R.: Improving vertex cover as a graph parameter. Discret. Math. Theoret. Comput. Sci. 17(2), 77–100 (2015)MathSciNetMATH Ganian, R.: Improving vertex cover as a graph parameter. Discret. Math. Theoret. Comput. Sci. 17(2), 77–100 (2015)MathSciNetMATH
16.
Zurück zum Zitat Jansen, B.M., et al.: The power of data reduction: kernels for fundamental graph problems (2013) Jansen, B.M., et al.: The power of data reduction: kernels for fundamental graph problems (2013)
17.
Zurück zum Zitat Lacroix, V., Fernandes, C.G., Sagot, M.F.: Motif search in graphs: application to metabolic networks. IEEE/ACM TCBB 3(4), 360–368 (2006) Lacroix, V., Fernandes, C.G., Sagot, M.F.: Motif search in graphs: application to metabolic networks. IEEE/ACM TCBB 3(4), 360–368 (2006)
18.
Zurück zum Zitat Mahadev, N.V., Peled, U.N.: Threshold Graphs and Related Topics, vol. 56. Elsevier, Amsterdam (1995)MATH Mahadev, N.V., Peled, U.N.: Threshold Graphs and Related Topics, vol. 56. Elsevier, Amsterdam (1995)MATH
Metadaten
Titel
On Structural Parameterizations of Graph Motif and Chromatic Number
verfasst von
Bireswar Das
Murali Krishna Enduri
Neeldhara Misra
I. Vinod Reddy
Copyright-Jahr
2017
DOI
https://doi.org/10.1007/978-3-319-53007-9_11