Independence Numbers of Random Subgraphs of Some Distance Graph

The distance graph G(n, 2, 1) is a graph where vertices are identified with twoelement subsets of {1, 2,..., n}, and two vertices are connected by an edge whenever the corresponding subsets have exactly one common element. A random subgraph G _p (n, 2, 1) in the Erd?os–Rényi model is obtained by selecting each edge of G(n, 2, 1) with probability p independently of other edges. We find a lower bound on the independence number of the random subgraph G_1/2(n, 2, 1).     

Mutually independent Hamiltonian cycles in dual-cubes

The hypercube family Q _n is one of the most well-known interconnection networks in parallel computers. With Q _n , dual-cube networks, denoted by DC _n , was introduced and shown to be a (n+1)-regular, vertex symmetric graph with some fault-tolerant Hamiltonian properties. In addition, DC _n ’s are shown to be superior to Q _n ’s in many aspects. In this article, we will prove that the n-dimensional dual-cube DC _n contains n+1 mutually independent Hamiltonian cycles for n≥2. More specifically, let v _i ∈V(DC _n ) for 0≤i≤|V(DC _n )|?1 and let \(\langle v_{0},v_{1},\ldots ,v_{|V(\mathit{DC}_{n})|-1},v_{0}\rangle\) be a Hamiltonian cycle of DC _n . We prove that DC _n contains n+1 Hamiltonian cycles of the form \(\langle v_{0},v_{1}^{k},\ldots,v_{|V(\mathit{DC}_{n})|-1}^{k},v_{0}\rangle\) for 0≤k≤n, in which v _i ^k ≠v _i ^k′ whenever k≠k′. The result is optimal since each vertex of DC _n has only n+1 neighbors.     

Mathematical models and routing algorithms for CAD technological preparation of cutting processes

Resource-conscious technologies for cutting sheet material include the ICP and ECP technologies that allow for aligning fragments of the contours of cutouts. In this work, we show the mathematical model for the problem of cutting out parts with these technologies and algorithms for finding cutting tool routes that satisfy technological constraints. We give a solution for the problem of representing a cutting plan as a plane graph G = (V,F,E), which is a homeomorphic image of the cutting plan. This has let us formalize technological constraints on the trajectory of cutting the parts according to the cutting plan and propose a series of algorithms for constructing a route in the graph G = (V,F,E), which is an image of an admissible trajectory. Using known coordinates of the preimages of vertices of graph G = (V,F,E) and the locations of fragments of the cutting plan that are preimages of edges of graph G = (V,F,E), the resulting route in the graph G = (V,E) can be interpreted as the cutting tool’s trajectory.The proposed algorithms for finding routes in a connected graph G have polynomial computational complexity. To find the optimal route in an unconnected graph G, we need to solve, for every dividing face f of graph G, a travelling salesman problem on the set of faces incident to f.     

The Outer-connected Domination Number of Sierpiński-like Graphs

An outer-connected dominating set in a graph G = (V, E) is a set of vertices D ? V satisfying the condition that, for each vertex v ? D, vertex v is adjacent to some vertex in D and the subgraph induced by V?D is connected. The outer-connected dominating set problem is to find an outer-connected dominating set with the minimum number of vertices which is denoted by \(\tilde {\gamma }_{c}(G)\). In this paper, we determine \(\tilde {\gamma }_{c}(S(n,k))\), \(\tilde {\gamma }_{c}(S^{+}(n,k))\), \(\tilde {\gamma }_{c}(S^{++}(n,k))\), and \(\tilde {\gamma }_{c}(S_{n})\), where S(n, k), S ⁺(n, k), S ⁺⁺(n, k), and S _n are Sierpi\(\acute {\mathrm {n}}\)ski-like graphs.     

Constant-Degree Graph Expansions that Preserve Treewidth

Many hard algorithmic problems dealing with graphs, circuits, formulas and constraints admit polynomial-time upper bounds if the underlying graph has small treewidth. The same problems often encourage reducing the maximal degree of vertices to simplify theoretical arguments or address practical concerns. Such degree reduction can be performed through a sequence of splittings of vertices, resulting in an expansion of the original graph. We observe that the treewidth of a graph may increase dramatically if the splittings are not performed carefully. In this context we address the following natural question: is it possible to reduce the maximum degree to a constant without substantially increasing the treewidth?We answer the above question affirmatively. We prove that any simple undirected graph G=(V,E) admits an expansion G′=(V′,E′) with the maximum degree ≤3 and tw(G′)≤tw(G)+1, where tw(?) is the treewidth of a graph. Furthermore, such an expansion will have no more than 2|E|+|V| vertices and 3|E| edges; it can be computed efficiently from a tree-decomposition of G. We also construct a family of examples for which the increase by 1 in treewidth cannot be avoided.     

The Complexity of König Subgraph Problems and Above-Guarantee Vertex Cover

A graph is König-Egerváry if the size of a minimum vertex cover equals that of a maximum matching in the graph. These graphs have been studied extensively from a graph-theoretic point of view. In this paper, we introduce and study the algorithmic complexity of finding König-Egerváry subgraphs of a given graph. In particular, given a graph G and a nonnegative integer k, we are interested in the following questions:

1. 1.
   does there exist a set of k vertices (edges) whose deletion makes the graph König-Egerváry?
    
2. 2.
   does there exist a set of k vertices (edges) that induce a König-Egerváry subgraph?
    

We show that these problems are NP-complete and study their complexity from the points of view of approximation and parameterized complexity. Towards this end, we first study the algorithmic complexity of Above Guarantee Vertex Cover, where one is interested in minimizing the additional number of vertices needed beyond the maximum matching size for the vertex cover. Further, while studying the parameterized complexity of the problem of deleting k vertices to obtain a König-Egerváry graph, we show a number of interesting structural results on matchings and vertex covers which could be useful in other contexts.

     

Embedding cycles and paths on solid grid graphs

Despite many algorithms for embedding graphs on unbounded grids, only a few results on embedding graphs on restricted grids have been published. In this paper, we study the problem of embedding paths and cycles on solid grid graphs. We show that a cycle of length k is unit-length embeddable on a solid grid graph G if k is an even integer between four and the length of the longest cycle of G. In addition, our result shows that a path of length k is unit-length embeddable on G, between its two given vertices s and t, if \(k\le L\) and \(k\equiv L (\mathrm{mod}\ 2)\), in which L is the length of the longest path between s and t. Our presented two algorithms show that such embeddings can be found in linear time for cycles and quadratic time for paths, with respect to the size of graph G. In the case of rectangular grid graphs, the running time of the algorithms can be improved to O(k) and O\((k^2)\), respectively. In addition, we extend our results to \(m\times n\times o\) 3D grids. A application of our result is in the interconnection network mapping in parallel processing.     

Approximating the Sparsest k-Subgraph in Chordal Graphs

Given a simple undirected graph G = (V, E) and an integer k < |V|, the Sparsest k-Subgraph problem asks for a set of k vertices which induces the minimum number of edges. As a generalization of the classical independent set problem, Sparsest k-Subgraph is ????-hard and even not approximable unless ?????? in general graphs. Thus, we investigate Sparsest k-Subgraph in graph classes where independent set is polynomial-time solvable, such as subclasses of perfect graphs. Our two main results are the ????-hardness of Sparsest k-Subgraph on chordal graphs, and a greedy 2-approximation algorithm. Finally, we also show how to derive a P T A S for Sparsest k-Subgraph on proper interval graphs.     

A linear-time algorithm for finding Hamiltonian (<Emphasis Type="Italic">s</Emphasis>, <Emphasis Type="Italic">t</Emphasis>)-paths in odd-sized rectangular grid graphs with a rectangular hole

A grid graph \(G_{\mathrm{g}}\) is a finite vertex-induced subgraph of the two-dimensional integer grid \(G^\infty \). A rectangular grid graph R(m, n) is a grid graph with horizontal size m and vertical size n. A rectangular grid graph with a rectangular hole is a rectangular grid graph R(m, n) such that a rectangular grid subgraph R(k, l) is removed from it. The Hamiltonian path problem for general grid graphs is NP-complete. In this paper, we give necessary conditions for the existence of a Hamiltonian path between two given vertices in an odd-sized rectangular grid graph with a rectangular hole. In addition, we show that how such paths can be computed in linear time.     

Non-contractible non-edges in 2-connected graphs

Any pair of non-adjacent vertices forms a non-edge in a graph. Contraction of a non-edge merges two non-adjacent vertices into a single vertex such that the edges incident on the non-adjacent vertices are now incident on the merged vertex. In this paper, we consider simple connected graphs, hence parallel edges are removed after contraction. The minimum number of nodes whose removal disconnects the graph is the connectivity of the graph. We say a graph is k-connected, if its connectivity is k. A non-edge in a k-connected graph is contractible if its contraction does not result in a graph of lower connectivity. Otherwise the non-edge is non-contractible. We focus our study on non-contractible non-edges in 2-connected graphs. We show that cycles are the only 2-connected graphs in which every non-edge is non-contractible.     

Parameterized complexity of connected even/odd subgraph problems

In 2011, Cai an Yang initiated the systematic parameterized complexity study of the following set of problems around Eulerian graphs: for a given graph G and integer k, the task is to decide if G contains a (connected) subgraph with k vertices (edges) with all vertices of even (odd) degrees. They succeed to establish the parameterized complexity of all cases except two, when we ask about:

•

a connected k-edge subgraph with all vertices of odd degrees, the problem known as k-Edge Connected Odd Subgraph; and     

Faster Parameterized Algorithms for <Emphasis Type="SmallCaps">Minimum Fill-in</Emphasis>

We present two parameterized algorithms for the Minimum Fill-in problem, also known as Chordal Completion: given an arbitrary graph G and integer k, can we add at most k edges to G to obtain a chordal graph? Our first algorithm has running time \(\mathcal {O}(k^{2}nm+3.0793^{k})\), and requires polynomial space. This improves the base of the exponential part of the best known parameterized algorithm time for this problem so far. We are able to improve this running time even further, at the cost of more space. Our second algorithm has running time \(\mathcal {O}(k^{2}nm+2.35965^{k})\) and requires \(\mathcal {O}^{\ast}(1.7549^{k})\) space. To achieve these results, we present a new lemma describing the edges that can safely be added to achieve a chordal completion with the minimum number of edges, regardless of k.     

On Fixed Cost k-Flow Problems

In the Fixed Cost k-Flow problem, we are given a graph G = (V, E) with edge-capacities {u _e ∣e ∈ E} and edge-costs {c _e ∣e ∈ E}, source-sink pair s, t ∈ V, and an integer k. The goal is to find a minimum cost subgraph H of G such that the minimum capacity of an st-cut in H is at least k. By an approximation-preserving reduction from Group Steiner Tree problem to Fixed Cost k-Flow, we obtain the first polylogarithmic lower bound for the problem; this also implies the first non-constant lower bounds for the Capacitated Steiner Network and Capacitated Multicommodity Flow problems. We then consider two special cases of Fixed Cost k-Flow. In the Bipartite Fixed-Cost k-Flow problem, we are given a bipartite graph G = (A ∪ B, E) and an integer k > 0. The goal is to find a node subset S ? A ∪ B of minimum size |S| such G has k pairwise edge-disjoint paths between S ∩ A and S ∩ B. We give an \(O(\sqrt {k\log k})\) approximation for this problem. We also show that we can compute a solution of optimum size with Ω(k/polylog(n)) paths, where n = |A| + |B|. In the Generalized-P2P problem we are given an undirected graph G = (V, E) with edge-costs and integer charges {b _v : v ∈ V}. The goal is to find a minimum-cost spanning subgraph H of G such that every connected component of H has non-negative charge. This problem originated in a practical project for shift design [11]. Besides that, it generalizes many problems such as Steiner Forest, k-Steiner Tree, and Point to Point Connection. We give a logarithmic approximation algorithm for this problem. Finally, we consider a related problem called Connected Rent or Buy Multicommodity Flow and give a log^3+?? n approximation scheme for it using Group Steiner Tree techniques.     

Optimal Path Embedding in the Exchanged Crossed Cube

The (s + t + 1)-dimensional exchanged crossed cube, denoted as ECQ(s, t), combines the strong points of the exchanged hypercube and the crossed cube. It has been proven that ECQ(s, t) has more attractive properties than other variations of the fundamental hypercube in terms of fewer edges, lower cost factor and smaller diameter. In this paper, we study the embedding of paths of distinct lengths between any two different vertices in ECQ(s, t). We prove the result in ECQ(s, t): if s ≥ 3, t ≥ 3, for any two different vertices, all paths whose lengths are between \( \max \left\{9,\left\lceil \frac{s+1}{2}\right\rceil +\left\lceil \frac{t+1}{2}\right\rceil +4\right\} \) and 2 ^s+t+1 ? 1 can be embedded between the two vertices with dilation 1. Note that the diameter of ECQ(s, t) is \( \left\lceil \frac{s+1}{2}\right\rceil +\left\lceil \frac{t+1}{2}\right\rceil +2 \). The obtained result is optimal in the sense that the dilations of path embeddings are all 1. The result reveals the fact that ECQ(s, t) preserves the path embedding capability to a large extent, while it only has about one half edges of CQ _n .     

On the Number of Edges of a Uniform Hypergraph with a Range of Allowed Intersections

We study the quantity p(n, k, t₁, t₂) equal to the maximum number of edges in a k-uniform hypergraph having the property that all cardinalities of pairwise intersections of edges lie in the interval [t₁, t₂]. We present previously known upper and lower bounds on this quantity and analyze their interrelations. We obtain new bounds on p(n, k, t₁, t₂) and consider their possible applications in combinatorial geometry problems. For some values of the parameters we explicitly evaluate the quantity in question. We also give a new bound on the size of a constant-weight error-correcting code.     

Remark on balanced incomplete block designs,near-resolvable block designs,and <Emphasis Type="Italic">q</Emphasis>-ary constant-weight codes

We prove that any balanced incomplete block design B(v, k, 1) generates a nearresolvable balanced incomplete block design NRB(v, k ? 1, k ? 2). We establish a one-to-one correspondence between near-resolvable block designs NRB(v, k ?1, k ?2) and the subclass of nonbinary (optimal, equidistant) constant-weight codes meeting the generalized Johnson bound.     

Combinatorial methods for constructing bipartite uniform minimal quasicomplete graphs (symmetrical block designs)

Consideration was given to a specific family of bipartite graphs consisting of two disjoint subsets X and Y of vertices and characterized by that each vertex in X (Y) is connected to each of the remaining vertices in X (Y) by a unique path of length two passing through some vertex in Y (X). The prefix “quasi” reflects the fact that complete connection of the vertices is realized by paths of length two rather than by edges. The problem of constructing uniform minimal graphs with identical cardinalities of the subsets X and Y which is of practical interest for complex communication networks was discussed. It belongs to the class of combinatorial problems of construction of the so-called symmetrical block designs.     

The Complexity Ecology of Parameters: An Illustration Using Bounded Max Leaf Number

In the framework of parameterized complexity, exploring how one parameter affects the complexity of a different parameterized (or unparameterized problem) is of general interest. A well-developed example is the investigation of how the parameter treewidth influences the complexity of (other) graph problems. The reason why such investigations are of general interest is that real-world input distributions for computational problems often inherit structure from the natural computational processes that produce the problem instances (not necessarily in obvious, or well-understood ways). The max leaf number ml(G) of a connected graph G is the maximum number of leaves in a spanning tree for G. Exploring questions analogous to the well-studied case of treewidth, we can ask: how hard is it to solve 3-Coloring, Hamilton Path, Minimum Dominating Set, Minimum Bandwidth or many other problems, for graphs of bounded max leaf number? What optimization problems are W[1]-hard under this parameterization? We do two things:

1. (1)
   We describe much improved FPT algorithms for a large number of graph problems, for input graphs G for which ml(G)≤k, based on the polynomial-time extremal structure theory canonically associated to this parameter. We consider improved algorithms both from the point of view of kernelization bounds, and in terms of improved fixed-parameter tractable (FPT) runtimes O ^*(f(k)).
    
2. (2)
   The way that we obtain these concrete algorithmic results is general and systematic. We describe the approach, and raise programmatic questions.
    

     

Incremental <Emphasis Type="Italic">k</Emphasis>-core decomposition: algorithms and evaluation

A k-core of a graph is a maximal connected subgraph in which every vertex is connected to at least k vertices in the subgraph. k-core decomposition is often used in large-scale network analysis, such as community detection, protein function prediction, visualization, and solving NP-hard problems on real networks efficiently, like maximal clique finding. In many real-world applications, networks change over time. As a result, it is essential to develop efficient incremental algorithms for dynamic graph data. In this paper, we propose a suite of incremental k-core decomposition algorithms for dynamic graph data. These algorithms locate a small subgraph that is guaranteed to contain the list of vertices whose maximum k-core values have changed and efficiently process this subgraph to update the k-core decomposition. We present incremental algorithms for both insertion and deletion operations, and propose auxiliary vertex state maintenance techniques that can further accelerate these operations. Our results show a significant reduction in runtime compared to non-incremental alternatives. We illustrate the efficiency of our algorithms on different types of real and synthetic graphs, at varying scales. For a graph of 16 million vertices, we observe relative throughputs reaching a million times, relative to the non-incremental algorithms.     

The panpositionable panconnectedness of crossed cubes

In many parallel and distributed multiprocessor systems, the processors are connected based on different types of interconnection networks. The topological structure of an interconnection network is typically modeled as a graph. Among the many kinds of network topologies, the crossed cube is one of the most popular. In this paper, we investigate the panpositionable panconnectedness problem with respect to the crossed cube. A graph G is r-panpositionably panconnected if for any three distinct vertices x, y, z of G and for any integer \(l_1\) satisfying \(r \le l_1 \le |V(G)| - r - 1\), there exists a path \(P = [x, P_1, y, P_2, z]\) in G such that (i) \(P_1\) joins x and y with \(l(P_1) = l_1\) and (ii) \(P_2\) joins y and z with \(l(P_2) = l_2\) for any integer \(l_2\) satisfying \(r \le l_2 \le |V(G)| - l_1 - 1\), where |V(G)| is the total number of vertices in G and \(l(P_1)\) (respectively, \(l(P_2)\)) is the length of path \(P_1\) (respectively, \(P_2\)). By mathematical induction, we demonstrate that the n-dimensional crossed cube \(CQ_n\) is n-panpositionably panconnected. This result indicates that the path embedding of joining x and z with a mediate vertex y in \(CQ_n\) is extremely flexible. Moreover, applying our result, crossed cube problems such as panpositionable pancyclicity, panpositionably Hamiltonian connectedness, and panpositionable Hamiltonicity can be solved.