Exponential speedup of fixed-parameter algorithms on K3 3-minor-free or K5-minor-free graphs

Erik D. Demaine; Mohammad Taghi Hajiaghayi; Dimitrios M. Thilikos

doi:10.1007/3-540-36136-7_24

Exponential speedup of fixed-parameter algorithms on K₃ ₃-minor-free or K₅-minor-free graphs

Erik D. Demaine, Mohammad Taghi Hajiaghayi, Dimitrios M. Thilikos

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

We present a fixed-parameter algorithm that constructively solves the k-dominating set problem on graphs excluding one of K₅ or K _3,3 as a minor in time O(4^16.5 ^√kn ^O(1)), which is an exponential factor faster than the previous O(2^O(k)n^O(1)). In fact, we present our algorithm for any H-minor-free graph where H is a single-crossing graph (can be drawn in the plane with at most one crossing) and obtain the algorithm for K_3,3(K ₅)-minor-free graphs as a special case. As a consequence, we extend our results to several other problems such as vertex cover, edge dominating set, independent set, clique-transversal set, kernels in digraphs, feedback vertex set and a series of vertex removal problems. Our work generalizes and extends the recent result of exponential speedup in designing fixed-parameter algorithms on planar graphs by Alber et al. to other (nonplanar) classes of graphs.

Original language	English (US)
Title of host publication	Algorithms and Computation - 13th International Symposium, ISAAC 2002, Proceedings
Pages	262-273
Number of pages	12
DOIs	https://doi.org/10.1007/3-540-36136-7_24
State	Published - 2002
Event	13th Annual International Symposium on Algorithms and Computation, ISAAC 2002 - Vancouver, BC, Canada Duration: Nov 21 2002 → Nov 23 2002

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	2518 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	13th Annual International Symposium on Algorithms and Computation, ISAAC 2002
Country/Territory	Canada
City	Vancouver, BC
Period	11/21/02 → 11/23/02

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/3-540-36136-7_24

Cite this

Demaine, E. D., Hajiaghayi, M. T., & Thilikos, D. M. (2002). Exponential speedup of fixed-parameter algorithms on K₃ ₃-minor-free or K₅-minor-free graphs. In Algorithms and Computation - 13th International Symposium, ISAAC 2002, Proceedings (pp. 262-273). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2518 LNCS). https://doi.org/10.1007/3-540-36136-7_24

Exponential speedup of fixed-parameter algorithms on K₃ ₃-minor-free or K₅-minor-free graphs. / Demaine, Erik D.; Hajiaghayi, Mohammad Taghi; Thilikos, Dimitrios M.
Algorithms and Computation - 13th International Symposium, ISAAC 2002, Proceedings. 2002. p. 262-273 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2518 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Demaine, ED, Hajiaghayi, MT & Thilikos, DM 2002, Exponential speedup of fixed-parameter algorithms on K₃ ₃-minor-free or K₅-minor-free graphs. in Algorithms and Computation - 13th International Symposium, ISAAC 2002, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 2518 LNCS, pp. 262-273, 13th Annual International Symposium on Algorithms and Computation, ISAAC 2002, Vancouver, BC, Canada, 11/21/02. https://doi.org/10.1007/3-540-36136-7_24

Demaine ED, Hajiaghayi MT, Thilikos DM. Exponential speedup of fixed-parameter algorithms on K₃ ₃-minor-free or K₅-minor-free graphs. In Algorithms and Computation - 13th International Symposium, ISAAC 2002, Proceedings. 2002. p. 262-273. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/3-540-36136-7_24

Demaine, Erik D. ; Hajiaghayi, Mohammad Taghi ; Thilikos, Dimitrios M. / Exponential speedup of fixed-parameter algorithms on K₃ ₃-minor-free or K₅-minor-free graphs. Algorithms and Computation - 13th International Symposium, ISAAC 2002, Proceedings. 2002. pp. 262-273 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{5ed99dcc1edf421aa68d1fd549c0f69f,

title = "Exponential speedup of fixed-parameter algorithms on K3 3-minor-free or K5-minor-free graphs",

abstract = "We present a fixed-parameter algorithm that constructively solves the k-dominating set problem on graphs excluding one of K5 or K 3,3 as a minor in time O(416.5 √kn O(1)), which is an exponential factor faster than the previous O(2O(k)nO(1)). In fact, we present our algorithm for any H-minor-free graph where H is a single-crossing graph (can be drawn in the plane with at most one crossing) and obtain the algorithm for K3,3(K 5)-minor-free graphs as a special case. As a consequence, we extend our results to several other problems such as vertex cover, edge dominating set, independent set, clique-transversal set, kernels in digraphs, feedback vertex set and a series of vertex removal problems. Our work generalizes and extends the recent result of exponential speedup in designing fixed-parameter algorithms on planar graphs by Alber et al. to other (nonplanar) classes of graphs.",

author = "Demaine, {Erik D.} and Hajiaghayi, {Mohammad Taghi} and Thilikos, {Dimitrios M.}",

year = "2002",

doi = "10.1007/3-540-36136-7_24",

language = "English (US)",

isbn = "3540001425",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "262--273",

booktitle = "Algorithms and Computation - 13th International Symposium, ISAAC 2002, Proceedings",

note = "13th Annual International Symposium on Algorithms and Computation, ISAAC 2002 ; Conference date: 21-11-2002 Through 23-11-2002",

}

TY - GEN

T1 - Exponential speedup of fixed-parameter algorithms on K3 3-minor-free or K5-minor-free graphs

AU - Demaine, Erik D.

AU - Hajiaghayi, Mohammad Taghi

AU - Thilikos, Dimitrios M.

PY - 2002

Y1 - 2002

N2 - We present a fixed-parameter algorithm that constructively solves the k-dominating set problem on graphs excluding one of K5 or K 3,3 as a minor in time O(416.5 √kn O(1)), which is an exponential factor faster than the previous O(2O(k)nO(1)). In fact, we present our algorithm for any H-minor-free graph where H is a single-crossing graph (can be drawn in the plane with at most one crossing) and obtain the algorithm for K3,3(K 5)-minor-free graphs as a special case. As a consequence, we extend our results to several other problems such as vertex cover, edge dominating set, independent set, clique-transversal set, kernels in digraphs, feedback vertex set and a series of vertex removal problems. Our work generalizes and extends the recent result of exponential speedup in designing fixed-parameter algorithms on planar graphs by Alber et al. to other (nonplanar) classes of graphs.

AB - We present a fixed-parameter algorithm that constructively solves the k-dominating set problem on graphs excluding one of K5 or K 3,3 as a minor in time O(416.5 √kn O(1)), which is an exponential factor faster than the previous O(2O(k)nO(1)). In fact, we present our algorithm for any H-minor-free graph where H is a single-crossing graph (can be drawn in the plane with at most one crossing) and obtain the algorithm for K3,3(K 5)-minor-free graphs as a special case. As a consequence, we extend our results to several other problems such as vertex cover, edge dominating set, independent set, clique-transversal set, kernels in digraphs, feedback vertex set and a series of vertex removal problems. Our work generalizes and extends the recent result of exponential speedup in designing fixed-parameter algorithms on planar graphs by Alber et al. to other (nonplanar) classes of graphs.

UR - http://www.scopus.com/inward/record.url?scp=84878663787&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84878663787&partnerID=8YFLogxK

U2 - 10.1007/3-540-36136-7_24

DO - 10.1007/3-540-36136-7_24

M3 - Conference contribution

AN - SCOPUS:84878663787

SN - 3540001425

SN - 9783540001423

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 262

EP - 273

BT - Algorithms and Computation - 13th International Symposium, ISAAC 2002, Proceedings

T2 - 13th Annual International Symposium on Algorithms and Computation, ISAAC 2002

Y2 - 21 November 2002 through 23 November 2002

ER -