The k-in-a-Path Problem for Claw-free Graphs

The k-in-a-Path problem is to test whether a graph contains an induced path spanning k given vertices. This problem is NP-complete in general graphs, already when k=3. We show how to solve it in polynomial time on claw-free graphs, when k is an arbitrary fixed integer not part of the input. As a consequence, also the k-Induced Disjoint Paths and the k-in-a-Cycle problem are solvable in polynomial time on claw-free graphs for any fixed k. The first problem has as input a graph G and k pairs of specified vertices (s _i ,t _i ) for i=1,…,k and is to test whether G contain k mutually induced paths P _i such that P _i connects s _i and t _i for i=1,…,k. The second problem is to test whether a graph contains an induced cycle spanning k given vertices. When k is part of the input, we show that all three problems are NP-complete, even for the class of line graphs, which form a subclass of the class of claw-free graphs.     

On the cubicity of certain graphs

The boxicity of a graph G is the minimum dimension b such that G is representable as the intersection graph of axis-parallel boxes in the b-dimensional space. When the boxes are restricted to be axis-parallel b-dimensional cubes, the minimum dimension b required to represent G is called the cubicity of G. In this paper we show that cubicity(Hd)?2d, where Hd is the d-dimensional hypercube. (The d-dimensional hypercube is the graph on d² vertices which corresponds to the d²d-vectors whose components are either 0 or 1, two of the vertices being adjacent when they differ in just one coordinate.) We also show that cubicity(Hd)?(d−1)/(logd). We also show that (1) cubicity(G)?(logα)/(log(D+1)), (2) cubicity(G)?(logn−logω)/(logD), where α,ω,D and n denote the stability number, the clique number, the diameter and the number of vertices of G. As consequences of these lower bounds we provide lower bounds for the cubicity of planar graphs, bipartite graphs, triangle-free graphs, etc., in terms of their diameter and the number of vertices.     

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.     

Finding Edge-Disjoint Paths in Partial k -Trees

For a given graph G and p pairs (s _i ,t _i ) , , of vertices in G , the edge-disjoint paths problem is to find p pairwise edge-disjoint paths P _i , , connecting s _i and t _i . Many combinatorial problems can be efficiently solved for partial k -trees (graphs of treewidth bounded by a fixed integer k ), but the edge-disjoint paths problem is NP-complete even for partial 3 -trees. This paper gives two algorithms for the edge-disjoint paths problem on partial k -trees. The first one solves the problem for any partial k -tree G and runs in polynomial time if p=O( log n) and in linear time if p=O(1) , where n is the number of vertices in G . The second one solves the problem under some restriction on the location of terminal pairs even if . Received January 21, 1977; revised September 19, 1997.     

Collective Tree Spanners in Graphs with Bounded Parameters

In this paper we study collective additive tree spanners for special families of graphs including planar graphs, graphs with bounded genus, graphs with bounded tree-width, graphs with bounded clique-width, and graphs with bounded chordality. We say that a graph G=(V,E) admits a system of μ collective additive tree r -spanners if there is a system $\mathcal{T}(G)In this paper we study collective additive tree spanners for special families of graphs including planar graphs, graphs with bounded genus, graphs with bounded tree-width, graphs with bounded clique-width, and graphs with bounded chordality. We say that a graph G=(V,E) admits a system of μ collective additive tree r -spanners if there is a system T(G)\mathcal{T}(G) of at most μ spanning trees of G such that for any two vertices x,y of G a spanning tree T ? T(G)T\in\mathcal{T}(G) exists such that d _T (x,y)≤d _G (x,y)+r. We describe a general method for constructing a “small” system of collective additive tree r-spanners with small values of r for “well” decomposable graphs, and as a byproduct show (among other results) that any weighted planar graph admits a system of O(?n)O(\sqrt{n}) collective additive tree 0-spanners, any weighted graph with tree-width at most k−1 admits a system of klog ₂ n collective additive tree 0-spanners, any weighted graph with clique-width at most k admits a system of klog _3/2 n collective additive tree (2w)(2\mathsf{w}) -spanners, and any weighted graph with size of largest induced cycle at most c admits a system of log ₂ n collective additive tree (2?c/2?w)(2\lfloor c/2\rfloor\mathsf{w}) -spanners and a system of 4log ₂ n collective additive tree (2(?c/3?+1)w)(2(\lfloor c/3\rfloor +1)\mathsf {w}) -spanners (here, w\mathsf{w} is the maximum edge weight in G). The latter result is refined for weighted weakly chordal graphs: any such graph admits a system of 4log ₂ n collective additive tree (2w)(2\mathsf{w}) -spanners. Furthermore, based on this collection of trees, we derive a compact and efficient routing scheme for those families of graphs.     

Edge-Packing in Planar Graphs

Maximum G Edge-Packing (EPack _G ) is the problem of finding the maximum number of edge-disjoint isomorphic copies of a fixed guest graph G in a host graph H . This paper investigates the computational complexity of edge-packing for planar guests and planar hosts. Edge-packing is solvable in polynomial time when both G and H are trees. Edge-packing is solvable in linear time when H is outerplanar and G is either a 3-cycle or a k -star (a graph isomorphic to K _1,k ). Edge-packing is NP-complete when H is planar and G is either a cycle or a tree with edges. A strategy for developing polynomial-time approximation algorithms for planar hosts is exemplified by a linear-time approximation algorithm that finds a k -star edge-packing of size at least half the optimal. Received May 1995, and in revised form November 1995, and in final form December 1997.     

Panconnectivity of Cartesian product graphs

A graph G of order n (≥2) is said to be panconnected if for each pair (x,y) of vertices of G there exists an xy-path of length ℓ for each ℓ such that d _G (x,y)≤ℓ≤n−1, where d _G (x,y) denotes the length of a shortest xy-path in G. In this paper, we consider the panconnectivity of Cartesian product graphs. As a consequence of our results, we prove that the n-dimensional generalized hypercube Q _n (k ₁,k ₂,…,k _n ) is panconnected if and only if k _i ≥3 (i=1,…,n), which generalizes a result of Hsieh et al. that the 3-ary n-cube Q³_nQ^{3}_{n} is panconnected.     

Optimal 1-edge fault-tolerant designs for ladders

A graph G∗ is 1-edge fault-tolerant with respect to a graph G, denoted by 1-EFT(G), if every graph obtained by removing any edge from G∗ contains G. A 1-EFT(G) graph is optimal if it contains the minimum number of edges among all 1-EFT(G) graphs. The kth ladder graph, L_k, is defined to be the cartesian product of the P_k and P₂ where P_n is the n-vertex path graph. In this paper, we present several 1-edge fault-tolerant graphs with respect to ladders. Some of these graphs are proven to be optimal.     

A Cubic Kernel for Feedback Vertex Set and Loop Cutset

The Feedback Vertex Set problem on unweighted, undirected graphs is considered. Improving upon a result by Burrage et al. (Proceedings 2nd International Workshop on Parameterized and Exact Computation, pp. 192–202, 2006), we show that this problem has a kernel with O(k ³) vertices, i.e., there is a polynomial time algorithm, that given a graph G and an integer k, finds a graph G′ with O(k ³) vertices and integer k′≤k, such that G has a feedback vertex set of size at most k, if and only if G′ has a feedback vertex set of size at most k′. Moreover, the algorithm can be made constructive: if the reduced instance G′ has a feedback vertex set of size k′, then we can easily transform a minimum size feedback vertex set of G′ into a minimum size feedback vertex set of G. This kernelization algorithm can be used as the first step of an FPT algorithm for Feedback Vertex Set, but also as a preprocessing heuristic for Feedback Vertex Set.     

Approximation Algorithms for Requirement Cut on Graphs

In this paper, we unify several graph partitioning problems including multicut, multiway cut, and k-cut, into a single problem. The input to the requirement cut problem is an undirected edge-weighted graph G=(V,E), and g groups of vertices X ₁,…,X _g ⊆V, with each group X _i having a requirement r _i between 0 and |X _i |. The goal is to find a minimum cost set of edges whose removal separates each group X _i into at least r _i disconnected components. We give an O(log n⋅log (gR)) approximation algorithm for the requirement cut problem, where n is the total number of vertices, g is the number of groups, and R is the maximum requirement. We also show that the integrality gap of a natural LP relaxation for this problem is bounded by O(log n⋅log (gR)). On trees, we obtain an improved guarantee of O(log (gR)). There is an Ω(log g) hardness of approximation for the requirement cut problem, even on trees.     

A Fast Algorithm for the Path 2-Packing Problem

Let G be an undirected graph and $\mathcal{T}=\{T_{1},\ldots,T_{k}\}Let G be an undirected graph and T={T₁,?,T_k}\mathcal{T}=\{T_{1},\ldots,T_{k}\} be a collection of disjoint subsets of nodes. Nodes in T ₁∪⋅⋅⋅∪T _k are called terminals, other nodes are called inner. By a T\mathcal{T} -path we mean a path P such that P connects terminals from distinct sets in T\mathcal{T} and all internal nodes of P are inner. We study the problem of finding a maximum cardinality collection ℘ of T\mathcal{T} -paths such that at most two paths in ℘ pass through any node. Our algorithm is purely combinatorial and has the time complexity O(mn ²), where n and m denote the numbers of nodes and edges in G, respectively.     

The construction of mutually independent Hamiltonian cycles in bubble-sort graphs

A Hamiltonian cycle C=? u ₁, u ₂, …, u _n(G), u ₁ ? with n(G)=number of vertices of G, is a cycle C(u ₁; G), where u ₁ is the beginning and ending vertex and u _i is the ith vertex in C and u _i ≠u _j for any i≠j, 1≤i, j≤n(G). A set of Hamiltonian cycles {C ₁, C ₂, …, C _k } of G is mutually independent if any two different Hamiltonian cycles are independent. For a hamiltonian graph G, the mutually independent Hamiltonianicity number of G, denoted by h(G), is the maximum integer k such that for any vertex u of G there exist k-mutually independent Hamiltonian cycles of G starting at u. In this paper, we prove that h(B _n )=n?1 if n≥4, where B _n is the n-dimensional bubble-sort graph.     

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.     

Editing to Eulerian graphs

The Eulerian Editing problem asks, given a graph G and an integer k, whether G can be modified into an Eulerian graph using at most k edge additions and edge deletions. We show that this problem is polynomial-time solvable for both undirected and directed graphs. We generalize these results for problems with degree parity constraints and degree balance constraints, respectively. We also consider the variants where vertex deletions are permitted. Combined with known results, this leads to full complexity classifications for both undirected and directed graphs and for every subset of the three graph operations.     

Dominating Induced Matchings for P 7-Free Graphs in Linear Time

Let G be a finite undirected graph with edge set E. An edge set E′?E is an induced matching in G if the pairwise distance of the edges of E′ in G is at least two; E′ is dominating in G if every edge e∈E?E′ intersects some edge in E′. The Dominating Induced Matching Problem (DIM, for short) asks for the existence of an induced matching E′ which is also dominating in G; this problem is also known as the Efficient Edge Domination Problem. The DIM problem is related to parallel resource allocation problems, encoding theory and network routing. It is ${\mathbb{NP}}$ -complete even for very restricted graph classes such as planar bipartite graphs with maximum degree three. However, its complexity was open for P _k -free graphs for any k≥5; P _k denotes a chordless path with k vertices and k?1 edges. We show in this paper that the weighted DIM problem is solvable in linear time for P ₇-free graphs in a robust way.     

Time slot scheduling of compatible jobs

A version of weighted coloring of a graph is introduced which is motivated by some types of scheduling problems: each node v of a graph G corresponds to some operation to be processed (with a processing time w(v)), edges represent nonsimultaneity requirements (incompatibilities). We have to assign each operation to one time slot in such a way that in each time slot, all operations assigned to this slot are compatible; the length of a time slot will be the maximum of the processing times of its operations. The number k of time slots to be used has to be determined as well. So, we have to find a k-coloring = of G such that w(S ₁) + ⋅s +w(S _k ) is minimized where w(S _i ) = max {w(v) :v∊V}. Properties of optimal solutions are discussed, and complexity and approximability results are presented. Heuristic methods are given for establishing some of these results. The associated decision problems are shown to be NP-complete for bipartite graphs, for line-graphs of bipartite graphs, and for split graphs.     

Computing median and antimedian sets in median graphs

The median (antimedian) set of a profile π=(u ₁,…,u _k ) of vertices of a graph G is the set of vertices x that minimize (maximize) the remoteness ∑ _i d(x,u _i ). Two algorithms for median graphs G of complexity O(n idim(G)) are designed, where n is the order and idim(G) the isometric dimension of G. The first algorithm computes median sets of profiles and will be in practice often faster than the other algorithm which in addition computes antimedian sets and remoteness functions and works in all partial cubes.     

On the locatic number of graphs

A vertex v of a connected graph G distinguishes a pair u, w of vertices of G if d(v, u)≠d(v, w), where d(·,·) denotes the length of a shortest path between two vertices in G. A k-partition Π={S ₁, S ₂, …, S _k } of the vertex set of G is said to be a locatic partition if for every pair of distinct vertices v and w of G, there exists a vertex s∈S _i for all 1≤i≤k that distinguishes v and w. The cardinality of a largest locatic partition is called the locatic number of G. In this paper, we study the locatic number of paths, cycles and characterize all the connected graphs of order n having locatic number n, n?1 and n?2. Some realizable results are also given in this paper.     

On the stability number of the edge intersection of two graphs

Let G be the graph obtained as the edge intersection of two graphs G₁, G₂ on the same vertex set V. We show that if at least one of G₁, G₂ is perfect, then α(G)?α(G₁)·α(G₂), where α() is the cardinality of the largest stable set. Moreover, for general G₁ and G₂, we show that α(G)?R(α(G₁)+1,α(G₂)+1)−1, where R(k,?) is the Ramsey number.