Multicolorings of Series-Parallel Graphs

Let G be a graph, and let each vertex v of G have a positive integer weight ω(v). A multicoloring of G is to assign each vertex v a set of ω(v) colors so that any pair of adjacent vertices receive disjoint sets of colors. This paper presents an algorithm to find a multicoloring of a given series-parallel graph G with the minimum number of colors in time O(n W), where n is the number of vertices and W is the maximum weight of vertices in G.     

Experimental Analysis of Heuristic Algorithms for the Dominating Set Problem

We say a vertex v in a graph G covers a vertex w if v=w or if v and w are adjacent. A subset of vertices of G is a dominating set if it collectively covers all vertices in the graph. The dominating set problem, which is NP-hard, consists of finding a smallest possible dominating set for a graph. The straightforward greedy strategy for finding a small dominating set in a graph consists of successively choosing vertices which cover the largest possible number of previously uncovered vertices. Several variations on this greedy heuristic are described and the results of extensive testing of these variations is presented. A more sophisticated procedure for choosing vertices, which takes into account the number of ways in which an uncovered vertex may be covered, appears to be the most successful of the algorithms which are analyzed. For our experimental testing, we used both random graphs and graphs constructed by test case generators which produce graphs with a given density and a specified size for the smallest dominating set. We found that these generators were able to produce challenging graphs for the algorithms, thus helping to discriminate among them, and allowing a greater variety of graphs to be used in the experiments. Received October 27, 1998; revised March 25, 2001.     

Multicolorings of Series-Parallel Graphs

Let G be a graph, and let each vertex v of G have a positive integer weight (v). A multicoloring of G is to assign each vertex v a set of (v) colors so that any pair of adjacent vertices receive disjoint sets of colors. This paper presents an algorithm to find a multicoloring of a given series-parallel graph G with the minimum number of colors in time O(n W), where n is the number of vertices and W is the maximum weight of vertices in G.     

网络流量的有效测量方法分析

把网络流量的有效测量问题抽象为求给定图G=(V,E)的最小弱顶点覆盖集的问题.给出了一个求最小弱顶点覆盖集的近似算法,并证明了该算法具有比界2(lnd+1),其中d是图G中顶点的最大度.指出了该算法的时间复杂性为O(|V|²).     

Vertex arboricity of planar graphs without chordal 6-cycles

The vertex arboricity va(G) of a graph G is the minimum number of colours the vertices can be coloured so that each colour class induces a forest. It was known that va(G)≤3 for every planar graph G, and the problem of computing vertex arboricity of graphs is NP-hard. In this paper, we prove that va(G)≤2 if G is a planar graph without chordal 6-cycles. This extends a result by Raspaud and Wang [On the vertex-arboricity of planar graphs, Eur. J. Combin. 29 (2008), pp. 1064–1075].     

A 2-approximation algorithm for the vertex cover P4 problem in cubic graphs

A subset F of vertices of a graph G is called a vertex cover P_k set if every path of order k in G contains at least one vertex from F. Denote by ψ_k(G) the minimum cardinality of a vertex cover P_k set in G. The vertex cover P_k (VCP_k) problem is to find a minimum vertex cover P_k set. It is easy to see that the VCP₂ problem corresponds to the well-known vertex cover problem. In this paper, we restrict our attention to the VCP₄ problem in cubic graphs. The paper proves that the VCP₄ problem is NP-hard for cubic graphs. Further, we give sharp lower and upper bounds on ψ₄(G) for cubic graphs and propose a 2-approximation algorithm for the VCP₄ problem in cubic graphs.     

Super-connected and hyper-connected jump graphs

Let G be a connected graph. The graph G is said to be super-connected if for every minimum vertex cut S of G, G?S has isolated vertices. Moreover, it is said to be hyper-connected if for every minimum vertex cut S, G?S has exactly two components, one of which is an isolated vertex. In this note, we give a necessary and sufficient condition for a graph G whose jump graph J(G) (the complement of line graph of G) is, respectively, super-connected and hyper-connected.     

On the k-path cover problem for cacti

In this paper we investigate the k-path cover problem for graphs, which is to find the minimum number of vertex disjoint k-paths that cover all the vertices of a graph. The k-path cover problem for general graphs is NP-complete. Though notable applications of this problem to database design, network, VLSI design, ring protocols, and code optimization, efficient algorithms are known for only few special classes of graphs. In order to solve this problem for cacti, i.e., graphs where no edge lies on more than one cycle, we introduce the so-called Steiner version of the k-path cover problem, and develop an efficient algorithm for the Steiner k-path cover problem for cacti, which finds an optimal k-path cover for a given cactus in polynomial time.     

On Cutwidth Parameterized by Vertex Cover

We study the Cutwidth problem, where the input is a graph G, and the objective is find a linear layout of the vertices that minimizes the maximum number of edges intersected by any vertical line inserted between two consecutive vertices. We give an algorithm for Cutwidth with running time O(2 ^k n ^O(1)). Here k is the size of a minimum vertex cover of the input graph G, and n is the number of vertices in G. Our algorithm gives an O(2 ^n/2 n ^O(1)) time algorithm for Cutwidth on bipartite graphs as a corollary. This is the first non-trivial exact exponential time algorithm for Cutwidth on a graph class where the problem remains NP-complete. Additionally, we show that Cutwidth parameterized by the size of the minimum vertex cover of the input graph does not admit a polynomial kernel unless NP?coNP/poly. Our kernelization lower bound contrasts with the recent results of Bodlaender et al. (ICALP, Springer, Berlin, 2011; SWAT, Springer, Berlin, 2012) that both Treewidth and Pathwidth parameterized by vertex cover do admit polynomial kernels.     

Spanning Trees and the Complexity of Flood-Filling Games

We consider problems related to the combinatorial game (Free-) Flood-It, in which players aim to make a coloured graph monochromatic with the minimum possible number of flooding operations. We show that the minimum number of moves required to flood any given graph G is equal to the minimum, taken over all spanning trees T of G, of the number of moves required to flood T. This result is then applied to give two polynomial-time algorithms for flood-filling problems. Firstly, we can compute in polynomial time the minimum number of moves required to flood a graph with only a polynomial number of connected subgraphs. Secondly, given any coloured connected graph and a subset of the vertices of bounded size, the number of moves required to connect this subset can be computed in polynomial time.     

General-demand disjoint path covers in a graph with faulty elements

A k-disjoint path cover of a graph is a set of k internally vertex-disjoint paths which cover the vertex set with k paths and each of which runs between a source and a sink. Given that each source and sink v is associated with an integer-valued demand d(v)≥1, we are concerned with general-demand k-disjoint path cover in which every source and sink v is contained in the d(v) paths. In this paper, we present a reduction of a general-demand disjoint path cover problem to an unpaired many-to-many disjoint path cover problem, and obtain some results on disjoint path covers of restricted HL-graphs and proper interval graphs with faulty vertices and/or edges.     

The 1-Fixed-Endpoint Path Cover Problem is Polynomial on Interval Graphs

We consider a variant of the path cover problem, namely, the k-fixed-endpoint path cover problem, or kPC for short, on interval graphs. Given a graph G and a subset T\mathcal{T} of k vertices of V(G), a k-fixed-endpoint path cover of G with respect to T\mathcal{T} is a set of vertex-disjoint paths ℘ that covers the vertices of G such that the k vertices of T\mathcal{T} are all endpoints of the paths in ℘. The kPC problem is to find a k-fixed-endpoint path cover of G of minimum cardinality; note that, if T\mathcal{T} is empty the stated problem coincides with the classical path cover problem. In this paper, we study the 1-fixed-endpoint path cover problem on interval graphs, or 1PC for short, generalizing the 1HP problem which has been proved to be NP-complete even for small classes of graphs. Motivated by a work of Damaschke (Discrete Math. 112:49–64, 1993), where he left both 1HP and 2HP problems open for the class of interval graphs, we show that the 1PC problem can be solved in polynomial time on the class of interval graphs. We propose a polynomial-time algorithm for the problem, which also enables us to solve the 1HP problem on interval graphs within the same time and space complexity.     

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.     

A Generalization of AT-Free Graphs and a Generic Algorithm for Solving Triangulation Problems

Abstract. A subset A of the vertices of a graph G is an asteroidal set if for each vertex a ∈ A a connected component of G-N[a] exists containing A\backslash{a} . An asteroidal set of cardinality three is called asteriodal triple and graphs without an asteriodal triple are called AT-free . The maximum cardinality of an asteroidal set of G , denoted by \an(G) , is said to be the asteriodal number of G . We present a scheme for designing algorithms for triangulation problems on graphs. As a consequence, we obtain algorithms to compute graph parameters such as treewidth, minimum fill-in and vertex ranking number. The running time of these algorithms is a polynomial (of degree asteriodal number plus a small constant) in the number of vertices and the number of minimal separators of the input graph.     

On the adjacent vertex distinguishing edge colourings of graphs

A k-adjacent vertex distinguishing edge colouring or a k-avd-colouring of a graph G is a proper k-edge colouring of G such that no pair of adjacent vertices meets the same set of colours. The avd-chromatic number, denoted by χ′_a(G), is the minimum number of colours needed in an avd-colouring of G. It is proved that for any connected 3-colourable Hamiltonian graph G, we have χ′_a(G)≤Δ+3.     

Computing the metric dimension of the categorial product of some graphs

A set of vertices W is a resolving set of a graph G if every two vertices of G have distinct representations of distances with respect to the set W. The number of vertices in a smallest resolving set is called the metric dimension. This invariant has extensive applications in robotics, since the metric dimension can represent the minimum number of landmarks, which uniquely determine the position of a robot moving in a graph space. Finding the metric dimension of a graph is a non-deterministic polynomial-time hard problem. We present exact values of the metric dimension of several networks, which can be obtained as categorial products of graphs.     

Inverse degree and super edge-connectivity

Let G be a connected graph of order n, minimum degree δ(G) and edge connectivity λ(G). The graph G is called maximally edge-connected if λ(G)=δ(G), and super edge-connected if every minimum edge-cut consists of edges incident with a vertex of minimum degree. Define the inverse degree of G with no isolated vertices as R(G)=∑ _v∈V(G)1/d(v), where d(v) denotes the degree of the vertex v. We show that if R(G)<2+(n?2δ)/(n?δ) (n?δ?1), then G is super edge-connected. We also give an analogous result for triangle-free graphs.     

Combinatorial algorithms for feedback problems in directed graphs

Given a weighted directed graph G=(V,A), the minimum feedback arc set problem consists of finding a minimum weight set of arcs A′⊆A such that the directed graph (V,A?A′) is acyclic. Similarly, the minimum feedback vertex set problem consists of finding a minimum weight set of vertices containing at least one vertex for each directed cycle. Both problems are NP-complete. We present simple combinatorial algorithms for these problems that achieve an approximation ratio bounded by the length, in terms of number of arcs, of a longest simple cycle of the digraph.     

A Linear Time Algorithm for the Arc Disjoint Menger Problem in Planar Directed Graphs

Given a graph G=(V,E) and two vertices s,t ∈ V , s\neq t , the Menger problem is to find a maximum number of disjoint paths connecting s and t . Depending on whether the input graph is directed or not, and what kind of disjointness criterion is demanded, this general formulation is specialized to the directed or undirected vertex, and the edge or arc disjoint Menger problem, respectively. For planar graphs the edge disjoint Menger problem has been solved to optimality [W2], while the fastest algorithm for the arc disjoint version is Weihe's general maximum flow algorithm for planar networks [W1], which has running time \bf O (|V| log |V|) . Here we present a linear time, i.e., asymptotically optimal, algorithm for the arc disjoint version in planar directed graphs. Received August 1997; revised January 1999.