Search

Abstract In this paper, we empirically profile three algorithms for the Shortest Negative Cost Cycle (SNCC) problem. In this problem, we are given a directed, weighted graph G = 〈 V , E , c 〉 , and the goal is to identify a negative cost cycle with the fewest number of edges. The SNCC problem finds applications in a number of domains ranging from program verification to certifying algorithm design. The first polynomial time algorithm for this problem was proposed in Subramani (2009). Since then, several additional techniques, including a randomized approach, have been proposed for the SNCC problem. Our goal in this paper is to analyze three algorithmic paradigms for this problem from the empirical perspective. Towards this end, we profile these algorithmic approaches over a wide range of inputs. Our results indicated that the randomized algorithm is the algorithm of choice over a number of graph classes. [ABSTRACT FROM AUTHOR]

Abstract The paper is devoted to a Gram classification of an important class of signed graphs with loops playing an important role in many branches of mathematics, physics and computer science including game theory, crystallography, Diophantine geometry, Lie theory, spectral graph theory, a graph coloring technique, algebraic methods in graph theory. They have many deep applications in spectral machine learning methods, electrical networks, to link sign prediction in signed unipartite and bipartite networks, and community partition in social networks. We continue the study of finite connected edge-bipartite graphs Δ (bigraphs, for short), with m ≥ 2 vertices (a class of signed graphs), started in Simson (2013) and developed in Simson (2016) by means of the non-symmetric Gram matrix G ˇ Δ ∈ M m (Z) defining Δ , its symmetric Gram matrix G Δ : = 1 2 [ G ˇ Δ + G ˇ Δ t r ] ∈ M m (1 2 Z) , and the Gram quadratic form q Δ : Z m → Z. In the present paper, given n ≥ 1 , we mainly study connected principal Cox-regular edge-bipartite graphs Δ with loops and n + 1 ≥ 2 vertices, in the sense that the symmetric Gram matrix G Δ ∈ M n + 1 (Z) of Δ is positive semi-definite of rank n ≥ 1. Our aim is to classify such edge-bipartite graphs by means of an inflation algorithm, up to the weak Gram Z -congruence Δ ∼ Z Δ ′ , where Δ ∼ Z Δ ′ means that G Δ ′ = B t r ⋅ G Δ ⋅ B , for some B ∈ M n + 1 (Z) with det B = ± 1. Our main result of the paper asserts that, given a principal Cox-regular connected edge-bipartite graph Δ with n + 1 ≥ 2 vertices, there exists an edge-bipartite Euclidean graph D n + 1 of Tables A and B, and a suitably chosen sequence t • − of the inflation operators, each of one of the forms Δ ′ ↦ t a − Δ ′ or Δ ′ ↦ t a b − Δ ′ , such that the composite operator Δ ↦ t • − Δ reduces Δ to the bigraph D n + 1 such that: (i) Δ ∼ Z D n + 1 and (ii) the bigraphs Δ , and D n + 1 have the same number of loops. The algorithm does not change loops and computes a matrix B ∈ M n + 1 (Z) , with det B = ± 1 , defining the weak Gram Z -congruence Δ ∼ Z D n + 1 , that is, satisfying the equation G D n + 1 = B t r ⋅ G Δ ⋅ B. [ABSTRACT FROM AUTHOR]

In this paper, we study the most basic domination invariants in graphs, in which number 2 is intrinsic part of their definitions. We classify them upon three criteria, two of which give the following previously studied invariants: the weak 2 -domination number, γ w 2 ( G ) , the 2 -domination number, γ 2 ( G ) , the { 2 } -domination number, γ { 2 } ( G ) , the double domination number, γ × 2 ( G ) , the total { 2 } -domination number, γ t { 2 } ( G ) , and the total double domination number, γ t × 2 ( G ) , where G is a graph in which the corresponding invariant is well defined. The third criterion yields rainbow versions of the mentioned six parameters, one of which has already been well studied, and three other give new interesting parameters. Together with a special, extensively studied Roman domination, γ R ( G ) , and two classical parameters, the domination number, γ ( G ) , and the total domination number, γ t ( G ) , we consider 13 domination invariants in graphs. In the main result of the paper we present sharp upper and lower bounds of each of the invariants in terms of every other invariant, a large majority of which are new results proven in this paper. As a consequence of the main theorem we obtain new complexity results regarding the existence of approximation algorithms for the studied invariants, matched with tight or almost tight inapproximability bounds, which hold even in the class of split graphs. [ABSTRACT FROM AUTHOR]

A circulant graph C n ( a 1 , … , a k ) is a graph with n vertices { v 0 , … , v n − 1 } such that each vertex v i is adjacent to vertices v ( i + a j ) m o d n , for j = 1 , … , k . In this paper we investigate the vertex colouring problem on circulant graphs. We approach the problem in a purely combinatorial way based on an array representation and propose an exact O ( k 3 log 2 n + n ) algorithm for a subclass of 3-chromatic C n ( a 1 , … , a k ) ’s with k ≥ 2 , which are characterized in the paper. [ABSTRACT FROM AUTHOR]

Many hard graph problems, such as Hamiltonian Cycle, become FPT when parameterized by treewidth, a parameter that is bounded only on sparse graphs. When parameterized by the more general parameter clique-width, Hamiltonian Cycle becomes W[1]-hard, as shown by Fomin et al. (2010). Sæther and Telle address this problem in their paper (Sæther and Telle, 2016) by introducing a new parameter, split-matching-width, which lies between treewidth and clique-width in terms of generality. They show that even though graphs of restricted split-matching-width might be dense, solving problems such as Hamiltonian Cycle can be done in FPT time. Recently, it was shown that Hamiltonian Cycle parameterized by treewidth is in EPT (Bodlaender et al., 2013; Fomin et al., 2014), meaning it can be solved in n O ( 1 ) 2 O ( k ) -time. In this paper, using tools from Fomin et al. (2014), we show that also parameterized by split-matching-width Hamiltonian Cycle is EPT. To the best of our knowledge, this is the first EPT algorithm for any “globally constrained” graph problem parameterized by a non-trivial and non-sparse structural parameter. To accomplish this, we also give an algorithm constructing a branch decomposition approximating the minimum split-matching-width to within a constant factor. Combined, these results show that the algorithms in Sæther and Telle (2016) for Edge Dominating Set, Chromatic Number and Max Cut all can be improved. In fact, using our new approximation algorithm, under the Exponential Time Hypothesis, the Hamiltonian Cycle algorithm of this paper, and the three algorithms for MaxCut, Edge Dominating Set, and Chromatic Number, are asymptotically optimal. [ABSTRACT FROM AUTHOR]

This paper presents a new algorithmic framework for some basic problems on binary images. Algorithms for binary images such as one of extracting a connected component containing a query pixel and that of connected components labeling play basic roles in image processing. Those algorithms usually use linear work space for efficient implementation. In this paper we propose algorithms for several basic problems on binary images which are efficient in time and space, using space-efficient algorithms for grid graphs. More exactly, some of them run in O ( n log n ) time using O ( 1 ) work space and the others run in O ( n ) or O ( n log n ) time using O ( n ) work space for a binary image of n pixels stored in a read-only array. [ABSTRACT FROM AUTHOR]

Abstract An edge metric generator of a connected graph G is a vertex subset S for which every two distinct edges of G have distinct distance to some vertex of S , where the distance between a vertex v and an edge e is defined as the minimum of distances between v and the two endpoints of e in G. The smallest cardinality of an edge metric generator of G is the edge metric dimension, denoted by dim e (G). It follows that 1 ≤ dim e (G) ≤ n − 1 for any n -vertex graph G. A graph whose edge metric dimension achieves the upper bound is topful. In this paper, the structure of topful graphs is characterized, and many necessary and sufficient conditions for a graph to be topful are obtained. Using these results we design an O (n 3) time algorithm which determines whether a graph of order n is topful or not. Moreover, we describe and address an interesting class of topful graphs whose super graphs obtained by adding one edge are not topful. [ABSTRACT FROM AUTHOR]

Abstract Several graph theoretic watermark methods have been proposed to encode numbers as graph structures in software watermarking environments. In this paper we propose an efficient and easily implementable codec system for encoding watermark numbers as reducible permutation flow-graphs and, thus, we extend the class of graphs used in such a watermarking environment. More precisely, we present an algorithm for encoding a watermark number w as a self-inverting permutation π ∗ , an algorithm for encoding the self-inverting permutation π ∗ into a reducible permutation graph F [ π ∗ ] whose structure resembles the structure of real program graphs, as well as decoding algorithms which extract the permutation π ∗ from the reducible permutation graph F [ π ∗ ] and the number w from π ∗. Both the encoding and the decoding process take, in the worst-case, time and space linear in the length of the binary representation of w. The two main components of our proposed codec system, i.e., the self-inverting permutation π ∗ and the reducible permutation graph F [ π ∗ ] , incorporate the binary representation of the watermark w in their structure and possess important structural properties, which make our system resilient to attacks; to this end, we experimentally evaluated our system under edge modification attacks on the graph F [ π ∗ ] and the results suggest that we can detect such attacks with high probability. [ABSTRACT FROM AUTHOR]

Given a graph G = ( V , E ) of order n and maximum degree Δ , the NP -complete S - labeling problem consists in finding a labeling of G , i.e. a bijective mapping ϕ : V → { 1 , 2 … n } , such that SL ϕ ( G ) = ∑ u v ∈ E min { ϕ ( u ) , ϕ ( v ) } is minimized. In this paper, we study the S - labeling problem, with a particular focus on algorithmic issues. We first give intrinsic properties of optimal labelings, which will prove useful for our algorithmic study. We then provide lower bounds on SL ϕ ( G ) , together with a generic greedy algorithm, which collectively allow us to approximate the problem in several classes of graphs—in particular, we obtain constant approximation ratios for regular graphs and bounded degree graphs. We also show that deciding whether there exists a labeling ϕ of G such that SL ϕ ( G ) ≤ | E | + k is solvable in O ∗ ( 2 2 k ( 2 k ) ! ) time, thus fixed-parameterized tractable in k . We finally show that the S - Labeling problem is polynomial-time solvable for two classes of graphs, namely split graphs and (sets of) caterpillars. [ABSTRACT FROM AUTHOR]

A graph G = ( V , E ) is a word-representable graph if there exists a word W over the alphabet V such that letters x and y alternate in W if and only if ( x , y ) ∈ E for each x ≠ y . In this paper we give an effective characterization of word-representable graphs in terms of orientations. Namely, we show that a graph is word-representable if and only if it admits a semi-transitive orientation defined in the paper. This allows us to prove a number of results about word-representable graphs, in particular showing that the recognition problem is in NP, and that word-representable graphs include all 3-colorable graphs. We also explore bounds on the size of the word representing the graph. The representation number of G is the minimum k such that G is a representable by a word, where each letter occurs k times; such a k exists for any word-representable graph. We show that the representation number of a word-representable graph on n vertices is at most 2 n , while there exist graphs for which it is n / 2 . [ABSTRACT FROM AUTHOR]

This paper introduces the notion of involution module, the first generalization of the modular decomposition of 2-structures which has a unique linear-sized decomposition tree. We derive an O ( n 2 ) decomposition algorithm and we take advantage of the involution modular decomposition tree to obtain several algorithmic results. It is well-known that cographs (or equivalently P 4 -free graphs) are the graphs that are totally decomposable w.r.t modular decomposition. In a similar way, we introduce the class of switch cographs, as the class of graphs that are totally decomposable w.r.t involution modular decomposition. This class generalizes the class of cographs and appears to be exactly the class of (Bull, Gem, Co-Gem, C 5 )-free graphs. We use our new decomposition tool to design three practical algorithms for the maximum cut, vertex cover and vertex separator problems. The complexity of these problems was still unknown for this class of graphs. This paper also improves the complexity of the maximum clique, the maximum independent set, the chromatic number and the maximum clique cover problems by giving efficient algorithms, thanks to the decomposition tree. Eventually, we show that this class of graphs has clique-width at most 4 and that a clique-width expression can be computed in linear time. [ABSTRACT FROM AUTHOR]

We study the problem of finding in a graph an inclusionwise maximal independent set of minimum cardinality, known as minimum maximal independent set or independent dominating set problem. This is one of the hardest problems in algorithmic graph theory. In particular, restricted to the class of so called SAT-graphs, this problem coincides with satisfiability , the central problem of theoretical computer science. The class of SAT-graphs, and many other important graph classes, such as graphs of bounded vertex degree or line graphs, can be characterized by finitely many forbidden induced subgraphs. We call such classes finitely defined. The paper [R. Boliac and V. Lozin, Independent domination in finitely defined classes of graphs, Theoretical Computer Science, 301 (2003) 271–284] reveals various conditions under which the independent dominating set problem remains NP-hard in a finitely defined class. In the present paper, we identify a number of finitely defined classes where the problem admits polynomial-time solutions. In particular, we prove that the problem is solvable in polynomial time in the class of P 2 + P 3 -free graphs by correcting a mistake of the first two authors of the paper in their earlier solution. This result is in a sharp contrast with the fact that in the class of P 3 + P 3 -free graphs the problem is known to be NP-hard, since this class contains all SAT-graphs. [ABSTRACT FROM AUTHOR]

The Grundy number of a graph is the maximum number of colors used by the greedy coloring algorithm over all vertex orderings. In this paper, we study the computational complexity of Grundy Coloring , the problem of determining whether a given graph has Grundy number at least k . We also study the variants Weak Grundy Coloring (where the coloring is not necessarily proper) and Connected Grundy Coloring (where at each step of the greedy coloring algorithm, the subgraph induced by the colored vertices must be connected). We show that Grundy Coloring can be solved in time O ∗ ( 2 . 44 3 n ) and Weak Grundy Coloring in time O ∗ ( 2 . 71 6 n ) on graphs of order n . While Grundy Coloring and Weak Grundy Coloring are known to be solvable in time O ∗ ( 2 O ( w k ) ) for graphs of treewidth w (where k is the number of colors), we prove that under the Exponential Time Hypothesis (ETH), they cannot be solved in time O ∗ ( 2 o ( w log w ) ) . We also describe an O ∗ ( 2 2 O ( k ) ) algorithm for Weak Grundy Coloring , which is therefore FPT for the parameter k . Moreover, under the ETH, we prove that such a running time is essentially optimal (this lower bound also holds for Grundy Coloring ). Although we do not know whether Grundy Coloring is in FPT , we show that this is the case for graphs belonging to a number of standard graph classes including chordal graphs, claw-free graphs, and graphs excluding a fixed minor. We also describe a quasi-polynomial time algorithm for Grundy Coloring and Weak Grundy Coloring on apex-minor graphs. In stark contrast with the two other problems, we show that Connected Grundy Coloring is NP -complete already for k = 7 colors. [ABSTRACT FROM AUTHOR]

In this paper, we introduce a new convexity on graphs similar to the well known P 3 -convexity, which we will call P 3 ∗ -convexity. We show that several P 3 ∗ -convexity parameters (hull number, convexity number, Carathéodory number, Radon number, interval number and percolation time) are NP-hard even on bipartite graphs. We prove a strong relationship between this convexity and the well known geodesic convexity, which implies several NP-hardness results for the latter. In order to show that, we prove that the hull number for the P 3 -convexity is NP-hard even for subgraphs of grids and that the convexity number for the P 3 -convexity is NP-hard even for bipartite graphs with diameter 3. We also obtain linear time algorithms to determine those parameters for the above mentioned convexities for cographs and P 4 -sparse graphs. [ABSTRACT FROM AUTHOR]

For a finite, simple, undirected graph G with a vertex weight function, the Maximum Weight Independent Set (MWIS) problem asks for an independent vertex set of G with maximum weight. MWIS is a well-known NP-hard problem of fundamental importance. For claw-free graphs, MWIS can be solved in polynomial time—in 1980, the first two such algorithms were independently found by Minty for MWIS and by Sbihi for the unweighted case. For a constant ℓ ≥ 2 , let ℓ G denote the disjoint union of ℓ copies of G . In this paper, using a dynamic programming approach (inspired by Farber’s result about MWIS for 2 K 2 -free graphs), we show that for any fixed ℓ , MWIS can be solved in polynomial time for ℓ claw-free graphs. This solves the open cases for MWIS on ( P 3 + claw)-free graphs and on ( 2 K 2 + claw)-free graphs and extends known results for claw-free graphs, ℓ K 2 -free graphs, ( K 2 + claw)-free graphs, and ℓ P 3 -free graphs. [ABSTRACT FROM AUTHOR]

The signless Laplacian Estrada index of a graph is defined as S L E E ( G ) = ∑ i = 1 n e q i , where q 1 , q 2 , … , q n are the eigenvalues of the signless Laplacian matrix of G . In this paper, we determine the unique bicyclic graph with maximum S L E E and the unique bipartite bicyclic graph with maximum S L E E , respectively. [ABSTRACT FROM AUTHOR]

Given a family F of graphs, let Free ( F ) be the class of graphs that do not contain any member of F as an induced subgraph. When F is a set of four-vertex graphs the complexity of the vertex coloring problem in Free ( F ) is known, with three exceptions: F = { claw , 4 K 1 } , F = { claw , 4 K 1 , co-diamond } , and F = { C 4 , 4 K 1 } . In this paper, we study the coloring problem for Free (claw, 4 K 1 ). We solve the vertex coloring problem for a subclass of Free (claw, 4 K 1 ) which contains the class of 4 K 1 -free line graphs. [ABSTRACT FROM AUTHOR]

This paper deals with open shops subject to the constraint that some conflicting jobs cannot be processed simultaneously on different machines. In the context of our study, these conflicts are given by an undirected graph, called the conflict graph. We seek a schedule that minimizes the maximum completion time (makespan). We first prove the NP-hardness of different versions of this problem. Then, we present polynomial-time solvable cases, for which we devise simple and efficient algorithms. On the other hand, we present heuristics and lower bounds for the general case. The heuristics are based on the construction of matchings in bipartite graphs as well as on a specific insertion technique combined with beam search. Finally, we test the efficiency of the heuristics and report our computational experiments that display satisfying results. [ABSTRACT FROM AUTHOR]

Abstract: In this paper 1 [1] The extended abstract of this paper appeared on PPAM 2009, LNCS 6067 (2010) 11–20. we study the problem of interval incidence coloring of bipartite graphs. We show the upper bound for interval incidence coloring number ( ) for bipartite graphs , and we prove that holds for regular bipartite graphs. We solve this problem for subcubic bipartite graphs, i.e. we fully characterize the subcubic graphs that admit 4, 5 or 6 coloring, and we construct a linear time exact algorithm for subcubic bipartite graphs. We also study the problem for bipartite graphs with and we show that 5-coloring is easy and 6-coloring is hard ( -complete). Moreover, we construct an time optimal algorithm for trees. [Copyright &y& Elsevier]

Abstract: This paper studies a variation of domination in graphs called rainbow domination. For a positive integer , a -rainbow dominating function of a graph is a function such that for any vertex with . The -rainbow domination number of is the minimum value of , where runs over all -rainbow dominating functions of . A related concept is as follows. A weak -dominating function of is a function such that for any vertex with . The weak -domination number of is the minimum value of , where runs over all weak -dominating functions of . In this paper, we prove that for any strongly chordal graph . Our approach is a more general setting called the -function, which leads to interesting results on other variations of domination. We also give a linear-time algorithm for finding the weak -domination numbers of block graphs. [Copyright &y& Elsevier]

Abstract: This paper deals with problems on non-oriented edge-colored graphs. The aim is to find a route between two given vertices and . This route can be a walk, a trail or a path. Each time a vertex is crossed by a walk there is an associated non-negative reload cost , where and denote, respectively, the colors of successive edges in this walk. The goal is to find a route whose total reload cost is minimum. Polynomial algorithms and proofs of NP-hardness are given for particular cases: when the triangle inequality is satisfied or not, when reload costs are symmetric (i.e., ) or asymmetric. We also investigate bounded degree graphs and planar graphs. We conclude the paper with the traveling salesman problem with reload costs. [Copyright &y& Elsevier]

Abstract: In this paper, we consider the evacuation problem in a network which consists of a directed graph with capacities and transit times on its arcs. This problem can be solved by the algorithm of Hoppe and Tardos [B. Hoppe, É. Tardos, The quickest transshipment problem, Math. Oper. Res. 25(1) (2000) 36–62] in polynomial time. However their running time is high-order polynomial, and hence is not practical in general. Thus, it is necessary to devise a faster algorithm for a tractable and practically useful subclass of this problem. In this paper, we consider a network with a sink such that (i) for each vertex the sum of the transit times of arcs on any path from to takes the same value, and (ii) for each vertex the minimum - cut is determined by the arcs incident to whose tails are reachable from . This class of networks is a generalization of grid networks studied in the paper [N. Kamiyama, N. Katoh, A. Takizawa, An efficient algorithm for evacuation problem in dynamic network flows with uniform arc capacity, IEICE Trans. Infrom. Syst. E89-D (8) (2006) 2372–2379]. We propose an efficient algorithm for this network problem. [Copyright &y& Elsevier]

Abstract: This paper deals with the mathematical properties of watersheds in weighted graphs linked to region merging methods, as used in image analysis. In a graph, a cleft (or a binary watershed) is a set of vertices that cannot be reduced, by point removal, without changing the number of regions (connected components) of its complement. To obtain a watershed adapted to morphological region merging, it has been shown that one has to use the topological thinnings introduced by M. Couprie and G. Bertrand. Unfortunately, topological thinnings do not always produce thin clefts. Therefore, we introduce a new transformation on vertex weighted graphs, called C-watershed, that always produces a cleft. We present the class of perfect fusion graphs, for which any two neighboring regions can be merged, while preserving all other regions, by removing from the cleft the points adjacent to both. An important theorem of this paper states that, on these graphs, the C-watersheds are topological thinnings and the corresponding divides are thin clefts. We propose a linear-time immersion-like algorithm to compute C-watersheds on perfect fusion graphs, whereas, in general, a linear-time topological thinning algorithm does not exist. Furthermore, we prove that this algorithm is monotone in the sense that the vertices are processed in increasing order of weight. Finally, we derive some characterizations of perfect fusion graphs based on the thinness properties of both C-watersheds and topological watersheds. [Copyright &y& Elsevier]

Abstract: Given a finite set , and a hypergraph , the hypergraph transversal problem calls for enumerating all minimal hitting sets (transversals) for . This problem plays an important role in practical applications as many other problems were shown to be polynomially equivalent to it. Fredman and Khachiyan [On the complexity of dualization of monotone disjunctive normal forms, J. Algorithms 21 (1996) 618–628] gave an incremental quasi-polynomial-time algorithm for solving the hypergraph transversal problem. In this paper, we present an efficient implementation of this algorithm. While we show that our implementation achieves the same theoretical worst-case bound, practical experience with this implementation shows that it can be substantially faster. We also show that a slight modification of the original algorithm can be used to obtain a stronger bound on the running time. More generally, we consider a monotone property over a bounded n-dimensional integral box. As an important application of the above hypergraph transversal problem, pioneered by Bioch and Ibaraki [Complexity of identification and dualization of positive Boolean functions, Inform. and Comput. 123 (1995) 50–63], we consider the problem of incrementally generating simultaneously all minimal subsets satisfying and all maximal subsets not satisfying , for properties given by a polynomial-time satisfiability oracle. Problems of this type arise in many practical applications. It is known that the above joint generation problem can be solved in incremental quasi-polynomial time via a polynomial-time reduction to a generalization of the hypergraph transversal problem on integer boxes. In this paper we present an efficient implementation of this procedure, and present experimental results to evaluate our implementation for a number of interesting monotone properties . [Copyright &y& Elsevier]

Abstract: The path-partition problem is to find a minimum number of vertex-disjoint paths that cover all vertices of a given graph. This paper studies the path-partition problem from an algorithmic point of view. As the Hamiltonian path problem is NP-complete for many classes of graphs, so is the path-partition problem. The main result of this paper is to present a linear-time algorithm for the path-partition problem in graphs whose blocks are complete graphs, cycles or complete bipartite graphs. [Copyright &y& Elsevier]

This paper deals with optimization problems on rotagraphs and fasciagraphs. These graphs are repetitive structures that generalize grids and toroidal grids, respectively. We develop a theoretical framework and get linear-time and constant-time generic algorithms for wide classes of combinatorial problems which are defined in a purely combinatorial way. These classes of problems include in particular many classical optimization problems that are NP-complete in general. Our results unify in a single framework many results of the literature, in particular on the topic of domination–and its variants–in grids. [ABSTRACT FROM AUTHOR]

A many-to-many k -disjoint path cover ( k -DPC for short) of a graph G joining the pairwise disjoint vertex sets S and T , each of size k , is a collection of k vertex-disjoint paths between S and T , which altogether cover every vertex of G . This is classified as paired , if each vertex of S must be joined to a specific vertex of T , or unpaired , if there is no such constraint. In this paper, we develop a linear-time algorithm for the Unpaired DPC problem of finding an unpaired DPC joining S and T given in a unit interval graph, to which the One-to-One DPC and the One-to-Many DPC problems are reduced in linear time. Additionally, we show that the Paired k - DPC problem on a unit interval graph is polynomially solvable for any fixed k . [ABSTRACT FROM AUTHOR]

Although, the Hamiltonicity of solid grid graphs are polynomial-time decidable, the complexity of the longest cycle problem in these graphs is still open. In this paper, by presenting a linear-time constant-factor approximation algorithm, we show that the longest cycle problem in solid grid graphs is in APX. More precisely, our algorithm finds a cycle of length at least 2 n 3 + 1 in 2-connected n -node solid grid graphs. [ABSTRACT FROM AUTHOR]

The scientific literature teems with clique-centric clustering strategies. In this paper we analyze one such method, the paraclique algorithm. Paraclique has found practical utility in a variety of application domains, and has been successfully employed to reduce the effects of noise. Nevertheless, its formal analysis and worst-case guarantees have remained elusive. We address this issue by deriving a series of lower bounds on paraclique densities. [ABSTRACT FROM AUTHOR]

In this paper, we study the competition graphs of oriented complete bipartite graphs. We characterize graphs that can be represented as the competition graphs of oriented complete bipartite graphs. We also present the graphs having the maximum number of edges and the graphs having the minimum number of edges among such graphs. [ABSTRACT FROM AUTHOR]

The average eccentricity e c c ( G ) of a graph G is the mean value of eccentricities of all vertices of G . In this paper, we continue the work of Ilić (2012) and resolve a conjecture, obtained by the system AutoGraphiX, about the upper bound on the sum of the average eccentricity and the domination number among connected graphs on n vertices. [ABSTRACT FROM AUTHOR]

An r -dynamic k -coloring of a graph G is a proper vertex k -coloring of G such that the neighbors of any vertex v receive at least min { r , deg ( v ) } different colors. The r -dynamic chromatic number of G , χ r ( G ) , is defined as the smallest k such that G admits an r -dynamic k -coloring. In this paper, first we introduce an upper bound for χ r ( G ) in terms of r , chromatic number, maximum degree and minimum degree. Then, motivated by a conjecture of Montgomery (2001) stating that for a d -regular graph G , χ 2 ( G ) − χ ( G ) ≤ 2 , we prove two upper bounds for χ 2 − χ on regular graphs. Our first upper bound ⌈ 5.437 log d + 2.721 ⌉ improves a result of Alishahi (2011). Also, our second upper bound shows that Montgomery’s conjecture is implied by the existence of a χ ( G ) -coloring for any regular graph G , such that any two vertices whose neighbors are unicolored in this coloring, have no common neighbor. [ABSTRACT FROM AUTHOR]

Diagnosability plays an important role in measuring the reliability of interconnection networks. Conditional faulty set is a special faulty set that does not contain all of neighbors of any vertex in a network. The conditional diagnosability is a metric that can give the maximum cardinality of the conditional faulty sets that the system is guaranteed to identify. This paper shows that the conditional diagnosability of the bubble-sort star graph B S n under the MM model is 6 n − 15 for n ≥ 6 and under the PMC model is 8 n − 21 for n ≥ 5 . [ABSTRACT FROM AUTHOR]

An orthogonal ray graph is an intersection graph of horizontal rays (closed half-lines) and vertical rays in the plane, which is introduced in connection with the defect-tolerant design of nano-circuits. An orthogonal ray graph is a 3-directional orthogonal ray graph if every vertical ray has the same direction. A 3-directional orthogonal ray graph is a 2-directional orthogonal ray graph if every horizontal ray has the same direction. The characterizations and the complexity of the recognition problem have been open for orthogonal ray graphs and 3-directional orthogonal ray graphs, while various characterizations with a quadratic-time recognition algorithm have been known for 2-directional orthogonal ray graphs. In this paper, we show several characterizations with a linear-time recognition algorithm for orthogonal ray trees by using the 2-directional orthogonal ray trees. We also show that a tree is a 3-directional orthogonal ray graph if and only if it is a 2-directional orthogonal ray graph. Moreover, we show some necessary conditions for orthogonal ray graphs and 3-directional orthogonal ray graphs. [ABSTRACT FROM AUTHOR]

A subset F of vertices of a graph G is called a vertex cover P t ( V C P t ) set if every path of order t in G contains at least one vertex from F . The vertex cover P t ( V C P t ) problem is to find a minimum V C P t set in a graph. The V C P t problem is NP-complete for any integer t ≥ 2 . In this paper, we restrict our attention to the V C P 4 problem and present an FPT algorithm with runtime O ∗ ( 3 k ) for the V C P 4 problem. The algorithm constructs a V C P 4 set of size at most k in a given graph G , or reports that no such V C P 4 set exists in G . [ABSTRACT FROM AUTHOR]

We consider the problem of finding an integral (and fractional) packing of branchings in a capacitated digraph with root-set demands. Schrijver described an algorithm that returns a packing with at most m + n 3 + r branchings that makes at most m ( m + n 3 + r ) calls to an oracle that basically computes a minimum cut, where n is the number of vertices, m is the number of arcs and r is the number of root-sets of the input digraph. Leston-Rey and Wakabayashi described an algorithm that returns a packing with at most m + r − 1 branchings but makes a large number of oracle calls. In this work we provide an algorithm, inspired on ideas of Schrijver and in a paper of Gabow and Manu, that returns a packing with at most m + r − 1 branchings and makes at most ( m + r + 2 ) n oracle calls. Moreover, for the arborescence packing problem our algorithm provides a packing with at most m − n + 2 arborescences–thus improving the bound of m of Leston-Rey and Wakabayashi–and makes at most ( m − n + 5 ) n oracle calls. [ABSTRACT FROM AUTHOR]

A dominating induced matching , also called an efficient edge domination , of a graph G = ( V , E ) with n = | V | vertices and m = | E | edges is a subset F ⊆ E of edges in the graph such that no two edges in F share a common endpoint and each edge in E ∖ F is incident with exactly one edge in F . It is NP-hard to decide whether a graph admits a dominating induced matching or not. In this paper, we design a 1.146 7 n n O ( 1 ) -time exact algorithm for this problem, improving all previous results. This problem can be redefined as a partition problem that is to partition the vertex set of a graph into two parts I and F , where I induces an independent set (a 0-regular graph) and F induces a perfect matching (a 1-regular graph). After giving several structural properties of the problem, we show that the problem always contains some “good vertices,” branching on which by including them to either I or F we can effectively reduce the graph. This leads to a fast exact algorithm to this problem. [ABSTRACT FROM AUTHOR]

In this paper, we introduce a new concept of saturated vertices for the alliances. For a given graph G = ( V , E ) and S ⊂ V , a vertex v ∈ V is said to be S -saturated , if the number of its defenders is equal to the number of its attackers for S . We define new parameters | λ ( S ) | and | λ ̄ ( S ) | as the number of S -saturated vertices and not S -saturated vertices of S , respectively. We study mathematical properties of (global) saturated boundary defensive, offensive and powerful k -alliances and theoretical results are obtained by giving in particular some tight bounds and exact values on the cardinality of such alliances. As a main result, we give tight bounds for the cardinality of every minimal global boundary powerful ( − 1 ) -alliance (MGBPA) in terms only of the order and the size of graph. Furthermore, we establish two algorithms which generate graphs containing (connected) MGBPA from a given complete graph K 2 n . [ABSTRACT FROM AUTHOR]

We consider (closed neighbourhood) packings and their generalization in graphs. A vertex set X in a graph G is a k - limited packing if for every vertex v ∈ V ( G ) , | N [ v ] ∩ X | ≤ k , where N [ v ] is the closed neighbourhood of v . The k - limited packing number L k ( G ) of a graph G is the largest size of a k -limited packing in G . Limited packing problems can be considered as secure facility location problems in networks. In this paper, we develop a new application of the probabilistic method to limited packings in graphs, resulting in lower bounds for the k -limited packing number and a randomized algorithm to find k -limited packings satisfying the bounds. In particular, we prove that for any graph G of order n with maximum vertex degree Δ , L k ( G ) ≥ k n ( k + 1 ) ( Δ k ) ( Δ + 1 ) k . Also, some other upper and lower bounds for L k ( G ) are given. [ABSTRACT FROM AUTHOR]

A cograph is a graph which does not contain any induced path on four vertices. In this paper, we characterize those cographs that are intersection graphs of paths on a grid in the following two cases: (i) the paths on the grid all have at most one bend and the intersections concern edges ( → B 1 -EPG); (ii) the paths on the grid are not bended and the intersections concern vertices ( → B 0 -VPG). In both cases, we give a characterization by a family of forbidden induced subgraphs. We further present linear-time algorithms to recognize B 1 -EPG cographs and B 0 -VPG cographs using their cotree. [ABSTRACT FROM AUTHOR]

In this paper, we study the problem of designing in-place algorithms for finding the maximum clique in the intersection graphs of axis-parallel rectangles and disks in R 2 . First, we propose an O ( n 2 log n ) time in-place algorithm for finding the maximum clique of the intersection graph of a set of n axis-parallel rectangles of arbitrary sizes. For the intersection graph of fixed height rectangles, the time complexity can be slightly improved to O ( n log n + n K ) , where K is the size of the maximum clique. For disk graphs, we consider two variations of the maximum clique problem, namely geometric clique and graphical clique. The time complexity of our algorithm for finding the largest geometric clique is O ( m log n + n 2 ) where m is the number of edges in the disk graph, and it works for disks of arbitrary radii. For graphical clique, our proposed algorithm works for unit disks (i.e., of same radii) and the worst case time complexity is O ( n 2 + m ( n + K 3 ) ) ; m is the number of edges in the unit disk intersection graph and K is the size of the largest clique in that graph. It uses O ( n 3 ) time in-place computation of maximum matching in a bipartite graph, where the vertices are given in an array, and the existence of an edge between a pair of vertices can be checked by an oracle on demand (from problem specification) in O ( 1 ) time. This problem is of independent interest. All these algorithms need O ( 1 ) work space in addition to the input array. [ABSTRACT FROM AUTHOR]

A subset S of vertices of a graph G is called a k -path vertex cover if every path of order k in G contains at least one vertex from S . The cardinality of a minimum k -path vertex cover is called the k -path vertex cover number of a graph G , denoted by ψ k ( G ) . It is known that the minimum k -path vertex cover problem ( k -PVCP) is NP-hard for all k ≥ 2 . In this paper we consider the weighted version of a k -PVCP ( k -WPVCP), in which vertices are given weights, and the problem is to find a minimum weight set in G such that the graph obtained by deleting this set from G has no P k . This problem was briefly introduced by Tu and Zhou (2011) but has not been studied to much extent. We give solutions and efficient algorithms for the k -WPVCP for some special classes of graphs. In particular, for complete graphs and cycles, and most importantly an algorithm that computes the k -path vertex cover number of a tree with time complexity O ( k ⋅ | V ( G ) | ) is presented. [ABSTRACT FROM AUTHOR]

Abstract: A graph is said to be a set graph if it admits an acyclic orientation that is also extensional, in the sense that the out-neighborhoods of its vertices are pairwise distinct. Equivalently, set graphs are the underlying graphs of digraph representations of hereditarily finite sets, where a set is hereditarily finite if it is finite and has only hereditarily finite sets as members. It is known that every connected -free (or claw-free) graph is a set graph, and that an extensional acyclic orientation of such a graph can be found in polynomial time. In this paper, we generalize this result in three different directions. First, we identify the largest hereditary class of graphs such that for every connected induced subgraph of , it holds that is a set graph if and only if it is claw-free. Second, we consider graphs in which no two distinct induced claws have equal or adjacent centers, and prove that in this class of graphs set graphs can be equivalently characterized in terms of a property related to successive vertex removal. Finally, we show that for every , connected -free graphs admit an acyclic orientation that is -extensional, in the sense that at most distinct vertices can have the same out-neighborhood. This also leads to a simple linear time algorithm for finding an extensional acyclic orientation of a given connected claw-free graph, thus improving over the previous algorithm. [Copyright &y& Elsevier]

Abstract: A subset of the vertex set of a graph is a secure dominating set of if is a dominating set of and if, for each vertex not in , there is a neighbouring vertex of in such that the swap set is again a dominating set of . The secure domination number of , denoted by , is the cardinality of a smallest secure dominating set of . A linear algorithm is proposed in this paper for finding a minimum secure dominating set and hence the value for a tree . The algorithm is based on a strategy of repeatedly pruning away pendent spiders of after having dominated them securely. [Copyright &y& Elsevier]

Abstract: A hypergraph is a set family defined on vertex set . The dual of is the set of minimal subsets of such that for any . The computation of the dual is equivalent to several problems, such as minimal hitting set enumeration of a subset family, generation problem for maximal frequent and minimal infrequent sets, and so on. Although many algorithms have been proposed for the problem, to the best of our knowledge, none of them can work on large-scale input with a large number of minimal hitting sets. In this paper, we propose efficient algorithms for checking the minimality and pruning methods. These algorithms enable us to construct time effective and polynomial space dualization algorithms. The computational experiments show that our algorithms are quite fast even for large-scale input for which existing algorithms do not terminate in a practical time. [Copyright &y& Elsevier]

Abstract: A graph is an opposition graph, respectively, a coalition graph, if it admits an acyclic orientation which puts the two end-edges of every chordless 4-vertex path in opposition, respectively, in the same direction. Opposition and coalition graphs have been introduced and investigated in connection to perfect graphs. Recognizing and characterizing opposition and coalition graphs still remain long-standing open problems. The present paper gives characterizations for co-bipartite opposition graphs and co-bipartite coalition graphs, and for bipartite opposition graphs. Implicit in our argument is a linear time recognition algorithm for these graphs. As an interesting by-product, we find new submatrix characterizations for the well-studied bipartite permutation graphs. [Copyright &y& Elsevier]

Abstract: A -cocoloring of a graph is a partition of the vertex set of into at most independent sets and at most cliques. It is known that determining the cochromatic number and the split chromatic number, which are respectively the minimum and the minimum such that is -cocolorable, is NP-hard problem. A -graph is a graph such that every subset of at most vertices induces at most distinct ’s. In 2011, Bravo et al. obtained a polynomial time algorithm to decide if a -graph is -cocolorable (Bravo et al., 2011). In this paper, we extend this result by obtaining polynomial time algorithms to decide the -cocolorability and to determine the cochromatic number and the split chromatic number for -graphs for every fixed and for graphs with bounded treewidth. We also obtain a polynomial time algorithm to obtain the maximum -cocolorable subgraph of a -graph for every fixed . All these algorithms are fixed parameter tractable. [Copyright &y& Elsevier]

Abstract: J. Hopcroft and D. Sheldon originally introduced network reputation games to investigate the self-interested behavior of web authors who want to maximize their PageRank on a directed web graph by choosing their outlinks in a game theoretic manner. They give best response strategies for each player and characterize properties of web graphs which are Nash equilibria. In this paper we consider three different models for PageRank games on undirected graphs such as certain social networks. In undirected graphs players may delete links at will, but typically cannot add links without the other player’s permission. In the deletion-model players are free to delete any of their bidirectional links but may not add links. We study the problem of determining whether the given graph represents a Nash equilibrium or not in this model. We give an time algorithm for a tree, and a parametric time algorithm for general graphs, where is the maximum vertex degree in any biconnected component of the graph. In the request-delete-model players are free to delete any bidirectional links and add any directed links, since these additions can be done unilaterally and can be viewed as requests for bidirected links. For this model we give an time algorithm for verifying Nash equilibria in trees. Finally, in the add–delete-model we allow a node to make arbitrary deletions and the addition of a single bidirectional link if it would increase the page rank of the other player also. In this model we give a parametric algorithm for verifying Nash equilibria in general graphs and characterize so called -insensitive Nash Equilibria. We also give a result showing a large class of graphs where there is an edge addition that causes the PageRank of both of its endpoints to increase, suggesting convergence towards complete subgraphs. [Copyright &y& Elsevier]

Abstract: The longest path problem asks for a path with the largest number of vertices in a given graph. In contrast to the Hamiltonian path problem, until recently polynomial algorithms for the longest path problem were known only for small graph classes, such as trees. Recently, a polynomial algorithm for this problem on interval graphs has been presented in Ioannidou et al. (2011) [19] with running time on a graph with vertices, thus answering the open question posed in Uehara and Uno (2004) [32]. Even though interval and circular-arc graphs look superficially similar, they differ substantially, as circular-arc graphs are not perfect; for instance, several problems– e.g. coloring –are NP-hard on circular-arc graphs, although they can be efficiently solved on interval graphs. In this paper, we prove that for every path of a circular-arc graph , we can appropriately “cut” the circle, such that the obtained (not induced) interval subgraph of admits a path on the same vertices as . This non-trivial result is of independent interest, as it suggests a generic reduction of a number of path problems on circular-arc graphs to the case of interval graphs with a multiplicative linear time overhead of . As an application of this reduction, we present the first polynomial algorithm for the longest path problem on circular-arc graphs. In addition, by exploiting deeper the structure of circular-arc graphs, we manage to get rid of the linear time overhead of the reduction, and thus this algorithm turns out to have the same running time as the one on interval graphs. Our algorithm, which significantly simplifies the approach of Ioannidou et al. (2011) [19], computes in the same time an -approximation of the (exponentially large in worst case) number of different vertex sets that provide a longest path; in the case where is an interval graph, we compute the exact number. Moreover, in contrast to Ioannidou et al. (2011) [19], this algorithm can be directly extended with the same running time to the case where every vertex has an arbitrary positive weight. [Copyright &y& Elsevier]

Abstract: We consider a frequency allocation problem, in which we are given a cellular telephone network whose geographical coverage area is divided into cells in which phone calls are serviced by frequencies assigned to them, so that none of the pairs of calls emanating from the same or neighboring cells is assigned the same frequency. The problem is to use the frequencies efficiently, i.e., to minimize the span of frequencies used. The frequency allocation problem can be regarded as a multicoloring problem on a weighted hexagonal graph. In this paper, we present a 1-local 4/3-competitive distributed algorithm for multicoloring a hexagonal graph without certain forbidden configuration (introduced in Šparl and Žerovnik (2010) [7]). [Copyright &y& Elsevier]