On maximum induced matchings in bipartite graphs

The problem of finding a maximum induced matching is known to be NP-hard in general bipartite graphs. We strengthen this result by reducing the problem to some special classes of bipartite graphs such as bipartite graphs with maximum degree 3 or C₄-free bipartite graphs. On the other hand, we describe a new polynomially solvable case for the problem in bipartite graphs which deals with a generalization of bi-complement reducible graphs.     

Signed and minus clique-transversal functions on graphs

A minus (respectively, signed) clique-transversal function of a graph G=(V,E) is a function (respectively, {−1,1}) such that _∑u∈Cf(u)?1 for every maximal clique C of G. The weight of a minus (respectively, signed) clique-transversal function of G is f(V)=_∑v∈Vf(v). The minus (respectively, signed) clique-transversal problem is to find a minus (respectively, signed) clique-transversal function of G of minimum weight. In this paper, we present a unified approach to these two problems on strongly chordal graphs. Notice that trees, block graphs, interval graphs, and directed path graphs are subclasses of strongly chordal graphs. We also prove that the signed clique-transversal problem is NP-complete for chordal graphs and planar graphs.     

Clustering in random line graphs

We investigate the degree distribution P(k) and the clustering coefficient C of the line graphs constructed on the Erdös-Rényi networks, the exponential and the scale-free growing networks. We show that the character of the degree distribution in these graphs remains Poissonian, exponential and power law, respectively, i.e. the same as in the original networks. When the mean degree 〈k〉 increases, the obtained clustering coefficient C tends to 0.50 for the transformed Erdös-Rényi networks, to 0.53 for the transformed exponential networks and to 0.61 for the transformed scale-free networks. These results are close to theoretical values, obtained with the model assumption that the degree-degree correlations in the initial networks are negligible.     

A partially structure-preserving algorithm for the permanents of adjacency matrices of fullerenes

A partially structure-preserving method for sparse symmetric matrices is proposed. Computational results on the permanents of adjacency matrices arising from molecular chemistry are presented. The largest adjacency matrix of fullerenes computed before is that of C₆₀ with a cost of several hours on supercomputers, while only about 6 min on an Intel Pentium PC (1.8 GHz) with our method. Further numerical computations are given for larger fullerenes and other adjacency matrices with n=60,80. This shows that our method is promising for problems from molecular chemistry.     

Block-graph width

Let G be a class of graphs. A graph G has G-width k if there are k independent sets N₁,…,N_k in G such that G can be embedded into a graph H∈G such that for every edge e in H which is not an edge in G, there exists an i such that both endvertices of e are in N_i. For the class B of block graphs we show that graphs with B-width at most 4 are perfect. We also show that B-width is NP-complete and show that it is fixed-parameter tractable. For the class C of complete graphs, similar results are also obtained.     

The edge-orientation problem and some of its variants on weighted graphs

Let G(V, E) be a connected undirected graph with n vertices and m edges, where each vertex v is associated with a cost C(v) and each edge e = (u, v) is associated with two weights, W(u → v) and W(v → u). The issue of assigning an orientation to each edge so that G becomes a directed graph is resolved in this paper. Determining a scheme to assign orientations of all edges such that max_x∈V{C(x)+∑_x→zW(x→z)} is minimized is the objective. This issue is called the edge-orientation problem (the EOP). Two variants of the EOP, the Out-Degree-EOP and the Vertex-Weighted EOP, are first proposed and then efficient algorithms for solving them on general graphs are designed. Ascertaining that the EOP is NP-hard on bipartite graphs and chordal graphs is the second result. Finally, an O(n log n)-time algorithm for the EOP on trees is designed. In general, the algorithmic results in this paper facilitate the implementation of the weighted fair queuing (WFQ) on real networks. The objective of the WFQ is to assign an effective weight for each flow to enhance link utilization. Our findings consequently can be easily extended to other classes of graphs, such as cactus graphs, block graphs, and interval graphs.     

Algorithms for multicommodity flows in planar graphs

This paper gives efficient algorithms for the muiticommodity flow problem for two classes C₁₂ and C₀₁ of planar undirected graphs. Every graph in C₁₂ has two face boundaries B₁ and B₂ such that each of the source-sink pairs lies on B₁ or B₂. On the other hand, every graph inC ₀₁ has a face boundaryB ₁ such that some of the source-sink pairs lie onB ₁ and all the other pairs share a common sink lying onB ₁. The algorithms run inO(kn +nT(n)) time if a graph hasn vertices andk source-sink pairs andT(n) is the time required for finding the single-source shortest paths in a planar graph ofn vertices.     

On the bi-enhancement of chordal-bipartite probe graphs

Given a class C of graphs, a graph G=(V,E) is said to be a C-probe graph if there exists a stable (i.e., independent) set of vertices X⊆V and a set F of pairs of vertices of X such that the graph G^′=(V,E∪F) is in the class C. Recently, there has been increasing interest and research on a variety of C-probe graph classes, such as interval probe graphs, chordal probe graphs and chain probe graphs.In this paper we focus on chordal-bipartite probe graphs. We prove a structural result that if B is a bipartite graph with no chordless cycle of length strictly greater than 6, then B is chordal-bipartite probe if and only if a certain “enhanced” graph B^∗ is a chordal-bipartite graph. This theorem is analogous to a result on interval probe graphs in Zhang (1994) [18] and to one on chordal probe graphs in Golumbic and Lipshteyn (2004) [11].     

On stabilization of energy for Hamiltonian systems

We study post-stabilization of numerical integrators for an autonomous Hamiltonian system in the form H=H₁+H₂, where H₁ and H₂ are two constants of motion. It is better to stabilize the two energies H₁ and H₂, respectively. As a particular case, the effectiveness of post-stabilization by the total energy is equivalent to one by the two independent energies when the splitting Hamiltonian becomes isotropic.     

On the transition graphs of turing machines

As for pushdown automata, we consider labelled Turing machines with ε-rules. With any Turing machine M and with a rational set C of configurations, we associate the restriction to C of the ϵ-closure of the transition set of M. We get the same family of graphs by using the labelled word rewriting systems. We show that this family is the set of graphs obtained from the binary tree by applying an inverse mapping into F followed by a rational restriction, where F is any family of recursively enumerable languages containing the rational closure of all linear languages. We show also that this family is obtained from the rational graphs by inverse rational mappings. Finally we show that this family is also the set of graphs recognized by (unlabelled) Turing machines with labelled final states, and even if we restrict to deterministic Turing machines.     

Automatized analytic continuation of Mellin-Barnes integrals

This paper describe a package written in MATHEMATICA that automatizes typical operations performed during evaluation of Feynman graphs with Mellin-Barnes (MB) techniques. The main procedure allows to analytically continue a MB integral in a given parameter without any intervention from the user and thus to resolve the singularity structure in this parameter. The package can also perform numerical integrations at specified kinematic points, as long as the integrands have satisfactory convergence properties. It is demonstrated that, at least in the case of massive graphs in the physical region, the convergence may turn out to be poor, making naïve numerical integration of MB integrals unusable. Possible solutions to this problem are presented, but full automatization in such cases may not be achievable.

Program summary

Title of program: MBProgram summary URL:http://cpc.cs.qub.ac.uk/summaries/ADYG_v1_0Catalogue identifier: ADYG_v1_0Program obtainable from: CPC Program Library, Queen's University of Belfast, N. IrelandComputers: AllOperating systems: AllProgramming language used:MATHEMATICA, Fortran 77 for numerical evaluationMemory required to execute with typical data: Sufficient for a typical installation of MATHEMATICA.No. of lines in distributed program, including test data, etc.: 12 013No. of bytes in distributed program, including test data, etc.: 231 899Distribution format: tar.gzLibraries used:CUBA [T. Hahn, Comput. Phys. Commun. 168 (2005) 78] for numerical evaluation of multidimensional integrals and CERNlib [CERN Program Library, obtainable from: http://cernlib.web.cern.ch/cernlib/] for the implementation of Γ and ψ functions in Fortran.Nature of physical problem: Analytic continuation of Mellin-Barnes integrals in a parameter and subsequent numerical evaluation. This is necessary for evaluation of Feynman integrals from Mellin-Barnes representations.Method of solution: Recursive accumulation of residue terms occurring when singularities cross integration contours. Numerical integration of multidimensional integrals with the help of the CUBA library.Restrictions on the complexity of the problem: Limited by the size of the available storage space.Typical running time: Depending on the problem. Usually seconds for moderate dimensionality integrals.     

Relationship between the eccentric connectivity index and Zagreb indices

For a (molecular) graph, the first Zagreb index M₁ is equal to the sum of the squares of the degrees of the vertices, and the second Zagreb index M₂ is equal to the sum of the products of the degrees of pairs of adjacent vertices. If G is a connected graph with vertex set V(G), then the eccentric connectivity index of G, ξ^C(G), is defined as, ∑_vi∈V(G)d_ie_i, where d_i is the degree of a vertex v_i and e_i is its eccentricity. In this report we compare the eccentric connectivity index (ξ^C) and the Zagreb indices (M₁ and M₂) for chemical trees. Moreover, we compare the eccentric connectivity index (ξ^C) and the first Zagreb index (M₁) for molecular graphs.     

Updating the complexity status of coloring graphs without a fixed induced linear forest

A graph is H-free if it does not contain an induced subgraph isomorphic to the graph H. The graph P_k denotes a path on k vertices. The ?-Coloring problem is the problem to decide whether a graph can be colored with at most ? colors such that adjacent vertices receive different colors. We show that 4-Coloring is NP-complete for P₈-free graphs. This improves a result of Le, Randerath, and Schiermeyer, who showed that 4-Coloring is NP-complete for P₉-free graphs, and a result of Woeginger and Sgall, who showed that 5-Coloring is NP-complete for P₈-free graphs. Additionally, we prove that the precoloring extension version of 4-Coloring is NP-complete for P₇-free graphs, but that the precoloring extension version of 3-Coloring can be solved in polynomial time for (P₂+P₄)-free graphs, a subclass of P₇-free graphs. Here P₂+P₄ denotes the disjoint union of a P₂ and a P₄. We denote the disjoint union of s copies of a P₃ by sP₃ and involve Ramsey numbers to prove that the precoloring extension version of 3-Coloring can be solved in polynomial time for sP₃-free graphs for any fixed s. Combining our last two results with known results yields a complete complexity classification of (precoloring extension of) 3-Coloring for H-free graphs when H is a fixed graph on at most 6 vertices: the problem is polynomial-time solvable if H is a linear forest; otherwise it is NP-complete.     

The super-connected property of recursive circulant graphs

In a graph G, a k-container C_k(u,v) is a set of k disjoint paths joining u and v. A k-container C_k(u,v) is k∗-container if every vertex of G is passed by some path in C_k(u,v). A graph G is k∗-connected if there exists a k∗-container between any two vertices. An m-regular graph G is super-connected if G is k∗-connected for any k with 1?k?m. In this paper, we prove that the recursive circulant graphs G(2^m,4), proposed by Park and Chwa [Theoret. Comput. Sci. 244 (2000) 35-62], are super-connected if and only if m≠2.     

Knowledge reduction based on the equivalence relations defined on attribute set and its power set

One of the key problems of knowledge discovery is knowledge reduction. This paper proposes a new method for knowledge reduction in information systems. First, two families of closed sets C_r and C_R are defined, where r and R are equivalence relations defined on the attribute set and its power set, respectively. The properties of C_r and C_R are also discussed. The necessary and sufficient condition for C_r=C_R is then given and employed to construct an approach to attribute reduction in information systems. It is also proved that under the condition C_r=C_R, the proposed approach to knowledge reduction is equivalent to the well-accepted one in reference [W.X. Zhang, Y. Leung, W.Z. Wu, Information Systems and Knowledge Discovery, Science Publishing Company, Beijing, 2003].     

Hamiltonicity in graphs with fewP 4's

In a recent series of articles R. Jamison and S. Olariu developed, starting from an extension of the notion of a cograph, a theory of the decomposition of graphs intoP ₄-connected components. It turned out in their work that the algorithmic idea to exploit the unique tree structure of cographs can be generalized to graphs with simpleP ₄-structure. In this paper we will show that deciding hamiltonicity and computing the path covering number are easy tasks forP ₄-sparse andP ₄-extendible graphs. We thereby generalize a result of H. A. Jung [8] concerning cographs.     

Dominating set is fixed parameter tractable in claw-free graphs

We show that the Dominating Set problem parameterized by solution size is fixed-parameter tractable (FPT) in graphs that do not contain the claw (K_1,3, the complete bipartite graph on four vertices where the two parts have one and three vertices, respectively) as an induced subgraph. We present an algorithm that uses 2^O(k2)n^O(1) time and polynomial space to decide whether a claw-free graph on n vertices has a dominating set of size at most k. Note that this parameterization of Dominating Set is W[2]-hard on the set of all graphs, and thus is unlikely to have an FPT algorithm for graphs in general.The most general class of graphs for which an FPT algorithm was previously known for this parameterization of Dominating Set is the class of K_i,j-free graphs, which exclude, for some fixed i,j∈N, the complete bipartite graph K_i,j as a subgraph. For i,j≥2, the class of claw-free graphs and any class of K_i,j-free graphs are not comparable with respect to set inclusion. We thus extend the range of graphs over which this parameterization of Dominating Set is known to be fixed-parameter tractable.We also show that, in some sense, it is the presence of the claw that makes this parameterization of the Dominating Set problem hard. More precisely, we show that for any t≥4, the Dominating Set problem parameterized by the solution size is W[2]-hard in graphs that exclude the t-claw K_1,t as an induced subgraph. Our arguments also imply that the related Connected Dominating Set and Dominating Clique problems are W[2]-hard in these graph classes.Finally, we show that for any t∈N, the Clique problem parameterized by solution size, which is W[1]-hard on general graphs, is FPT in t-claw-free graphs. Our results add to the small and growing collection of FPT results for graph classes defined by excluded subgraphs, rather than by excluded minors.     

Some results on graphs without long induced paths

Many NP-hard graph problems remain difficult on P_k-free graphs for certain values of k. Our goal is to distinguish subclasses of P_k-free graphs where several important graph problems can be solved in polynomial time. In particular, we show that the independent set problem is polynomial-time solvable in the class of (P_k,K_1,n)-free graphs for any positive integers k and n, thereby generalizing several known results.     

Iterations for solving linear variational inequalities on domains with nonlinear boundaries

This paper deals with numerical methods for solving linear variational inequalities on an arbitrary closed convex subsetC of ? ⁿ . Although there were numerous iterations studied for the caseC=? ₊ ⁿ , few were proposed for the case whenC is a closed convex subset. The essential difficulty in this case is the nonlinearities ofC's boundaries. In this paper iteration processes are designed for solving linear variational inequalities on an arbitrary closed convex subsetC. In our algorithms the computation of a linear variational inequality is decomposed into a sequence of problems of projecting a vector to the closed convex subsetC, which are computable as long as the equations describing the boundaries are given. In particular, using our iterations one can easily compute a solution whenC is one of the common closed convex subsets such as cube, ball, ellipsoid, etc. The non-accurate iteration, the estimate of the solutions on unbounded domains and the theory of approximating the boundaries are also established. Moreover, a necessary and sufficient condition is given for a vector to be an approximate solution. Finally, some numerical examples are presented, which show that the designed algorithms are effective and efficient. The exposition of this paper is self-contained.     

Computing the Treewidth and the Minimum Fill-In with the Modular Decomposition

Abstract. Using the notion of modular decomposition we extend the class of graphs on which both the treewidth and the minimum fill-in can be solved in polynomial time. We show that if C is a class of graphs that are modularly decomposable into graphs that have a polynomial number of minimal separators, or graphs formed by adding a matching between two cliques, then both the treewidth and the minimum fill-in on C can be solved in polynomial time. For the graphs that are modular decomposable into cycles we give algorithms that use respectively O(n) and O(n ³ ) time for treewidth and minimum fill-in.