Charles Darwin University

CDU eSpace
Institutional Repository

 
CDU Staff and Student only
 

Parameterizing by the number of numbers

Fellows, Michael R., Gaspers, Serge and Rosamond, Frances A. (2010). Parameterizing by the number of numbers. In: Raman, Venkatesh and Saurabh, Saket IPEC. Parameterized and Exact 2010, Chennai, India, 13-15 December 2010.

Document type: Conference Paper

IRMA ID 81704288xPUB380
Author Fellows, Michael R.
Gaspers, Serge
Rosamond, Frances A.
Title Parameterizing by the number of numbers
Conference Name IPEC. Parameterized and Exact 2010
Conference Location Chennai, India
Conference Dates 13-15 December 2010
Conference Publication Title Parameterized and Exact Computation: 5th International Symposium, IPEC 1010, Proceedings
Editor Raman, Venkatesh
Saurabh, Saket
Place of Publication Germany
Publisher Springer
Publication Year 2010
Volume Number 6478 LNCS
ISBN 878-3-642-17492-6   (check CDU catalogue open catalogue search in new window)
ISSN 0302-9743   (check CDU catalogue open catalogue search in new window)
Start Page 123
End Page 134
Total Pages 11
HERDC Category E1 - Conference Publication (DIISR)
Abstract The usefulness of parameterized algorithmics has often depended on what Niedermeier has called “the art of problem parameterization”. In this paper we introduce and explore a novel but general form of parameterization: the number of numbers. Several classic numerical problems, such as SUBSET SUM, PARTITION, 3-PARTITION, NUMERICAL 3-DIMENSIONAL MATCHING, and NUMERICAL MATCHING WITH TARGET SUMS, have multisets of integers as input. We initiate the study of parameterizing these problems by the number of distinct integers in the input. We rely on an FPT result for INTEGER LINEAR PROGRAMMING FEASIBILITY to show that all the above-mentioned problems are fixed-parameter tractable when parameterized in this way. In various applied settings, problem inputs often consist in part of multisets of integers or multisets of weighted objects (such as edges in a graph, or jobs to be scheduled). Such number-of-numbers parameterized problems often reduce to subproblems about transition systems of various kinds, parameterized by the size of the system description. We consider several core problems of this kind relevant to number-of-numbers parameterization. Our main hardness result considers the problem: given a non-deterministic Mealy machine M (a finite state automatonoutputting a letter on each transition), an input for the output word specifying how many times each letter of the output alphabet should be written, decide whether there exists a computation of M reading x that outputs a word y that meets the requirement c. We show that this problem is hard for W[1]. If the question is whether there exists an input word x such that a computation of M on x outputs a word that meets c, the problem becomes fixed-parameter tractable
Keyword Parameterized complexity
Problem parameterization
Variety of a multiset
Numerical problems
 
Versions
Version Filter Type
Access Statistics: 141 Abstract Views, 13 File Downloads  -  Detailed Statistics
Created: Fri, 17 Jan 2014, 00:10:20 CST