TITLE: Groups of deficiency zero
AUTHORS: George Havas, M.F. Newman and E.A. O'Brien
CITATION: Geometric and Computational Perspectives on Infinite
Groups, DIMACS Series in Discrete Mathematics and Theoretical Computer
Science 25 (1996) 53-67
REVIEWS:
Math. Rev. 96h:20063 (S.C. Althoen); Zbl. 960.14728 (E. Khukhro)
ABSTRACT: We make a systematic study of groups of deficiency
zero, concentrating on groups of prime-power order. We prove that a
number of p-groups have deficiency zero and give explicit balanced
presentations for them. This significantly increases the number of such
groups known. We describe a reasonably general computational approach
which leads to these results. We also list some other finite groups of
deficiency zero.
TITLE:
A new algorithm and refined bounds for extended gcd computation
AUTHORS: David Ford and George Havas
CITATION: Algorithmic Number Theory, Lecture Notes in
Computer Science 1122 (1996) 145-150
ABSTRACT: Extended gcd computation is interesting itself. It also
plays a fundamental role in other calculations. We present a new
algorithm for solving the extended gcd problem. This algorithm has a
particularly simple description and is practical. It also provides
refined bounds on the size of the multipliers obtained.
TITLE:
Central factors of deficiency zero groups
AUTHORS: George Havas and Edmund F. Robertson
CITATION: Communications in Algebra 24 (1996) 3483-3487
ABSTRACT: We answer a question of some twenty years standing: are
the central factors of nilpotent groups of deficiency zero 3-generated?
We prove a negative answer by giving an explicit presentation for a
3-generator, 3-relator group of order 131072 and class 5 which has
central factors which are 4-generated but not 3-generated. We outline
the computational techniques which lead to this result.
TITLE:
Empirical analysis of distributed depth-first search algorithms
AUTHORS: S.A.M. Makki and George Havas
CITATION: Proc. Eighth IASTED Internat. Conf. Parallel and
Distributed Computing and Systems, Acta Press (1996) 292-296
ABSTRACT: We evaluate the practical performance of two improved
distributed depth-first search algorithms applied to general and
commonly used network structures. In particular we study the behavior of
the algorithms in terms of a parameter which depends on the network
topology and routing chosen. We deduce that performance is
significantly enhanced for smaller networks of sizes which arise in
practice. With increasing network size the extended version of the
algorithm performs appreciably better than the basic algorithm. We
present some unresolved questions about these algorithms.
TITLE: A family of perfect hashing methods
AUTHORS:
Bohdan S. Majewski, Nicholas C. Wormald, George Havas and Zbigniew J. Czech
CITATION: Computer Journal 39 (1996) 547-554
ABSTRACT: Minimal perfect hash functions are used for memory efficient
storage and fast retrieval of items from static sets. We present an infinite
family of efficient and practical algorithms for generating order preserving
minimal perfect hash functions. We show that almost all members of the
family construct space and time optimal order preserving minimal perfect
hash functions, and we identify the one with minimum constants. Members
of the family generate a hash function in two steps. First a special kind
of function into an r-graph is computed probabilistically. Then this function
is refined deterministically to a minimal perfect hash function. We give
strong theoretical evidence that the first step uses linear random time.
The second step runs in linear deterministic time. The family not only
has theoretical importance, but also offers the fastest known method for
generating perfect hash functions.
TITLE:
Distributed algorithms for depth-first search
AUTHORS: S.A.M. Makki and George Havas
CITATION: Information Processing Letters 60 (1996) 7-12
ABSTRACT: We present distributed algorithms for constructing a
depth-first search tree for a communication network which are more
efficient than previous methods. Our algorithms require 2|V|-2 messages
and units of time in the worst case, where |V| is the number of sites in
the network, and as little as |V| messages and time units in the best
case. The actual number of messages and time units depends on the
network topology and possibly on the routing chosen. We can interpret
this to mean that the number of messages and time units is |V|(1+r) in
the worst case, where 0<=r<1 and the value of r depends on the
topology and the routing. In a best case for the simplest algorithm, for
example when the underlying network has a ring topology, r=0 and our
basic algorithm requires |V| messages and time units, regardless of
routing. We extend the basic algorithm to achieve the same best case
bound for other topologies. The worst case bound, which has r=1-2/|V|,
applies if the network topology is a tree. The improvement over the
best of previous algorithms is achieved by dynamic backtracking, with a
minor increase in message length.
TITLE: Integer matrix diagonalization
AUTHORS: George Havas and Bohdan S. Majewski
CITATION: Journal of Symbolic Computation 24
(1997) 399-408.
ABSTRACT: We consider algorithms for computing the Smith normal
form of integer matrices. Various different strategies have been
proposed, primarily trying to avoid the major obstacle that occurs in
such computations -- explosive growth in size of intermediate entries.
We present a new algorithm with excellent performance. We investigate
the complexity of such computations, indicating a relationship with an
NP-complete problem. On the other hand we prove that a substantial part
of Smith normal form computation can be performed in an optimal way in
polynomial time. Based on this we justify our new heuristics which
perform well in practice. We present experimental evidence which shows
our algorithm outperforming the previous methods.
TITLE: Practical parallel coset enumeration
AUTHORS: Gene Cooperman and George Havas
CITATION: Workshop on High Performance Computing and Gigabit Local
Area Networks, Lecture Notes in Control and Information Sciences 226
(1997) 15-27
ABSTRACT: Coset enumeration is a most important procedure for
investigating finitely presented groups. We present a practical parallel
procedure for coset enumeration on shared memory processors. The shared
memory architecture is particularly interesting because such parallel
computation is both faster and cheaper. The lower cost comes when the
program requires large amounts of memory, and additional CPU's allow us
to lower the time that the expensive memory is being used. Rather than
report on a suite of test cases, we take a single, typical case, and
analyze the performance factors in-depth. The parallelization is
achieved through a master-slave architecture. This results in an
interesting phenomenon, whereby the CPU time is divided into a
sequential and a parallel portion, and the parallel part demonstrates a
speedup that is linear in the number of processors. We describe an early
version for which only 40% of the program was parallelized, and we
describe how this was modified to achieve 90% parallelization while
using 15 slave processors and a master.
TITLE: Perfect hashing
AUTHORS: Zbigniew J. Czech, George Havas and Bohdan S. Majewski
CITATION: Theoretical Computer Science 182 (1997) 1-143
AWARD:The authors received awards for this
paper from the Polish National Minister for Education
CONTENTS:
TITLE:
An efficient method for constructing a distributed depth-first search tree
AUTHORS: S.A.M. Makki and George Havas
CITATION: PDPTA'97 (Proc. Internat. Conf. Parallel and
Distributed Processing Techniques and Applications), CSREA Press (1997)
660-666
ABSTRACT:
An efficient distributed depth-first search algorithm is presented.
The algorithm in the worst case requires (1+r)(|V|-1) messages and
(1+r)(|V|-1) units of time, where 0<=r<1 and |V| is the number
of sites in the network. The value of r depends on the search path and
the graph topology. In the best case when r=0, the algorithm requires
only |V|-1 messages and time units. This new algorithm improves
over the best of previous algorithms by using a stack-type structure
which enables better dynamic backtracking. The improvement in worst
case complexity is only minor. However it is much better in practice,
manifested by significantly smaller values of r.
TITLE: On the worst-case complexity of integer Gaussian elimination
AUTHORS: Xin Gui Fang and George Havas
CITATION: ISSAC'97 (Proc. 1997 Internat. Sympos. on
Symbolic and Algebraic Computation), ACM Press (1997) 28-31
ABSTRACT:
Gaussian elimination is the basis for classical algorithms for
computing canonical forms of integer matrices. Experimental results
have shown that integer Gaussian elimination may lead to rapid growth
of intermediate entries. On the other hand various polynomial time
algorithms do exist for such computations, but these algorithms are
relatively complicated to describe and understand. Gaussian
elimination provides the simplest descriptions of algorithms for this
purpose. These algorithms have a nice polynomial number of steps, but
the steps deal with long operands. Here we show that there is an
exponential length lower bound on the operands for a well-defined
variant of Gaussian elimination when applied to Smith and Hermite
normal form calculation. We present explicit matrices for which this
variant produces exponential length entries. Thus, Gaussian
elimination has worst-case exponential space and time complexity for
such applications. The analysis provides guidance as to how integer
matrix algorithms based on Gaussian elimination may be further
developed for better performance, which is important since many
practical algorithms for computing canonical forms are so based.
TITLE: Counting trees
AUTHORS: George Havas, Dean G. Hoffman and Colin Ramsay
CITATION: Research on Combinatorial Algorithms (Proc. Eighth
Australasian Workshop on Combinatorial Algorithms), Queensland
University of Technology (1997) 1-10
ABSTRACT:
We consider the problem of enumerating particular kinds of spanning
trees of a graph. The problem is interesting in its own right and has
applications in the analysis of graph algorithms. The general problem
seems hard to resolve. We present an algorithm to list depth-first trees
for moderate sized graphs. We use this algorithm to count the number
of depth-first spanning trees in a variety of graphs, and we give the
results for hypercubes, meshes and tori, and complete bipartite graphs.
We also give a proof of a theoretical result for complete multipartite
graphs.
TITLE: NC Approximation Algorithms for 2-Connectivity Augmentation in
A Graph
AUTHORS: Weifa Liang and George Havas
CITATION: Euro-Par'97 Parallel Processing ,
Lecture Notes in Computer Science 1300 (1997) 430-439.
ABSTRACT:
We devise NC approximation algorithms for the optimal 2-edge
connectivity and the optimal 2-vertex connectivity augmentation problems.
Consequently, we find an approximation solution for the problem of the
minimum 2-edge (biconnected) spanning subgraph on a weighted 2-edge
connected (biconnected) graph.
TITLE: Parallel approximate edge coloring revisited
AUTHORS: Weifa Liang, George Havas and Anne Street
CITATION: Proceedings of PART'97: The 4th Australasian Conference on
Parallel and Real-Time Systems, Springer-Verlag (1998) 95-103.
ABSTRACT:
This paper presents a fast NC algorithm for edge coloring a graph
with an approximately optimal number of colors.
TITLE: Finding the k most vital edges with respect to minimum
spanning trees for k=2 and 3
AUTHORS: Weifa Liang and George Havas
CITATION: Computing Theory '98 (Proc. 4th Australasian Theory
Symposium), Springer Verlag (1998) 37-50.
ABSTRACT:
Let G(V,E) be a weighted, undirected, connected simple graph with n
vertices and m edges. The k most vital edge problem with respect
to minimum spanning trees is to find a set S of k edges from E
such that the removal of all edges in S results in the greatest
increase in the weight of the minimum spanning tree in the remaining
graph G(V,E-S). In this paper we present a better algorithm to
solve this problem for k=2 and 3. The algorithms can also be implemented
on a CREW PRAM.
TITLE:
Symmetric presentations and orthogonal groups
AUTHORS: C.M. Campbell, George Havas, S.A. Linton and E.F. Robertson
CITATION: The Atlas of Finite Groups: Ten Years On,
London Mathematical Society Lecture Note Series 249,
Cambridge University Press (1998) 1-10.
ABSTRACT: We examine series of finite presentations which are
invariant under the full symmetric group acting on the set of
generators. Evidence from computational experiments reveals a remarkable
tendency for the groups in these series to be closely related to the
orthogonal groups. We examine cases of finite groups in such series and
look in detail at an infinite group with such a presentation. We prove
some theoretical results about 3-generator symmetric presentations and
make a number of conjectures regarding n-generator symmetric
presentations.
TITLE:
Extended gcd and Hermite normal form algorithms via lattice basis reduction
AUTHORS: George Havas, Bohdan S. Majewski and Keith R. Matthews
CITATION: Experimental Mathematics 7 (1998) 125-136
(Addenda and errata: Experimental Mathematics 8 (1999) 205)
ABSTRACT:
Extended gcd calculation has a long history and plays an important role
in computational number theory and linear algebra. Recent results have
shown that finding optimal multipliers in extended gcd calculations is
difficult. We present an algorithm which uses lattice basis reduction to
produce small integer multipliers x1,...,xm for the
equation s=gcd(s1,...,sm)=
x1s1+...+xmsm,
where s1,...,sm are given integers. The method
generalises to produce small unimodular transformation matrices for
computing the Hermite normal form of an integer matrix.
TITLE:
Improved Lightpath (Wavelength) Routing in Large WDM Networks
AUTHORS: Weifa Liang, George Havas and Xiaojun Shen
CITATION: Proc. 18th International Conference on Distributed
Computing Systems, IEEE Computer Society (1998) 516-523
ABSTRACT:
We address the problem of efficient circuit
switching in wide area networks. The solution provided is based on
finding optimal routes for lightpaths and semilightpaths. A lightpath
is a fully optical transmission path, while a semilightpath is a
transmission path constructed by chaining several lightpaths together,
using wavelength conversion at their junctions. The problem thus is to
find an optimal lightpath/semilightpath in the network in terms of the
cost of wavelength conversion and the cost of using the wavelengths on
links. We first present fast, efficient algorithms both for the
general problem and for a natural restricted version.
The new algorithms outperform earlier work, providing time improvements
amounting to an almost linear time factor in most cases. Also, all our
algorithms can be implemented on the network in a distributed way.
TITLE: Matrix reduction algorithms for Euclidean rings
AUTHORS: George Havas and Clemens Wagner
CITATION: Proc. 1998 Asian Symposium on Computer Mathematics,
Lanzhou University Press (1998) 65-70
ABSTRACT:
Reduction methods are the basis of algorithms for determining canonical
forms of matrices over many computational domains. Experimental results
have shown that various methods based on Gaussian elimination (which
is a specialized kind of reduction algorithm) in Euclidean rings may
lead to rapid growth of intermediate entries. On the other hand
polynomial time algorithms do exist for such computations, but these
algorithms are relatively complicated to describe and understand.
Straightforward reduction methods provide the simplest descriptions of
algorithms for this purpose. Such algorithms have a nice polynomial
number of steps, but the steps may deal with operands with very large
values. Here we show that there is a doubly exponential lower bound
on the operands for a well-defined reduction algorithm when applied
to Smith and Hermite normal form calculation for certain Euclidean
rings. We present explicit matrices for which this variant produces
doubly exponential entries. Thus, reduction algorithms have worst-case
exponential space and time complexity for such applications. The analysis
provides guidance as to how matrix algorithms for Euclidean rings which
use reduction algorithms may be further developed for better performance,
which is important since many practical algorithms for computing canonical
forms are so based.
TITLE: Functional decomposition of a class of wild polynomials
AUTHORS: Robert Coulter, George Havas and Marie Henderson
CITATION: Journal of Combinatorial Mathematics and Combinatorial
Computing 28 (1998) 87-94
ABSTRACT:
No general algorithm is known for the functional decomposition of wild
polynomials over a finite field. However partial solutions exist. In
particular, a fast functional decomposition algorithm for linearised
polynomials has been developed using factoring methods in skew-polynomial
rings. This algorithm is extended to a related class of wild polynomials,
which are sub-linearised polynomials.
TITLE: Elementary Algebra Revisited: Randomized Algorithms
AUTHORS: Gene Cooperman and George Havas
CITATION: Randomization Methods in Algorithm Design,
DIMACS Series in Discrete Mathematics and Theoretical Computer Science
43 (1999) 37-44
ABSTRACT:
We look at some simple algorithms for elementary problems in algebra
that yield dramatic efficiency improvements over standard methods
through randomization. The randomized algorithms are, in some sense,
obvious. Their formal statement was delayed partly by the need
for rigorous analysis, but more so by the need to re-think traditional
approaches to elementary algorithms. We illustrate this philosophy
with some basic problems in computational number theory (GCD of many
integers), linear algebra (low-rank Gaussian elimination) and group
theory (random subproducts for subgroup construction), along with a
brief survey of other areas.
TITLE:
Automorphism groups of certain non-quasiprimitive almost simple graphs
AUTHORS: Xin Gui Fang, George Havas and Jie Wang
CITATION: Groups St Andrews 1997 in Bath, I,
London Mathematical Society Lecture Note Series 260,
Cambridge University Press (1999) 267-274
ABSTRACT:
A graph GAMMA is G-quasiprimitive if G is a group of automorphisms
of GAMMA such that each nontrivial normal subgroup of G acts
transitively on the vertices of GAMMA. We consider GAMMA a finite,
connected S-locally-primitive graph with S a nonabelian simple group.
We give a set of conditions under which we may guarantee that either
the full automorphism group of GAMMA is not quasiprimitive or there is a
non-quasiprimitive subgroup Y of Aut(GAMMA) such that C.G is maximal in Y,
where C is the centralizer of S in Aut(GAMMA) and G is an almost simple
group with socle S. As an application of this result we show that,
in certain circumstances, we can specify Aut(GAMMA).
TITLE: GCD of many integers
AUTHORS:
Gene Cooperman, Sandra Feisel, Joachim von zur Gathen and George Havas
CITATION: Computing and Combinatorics,
Lecture Notes in Computer Science 1627 (1999) 310-317
ABSTRACT:
A probabilistic algorithm is exhibited that calculates the gcd of
many integers using gcds of pairs of integers; the expected number
of pairwise gcds required is less than two.
TITLE: On routing in circulant graphs
AUTHORS: Jin-Yi Cai, George Havas, Bernard Mans, Ajay Nerurkar,
Jean-Pierre Seifert and Igor Shparlinski
CITATION: Computing and Combinatorics,
Lecture Notes in Computer Science 1627 (1999) 360-369
ABSTRACT:
We investigate various problems related to circulant graphs -- finding
the shortest path between two vertices, finding the shortest loop, and
computing the diameter. These problems are related to shortest vector
problems in a special class of lattices. We give matching upper and
lower bounds on the length of the shortest loop. We prove NP-hardness
results, and establish a worst-case/average-case connection for the
shortest loop problem. A pseudo-polynomial time algorithm for these
problems is also given. Our main tools are results and methods from
the geometry of numbers.
TITLE: Groups with exponent six
AUTHORS:
George Havas, M.F. Newman, Alice C. Niemeyer and Charles C. Sims
CITATION: Communications in Algebra 27 (1999) 3619-3638
ABSTRACT:
Burnside asked questions about periodic groups in his influential paper of
1902. The study of groups with exponent six is a special case of the study
of the Burnside questions on which there has been significant progress.
It has contributed a number of worthwhile aspects to the theory of
groups and in particular to computation related to groups. Finitely
generated groups with exponent six are finite. We investigate the nature
of relations required to provide proofs of finiteness for some groups
with exponent six. We give upper and lower bounds for the number of sixth
powers needed to define the largest two-generator group with exponent
six. We solve related questions about other groups with exponent six
using substantial computations which we explain.
TITLE: A Family of Non-Quasiprimitive Graphs
Admitting a Quasiprimitive 2-Arc Transitive Group Action
AUTHORS: Xin Gui Fang, George Havas and Jie Wang
CITATION: European Journal of Combinatorics 20 (1999) 551-557.
ABSTRACT:
Let GAMMA be a simple graph and let G be a group of automorphisms of
GAMMA. The graph is (G,2)-arc transitive if G is transitive on the set
of the 2-arcs of GAMMA. In this paper we construct a new family of
PSU(3,q2) 2-arc transitive graphs GAMMA of valency 9 such
that Aut(GAMMA)=Z3.G, for some almost simple group G with
socle PSU(3,q2). This gives a new infinite family of
non-quasiprimitive almost simple graphs.
TITLE: On Sims' presentation for Lyons' simple group
AUTHORS: Holger W. Gollan and George Havas
CITATION: Computational Methods for Representations of Groups and
Algebras, Progress in Mathematics 173 (1999) 235-240, Birkhaeuser
ABSTRACT: This paper gives a verification that the corrected
Sims presentation is indeed a presentation of Lyons simple group. We
prove that Lyons original characterization of his new simple group works
inside a permutation group of degree 8,835,156.
TITLE: A presentation for the Lyons simple group
AUTHORS: George Havas and Charles C. Sims
CITATION: Computational Methods for Representations of Groups and
Algebras, Progress in Mathematics 173 (1999) 241-249, Birkhaeuser
ABSTRACT: We give a presentation of the Lyons simple group
together with information on a complete computational proof that the
presentation is correct. This fills a longstanding gap in the literature
on the sporadic simple groups. This presentation is a basis for various
matrix and permutation representations of the group.
TITLE: Some challenging group presentations
AUTHORS: George Havas, Derek F. Holt, P.E. Kenne and Sarah Rees
CITATION: Journal of the Australian Mathematical Society (Series A)
67 (1999) 206-213
ABSTRACT: We study four challenging presentations which arise as
groups of deficiency zero. We show that two presentations are for finite
groups while two are for infinite groups. This answers three questions
in the literature and provides the first published example of a group of
deficiency zero with soluble length seven. The tools we use are coset
enumeration and Knuth-Bendix rewriting, which are well-established as
methods for proving finiteness or otherwise of a finitely presented group.
We briefly comment on their capabilities and compare their performance.
TITLE: The complexity of the extended GCD problem
AUTHORS: George Havas and Jean-Pierre Seifert
CITATION: Mathematical Foundations of Computer Science 1999,
Lecture Notes in Computer Science 1672 (1999) 103-113
ABSTRACT:
We undertake a thorough complexity study of the following fundamental
optimization problem, known as the lp-norm shortest Extended
GCD multiplier problem:
given a1,...,an in Z, find an lp-norm
shortest gcd multiplier for a1,...,an, i.e., a vector
x in Zn with minimum
sum(|xi|p)1/p
satisfying sum(xiai) =
gcd(a1,...,an).
First, we prove that the shortest GCD multiplier problem (in its feasibility recognition form) is NP-complete for every lp-norm with p in N. We then strengthen this negative result by ruling out even polynomial-time algorithms which only approximate an lp-norm shortest gcd multiplier within a factor n1/(p logg n), for g an arbitrary small positive constant, under the widely accepted complexity theory assumption NP not in DTIME(npoly(log n)).
For positive results we focus on the l2-norm GCD multiplier problem. We show that approximating this problem within a factor of n1/2 is very unlikely NP-hard by placing it in NP intersection coAM through a simple constant-round interactive proof system. This result is complemented by a polynomial-time algorithm which computes an l2-norm shortest gcd multiplier up to a factor of 2(n-1)/2.
This study is motivated by the importance of extended gcd calculations in applications in computational algebra and number theory. Our results rest upon the close connection between the hardness of approximation and the theory of interactive proof systems.
TITLE: Some Performance Studies in Exact Linear Algebra
AUTHORS: George Havas and Clemens Wagner
CITATION: Distributed high performance computing and gigabit wide
area networks, Lecture Notes in Control and Information Sciences 249
(1999) 161-170
ABSTRACT:
We consider parallel algorithms for computing the Hermite normal form
of matrices over Euclidean rings. We use standard types of reduction methods
which are the basis of many algorithms for determining canonical forms
of matrices over various computational domains. Our implementations
take advantage of well-performing sequential code and give very good
performance.
TITLE:
On the automorphism groups of quasiprimitive almost simple graphs
AUTHORS: Xin Gui Fang, George Havas and Cheryl E. Praeger
CITATION: Journal of Algebra 222 (1999) 271-283
ABSTRACT:
A permutation group is said to be quasiprimitive if each of its nontrivial
normal subgroups is transitive. A graph GAMMA is G-quasiprimitive if G is
a group of automorphisms of GAMMA such that G acts quasiprimitively on the
vertices of GAMMA. In this paper we assume that G is is an almost simple
group and investigate the full automorphism group of a G-quasiprimitive
graph GAMMA. We show that, for a connected nonbipartite G-quasiprimitive
and G-locally-primitive graph GAMMA with G almost simple one of the
following three situations holds: Aut(GAMMA) is quasiprimitive; or each
intransitive minimal normal subgroup of Aut(GAMMA) centralizes the socle
of G; or G is an almost simple group of Lie type of characteristic
p, and the socle of Aut(GAMMA) involves an explicitly known faithful
GF(p)G-module M, with G, M belonging to a (short) explicit list.
TITLE:
Finding a Low-Diameter and Low-Weight k-Connected Subgraph
AUTHORS: Weifa Liang, George Havas and Anne Street
CITATION: Congressus Numerantium 136 (1999) 161-175
ABSTRACT:
Low-diameter, low-weight subgraphs have useful applications in
networks. The problem is how to find them. Given a weighted undirected
k-connected graph G=(V,E), let diam(G) denote the diameter of G and let
w(G) the sum of the weights of the edges in G. In this context, the
problem is to find a k-connected spanning subgraph G'=(V,E') of G such
that the diameter and the weight of G' are minimized simultaneously.
Since this problem is NP-hard, it is unlikely that there is a
polynomial algorithm for it. We present an approximate solution with
a performance guarantee. That is, we find a k-connected spanning
subgraph G' in polynomial time such that diam(G')<=a×diam(G)
and w(G')<=b×w(G*) for any fixed a>1, where G* is a minimum
k-connected spanning subgraph of G and b is a constant depending on a
and k.
