Approximability of partitioning graphs with supply and demand

Suppose that each vertex of a graph G is either a supply vertex or a demand vertex and is assigned a positive real number, called the supply or the demand. Each demand vertex can receive “power” from at most one supply vertex through edges in G. One thus wishes to partition G into connected components by deleting edges from G so that each component C either has no supply vertex or has exactly one supply vertex whose supply is at least the sum of demands in C, and wishes to maximize the fulfillment, that is, the sum of demands in all components with supply vertices. This maximization problem is known to be NP-hard even for trees having exactly one supply vertex and strongly NP-hard for general graphs. In this paper, we focus on the approximability of the problem. We first show that the problem is MAXSNP-hard and hence there is no polynomial-time approximation scheme (PTAS) for general graphs unless $\mathrm{P}=\mathrm{NP}$. We then present a fully polynomial-time approximation scheme (FPTAS) for series-parallel graphs having exactly one supply vertex.     

Minimum-weight cycle covers and their approximability

A cycle cover of a graph is a set of cycles such that every vertex is part of exactly one cycle. An L-cycle cover is a cycle cover in which the length of every cycle is in the set L⊆N.We investigate how well L-cycle covers of minimum weight can be approximated. For undirected graphs, we devise non-constructive polynomial-time approximation algorithms that achieve constant approximation ratios for all sets L. On the other hand, we prove that the problem cannot be approximated with a factor of 2−ε for certain sets L.For directed graphs, we devise non-constructive polynomial-time approximation algorithms that achieve approximation ratios of O(n), where n is the number of vertices. This is asymptotically optimal: We show that the problem cannot be approximated with a factor of o(n) for certain sets L.To contrast the results for cycle covers of minimum weight, we show that the problem of computing L-cycle covers of maximum weight can, at least in principle, be approximated arbitrarily well.     

Solving the path cover problem on circular-arc graphs by using an approximation algorithm

A path cover of a graph G=(V,E) is a family of vertex-disjoint paths that covers all vertices in V. Given a graph G, the path cover problem is to find a path cover of minimum cardinality. This paper presents a simple O(n)-time approximation algorithm for the path cover problem on circular-arc graphs given a set of n arcs with endpoints sorted. The cardinality of the path cover found by the approximation algorithm is at most one more than the optimal one. By using the result, we reduce the path cover problem on circular-arc graphs to the Hamiltonian cycle and Hamiltonian path problems on the same class of graphs in O(n) time. Hence the complexity of the path cover problem on circular-arc graphs is the same as those of the Hamiltonian cycle and Hamiltonian path problems on circular-arc graphs.     

Complete partitions of graphs

A complete partition of a graph G is a partition of its vertex set in which any two distinct classes are connected by an edge. Let cp(G) denote the maximum number of classes in a complete partition of G. This measure was defined in 1969 by Gupta [19], and is known to be NP-hard to compute for several classes of graphs. We obtain essentially tight lower and upper bounds on the approximability of this problem. We show that there is a randomized polynomial-time algorithm that given a graph G with n vertices, produces a complete partition of size Ω(cp(G)/√lgn). This algorithm can be derandomized. We show that the upper bound is essentially tight: there is a constant C > 1, such that if there is a randomized polynomial-time algorithm that for all large n, when given a graph G with n vertices produces a complete partition into at least C·cp(G)/√lgn classes, then NP ⊆ RTime(n ^{O(lg lg n)}). The problem of finding a complete partition of a graph is thus the first natural problem whose approximation threshold has been determined to be of the form Θ((lgn) ^c ) for some constant c strictly between 0 and 1. The work reported here is a merger of the results reported in [30] and [21].     

Approximating the fixed linear crossing number

We present a randomized polynomial-time approximation algorithm for the fixed linear crossing number problem (FLCNP). In this problem, the vertices of a graph are placed in a fixed order along a horizontal “node line” in the plane, each edge is drawn as an arc in one of the two half-planes (pages), and the objective is to minimize the number of edge crossings. FLCNP is NP-hard, and no previous polynomial-time approximation algorithms are known. We show that the problem can be generalized to k pages and transformed to the maximum k-cut problem which admits a randomized polynomial-time approximation. For the 2-page case, our approach leads to a randomized polynomial time 0.878+0.122ρ approximation algorithm for FLCNP, where ρ is the ratio of the number of conflicting pairs (pairs of edges that cross if drawn in the same page) to the crossing number. We further investigate this performance ratio on the random graph family G_n,1/2, where each edge of the complete graph K_n occurs with probability . We show that a longstanding conjecture for the crossing number of K_n implies that with probability at least 1-4e^-λ2, the expected performance bound of the algorithm on a random graph from G_n,1/2 is 1.366+O(λ/n). A series of experiments is performed to compare the algorithm against two other leading heuristics on a set of test graphs. The results indicate that the randomized algorithm yields near-optimal solutions and outperforms the other heuristics overall.     

Mutual exclusion scheduling with interval graphs or related classes, Part I

In this paper, the mutual exclusion scheduling problem is addressed. 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. 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 and K. Jansen Restrictions of graph partition problems. Part I, Theoretical Computer Science 148(1995) pp. 93-109]. Several polynomial-time solvable cases significant in practice are exhibited here, for which we took care to devise simple and efficient algorithms (in particular linear-time and space algorithms). On the other hand, by reinforcing the NP-hardness result of Bodlaender and Jansen, we obtain a more precise cartography of the complexity of the problem for the classes of graphs studied.     

Finding large cycles in Hamiltonian graphs

We show how to find in Hamiltonian graphs a cycle of length n^{Ω(1/loglogn)}=exp(Ω(logn/loglogn)). This is a consequence of a more general result in which we show that if G has a maximum degree d and has a cycle with k vertices (or a 3-cyclable minor H with k vertices), then we can find in O(n³) time a cycle in G of length k^Ω(1/logd). From this we infer that if G has a cycle of length k, then one can find in O(n³) time a cycle of length k^{Ω(1/(log(n/k)+loglogn))}, which implies the result for Hamiltonian graphs. Our results improve, for some values of k and d, a recent result of Gabow (2004) [11] showing that if G has a cycle of length k, then one can find in polynomial time a cycle in G of length . We finally show that if G has fixed Euler genus g and has a cycle with k vertices (or a 3-cyclable minor H with k vertices), then we can find in polynomial time a cycle in G of length f(g)k^Ω(1), running in time O(n²) for planar graphs.     

Approximation algorithms for the minimum rainbow subgraph problem

We consider the minimum rainbow subgraph problem (MRS): given a graph G, whose edges are coloured with p colours. Find a subgraph F⊆G of G of minimum order and with p edges such that each colour occurs exactly once. For graphs with maximum degree Δ(G) there is a greedy polynomial-time approximation algorithm for the MRS problem with an approximation ratio of Δ(G). In this paper we present a polynomial-time approximation algorithm with an approximation ratio of for Δ≥2.     

On the 2-rainbow domination in graphs

The concept of 2-rainbow domination of a graph G coincides with the ordinary domination of the prism G□K₂. In this paper, we show that the problem of deciding if a graph has a 2-rainbow dominating function of a given weight is NP-complete even when restricted to bipartite graphs or chordal graphs. Exact values of 2-rainbow domination numbers of several classes of graphs are found, and it is shown that for the generalized Petersen graphs GP(n,k) this number is between ⌈4n/5⌉ and n with both bounds being sharp.     

Weighted coloring on planar, bipartite and split graphs: Complexity and approximation

We study complexity and approximation of min weighted node coloring in planar, bipartite and split graphs. We show that this problem is NP-hard in planar graphs, even if they are triangle-free and their maximum degree is bounded above by 4. Then, we prove that min weighted node coloring is NP-hard in P₈-free bipartite graphs, but polynomial for P₅-free bipartite graphs. We next focus on approximability in general bipartite graphs and improve earlier approximation results by giving approximation ratios matching inapproximability bounds. We next deal with min weighted edge coloring in bipartite graphs. We show that this problem remains strongly NP-hard, even in the case where the input graph is both cubic and planar. Furthermore, we provide an inapproximability bound of 7/6−ε, for any ε>0 and we give an approximation algorithm with the same ratio. Finally, we show that min weighted node coloring in split graphs can be solved by a polynomial time approximation scheme.     

Minimum monopoly in regular and tree graphs

In this paper we consider a graph optimization problem called minimum monopoly problem, in which it is required to find a minimum cardinality set S⊆V, such that, for each u∈V, |N[u]∩S|?|N[u]|/2 in a given graph G=(V,E). We show that this optimization problem does not have a polynomial-time approximation scheme for k-regular graphs (k?5), unless P=NP. We show this by establishing two L-reductions (an approximation preserving reduction) from minimum dominating set problem for k-regular graphs to minimum monopoly problem for 2k-regular graphs and to minimum monopoly problem for (2k-1)-regular graphs, where k?3. We also show that, for tree graphs, a minimum monopoly set can be computed in linear time.     

On maximizing clique, clique-Helly and hereditary clique-Helly induced subgraphs

Clique-Helly and hereditary clique-Helly graphs are polynomial-time recognizable. Recently, we presented a proof that the clique graph recognition problem is NP-complete [L. Alcón, L. Faria, C.M.H. de Figueiredo, M. Gutierrez, Clique graph recognition is NP-complete, in: Proc. WG 2006, in: Lecture Notes in Comput. Sci., vol. 4271, Springer, 2006, pp. 269-277]. In this work, we consider the decision problems: given a graph G=(V,E) and an integer k≥0, we ask whether there exists a subset V^′⊆V with |V^′|≥k such that the induced subgraph G[V^′] of G is, variously, a clique, clique-Helly or hereditary clique-Helly graph. The first problem is clearly NP-complete, from the above reference; we prove that the other two decision problems mentioned are NP-complete, even for maximum degree 6 planar graphs. We consider the corresponding maximization problems of finding a maximum induced subgraph that is, respectively, clique, clique-Helly or hereditary clique-Helly. We show that these problems are Max SNP-hard, even for maximum degree 6 graphs. We show a general polynomial-time -approximation algorithm for these problems when restricted to graphs with fixed maximum degree Δ. We generalize these results to other graph classes. We exhibit a polynomial 6-approximation algorithm to minimize the number of vertices to be removed in order to obtain a hereditary clique-Helly subgraph.     

On maximum planar induced subgraphs

The nonplanar vertex deletion or vertex deletion vd(G) of a graph G is the smallest nonnegative integer k, such that the removal of k vertices from G produces a planar graph G^′. In this case G^′ is said to be a maximum planar induced subgraph of G. We solve a problem proposed by Yannakakis: find the threshold for the maximum degree of a graph G such that, given a graph G and a nonnegative integer k, to decide whether vd(G)?k is NP-complete. We prove that it is NP-complete to decide whether a maximum degree 3 graph G and a nonnegative integer k satisfy vd(G)?k. We prove that unless P=NP there is no polynomial-time approximation algorithm with fixed ratio to compute the size of a maximum planar induced subgraph for graphs in general. We prove that it is Max SNP-hard to compute vd(G) when restricted to a cubic input G. Finally, we exhibit a polynomial-time -approximation algorithm for finding a maximum planar induced subgraph of a maximum degree 3 graph.     

On Generating Triangle-Free Graphs

We show that the problem to decide whether a graph can be made triangle-free with at most k edge deletions remains NP-complete even when restricted to planar graphs of maximum degree seven. In addition, we provide polynomial-time data reduction rules for this problem and obtain problem kernels consisting of 6k vertices for general graphs and 11k/3 vertices for planar graphs.     

On a disparity between relative cliquewidth and relative NLC-width

Cliquewidth and NLC-width are two closely related parameters that measure the complexity of graphs. Both clique- and NLC-width are defined to be the minimum number of labels required to create a labelled graph by certain terms of operations. Many hard problems on graphs become solvable in polynomial-time if the inputs are restricted to graphs of bounded clique- or NLC-width. Cliquewidth and NLC-width differ at most by a factor of two.The relative counterparts of these parameters are defined to be the minimum number of labels necessary to create a graph while the tree-structure of the term is fixed. We show that Relative Cliquewidth and Relative NLC-width differ significantly in computational complexity. While the former problem is NP-complete the latter is solvable in polynomial time. The relative NLC-width can be computed in O(n³) time, which also yields an exact algorithm for computing the NLC-width in time O(3ⁿn). Additionally, our technique enables a combinatorial characterisation of NLC-width that avoids the usual operations on labelled graphs.     

Minimum cut bases in undirected networks

Given an undirected, connected network G=(V,E) with weights on the edges, the cut basis problem is asking for a maximal number of linear independent cuts such that the sum of the cut weights is minimized. Surprisingly, this problem has not attained as much attention as another graph theoretic problem closely related to it, namely, the cycle basis problem. We consider two versions of the problem: the unconstrained and the fundamental cut basis problem.For the unconstrained case, where the cuts in the basis can be of an arbitrary kind, the problem can be written as a multiterminal network flow problem, and is thus solvable in strongly polynomial time. In contrast, the fundamental cut basis problem, where all cuts in the basis are obtained by deleting an edge, each from a spanning tree T, is shown to be NP-hard. In this proof, we also show that a tree which induces the minimum fundamental cycle basis is also an optimal solution for the minimum fundamental cut basis problem in unweighted graphs.We present heuristics, integer programming formulations and summarize first experiences with numerical tests.     

The basis number of the composition of theta graphs with stars and wheels

he basis number, b(G), of a graph G is defined to be the least integer k such that G has a k-fold basis for its cycle space. In this paper we investigate the basis number of the composition of theta graphs with stars and wheels. This revised version was published online in June 2006 with corrections to the Cover Date.     

Hamilton cycles in claw-heavy graphs

A graph G on n≥3 vertices is called claw-heavy if every induced claw (K_1,3) of G has a pair of nonadjacent vertices such that their degree sum is at least n. In this paper we show that a claw-heavy graph G has a Hamilton cycle if we impose certain additional conditions on G involving numbers of common neighbors of some specific pair of nonadjacent vertices, or forbidden induced subgraphs. Our results extend two previous theorems of Broersma, Ryjá?ek and Schiermeyer [H.J. Broersma, Z. Ryjá?ek, I. Schiermeyer, Dirac’s minimum degree condition restricted to claws, Discrete Math. 167-168 (1997) 155-166], on the existence of Hamilton cycles in 2-heavy graphs.     

The Basis Number of Some Special Non-Planar Graphs

The basis number of a graph G was defined by Schmeichel to be the least integer h such that G has an h-fold basis for its cycle space. He proved that for m, n 5, the basis number b(K _m,n ) of the complete bipartite graph K _m,n is equal to 4 except for K _6,10, K _5,n and K _6,n with n = 5, 6, 7, 8. We determine the basis number of some particular non-planar graphs such as K _5,n and K _6,n , n = 5, 6, 7, 8, and r-cages for r = 5, 6, 7, 8, and the Robertson graph.     

The basis number of a graph

MacLane proved that a graph is planar if and only if it has a 2-fold basis for its cycle space. We define the basis number of a graph G to be the least integer k such that G has a k-fold basis for its cycle space. We investigate the basis number of the complete graphs, complete bipartite graphs, and the n-cube.