Luke Mathieson is a theoretical computer scientist and Scholarly Teaching Fellow at UTS. His research is centred on parameterised complexity and its applications, but extends to a variety of areas of complexity theory, algorithmics and mathematics.
He has taught an extensive range of computer science subjects, particularly focussing on the theory of computation, computational complexity and algorithmics.
He is also a epeeist, a science fiction fan and a terrible guitarist.
Can supervise: YES
Luke's main research interests are in parameterized complexity and the fundamentals of computational complexity, however his research spans a number of areas:
- Computational complexity
- Parameterized complexity
- Finite Model Theory/Logic
- Memetic algorithms
A major theme of his research is the complexity of graph editing problems, a topic in which he specialises.
Luke has taught subjects in most areas of computer science, but specialises in core theory topics such as:
- Computational complexity
- Data structures
- Formal languages and automata
- Graph theory and discrete mathematics
At UTS he teaches the following subjects:
- 31251 Data structures and algorithms
- 48024 Applications Programming
- 41078 Computing Science Studio 1
- 41080 Theory of Computing Science
Lancia, G, Mathieson, L & Moscato, P 2017, 'Separating sets of strings by finding matching patterns is almost always hard', Theoretical Computer Science, vol. 665, pp. 73-86.View/Download from: Publisher's site
© 2017 Elsevier B.V. We study the complexity of the problem of searching for a set of patterns that separate two given sets of strings. This problem has applications in a wide variety of areas, most notably in data mining, computational biology, and in understanding the complexity of genetic algorithms. We show that the basic problem of finding a small set of patterns that match one set of strings but do not match any string in a second set is difficult (NP-complete, W-hard when parameterized by the size of the pattern set, and APX-hard). We then perform a detailed parameterized analysis of the problem, separating tractable and intractable variants. In particular we show that parameterizing by the size of pattern set and the number of strings, and the size of the alphabet and the number of strings give FPT results, amongst others.
© 2016, Springer Science+Business Media New York. Dynamic systems are becoming steadily more important with the profusion of mobile and distributed computing devices. Coincidentally incremental computation is a natural approach to deal with ongoing changes. We explore incremental computation in the parameterized complexity setting and show that incrementalization leads to non-trivial complexity classifications. Interestingly, some incremental versions of hard problems become tractable, while others remain hard. Moreover tractability or intractability is not a simple function of the problem's static complexity, every level of the W-hierarchy exhibits complete problems with both tractable and intractable incrementalizations. For problems that are already tractable in their static form, we also show that incrementalization can lead to interesting algorithms, improving upon the trivial approach of using the static algorithm at each step.
© 2017 Graph editing problems offer an interesting perspective on sub- and supergraph identification problems for a large variety of target properties. They have also attracted significant attention in recent years, particularly in the area of parameterized complexity as the problems have rich parameter ecologies. In this paper we examine generalisations of the notion of editing a graph to obtain a regular subgraph. In particular we extend the notion of regularity to include two variants of edge-regularity along with the unifying constraint of strong regularity. We present a number of results, with the central observation that these problems retain the general complexity profile of their regularity-based inspiration: when the number of edits k and the maximum degree r are taken together as a combined parameter, the problems are tractable (i.e. in FPT), but are otherwise intractable. We also examine variants of the basic editing to obtain a regular subgraph problem from the perspective of parameterizing by the treewidth of the input graph. In this case the treewidth of the input graph essentially becomes a limiting parameter on the natural k+r parameterization.
Konyagin, SV, Luca, F, Mans, B, Mathieson, L, Sha, M & Shparlinski, IE 2016, 'Functional graphs of polynomials over finite fields', JOURNAL OF COMBINATORIAL THEORY SERIES B, vol. 116, pp. 87-122.View/Download from: Publisher's site
Mathieson, L 2016, 'Synergies in critical reflective practice and science: Science as reflection and reflection as science', Journal of University Teaching and Learning Practice, vol. 13, no. 2, pp. 1-13.
© 2016, University of Wollongong. All rights reserved. The conceptions of reflective practice in education have their roots at least partly in the work of Dewey, who describes reflection as "the active, persistent, and careful consideration of any belief or supposed form of knowledge in the light of the grounds that support it and the further conclusions to which it tends" (Dewey 1933, p.9). This conception of reflection has carried on into more-focused efforts to describe critical reflection as a tool for improving professional practice (where academic and educational practice is the particular interest of this study); "... some puzzling or troubling or interesting phenomenon" allows the practitioner to access "the understandings which have been implicit in his action, understandings which he surfaces, criticizes, restructures, and embodies in further action" (Schön 1983, p. 50). Both of these descriptions embody a central idea of critical reflective practice: that the examination of practice involves the divination (in a rational, critical sense) of order and perhaps meaning from the facts at hand (which, in turn, are brought to light by the events that occur as the results of implementation of theory). As part of a lecture series, Gottlieb defined science as "an intellectual activity carried out by humans to understand the structure and functions of the world in which they live" (Gottlieb 1997). While science and critical reflective practice attempt to build models about different parts of our world – the natural world and the world of professional (educational) practice respectively – both embody certain underlying aims and methodologies. Indeed, it is striking that in these definitions the simple replacement of the terminology of reflective practice with the terminology of science (or vice versa) leads to a perfectly comprehensible definition of either.It is this confluence that this paper studies, building from two separate foundations, critical reflective pr...
© 2014, Springer Science+Business Media New York. We study the problem of augmenting a weighted graph by inserting edges of bounded total cost while minimizing the diameter of the augmented graph. Our main result is an FPT $$4$$4-approximation algorithm for the problem.
Frati, F, Gaspers, S, Gudmundsson, J & Mathieson, L 2013, 'Augmenting graphs to minimize the diameter', Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 8283 LNCS, pp. 383-393.View/Download from: Publisher's site
We study the problem of augmenting a weighted graph by inserting edges of bounded total cost while minimizing the diameter of the augmented graph. Our main result is an FPT 4-approximation algorithm for the problem. © 2013 Springer-Verlag.
Arefin, AS, Mathieson, L, Johnstone, D, Berretta, R & Moscato, P 2012, 'Unveiling Clusters of RNA Transcript Pairs Associated with Markers of Alzheimer's Disease Progression', PLOS ONE, vol. 7, no. 9.View/Download from: Publisher's site
Mathieson, L & Szeider, S 2012, 'Editing graphs to satisfy degree constraints: A parameterized approach', JOURNAL OF COMPUTER AND SYSTEM SCIENCES, vol. 78, no. 1, pp. 179-191.View/Download from: Publisher's site
Mellor, D, Prieto, E, Mathieson, L & Moscato, P 2010, 'A Kernelisation Approach for Multiple d-Hitting Set and Its Application in Optimal Multi-Drug Therapeutic Combinations', PLOS ONE, vol. 5, no. 10.View/Download from: Publisher's site
Rizzi, R, Mahata, P, Mathieson, L & Moscato, P 2010, 'Hierarchical Clustering Using the Arithmetic-Harmonic Cut: Complexity and Experiments', PLOS ONE, vol. 5, no. 12.View/Download from: Publisher's site
Mann, RL, Mathieson, L & Greenhill, C, 'On the Parameterised Complexity of Induced Multipartite Graph Parameters'.
We introduce a family of graph parameters, called induced multipartite graph
parameters, and study their computational complexity. First, we consider the
following decision problem: an instance is an induced multipartite graph
parameter $p$ and a given graph $G$, and for natural numbers $k\geq2$ and
$\ell$, we must decide whether the maximum value of $p$ over all induced
$k$-partite subgraphs of $G$ is at most $\ell$. We prove that this problem is
W-hard. Next, we consider a variant of this problem, where we must decide
whether the given graph $G$ contains a sufficiently large induced $k$-partite
subgraph $H$ such that $p(H)\leq\ell$. We show that for certain parameters this
problem is para-NP-hard, while for others it is fixed-parameter tractable.
Mathieson, L & Moscato, P 2019, 'An Introduction to Proximity Graphs' in Moscato, P & de Vries, NJ (eds), Business and Consumer Analytics: New Ideas, Springer International Publishing, Germany, pp. 213-233.View/Download from: Publisher's site
Proximity graphs are one of the combinatorial data-miner's frontline tools. They allow expression of complex proximity relationships and are the basis of many other algorithms. Here we introduce the concept of proximity graphs, present basic definitions and discuss some of the most common types of proximity graphs.
Mathieson, L, de Vries, NJ & Moscato, P 2019, 'Using Network Alignment to Identify Conserved Consumer Behaviour Modelling Constructs' in Moscato, P & de Vries, NJ (eds), Business and Consumer Analytics: New Ideas, Springer International Publishing, pp. 513-541.View/Download from: Publisher's site
Extracting topological information from networks is a central problem in many fields including business analytics. With the increase in large-scale datasets, effectively comparing similarities and differences between networks is impossible without automation. In some cases, computational search of simple subgraphs is used to understand the structure of a network. These approaches, however, miss the "global picture" of network similarity. Here we examine the Network Alignment problem, in which we look for a mapping between vertex sets of two networks preserving topological information. Elsewhere, we showed that data analytics problems are often of varied computational complexity. We prove that this problem is W-complete for several parameterizations. Since we expect large instances in the data analytics field, our result indicates that this problem is a prime candidate for metaheuristic approaches as it will be hard in practice to solve exact methods. We develop a memetic algorithm and demonstrate the effectiveness of the Network Alignment problem as a tool for discovering structural information through an application in the area of consumer behaviour modelling. We believe this to be the first demonstration of such an approach in the social sciences and in particular a consumer analytics application.
Moscato, P & Mathieson, L 2019, 'Memetic Algorithms for Business Analytics and Data Science: A Brief Survey' in Moscato, P & de Vries, NJ (eds), Business and Consumer Analytics: New Ideas, Springer International Publishing, Switzerland, pp. 545-608.View/Download from: Publisher's site
This chapter reviews applications of Memetic Algorithms in the areas of business analytics and data science. This approach originates from the need to address optimization problems that involve combinatorial search processes. Some of these problems were from the area of operations research, management science, artificial intelligence and machine learning. The methodology has developed considerably since its beginnings and now is being applied to a large number of problem domains. This work gives a historical timeline of events to explain the current developments and, as a survey, gives emphasis to the large number of applications in business and consumer analytics that were published between January 2014 and May 2018.
Mathieson, L, Cotta, C & Moscato, P 2018, 'Memetic Algorithms' in Resende, MGC, Marti, R & Pardalos, PM (eds), Handbook of Heuristics, Springer, Switzerland, pp. 607-638.View/Download from: Publisher's site
Mathieson, L, Mendes, A, Marsden, J, Pond, J & Moscato, P 2017, 'Computer-Aided Breast Cancer Diagnosis with Optimal Feature Sets: Reduction Rules and Optimization Techniques.' in Bioinformatics, Springer, Germany, pp. 299-325.View/Download from: Publisher's site
This chapter introduces a new method for knowledge extraction from databases for the purpose of finding a discriminative set of features that is also a robust set for within-class classification. Our method is generic and we introduce it here in the field of breast cancer diagnosis from digital mammography data. The mathematical formalism is based on a generalization of the k-Feature Set problem called (α, β)-k-Feature Set problem, introduced by Cotta and Moscato (J Comput Syst Sci 67(4):686-690, 2003). This method proceeds in two steps: first, an optimal (α, β)-k-feature set of minimum cardinality is identified and then, a set of classification rules using these features is obtained. We obtain the (α, β)-k-feature set in two phases; first a series of extremely powerful reduction techniques, which do not lose the optimal solution, are employed; and second, a metaheuristic search to identify the remaining features to be considered or disregarded. Two algorithms were tested with a public domain digital mammography dataset composed of 71 malignant and 75 benign cases. Based on the results provided by the algorithms, we obtain classification rules that employ only a subset of these features.
Mathieson, L, Gallardo, JE, Cotta, C & Moscato, P 2016, 'Memetic Algorithms: A Contemporary Introduction' in Webster, JG (ed), Wiley Encyclopedia of Electrical and Electronics Engineering, John Wiley & Sons, USA.View/Download from: Publisher's site
Memetic algorithms (MAs) constitute a search and optimization paradigm based on the orchestrated interplay between global and local search components, and have the exploitation of specific problem knowledge as one of their central tenets. MAs can take different forms although a classical incarnation involves the integration of independent search processes within a population-based optimization approach. We discuss this basic structure as well as several of the issues arising in the design process. This paves the way for providing a glimpse of some algorithmic extensions of this basic scheme. After providing an overview of the numerous practical applications of MAs, we close this article with some current perspectives of these techniques.
Pelchen, T, Mathieson, L & Lister, R 2020, 'On the evidence for a learning hierarchy in data structures exams', ACE 2020 - Proceedings of the 22nd Australasian Computing Education Conference, Held in conjunction with Australasian Computer Science Week, pp. 122-131.View/Download from: Publisher's site
© 2020 Association for Computing Machinery. ACM ISBN 978-1-4503-7686-0/20/02...$15.00 Several previous research studies have found a relationship between the ability of novices to trace and explain code, and the ability to write code. Harrington and Cheng refer to that relationship as the Learning Hierarchy. However, almost all of those studies examined students at the end of their first semester of learning to program (i.e. CS1). This paper is only the third paper to describe a study of explain in plain English questions on students at the end of an introductory data structures course. The preceding two papers reached contradictory conclusions. Corney et al. presented results consistent with the Learning Hierarchy identified in the CS1 studies. However, Harrington and Cheng presented results for data structures students suggesting that the hierarchy reversed by the time students had progressed to the level of learning about data structures; that is, tracing and explaining were skills that followed writing. In our study of data structures students, we present results that are consistent with the Learning Hierarchy derived from the CS1 students. We believe that the reversal identified by Harrington and Cheng can occur, but only as a consequence of a mismatch in the relative difficulty of tracing, explaining and writing questions.
Haque, MN, Mathieson, L & Moscato, P 2019, 'A Memetic Algorithm Approach to Network Alignment', The Genetic and Evolutionary Computation Conference, Prague, Czech Republic.View/Download from: UTS OPUS
Ahadi, A & Mathieson, L 2019, 'A Comparison of Three Popular Source code Similarity Tools for Detecting Student Plagiarism', ACE 2019 Proceedings of the 21st Australasian Computing Education Conference, Australasian Computing Education Conference, ACM, Australia, pp. 112-117.View/Download from: Publisher's site
© 2019 Association for Computing Machinery. This paper investigates automated code plagiarism detection in the context of an undergraduate level data structures and algorithms module. We compare three software tools which aim to detect plagiarism in the students' programming source code. We evaluate the performance of these tools on an individual basis and the degree of agreement between them. Based on this evaluation we show that the degree of agreement between these tools is relatively low. We also report the challenges faced during utilization of these methods and suggest possible future improvements for tools of this kind. The discrepancies in the results obtained by these detection techniques were used to devise guidelines for effectively detecting code plagiarism.
Ahadi, A, Lister, R & Mathieson, L 2019, 'ArAl: An Online Tool for Source Code Snapshot Metadata Analysis', Proceedings of the Twenty-First Australasian Computing Education Conference, Australasian Computing Education Conference, ACM, Australia, pp. 118-125.View/Download from: Publisher's site
Haque, MN, Mathieson, L & Moscato, P 2019, 'A Memetic Algorithm Approach to Network Alignment: mapping the classification of mental disorders of DSM-IV with ICD-10', GECCO '19: Proceedings of the Genetic and Evolutionary Computation Conference, The Genetic and Evolutionary Computation Conference, ACM, Prague, Czech Republic, pp. 258-265.View/Download from: Publisher's site
Given two graphs modelling related, but possibly distinct, networks, the alignment of the networks can help identify significant structures and substructures which may relate to the functional purpose of the network components. The Network Alignment Problem is the NP-hard computational formalisation of this goal and is a useful technique in a variety of data mining and knowledge discovery domains. In this paper we develop a memetic algorithm to solve the Network Alignment Problem and demonstrate the effectiveness of the approach on a series of biological networks against the existing state of the art alignment tools. We also demonstrate the use of network alignment as a clustering and classification tool on two mental health disorder diagnostic databases.
Ahadi, A, Lister, R & Mathieson, L 2018, 'Syntax Error Based Quantification of the Learning Progress of the Novice Programmer', 23rd Conference on Innovation and Technology in Computer Science Education, Innovation and Technology in Computer Science Education, The Association for Computing Machinery, Inc., Larnaca, Cyprus, pp. 10-14.View/Download from: Publisher's site
Recent data-driven research has produced metrics for quantifying a novice programmer's error profile, such as Jadud's error quotient. However, these metrics tend to be context dependent and contain free parameters. This paper reviews the caveats of such metrics and proposes a more general approach to developing a metric. The online implementation of the proposed metric is publicly available at http://online-analysis-demo.herokuapp.com/.
Haque, MN, Mathieson, L & Moscato, P 2017, 'A Memetic Algorithm for community detection by maximising the Connected Cohesion', Proceedings of the 2017 IEEE Symposium Series on Computational Intelligence, IEEE Symposium Series on Computational Intelligence, IEEE, Honolulu, Hawaii, USA, pp. 1-8.View/Download from: Publisher's site
Community detection is an exciting field of research
which has attracted the interest of many researchers during the
last decade. While many algorithms and heuristics have been
proposed to scale existing approaches a relatively smaller number
of studies have looked at exploring different measures of quality
of the detected community.
Recently, a new score called 'cohesion' was introduced in the
computing literature. The cohesion score is based comparing the
number of triangles in a given group of vertices to the number
of triangles only partly in that group. In this contribution, we
propose a memetic algorithm that aims to find a subset of the
vertices of an undirected graph that maximizes the cohesion
score. The associated combinatorial optimisation problem is
known to be NP-Hard and we also prove it to be W-hard when
parameterized by the score. We used a Local Search individual
improvement heuristic to expand the putative solution. Then we
removed all vertices from the group which are not a part of
any triangle and expand the neighbourhood by adding triangles
which have at least two nodes already in the group. Finally we
compute the maximum connected component of this group.
The highest quality solutions of the memetic algorithm have
been obtained for four real-world network scenarios and we
compare our results with ground-truth information about the
graphs. We also compare the results to those obtained with eight
other community detection algorithms via interrater agreement
Our results give a new lower bound on the parameterized
complexity of this problem and give novel insights on its poten
de Vries, NJ, Arefin, AS, Mathieson, L, Lucas, B & Moscato, P 2016, 'Relative neighborhood graphs uncover the dynamics of social media engagement', Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), International Conference on Advanced Data Mining and Applications, Springer, Gold Coast, Queensland, Australia, pp. 283-297.View/Download from: Publisher's site
In this paper, we examine if the Relative Neighborhood Graph (RNG) can reveal related dynamics of page-level social media metrics. A statistical analysis is also provided to illustrate the application of the method in two other datasets (the Indo-European Language dataset and the Shakespearean Era Text dataset). Using social media metrics on the world's 'top check-in locations' Facebook pages dataset, the statistical analysis reveals coherent dynamical patterns. In the largest cluster, the categories 'Gym', 'Fitness Center', and 'Sports and Recreation' appear closely linked together in the RNG. Taken together, our study validates our expectation that RNGs can provide a "parameter-free" mathematical formalization of proximity. Our approach gives useful insights on user behaviour in social media page-level metrics as well as other applications.
Mans, B & Mathieson, L 2013, 'On the treewidth of dynamic graphs', Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), pp. 349-360.View/Download from: Publisher's site
Dynamic graph theory is a novel, growing area that deals with graphs that change over time and is of great utility in modelling modern wireless, mobile and dynamic environments. As a graph evolves, possibly arbitrarily, it is challenging to identify the graph properties that can be preserved over time and understand their respective computability. In this paper we are concerned with the treewidth of dynamic graphs. We focus on metatheorems, which allow the generation of a series of results based on general properties of classes of structures. In graph theory two major metatheorems on treewidth provide complexity classifications by employing structural graph measures and finite model theory. Courcelle's Theorem gives a general tractability result for problems expressible in monadic second order logic on graphs of bounded treewidth, and Frick & Grohe demonstrate a similar result for first order logic and graphs of bounded local treewidth. We extend these theorems by showing that dynamic graphs of bounded (local) treewidth where the length of time over which the graph evolves and is observed is finite and bounded can be modelled in such a way that the (local) treewidth of the underlying graph is maintained. We show the application of these results to problems in dynamic graph theory and dynamic extensions to static problems. In addition we demonstrate that certain widely used dynamic graph classes naturally have bounded local treewidth. © 2013 Springer-Verlag Berlin Heidelberg.
Arefin, AS, Inostroza-Ponta, M, Mathieson, L, Berretta, R & Moscato, P 2011, 'Clustering nodes in large-scale biological networks using external memory algorithms', Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), International Conference on Algorithms and Architectures for Parallel Processing, Springer, Melbourne, Australia, pp. 375-386.View/Download from: Publisher's site
Novel analytical techniques have dramatically enhanced our understanding of many application domains including biological networks inferred from gene expression studies. However, there are clear computational challenges associated to the large datasets generated from these studies. The algorithmic solution of some NP-hard combinatorial optimization problems that naturally arise on the analysis of large networks is difficult without specialized computer facilities (i.e. supercomputers). In this work, we address the data clustering problem of large-scale biological networks with a polynomial-time algorithm that uses reasonable computing resources and is limited by the available memory. We have adapted and improved the MSTkNN graph partitioning algorithm and redesigned it to take advantage of external memory (EM) algorithms. We evaluate the scalability and performance of our proposed algorithm on a well-known breast cancer microarray study and its associated dataset. © 2011 Springer-Verlag.
Mathieson, L & Szeider, S 2008, 'Parameterized graph editing with chosen vertex degrees', COMBINATORIAL OPTIMIZATION AND APPLICATIONS, PROCEEDINGS, 2nd International Conference on Combinatorial Optimization and Applications, SPRINGER-VERLAG BERLIN, St Johns, CANADA, pp. 13-22.
Mathieson, L & Szeider, S 2008, 'The parameterized complexity of regular subgraph problems and generalizations', Conferences in Research and Practice in Information Technology Series.
We study variants and generalizations of the problem of finding an r-regular subgraph (where r ≥ 3) in a given graph by deleting at most k vertices. Moser and Thilikos (2006) have shown that the problem is fixed-parameter tractable (FPT) if parameterized by (k, r). They asked whether the problem remains fixed-parameter tractable if parameterized by k alone. We answer this question negatively: we show that if parameterized by k alone the problem is W-hard and therefore very unlikely fixed-parameter tractable. We also give W-hardness results for variants of the problem where the parameter is the number of vertex and edge deletions allowed, and for a new generalized form of the problem where the obtained subgraph is not necessarily regular but its vertices have certain prescribed degrees. Following this we demonstrate fixed-parameter tractability for the considered problems if the parameter includes the regularity r or an upper bound on the prescribed degrees in the generalized form of the problem. These FPT results are obtained via kernelization, so also provide a practical approach to the problems presented. © 2008, Australian Computer Society, Inc.
Moscato, P, Mathieson, L, Mendes, A & Berretta, R 2005, 'The electronic primaries: Predicting the U.S. Presidency using feature selection with safe data reduction', Conferences in Research and Practice in Information Technology Series, pp. 371-380.
The data mining inspired problem of finding the critical, and most useful features to be used to classify a data set, and construct rules to predict the class of future examples is an interesting and important problem. It is also one of the most useful problems with applications in many areas such as microarray analysis, genomics, proteomics, pattern recognition, data compression and knowledge discovery. Expressed as κ-Feature Set it is also a formally hard problem. In this paper we present a method for coping with this hardness using the combinatorial optimisation and parameterized complexity inspired technique of sound reduction rules. We apply our method to an interesting data set which is used to predict the winner of the popular vote in the U.S. presidential elections. We demonstrate the power and exibility of the reductions, especially when used in the context of the (α β)κ-Feature Set variant problem. Copyright © 2005, Australian Computer Society, Inc.
Mathieson, L, King, T & Brankovic, L 2004, '2-Compromise: usability in 1-dimensional statistical database', Fifteenth Australasian Workshop on Combinatorial Algorithms, pp. 5-15.
Mathieson, L, Prieto, E & Shaw, P 2004, 'Packing edge disjoint triangles: A parameterized view', PARAMETERIZED AND EXACT COMPUTATION, PROCEEDINGS, 1st International Conference on Parameterized and Exact Computation (IWPEC 2004), SPRINGER-VERLAG BERLIN, Bergen, NORWAY, pp. 127-137.
Casteigts, A, Mans, B & Mathieson, L 2012, 'On the Feasibility of Maintenance Algorithms in Dynamic Graphs'.
Near ubiquitous mobile computing has led to intense interest in dynamic graph
theory. This provides a new and challenging setting for algorithmics and
complexity theory. For any graph-based problem, the rapid evolution of a
(possibly disconnected) graph over time naturally leads to the important
complexity question: is it better to calculate a new solution from scratch or
to adapt the known solution on the prior graph to quickly provide a solution of
guaranteed quality for the changed graph?
In this paper, we demonstrate that the former is the best approach in some
cases, but that there are cases where the latter is feasible. We prove that,
under certain conditions, hard problems cannot even be approximated in any
reasonable complexity bound --- i.e., even with a large amount of time, having
a solution to a very similar graph does not help in computing a solution to the
current graph. To achieve this, we formalize the idea as a maintenance
algorithm. Using r-Regular Subgraph as the primary example we show that
W-hardness for the parameterized approximation problem implies the
non-existence of a maintenance algorithm for the given approximation ratio.
Conversely we show that Vertex Cover, which is fixed-parameter tractable, has a
2-approximate maintenance algorithm. The implications of NP-hardness and
NPO-hardness are also explored.
Mathieson, L 2012, 'A Proof Checking View of Parameterized Complexity'.
The PCP Theorem is one of the most stunning results in computational
complexity theory, a culmination of a series of results regarding proof
checking it exposes some deep structure of computational problems. As a
surprising side-effect, it also gives strong non-approximability results. In
this paper we initiate the study of proof checking within the scope of
Parameterized Complexity. In particular we adapt and extend the PCP[n log log
n, n log log n] result of Feige et al. to several parameterized classes, and
discuss some corollaries.