On the power of a perturbation for testing non-isomorphism of graphs

In this paper we prove an inverted version of A. J. Schwenk's result, which in turn is related to Ulam's reconstruction conjecture. Instead of deleting vertices from an undirected graphG, we add a new vertexv and join it to all other vertices ofG to get a perturbed graphG+v. We derive an expression for the characteristic polynomial of the perturbed graphG+v in terms of the characteristic polynomial of the original graphG. We then show the extent to which the characteristic polynomials of the perturbed graphs can be used in determining whether two graphs are non-isomorphic.This work was supported by the U.S. Army Research Office under Grant DAAG29-82-K-0107.     

Hamiltonian index is NP-complete

In this paper we show that the problem to decide whether the hamiltonian index of a given graph is less than or equal to a given constant is NP-complete (although this was conjectured to be polynomial). Consequently, the corresponding problem to determine the hamiltonian index of a given graph is NP-hard. Finally, we show that some known upper and lower bounds on the hamiltonian index can be computed in polynomial time.     

Feasible Graphs and Colorings

The problem of when a recursive graph has a recursive k-coloring has been extensively studied by Bean, Schmerl, Kierstead, Remmel, and others. In this paper, we study the polynomial time analogue of that problem. We develop a number of negative and positive results about colorings of polynomial time graphs. For example, we show that for any recursive graph G and for any k, there is a polynomial time graph G′ whose vertex set is {0,1}* such that there is an effective degree preserving correspondence between the set of k-colorings of G and the set of k-colorings of G′ and hence there are many examples of k-colorable polynomial time graphs with no recursive k-colorings. Moreover, even though every connected 2-colorable recursive graph is recursively 2-colorable, there are connected 2-colorable polynomial time graphs which have no primitive recursive 2-coloring. We also give some sufficient conditions which will guarantee that a polynomial time graph has a polynomial time or exponential time coloring.     

Parameter choices on Guruswami–Sudan algorithm for polynomial reconstruction

Guruswami–Sudan algorithm for polynomial reconstruction problem plays an important role in the study of error-correcting codes. In this paper, we study new better parameter choices in Guruswami–Sudan algorithm for the polynomial reconstruction problem. As a consequence, our result gives a better upper bound for the number of solutions for the polynomial reconstruction problem comparing with the original algorithm.     

A certain polynomial of a graph and graphs with an extremal number of trees

The polynomial we consider here is the characteristic polynomial of a certain (not adjacency) matrix associated with a graph. This polynomial was introduced in connection with the problem of counting spanning trees in graphs [8]. In the present paper the properties of this polynomial are used to construct some classes of graphs with an extremal numbers of spanning trees.     

On finding augmenting graphs

Method of augmenting graphs is a general approach to solve the maximum independent set problem. As the problem is generally NP-hard, no polynomial time algorithms are available to implement the method. However, when restricted to particular classes of graphs, the approach may lead to efficient solutions. A famous example of this type is the maximum matching algorithm: it finds a maximum matching in a graph G, which is equivalent to finding a maximum independent set in the line graph of G. In the particular case of line graphs, the method reduces to finding augmenting (alternating) chains. Recent investigations of more general classes of graphs revealed many more types of augmenting graphs. In the present paper we study the problem of finding augmenting graphs different from chains. To simplify this problem, we introduce the notion of a redundant set. This allows us to reduce the problem to finding some basic augmenting graphs. As a result, we obtain a polynomial time solution to the maximum independent set problem in a class of graphs which extends several previously studied classes including the line graphs.     

On the Location of Roots of Graph Polynomials

Roots of graph polynomials such as the characteristic polynomial, the chromatic polynomial, the matching polynomial, and many others are widely studied. In this paper we examine to what extent the location of these roots reflects the graph theoretic properties of the underlying graph.     

线图上的团染色问题

设G=(V,E)为简单图, G的每个至少有两个顶点的极大完全子图称为G的一个团. 图的团染色定义为给图的点进行染色使得图中没有单一颜色的团, 也就是说每一个团具有至少2种颜色.图的一个k-团染色 是指用k 种颜色给图的点着色使得图G 的每一个团至少有2种颜色.图G的团染色数\chi_{C}(G)是指最小的数k使得图G 存在k-团染色. 首先指出了完全图的线图的团染色数与推广的Ramsey 数之间的一个联系, 其次对于最大度不超过7的线图给出了一个最优团染色的多项式时间算法.     

超图的Laplacian

本文讨论了由Ｆ．Ｒ．Ｋ．Ｃｈｕｎｇ 引入的ｋ－图的Ｌａｐｌａｃｉａｎ 的一些基本性质．通过引入ｋ－图的邻接图的概念,得到了ｋ－图的Ｌａｐｌａｃｉａｎ 及其特征多项式的更明确的表达式．同时,也改进了文［１］中关于ｄ－正则ｋ－图的谱值的一个下界     

The toughness of split graphs

In this short note we argue that the toughness of split graphs can be computed in polynomial time. This solves an open problem from a recent paper by Kratsch et al. (Discrete Math. 150 (1996) 231–245).     

A matrix pencil approach to the existence of compactly supported reconstruction functions in average sampling

The aim of this work is to solve a question raised for average sampling in shift-invariant spaces by using the well-known matrix pencil theory. In many common situations in sampling theory, the available data are samples of some convolution operator acting on the function itself: this leads to the problem of average sampling, also known as generalized sampling. In this paper we deal with the existence of a sampling formula involving these samples and having reconstruction functions with compact support. Thus, low computational complexity is involved and truncation errors are avoided. In practice, it is accomplished by means of a FIR filter bank. An answer is given in the light of the generalized sampling theory by using the oversampling technique: more samples than strictly necessary are used. The original problem reduces to finding a polynomial left inverse of a polynomial matrix intimately related to the sampling problem which, for a suitable choice of the sampling period, becomes a matrix pencil. This matrix pencil approach allows us to obtain a practical method for computing the compactly supported reconstruction functions for the important case where the oversampling rate is minimum. Moreover, the optimality of the obtained solution is established.     

Edge decompositions and rooted packings of graphs

Let H be a fixed graph. In this paper we consider the problem of edge decomposition of a graph into subgraphs isomorphic to H or $2K_2$ (a 2-edge matching). We give a partial classification of the problems of existence of such decomposition according to the computational complexity. More specifically, for some large class of graphs H we show that this problem is polynomial time solvable and for some other large class of graphs it is NP-complete. These results can be viewed as some edge decomposition analogs of a result by Loebl and Poljak who classified according to the computational complexity the problem of existence of a graph factor with components isomorphic to H or $K_2$. In the proofs of our results we apply so-called rooted packings into graphs which are mutual generalizations of both edge decompositions and factors of graphs.     

On the use of graphs in discrete tomography

In this tutorial paper, we consider the basic image reconstruction problem which stems from discrete tomography. We derive a graph theoretical model and we explore some variations and extensions of this model. This allows us to establish connections with scheduling and timetabling applications. The complexity status of these problems is studied and we exhibit some polynomially solvable cases. We show how various classical techniques of operations research like matching, 2-SAT, network flows are applied to derive some of these results.      

Interpolating solutions of the Poisson equation in the disk based on Radon projections

We consider an algebraic method for reconstruction of a function satisfying the Poisson equation with a polynomial right-hand side in the unit disk. The given data, besides the right-hand side, is assumed to be in the form of a finite number of values of Radon projections of the unknown function. We first homogenize the problem by finding a polynomial which satisfies the given Poisson equation. This leads to an interpolation problem for a harmonic function, which we solve in the space of harmonic polynomials using a previously established method. For the special case where the Radon projections are taken along chords that form a regular convex polygon, we extend the error estimates from the harmonic case to this Poisson problem. Finally we give some numerical examples.     

Linear broadcast routing

In this paper we examine the problem of performing broadcasts in networks where the messages are constrained to follow linear paths. Many high speed networks, where routing is done in specialized hardware, have this characteristic. We show that the general problem is NP-complete but find a polynomial time approximation algorithm which is guaranteed to provide a solution which is within twice the optimal. We also suggest some generalizations of this work and propose several open problems.     

DNA approach to scenery reconstruction

The basic reconstruction problem lead with the general task of retrieving a scenery from observations made by a random walker. A critical factor associated with the problem is reconstructing the scenery in polynomial time. In this article, we propose a novel technique based on the modern DNA sequencing method for reconstructing a 3-color scenery of length n. The idea is first to reconstruct small pieces of length order log n and then assembled them together to form the required piece. We show that this reconstruction and assembly for a finite piece of a 3-color scenery takes polynomial amount of time.     

Eigenvalues of a symmetric tridiagonal matrix: A divide-and-conquer approach

Summary The Symmetric Tridiagonal Eigenproblem has been the topic of some recent work. Many methods have been advanced for the computation of the eigenvalues of such a matrix. In this paper, we present a divide-and-conquer approach to the computation of the eigenvalues of a symmetric tridiagonal matrix via the evaluation of the characteristic polynomial. The problem of evaluation of the characteristic polynomial is partitioned into smaller parts which are solved and these solutions are then combined to form the solution to the original problem. We give the update equations for the characteristic polynomial and certain auxiliary polynomials used in the computation. Furthermore, this set of recursions can be implemented on a regulartree structure. If the concurrency exhibited by this algorithm is exploited, it can be shown that thetime for computation of all the eigenvalues becomesO(nlogn) instead ofO(n ²) as is the case for the approach where the order is increased by only one at every step. We address the numerical problems associated with the use of the characteristic polynomial and present a numerically stable technique for the eigenvalue computation.     

Lattice point counts for the Shi arrangement and other affinographic hyperplane arrangements

Hyperplanes of the form xj=xi+c are called affinographic. For an affinographic hyperplane arrangement in Rn, such as the Shi arrangement, we study the function f(m) that counts integral points in n[1,m] that do not lie in any hyperplane of the arrangement. We show that f(m) is a piecewise polynomial function of positive integers m, composed of terms that appear gradually as m increases. Our approach is to convert the problem to one of counting integral proper colorations of a rooted integral gain graph.An application is to interval coloring in which the interval of available colors for vertex vi has the form [hi+1,m].A related problem takes colors modulo m; the number of proper modular colorations is a different piecewise polynomial that for large m becomes the characteristic polynomial of the arrangement (by which means Athanasiadis previously obtained that polynomial). We also study this function for all positive moduli.     

The Complexity Analysis of the Inverse Center Location Problem

Given a feasible solution, the inverse optimization problem is to modify some parameters of the original problem as little as possible, and sometimes also with bound restrictions on these adjustments, to make the feasible solution become an optimal solution under the new parameter values. So far it is unknown that for a problem which is solvable in polynomial time, whether its inverse problem is also solvable in polynomial time. In this note we answer this question by considering the inverse center location problem and show that even though the original problem is polynomially solvable, its inverse problem is NP–hard.     

On the reconstruction of graph invariants

The reconstruction conjecture has remained open for simple undirected graphs since it was suggested in 1941 by Kelly and Ulam. In an attempt to prove the conjecture, many graph invariants have been shown to be reconstructible from the vertex-deleted deck, and in particular, some prominent graph polynomials. Among these are the Tutte polynomial, the chromatic polynomial and the characteristic polynomial. We show that the interlace polynomial, the U-polynomial, the universal edge elimination polynomial ξ and the colored versions of the latter two are reconstructible.We also present a method of reconstructing boolean graph invariants, or in other words, proving recognizability of graph properties (of colored or uncolored graphs), using first order logic.