On the Relative Significance of Kernelization versus Branching for Parallel FPT Implementations

Ronald D. Hagan; Charles A. Philips; Kai Wang; Gary L. Rogers; Callum Lowcay; Michael A. Langston

doi:10.2316/P.2013.795-049

On the Relative Significance of Kernelization versus Branching for Parallel FPT Implementations

Ronald D. Hagan, Charles A. Philips, Kai Wang, Gary L. Rogers, Callum Lowcay, Michael A. Langston

Computer Science

University of Tennessee, Knoxville

Research output: Contribution to book or proceeding › Chapter

2 Scopus citations

Abstract

We investigate the relative significance of kernelization versus branching for parallel FPT implementations. Using the well-known vertex cover problem as a familiar example, we build and experiment with a testbed of five different classes of difficult graphs. For some, we find that kernelization alone obviates the need for parallelism. For others, we show that kernelization and branching work in synergy to produce efficient implementations. And yet for others, kernelization fails completely, leaving branching to solve the entire problem. Structural graph properties are studied in an effort to explicate this trichotomy. The NP -completeness of vertex cover makes scalability an extreme challenge. We mainly employ Hopper, named after the famous computing pioneer Admiral Grace Murray Hopper. The Hopper platform is currently one of the world’s fastest supercomputers.

Original language	American English
Title of host publication	Proceedings of the International Conference on Artificial Intelligence and Applications
DOIs	https://doi.org/10.2316/P.2013.795-049
State	Published - Feb 2013

Keywords

Fixed-Parameter Tractability
High Performance Computation
Kernelization and Branching
Parallel Algorithms and Implementations

DC Disciplines

Engineering
Computer Sciences

Access to Document

10.2316/P.2013.795-049License: Unspecified

Cite this

@inbook{cf880d47fd404bd6886f212880cde9ce,

title = "On the Relative Significance of Kernelization versus Branching for Parallel FPT Implementations",

abstract = " We investigate the relative significance of kernelization versus branching for parallel FPT implementations. Using the well-known vertex cover problem as a familiar example, we build and experiment with a testbed of five different classes of difficult graphs. For some, we find that kernelization alone obviates the need for parallelism. For others, we show that kernelization and branching work in synergy to produce efficient implementations. And yet for others, kernelization fails completely, leaving branching to solve the entire problem. Structural graph properties are studied in an effort to explicate this trichotomy. The NP -completeness of vertex cover makes scalability an extreme challenge. We mainly employ Hopper, named after the famous computing pioneer Admiral Grace Murray Hopper. The Hopper platform is currently one of the world{\textquoteright}s fastest supercomputers.",

keywords = "Fixed-Parameter Tractability, High Performance Computation, Kernelization and Branching, Parallel Algorithms and Implementations",

author = "Hagan, {Ronald D.} and Philips, {Charles A.} and Kai Wang and Rogers, {Gary L.} and Callum Lowcay and Langston, {Michael A.}",

note = "We investigate the relative significance of kernelization versus branching for parallel FPT implementations.",

year = "2013",

month = feb,

doi = "10.2316/P.2013.795-049",

language = "American English",

booktitle = "Proceedings of the International Conference on Artificial Intelligence and Applications",

}

TY - CHAP

T1 - On the Relative Significance of Kernelization versus Branching for Parallel FPT Implementations

AU - Hagan, Ronald D.

AU - Philips, Charles A.

AU - Wang, Kai

AU - Rogers, Gary L.

AU - Lowcay, Callum

AU - Langston, Michael A.

N1 - We investigate the relative significance of kernelization versus branching for parallel FPT implementations.

PY - 2013/2

Y1 - 2013/2

N2 - We investigate the relative significance of kernelization versus branching for parallel FPT implementations. Using the well-known vertex cover problem as a familiar example, we build and experiment with a testbed of five different classes of difficult graphs. For some, we find that kernelization alone obviates the need for parallelism. For others, we show that kernelization and branching work in synergy to produce efficient implementations. And yet for others, kernelization fails completely, leaving branching to solve the entire problem. Structural graph properties are studied in an effort to explicate this trichotomy. The NP -completeness of vertex cover makes scalability an extreme challenge. We mainly employ Hopper, named after the famous computing pioneer Admiral Grace Murray Hopper. The Hopper platform is currently one of the world’s fastest supercomputers.

AB - We investigate the relative significance of kernelization versus branching for parallel FPT implementations. Using the well-known vertex cover problem as a familiar example, we build and experiment with a testbed of five different classes of difficult graphs. For some, we find that kernelization alone obviates the need for parallelism. For others, we show that kernelization and branching work in synergy to produce efficient implementations. And yet for others, kernelization fails completely, leaving branching to solve the entire problem. Structural graph properties are studied in an effort to explicate this trichotomy. The NP -completeness of vertex cover makes scalability an extreme challenge. We mainly employ Hopper, named after the famous computing pioneer Admiral Grace Murray Hopper. The Hopper platform is currently one of the world’s fastest supercomputers.

KW - Fixed-Parameter Tractability

KW - High Performance Computation

KW - Kernelization and Branching

KW - Parallel Algorithms and Implementations

UR - http://doi.org/10.2316/P.2013.795-049

U2 - 10.2316/P.2013.795-049

DO - 10.2316/P.2013.795-049

M3 - Chapter

BT - Proceedings of the International Conference on Artificial Intelligence and Applications

ER -

On the Relative Significance of Kernelization versus Branching for Parallel FPT Implementations

Abstract

Keywords

DC Disciplines

Access to Document

Other files and links

Fingerprint

Cite this