Are linear algorithms always good for linear problems?

We exhibit linear problems for which every linear algorithm has infinite error, and show a (mildly) nonlinear algorithm with finite error. The error of this nonlinear algorithm can be arbitrarily small if appropriate information is used. We illustrate these examples by the inversion of a finite Laplace transform, a problem arising in remote sensing.     

Error bounds and parameter choice strategies for simplified regularization in Hilbert scales

Simplified regularization in the setting of Hilbert scales has been considered for obtaining stable approximate solutions for ill-posed operator equations. The derived error estimates using an a posteriori as well as an a priori parameter choice strategy are shown to be of optimal order with respect to certain natural assumptions on the ill-posedness of the equation.The work of M. Thamban Nair is partially supported by IC&SR, I.I.T., Madras     

Optimal order results for a class of regularization methods using unbounded operators

A class of regularization methods using unbounded regularizing operators is considered for obtaining stable approximate solutions for ill-posed operator equations. With an a posteriori as well as an a priori parameter choice strategy, it is shown that the method yields the optimal order. Error estimates have also been obtained under stronger assumptions on the generalized solution. The results of the paper unify and simplify many of the results available in the literature. For example, the optimal results of the paper include, as particular cases for Tikhonov regularization, the main result of Mair (1994) with an a priori parameter choice, and a result of Nair (1999) with an a posteriori parameter choice. Thus the observations of Mair (1994) on Tikhonov regularization of ill-posed problems involving finitely and infinitely smoothing operators is applicable to various other regularization procedures as well. Subsequent results on error estimates include, as special cases, an optimal result of Vainikko (1987) and also some recent results of Tautenhahn (1996) in the setting of Hilbert scales.     

The h-p version of the coupling of finite element and boundary element methods for transmission problems in polyhedral domains

Summary. This paper analyzes the rate of convergence of the h-p version of the coupling of the finite element and boundary element method for transmission problems with a linear differential operator with variable coefficients in a bounded polyhedral domain and with constant coefficients in the exterior domain . This procedure uses the variational formulation of the differential equation in and involves integral operators on the interface between and . The finite elements are used to obtain approximate solutions of the differential equation in and the boundary elements are used to obtain approximate solutions of the integral equations. For given piecewise analytic data we show that the Galerkin solution of this coupling procedure converges exponentially fast in the energy norm if the h-p version is used both for finite elements and boundary elements. Received February 10, 1996 / Revised version received April 4, 1997     

The elimination procedure for the competition number is not optimal

Given an acyclic digraph D, the competition graph C(D) is defined to be the undirected graph with V(D) as its vertex set and where vertices x and y are adjacent if there exists another vertex z such that the arcs (x,z) and (y,z) are both present in D. The competition number k(G) for an undirected graph G is the least number r such that there exists an acyclic digraph F on |V(G)|+r vertices where C(F) is G along with r isolated vertices. Kim and Roberts [The Elimination Procedure for the Competition Number, Ars Combin. 50 (1998) 97-113] introduced an elimination procedure for the competition number, and asked whether the procedure calculated the competition number for all graphs. We answer this question in the negative by demonstrating a graph where the elimination procedure does not calculate the competition number. This graph also provides a negative answer to a similar question about the related elimination procedure for the phylogeny number introduced by the current author in [S.G. Hartke, The Elimination Procedure for the Phylogeny Number, Ars Combin. 75 (2005) 297-311].     

Recognizing graphic matroids

There is no polynomially bounded algorithm to test if a matroid (presented by an “independence oracle”) is binary. However, there is one to test graphicness. Finding this extends work of previous authors, who have given algorithms to test binary matroids for graphicness. Our main tool is a new result that ifM′ is the polygon matroid of a graphG, andM is a different matroid onE(G) with the same rank, then there is a vertex ofG whose star is not a cocircuit ofM.     

Mutual exclusion scheduling with interval graphs or related classes. Part II

This paper is the second part of a study devoted to the mutual exclusion scheduling problem. Given a simple and undirected graph G and an integer k, the problem is to find a minimum coloring of G such that each color is used at most k times. The cardinality of such a coloring is denoted by χ(G,k). When restricted to interval graphs or related classes like circular-arc graphs and tolerance graphs, the problem has some applications in workforce planning. Unfortunately, the problem is shown to be NP-hard for interval graphs, even if k is a constant greater than or equal to four [H.L. Bodlaender, K. Jansen, Restrictions of graph partition problems. Part I. Theoret. Comput. Sci. 148 (1995) 93-109]. In this paper, the problem is approached from a different point of view by studying a non-trivial and practical sufficient condition for optimality. In particular, the following proposition is demonstrated: if an interval graph G admits a coloring such that each color appears at least k times, then χ(G,k)=⌈n/k⌉. This proposition is extended to several classes of graphs related to interval graphs. Moreover, all our proofs are constructive and provide efficient algorithms to solve the MES problem for these graphs, given a coloring satisfying the condition in input.     

An infinite family of tetravalent half-arc-transitive graphs

A graph is half-arc-transitive if its automorphism group acts transitively on vertices and edges, but not on arcs. In this paper, a new infinite family of tetravalent half-arc-transitive graphs with girth 4 is constructed, each of which has order 16m such that m>1 is a divisor of 2t²+2t+1 for a positive integer t and is tightly attached with attachment number 4m. The smallest graph in the family has order 80.     

On the maximum cardinality search lower bound for treewidth

The Maximum Cardinality Search (MCS) algorithm visits the vertices of a graph in some order, such that at each step, an unvisited vertex that has the largest number of visited neighbours becomes visited. A maximum cardinality search ordering (MCS-ordering) of a graph is an ordering of the vertices that can be generated by the MCS algorithm. The visited degree of a vertex v in an MCS-ordering is the number of neighbours of v that are before v in the ordering. The visited degree of an MCS-ordering ψ of G is the maximum visited degree over all vertices v in ψ. The maximum visited degree over all MCS-orderings of graph G is called its maximum visited degree. Lucena [A new lower bound for tree-width using maximum cardinality search, SIAM J. Discrete Math. 16 (2003) 345-353] showed that the treewidth of a graph G is at least its maximum visited degree.We show that the maximum visited degree is of size O(logn) for planar graphs, and give examples of planar graphs G with maximum visited degree k with O(k!) vertices, for all k∈N. Given a graph G, it is NP-complete to determine if its maximum visited degree is at least k, for any fixed k?7. Also, this problem does not have a polynomial time approximation algorithm with constant ratio, unless P=NP. Variants of the problem are also shown to be NP-complete.In this paper, we also propose some heuristics for the problem, and report on an experimental analysis of them. Several tiebreakers for the MCS algorithm are proposed and evaluated. We also give heuristics that give upper bounds on the value of the maximum visited degree of a graph, which appear to give results close to optimal on many graphs from real life applications.     

Polynomial time algorithms for recognizing and isomorphism testing of cyclic tournaments

In [3] the problem of finding an efficient criterion for isomorphism testing of cyclic graphs was posed. In the context of the theory of computational complexity the problem reduces to that of the existence of a polynomial-time algorithm for recognizing their isomorphism. The main result of the present paper is an algorithm for finding among all tournaments the cyclic ones. For cyclic tournaments generators of the automorphism group and the set of canonical labels are constructed. The running time of the algorithm is bounded by a polynomial function of the number of input tournament vertices. Thus an affirmative answer to the above problem is obtained.     

Linearity of grid minors in treewidth with applications through bidimensionality

We prove that any H-minor-free graph, for a fixed graph H, of treewidth w has an Ω(w) × Ω(w) grid graph as a minor. Thus grid minors suffice to certify that H-minorfree graphs have large treewidth, up to constant factors. This strong relationship was previously known for the special cases of planar graphs and bounded-genus graphs, and is known not to hold for general graphs. The approach of this paper can be viewed more generally as a framework for extending combinatorial results on planar graphs to hold on H-minor-free graphs for any fixed H. Our result has many combinatorial consequences on bidimensionality theory, parameter-treewidth bounds, separator theorems, and bounded local treewidth; each of these combinatorial results has several algorithmic consequences including subexponential fixed-parameter algorithms and approximation algorithms. A preliminary version of this paper appeared in the ACM-SIAM Symposium on Discrete Algorithms (SODA 2005) [16].     

Fully-Dynamic Min-Cut*

We show that we can maintain up to polylogarithmic edge connectivity for a fully-dynamic graph in worst-case time per edge insertion or deletion. Within logarithmic factors, this matches the best time bound for 1-edge connectivity. Previously, no o(n) bound was known for edge connectivity above 3, and even for 3-edge connectivity, the best update time was O(n^2/3), dating back to FOCS'92. Our algorithm maintains a concrete min-cut in terms of a pointer to a tree spanning one side of the cut plus ability to list the cut edges in O(log n) time per edge. By dealing with polylogarithmic edge connectivity, we immediately get a sampling based expected factor (1+o(1)) approximation to general edge connectivity in time per edge insertion or deletion. This algorithm also maintains a pointer to one side of a near-minimal cut, but if we want to list the cut edges in O(log n) time per edge, the update time increases to . * A preliminary version of this work was presented at the The 33rd ACM Symposium on Theory of Computing( STOC) [22], Crete, Greece, July 2001.     

Classification of regular embeddings of hypercubes of odd dimension

By a regular embedding of a graph into a closed surface we mean a 2-cell embedding with the automorphism group acting regularly on flags. Recently, Kwon and Nedela [Non-existence of nonorientable regular embeddings of n-dimensional cubes, Discrete Math., to appear] showed that no regular embeddings of the n-dimensional cubes Q_n into nonorientable surfaces exist for any positive integer n>2. In 1997, Nedela and Škoviera [Regular maps from voltage assignments and exponent groups, European J. Combin. 18 (1997) 807-823] presented a construction giving for each solution of the congruence a regular embedding M_e of the hypercube Q_n into an orientable surface. It was conjectured that all regular embeddings of Q_n into orientable surfaces can be constructed in this way. This paper gives a classification of regular embeddings of hypercubes Q_n into orientable surfaces for n odd, proving affirmatively the conjecture of Nedela and Škoviera for every odd n.     

Bounded width problems and algebras

Let be finite relational structure of finite type, and let CSP denote the following decision problem: if is a given structure of the same type as , is there a homomorphism from to ? To each relational structure is associated naturally an algebra whose structure determines the complexity of the associated decision problem. We investigate those finite algebras arising from CSP’s of so-called bounded width, i.e., for which local consistency algorithms effectively decide the problem. We show that if a CSP has bounded width then the variety generated by the associated algebra omits the Hobby-McKenzie types 1 and 2. This provides a method to prove that certain CSP’s do not have bounded width. We give several applications, answering a question of Nešetřil and Zhu [26], by showing that various graph homomorphism problems do not have bounded width. Feder and Vardi [17] have shown that every CSP is polynomial-time equivalent to the retraction problem for a poset we call the Feder − Vardi poset of the structure. We show that, in the case where the structure has a single relation, if the retraction problem for the Feder-Vardi poset has bounded width then the CSP for the structure also has bounded width. This is used to exhibit a finite order-primal algebra whose variety admits type 2 but omits type 1 (provided P ≠ NP). Presented by M. Valeriote. Received January 8, 2005; accepted in final form April 3, 2006. The first author’s research is supported by a grant from NSERC and the Centre de Recherches Mathématiques. The second author’s research is supported by OTKA no. 034175 and 48809 and T 037877. Part of this research was conducted while the second author was visiting Concordia University in Montréal and also when the first author was visiting the Bolyai Institute in Szeged. The support of NSERC, OTKA and the Bolyai Institute is gratefully acknowledged.     

An analysis of the greedy algorithm for the submodular set covering problem

We consider the problem: min \(\{ \mathop \Sigma \limits_{j \in s} f_j :z(S) = z(N),S \subseteqq N\} \) wherez is a nondecreasing submodular set function on a finite setN. Whenz is integer-valued andz(Ø)=0, it is shown that the value of a greedy heuristic solution never exceeds the optimal value by more than a factor \(H(\mathop {\max }\limits_j z(\{ j\} ))\) where \(H(d) = \sum\limits_{i = 1}^d {\frac{1}{i}} \) . This generalises earlier results of Dobson and others on the applications of the greedy algorithm to the integer covering problem: min {fy: Ay ≧b, y ε {0, 1}} wherea _ij ,b _i } ≧ 0 are integer, and also includes the problem of finding a minimum weight basis in a matroid.     

Minimizing the jump number for partially ordered sets: A graph-theoretic approach

The purpose of this paper is to present a graph-theoretic approach to the jump number problem for N-free posets which is based on the observation that the Hasse diagram of an N-free poset is a line digraph. Therefore, to every N-free poset P we can assign another digraph which is the root digraph of the Hasse diagram of P. Using this representation we show that the jump number of an N-free poset is equal to the cyclomatic number of its root digraph and can be found (without producing any linear extension) by an algorithm which tests if a given poset is N-free. Moreover, we demonstrate that there exists a correspondence between optimal linear extensions of an N-free poset and spanning branchings of its root digraph. We provide also another proof of the fact that optimal linear extensions of N-free posets are exactly greedy linear extensions. In conclusion, we discuss some possible generalizations of these results to arbitrary posets.     

Algorithms for inversion of diagonal plus semiseparable operator matrices

LetH be a Hilbert space andRHH be a bounded linear operator represented by an operator matrix which is a sum of a diagonal and of a semiseparable type of order one operator matrices. We consider three methods for solution of the operator equationRx=y. The obtained results yields new algorithms for solution of integral equations and for inversion of matrices.     

Automorphism groups of comparability and covering graphs

Let G be a group and H a subgroup of G. It is shown that there exists a partially ordered set (X, ) such that G is isomorphic to the group of all automorphisms of the comparability graph of (X, ) and such that under this isomorphism H is mapped onto the group of all order-automorphisms of (X, ). There also exists a partially ordered set (Y, ) such that G is isomorphic to the group of all automorphisms of the covering graph of (Y, ) and such that under this isomorphism H is mapped onto the group of all order-automorphisms of (Y, ). In this representation X and Y can be taken to be finite if G is finite and of the same cardinality as G if G is infinite.     

Highly Arc-Transitive Digraphs With No Homomorphism Onto <Emphasis Type="Bold">Z</Emphasis>

In an infinite digraph D, an edge e' is reachable from an edge e if there exists an alternating walk in D whose initial and terminal edges are e and e'. Reachability is an equivalence relation and if D is 1-arc-transitive, then this relation is either universal or all of its equivalence classes induce isomorphic bipartite digraphs. In Combinatorica, 13 (1993), Cameron, Praeger and Wormald asked if there exist highly arc-transitive digraphs (apart from directed cycles) for which the reachability relation is not universal and which do not have a homomorphism onto the two-way infinite directed path (a Cayley digraph of Z with respect to one generator). In view of an earlier result of Praeger in Australas. J. Combin., 3 (1991), such digraphs are either locally infinite or have equal in- and out-degree. In European J. Combin., 18 (1997), Evans gave an affirmative answer by constructing a locally infinite example. For each odd integer n >= 3, a construction of a highly arc-transitive digraph without property Z satisfying the additional properties that its in- and out-degree are equal to 2 and that the reachability equivalence classes induce alternating cycles of length 2n, is given. Furthermore, using the line digraph operator, digraphs having the above properties but with alternating cycles of length 4 are obtained. Received April 12, 1999 Supported in part by "Ministrstvo za šolstvo, znanost in šport Slovenije", research program PO-0506-0101-99.     

Distributed near-optimal matching

In this paper, we consider the following distributed bipartite matching problem: LetG=(L,R;E) be a bipartite graph in which boys are partL (left nodes), and girls are partR (right nodes.) There is an edge(l _i ,r _j )E iff boyl _i is interested in girlr _j . Every boyl _i will propose to a girlr _j among all those he is interested in, i.e., his adjacent right nodes in the bipartite graphG. If several boys propose to the same girl, only one of them will be accepted by the girl. We assume that none of the boys communicate with others. This matching problem is typical of distributed computing under incomplete information: Each boy only knows his own preference but none of the others. We first study the one-round matching problem: each boy proposes to at most one girl, so that the total number of girls receiving a proposal is maximized. If the maximum matching isM, then no deterministic algorithm can produce a matching of size not bounded by a constant, but a randomized algorithm achieves — and this is shown optimal by an adversary argument. If we allow many rounds in matching, with the senders learning from their failures, then, for deterministic algorithms, the ratio (of the optimal solution to the solution of the algorithm) is unbounded when the number of rounds is smaller than (G), and becomes bounded (two) at the (G)-th round. In contrast, an extension of the one-round randomized algorithm establishes that there is no such discontinuity in the randomized case. This randomized result is also matched by an upper bound of asymptotically the same order.