On bounded block decomposition problems for under-specified systems of equations

M.J. Bomhoff, Walter Kern, Georg J. Still

Research output: Book/ReportReportProfessional

73 Downloads (Pure)

Abstract

When solving a system of equations, it can be beneficial not to solve it in its entirety at once, but rather to decompose it into smaller subsystems that can be solved in order. Based on a bisimplicial graph representation we analyze the parameterized complexity of two problems central to such a decomposition: The Free Square Block problem related to finding smallest subsystems that can be solved separately, and the Bounded Block Decomposition problem related to determining a decomposition where the largest subsystem is as small as possible. We show both problems to be W[1]-hard. Finally we relate these problems to crown structures and settle two open questions regarding them using our results.
Original languageUndefined
Place of PublicationEnschede
PublisherUniversity of Twente, Department of Applied Mathematics
Number of pages17
Publication statusPublished - Dec 2010

Publication series

NameMemorandum / Department of Applied Mathematics
PublisherDepartment of Applied Mathematics, University of Twente
No.1930
ISSN (Print)1874-4850
ISSN (Electronic)1874-4850

Keywords

  • Bipartite graph
  • EWI-19046
  • Parameterized complexity
  • METIS-276208
  • Decomposition
  • IR-75139

Cite this