Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Algorithms for Queryable Uncertainty Read chapter Read first chapter

2016 | OriginalPaper | Chapter

Kernelization of Two Path Searching Problems on Split Graphs

Authors : Yongjie Yang, Yash Raj Shrestha, Wenjun Li, Jiong Guo

Published in: Frontiers in Algorithmics

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

In the k-Vertex-Disjoint Paths problem, we are given a graph G and k terminal pairs of vertices, and are asked whether there is a set of k vertex-disjoint paths linking these terminal pairs, respectively. In the k-Path problem, we are given a graph and are asked whether there is a path of length k. It is known that both problems are NP-hard even in split graphs, which are the graphs whose vertices can be partitioned into a clique and an independent set. We study kernelization for the two problems in split graphs. In particular, we derive a 4k vertex-kernel for the k-Vertex-Disjoint Paths problem and a \(\frac{3}{2}k^2+\frac{1}{2}k\) vertex-kernel for the k-Path problem.

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now
previous chapter A PTAS for the Multiple Parallel Identical Multi-stage Flow-Shops to Minimize the Makespan
next chapter The Bounded Batch Scheduling with Common Due Window and Non-identical Size Jobs
Literature
1.
2.
Abu-Khzam, F.N., Fellows, M.R., Langston, M.A., Suters, W.H.: Crown structures for vertex cover kernelization. Theor. Comput. Syst. 41(3), 411–430 (2007)MathSciNetCrossRefMATH
3.
Adcock, A.B., Demaine, E.D., Demaine, M.L., O’Brien, M.P., Reidl, F., Villaamil, F.S., Sullivan, B.D.: Zig-zag numberlink is NP-complete. JIP 23(3), 239–245 (2015)
4.
Bodlaender, H.L., Downey, R.G., Fellows, M.R., Hermelin, D.: On problems without polynomial kernels. J. Comput. Syst. Sci. 75(8), 423–434 (2009)MathSciNetCrossRefMATH
5.
Bodlaender, H.L., Thomassé, S., Yeo, A.: Kernel bounds for disjoint cycles and disjoint paths. Theor. Comput. Sci. 412(35), 4570–4578 (2011)MathSciNetCrossRefMATH
6.
Chor, B., Fellows, M., Juedes, D.W.: Linear kernels in linear time, or how to save k colors in \(O(n^2)\) steps. In: Hromkovič, J., Nagl, M., Westfechtel, B. (eds.) WG 2004. LNCS, vol. 3353, pp. 257–269. Springer, Heidelberg (2004)CrossRef
7.
Frank, A.: Packing paths, circuits and cuts: a survey. In: Korte, B., Lovász, L., Prömel, H.J., Schrijver, A. (eds.) Paths, Flows, and VLSI-Layout, pp. 49–100. Springer, Berlin (1990)
8.
Heggernes, P., Hof, P., van Leeuwen, E.J., Saei, R.: Finding disjoint paths in split graphs. Theor. Comput. Syst. 57(1), 140–159 (2015)MathSciNetCrossRefMATH
9.
Heggernes, P., Lokshtanov, D., Mihai, R., Papadopoulos, C.: Cutwidth of split graphs and threshold graphs. SIAM J. Discrete Math. 25(3), 1418–1437 (2011)MathSciNetCrossRefMATH
10.
Jansen, B.M.P.: Turing kernelization for finding long paths and cycles in restricted graph classes. In: Schulz, A.S., Wagner, D. (eds.) ESA 2014. LNCS, vol. 8737, pp. 579–591. Springer, Heidelberg (2014)
11.
Karp, R.M., Leighton, F.T., Rivest, R.L., Thompson, C.D., Vazirani, U.V., Vazirani, V.V.: Global wire routing in two-dimensional arrays. Algorithmica 2, 113–129 (1987)MathSciNetCrossRefMATH
12.
Kramer, M.R., van Leeuwen, J.: The complexity of wire-routing and finding minimum area layouts for arbitrary VLSI circuits. Adv. Comput. Res. 2, 129–146 (1984)
13.
Lynch, J.F.: The equivalence of theorem proving and the interconnection problem. SIGDA Newsl. 5(3), 31–36 (1975)CrossRef
14.
15.
16.
Natarajan, S., Sprague, A.P.: Disjoint paths in circular arc graphs. Nord. J. Comput. 3(3), 256–270 (1996)MathSciNet
17.
Prieto, E., Sloper, C.: Looking at the stars. In: Downey, R.G., Fellows, M.R., Dehne, F. (eds.) IWPEC 2004. LNCS, vol. 3162, pp. 138–148. Springer, Heidelberg (2004)CrossRef
18.
Raman, V., Saurabh, S.: Short cycles make W-hard problems hard: FPT algorithms for W-hard problems in graphs with no short cycles. Algorithmica 52(2), 203–225 (2008)MathSciNetCrossRefMATH
19.
Robertson, N., Seymour, P.D.: An outline of a disjoint path algorithm. In: Korte, B., Lovász, L., Prömel, H.J., Schrijver, A. (eds.) Paths, Flows, and VLSI-Layout, pp. 267–292. Springer, Berlin (1990)
20.
21.
Wang, J., Yang, Y., Guo, J., Chen, J.: Planar graph vertex partition for linear problem kernels. J. Comput. Syst. Sci. 79(5), 609–621 (2013)MathSciNetCrossRefMATH
22.
Metadata
Title
Kernelization of Two Path Searching Problems on Split Graphs
Authors
Yongjie Yang
Yash Raj Shrestha
Wenjun Li
Jiong Guo
Copyright Year
2016
Book
Frontiers in Algorithmics

Print ISBN: 978-3-319-39816-7

Electronic ISBN: 978-3-319-39817-4

Copyright Year: 2016

DOI
https://doi.org/10.1007/978-3-319-39817-4_23

Premium Partner

    Image Credits