Search

We study the deterministic silent self-stabilizing construction of two disjoint minimal dominating sets (MDSs) in anonymous networks. We focus on algorithms where nodes share only their status (i.e. the name of their MDS to which they belong, if they belong to a MDS). We prove that such an algorithm cannot be designed in distance-1 model under a central daemon; therefore, we study this problem in the distance-2 model under a central daemon. We present an algorithm building two disjoint minimal dominating sets such that one of them is also a maximal independent set (MIS). Any execution of this algorithm converges in 5n moves. Our approach to compute this value is novel: the number of moves is not computed per node. We propose a second algorithm faster than the first one at the expense of the independence property of one of the constructed sets. A node executes at most 2 moves. If the network is not anonymous, the presented algorithms can be translated into a silent self-stabilizing algorithms converging in O($n$•$m$) moves in the distance-1 model under the distributed daemon where m is the number of edges and n the number of nodes. This improves the complexity of O($n$.$m$) moves of proposed algorithms with the same assumptions.

Lecture Notes in Computer Science book series (LNCS, volume 11485); International audience; We study extension variants of the classical problems Vertex Cover and Independent Set. Given a graph G=(V,E) and a vertex set U⊆V, it is asked if there exists a minimal vertex cover (resp. maximal independent set) S with U⊆S (resp. U⊇S). Possibly contradicting intuition, these problems tend to be NP-complete, even in graph classes where the classical problem can be solved efficiently. Yet, we exhibit some graph classes where the extension variant remains polynomial-time solvable. We also study the parameterized complexity of theses problems, with parameter |U|, as well as the optimality of simple exact algorithms under ETH. All these complexity considerations are also carried out in very restricted scenarios, be it degree or topological restrictions (bipartite, planar or chordal graphs). This also motivates presenting some explicit branching algorithms for degree-bounded instances. e further discuss the price of extension, measuring the distance of U to the closest set that can be extended, which results in natural optimization problems related to extension problems for which we discuss polynomial-time approximability.

Optimization problems consist of either maximizing or minimizing an objective function. Instead of looking for a maximum solution (resp. minimum solution), one can find a minimum maximal solution (resp. maximum minimal solution). Such "flipping" of the objective function was done for many classical optimization problems. For example, Minimum Vertex Cover becomes Maximum Minimal Vertex Cover, Maximum Independent Set becomes Minimum Maximal Independent Set and so on. In this paper, we propose to study the weighted version of Maximum Minimal Edge Cover called Upper Edge Cover, a problem having application in the genomic sequence alignment. It is well-known that Minimum Edge Cover is polynomial-time solvable and the "flipped" version is NP-hard, but constant approximable. We show that the weighted Upper Edge Cover is much more difficult than Upper Edge Cover because it is not $O(\frac{1}{n^{1/2-\varepsilon}})$ approximable, nor $O(\frac{1}{\Delta^{1-\varepsilon}})$ in edge-weighted graphs of size $n$ and maximum degree $\Delta$ respectively. Indeed, we give some hardness of approximation results for some special restricted graph classes such as bipartite graphs, split graphs and $k$-trees. We counter-balance these negative results by giving some positive approximation results in specific graph classes., Comment: 19 pages, 4 figures

Very recently, Thomass\'e, Trotignon and Vuskovic [WG 2014] have given an FPT algorithm for Weighted Independent Set in bull-free graphs parameterized by the weight of the solution, running in time $2^{O(k^5)} \cdot n^9$. In this article we improve this running time to $2^{O(k^2)} \cdot n^7$. As a byproduct, we also improve the previous Turing-kernel for this problem from $O(k^5)$ to $O(k^2)$. Furthermore, for the subclass of bull-free graphs without holes of length at most $2p-1$ for $p \geq 3$, we speed up the running time to $2^{O(k \cdot k^{\frac{1}{p-1}})} \cdot n^7$. As $p$ grows, this running time is asymptotically tight in terms of $k$, since we prove that for each integer $p \geq 3$, Weighted Independent Set cannot be solved in time $2^{o(k)} \cdot n^{O(1)}$ in the class of $\{bull,C_4,\ldots,C_{2p-1}\}$-free graphs unless the ETH fails., Comment: 15 pages

Given a connected undirected graph $$G=(V, E)$$ , a subset W of nodes of G is a weakly connected independent set if W is an independent set and the partial graph $$(V, \delta (W))$$ is connected, where $$\delta (W)$$ is the set of edges with only one endnode in W. This article proposes several distinct results about the weakly connected independent sets of a graph obtained by corona or join operations: the complete description of the wcis polytope for a corona or a join of two graphs of which we know the wcis polytopes or the maximal independent set polytopes, and the consequences of these graph operations on the minimum weight weakly connected independent set problem (MWWCISP). A class of graphs is also inductively defined from the connected bipartite graphs, the cycles and the strongly chordal graphs, for which the MWWCISP is polynomially solvable. This work is a direct continuation of the article (Bendali et al. in Discrete Optim 22:87–110, 2016) where a similar theorem about complete description of the wcis polytope has been given for 1-sum operation.

We show that any $3$-connected cubic plane graph on $n$ vertices, with all faces of size at most $6$, can be made bipartite by deleting no more than $\sqrt{(p+3t)n/5}$ edges, where $p$ and $t$ are the numbers of pentagonal and triangular faces, respectively. In particular, any such graph can be made bipartite by deleting at most $\sqrt{12n/5}$ edges. This bound is tight, and we characterise the extremal graphs. We deduce tight lower bounds on the size of a maximum cut and a maximum independent set for this class of graphs. This extends and sharpens the results of Faria, Klein and Stehlik [SIAM J. Discrete Math. 26 (2012) 1458-1469]., 16 pages; to appear in European J. Combin.; an extended abstract of this paper appeared in the proceedings of EuroComb 2017

Let I be an independent set of a graph G. Imagine that a token is located on any vertex of I. We can now move the tokens of I along the edges of the graph as long as the set of tokens still defines an independent set of G. Given two independent sets I and J, the Token Sliding problem consists in deciding whether there exists a sequence of independent sets which transforms I into J so that every pair of consecutive independent sets of the sequence can be obtained via a token move. This problem is known to be PSPACE-complete even on planar graphs. In 2014, Demaine et al. asked whether the Token Sliding reconfiguration problem is polynomial time solvable on interval graphs and more generally in chordal graphs. Yamada and Uehara showed in 2016 that a polynomial time transformation can be found in proper interval graphs. In this paper, we answer the first question of Demaine et al. and generalize the result of Yamada and Uehara by showing that we can decide in polynomial time whether two independent sets of an interval graph are in the same connected component. Moveover, we answer similar questions by showing that: (i) determining if there exists a token sliding transformation between every pair of k-independent sets in an interval graph can be decided in polynomial time; (ii) deciding this problem becomes co-NP-hard and even co-W[2]-hard (parameterized by the size of the independent set) on split graphs, a sub-class of chordal graphs., Comment: 21 pages

The triangle partition problem is a generalization of the well-known graph matching problem consisting of finding the maximum number of independent edges in a given graph, i.e., edges with no common node. Triangle partition instead aims to find the maximum number of disjoint triangles. The triangle partition problem is known to be NP-complete. Thus, in this paper, the focus is on the local maximization variant, called maximal triangle partition (MTP). Thus, paper presents a new self-stabilizing algorithm for MTP that converges in O(m) moves under the unfair distributed daemon.

International audience; This paper presents our ongoing work on the Vertex Separator Problem (VSP), and its application to knowledge discovery in graphs representing real data. The classic VSP is modeled as an integer linear program. We propose several variants to adapt this model to graphs with various properties. To evaluate the relevance of our approach on real data, we created two graphs of different size from the IMDb database. The model was applied to the separation of these graphs. The results demonstrate how the model is able to semantically separate graphs into clusters.

LNCS, volume 10236; International audience; An independent 2-clique of a graph is a subset of vertices that is an independent set and such that any two vertices inside have a common neighbor outside. In this paper, we study the complexity of finding an independent 2-clique of maximum size in several graph classes and we compare its complexity with the complexity of maximum independent set. We prove that this problem is NP-hard on apex graphs, APX-hard on line graphs, not n1/2−ϵ-approximable on bipartite graphs and not n1−ϵ-approximable on split graphs, while it is polynomial-time solvable on graphs of bounded degree and their complements, graphs of bounded treewidth, planar graphs, (C3,C6)-free graphs, threshold graphs, interval graphs and cographs.

Given a graph $G$, viewed as a loop-less symmetric digraph, we study the maximum number of fixed points in a conjunctive boolean network with $G$ as interaction graph. We prove that if $G$ has no induced $C_4$, then this quantity equals both the number of maximal independent sets in $G$ and the maximum number of maximal independent sets among all the graphs obtained from $G$ by contracting some edges. We also prove that, in the general case, it is coNP-hard to decide if one of these equalities holds, even if $G$ has a unique induced $C_4$., Comment: 28 pages, 13 figures, accepted in Journal of Computer and System Sciences, 2017

A set $D$ of vertices of a graph $G$ is locating if every two distinct vertices outside $D$ have distinct neighbors in $D$; that is, for distinct vertices $u$ and $v$ outside $D$, $N(u) \cap D \neq N(v) \cap D$, where $N(u)$ denotes the open neighborhood of $u$. If $D$ is also a dominating set (total dominating set), it is called a locating-dominating set (respectively, locating-total dominating set) of $G$. A graph $G$ is twin-free if every two distinct vertices of $G$ have distinct open and closed neighborhoods. It is conjectured [D. Garijo, A. Gonzalez and A. Marquez, The difference between the metric dimension and the determining number of a graph. Applied Mathematics and Computation 249 (2014), 487--501] and [F. Foucaud and M. A. Henning. Locating-total dominating sets in twin-free graphs: a conjecture. The Electronic Journal of Combinatorics 23 (2016), P3.9] respectively, that any twin-free graph $G$ without isolated vertices has a locating-dominating set of size at most one-half its order and a locating-total dominating set of size at most two-thirds its order. In this paper, we prove these two conjectures for the class of line graphs. Both bounds are tight for this class, in the sense that there are infinitely many connected line graphs for which equality holds in the bounds., Comment: 23 pages, 2 figures

The maximum stable set problem is NP-hard, even when restricted to triangle-free graphs. In particular, one cannot expect a polynomial time algorithm deciding if a bull-free graph has a stable set of size k, when k is part of the instance. Our main result in this paper is to show the existence of an FPT algorithm when we parameterize the problem by the solution size k. A polynomial kernel is unlikely to exist for this problem. We show however that our problem has a polynomial size Turing-kernel. More precisely, the hard cases are instances of size O(k 5 ). As a byproduct, if we forbid odd holes in addition to the bull, we show the existence of a polynomial time algorithm for the stable set problem. We also prove that the chromatic number of a bull-free graph is bounded by a function of its clique number and the maximum chromatic number of its triangle-free induced subgraphs. All our results rely on a decomposition theorem of bull-free graphs due to Chudnovsky which is modified here, allowing us to provide extreme decompositions, adapted to our computational purpose.

Trapezoid graphs are intersection graphs of trapezoids between two horizontal lines. Many NP-hard problems can be solved in polynomial time if they are restricted on trapezoid graphs. A matching in a graph is a set of pairwise disjoint edges, and a maximum matching is a matching of maximum size. In this paper, we first propose an $O(n(\log n)^3)$ algorithm for finding a maximum matching in trapezoid graphs, then improve the complexity to $O(n(\log n)^2)$. Finally, we generalize this algorithm to a larger graph class, namely $k$-trapezoid graphs. To the best of our knowledge, these are the first efficient maximum matching algorithms for trapezoid graphs.

International audience; We present and analyse Las Vegas distributed algorithms which computea MIS or a colouring for anonymous rings with an arbitrary orientation of the edges;their bit complexityand time complexity are $O(\sqrt{\log n})$ with high probability. These algorithms areoptimal modulo a multiplicative constant.

Let G=(V,E) be a connected graph. An independent set WV is said to be weakly connected if the spanning subgraph GW=(V,(W)) is connected where (W) is the set of edges with exactly one end in W. We present an integer programming formulation for the minimum weakly connected independent set problem and discuss its associated polytope. Some classical graph operations are also used for defining new polyhedra from pieces. We give valid inequalities and describe heuristic separation procedures. Finally, we develop a Branch-and-Cut algorithm and test it on two classes of graphs.

International audience; We study the problems Locating-Dominating Set and Metric Dimension, which consist of determining a minimum-size set of vertices that distinguishes the vertices of a graph using either neighbourhoods or distances. We consider these problems when restricted to interval graphs and permutation graphs. We prove that both decision problems are NP-complete, even for graphs that are at the same time interval graphs and permutation graphs and have diameter 2. While Locating-Dominating Set parameterized by solution size is trivially fixed-parameter-tractable, it is known that Metric Dimension is W [2]-hard. We show that for interval graphs, this parameterization of Metric Dimension is fixed-parameter-tractable.

A geometric graph is angle-monotone if every pair of vertices has a path between them that---after some rotation---is $x$- and $y$-monotone. Angle-monotone graphs are $\sqrt 2$-spanners and they are increasing-chord graphs. Dehkordi, Frati, and Gudmundsson introduced angle-monotone graphs in 2014 and proved that Gabriel triangulations are angle-monotone graphs. We give a polynomial time algorithm to recognize angle-monotone geometric graphs. We prove that every point set has a plane geometric graph that is generalized angle-monotone---specifically, we prove that the half-$\theta_6$-graph is generalized angle-monotone. We give a local routing algorithm for Gabriel triangulations that finds a path from any vertex $s$ to any vertex $t$ whose length is within $1 + \sqrt 2$ times the Euclidean distance from $s$ to $t$. Finally, we prove some lower bounds and limits on local routing algorithms on Gabriel triangulations., Comment: Appears in the Proceedings of the 24th International Symposium on Graph Drawing and Network Visualization (GD 2016)

In the context of distributed network computing, an important concern is the ability to design local algorithms, that is, distributed algorithms in which every node (Each node is a computing entity, which has the ability to exchange messages with its neighbors in the network along its communication links.) of the network can deliver its result after having consulted only nodes in its vicinity. The word “vicinity” has a rather vague interpretation in general. Nevertheless, the objective is commonly to design algorithms in which every node outputs after having exchanged information with nodes at constant distance from it (i.e., at distance independent of the number of nodes n in the networks) or at distance at most polylogarithmic in n, but certainly significantly smaller than n or than the diameter of the network. The tasks to be solved by distributed algorithms acting in networks can be formalized as follows. The network itself is modeled by an undirected connected graph G with node set V.G/ and edge set E.G/, without loops and double edges. In the sequel, by graph we are only referring to this specific type of graphs. Nodes are labeled by a function ` W V ! f0; 1g that assigns to every node v its label `.v/. A pair .G; `/, where G is a graph and ` is a labeling of G, is called configuration, and a collection L of configurations is called a distributed language. A typical example of a distributed language is: Lproperly colored D f.G; `/ W `.v/ ¤ `.v0/ for all fv; v0g 2 E.G/g. Unless specified otherwise, we are always assuming that the considered languages are decidable in the sense of classical (sequential) computability theory. To every distributed language L can be associated a construction task which consists in computing the appropriate labels for a given network (Here, we are restricting ourselves to input-free construction tasks, but the content of this chapter can be generalized to tasks with inputs, in which case the labels are input-output pairs, and, given the inputs, the nodes must produce the appropriate outputs to fit in the considered language.)

International audience; The locating-dominating set problem is a special domination problem, challenging both from a theoretical and a computational point of view. Hence, a typical line of attack is to determine minimum locating-dominating sets of special graphs or to provide bounds for their size. Here, we study the locating-dominating set problem from a polyhedral point of view and demonstrate how the associated polyhedra can be entirely described for some basic families of graphs. The latter enables us to determine minimum weight locating-dominating sets in the studied graph classes for arbitrary integral node weights. We discuss further lines of research in order to apply similar techniques for other graph classes, to obtain the exact values or strong lower bounds for the size of minimum locating-dominating sets, stemming from linear relaxations of the polyhedra, enhanced by suitable cutting planes.

International audience; We consider a framework for nonlinear operators on functions evaluated on graphs via stacks of level sets. We investigate a family of transformations on functions evaluated on graph which includes adaptive flat and non-flat erosions and dilations in the sense of mathematical morphology. Additionally, the connection to mean motion curvature on graphs is noted. Proposed operators are illustrated in the cases of functions on graphs, textured meshes and graphs of images.

International audience; An effective way to analyze and apprehend the structural properties of networks is to find their most critical nodes. This makes them easier to control, whether the purpose is to keep or to delete them. Given a graph, Critical Node Detection problem (CNDP) consists in finding a set of nodes, deletion of which satisfies some given connectivity metrics in the induced graph. In this paper, we propose and study a new variant of this problem, called Component-Cardinality-Constrained Critical Node Problem (3C-CNP ). In this variant, we seek to find a minimal set of nodes, removal of which constrains the size of each connected component in the induced graph to a given bound. We prove the NP-hardness of this problem on a graph of maximum degree Δ=4Δ=4, through which we deduce the NP-hardness of CNP (Arulselvan et al., 2009) on the same class of graphs. Also, we study 3C-CNP on trees for different cases depending on node weights and connection costs. For the case where node weights and connection costs have non-negative values, we prove its NP-completeness. While, for the case where node weights (or connection costs) have unit values, we present a polynomial algorithm. Also, we study 3C-CNP on chordal graphs, where we show that it is NP-complete on split graphs, and polynomially solvable on proper interval graphs.

Modeling topologies in Wireless Sensor Networks principally uses domination theory in graphs. Indeed, many dominating structures have been proposed as virtual backbones for wireless networks. In this paper, we study a dominating set that we call Weakly Connected Independent Set (wcis ). Given an undirected connected graph G = (V,E ), we say that an independent set S in G is weakly connected if the spanning subgraph (V, [ S,V \ S ]) is connected, where [ S,V \ S ] is the set of edges having exactly one end in S . The minimum weakly independent connected set problem consists in determining a wcis of minimum size in G . First, we discuss some complexity and approximation results for that problem. Then we propose an implicit enumeration algorithm which computes a minimum wcis in a graph with n vertices with a running time O ∗ (1.4655n ) and polynomial space. Processing results are given that show that our enumeration program solves the mwcis problem for graphs whose number of vertices is less than 120.

International audience; An identifying code is a subset of vertices of a graph with the property that each vertex is uniquely determined (identi ed) by its nonempty neighbourhood within the identifying code. When only vertices out of the code are asked to be identi ed, we get the related concept of a locating-dominating set. These notions are closely related to a number of similar and well-studied concepts such as the one of a test cover. In this paper, we study the decision problems Identifying Code and Locating-Dominating Set (which consist in deciding whether a given graph admits an identifying code or a locating-dominating set, respectively, with a given size) and their minimization variants Minimum Identifying Code and Minimum Locating-Dominating Set. These problems are known to be NP-hard, even when the input graph belongs to a number of speci c graph classes such as planar bipartite graphs. Moreover, it is known that they are approximable within a logarithmic factor, but hard to approximate within any sub-logarithmic factor. We extend the latter result to the case where the input graph is bipartite, split or co-bipartite: both problems remain hard in these cases. Among other results, we also show that for bipartite graphs of bounded maximum degree (at least 3), the two problems are hard to approximate within some constant factor, a question which was open. We summarize all known results in the area, and we compare them to the ones for the related problem Dominating Set. In particular, our work exhibits important graph classes for which Dominating Set is efficiently solvable, but Identifying Code and Locating-Dominating Set are hard (whereas in all previous works, their complexity was the same). We also introduce graph classes for which the converse holds, and for which the complexities of Identifying Code and Locating-Dominating Set diff er.

International audience; In this paper we study distributed algorithms on massive graphs where links represent a particular relationship between nodes (for instance, nodes may represent phone numbers and links may indicate telephone calls). Since such graphs are massive they need to be processed in a distributed way. When computing graph-theoretic properties, nodes become natural units for distributed computation. Links do not necessarily represent communication channels between the computing units and therefore do not restrict the communication flow. Our goal is to model and analyze the computational power of such distributed systems where one computing unit is assigned to each node. Communication takes place on a whiteboard where each node is allowed to write at most one message. Every node can read the contents of the whiteboard and, when activated, can write one small message based on its local knowledge. When the protocol terminates its output is computed from the final contents of the whiteboard. We describe four synchronization models for accessing the whiteboard. We show that message size and synchronization power constitute two orthogonal hierarchies for these systems.We exhibit problems that separate these models, i.e., that can be solved in one model but not in a weaker one, even with increased message size. These problems are related to maximal independent set and connectivity. We also exhibit problems that require a given message size independently of the synchronization model.

International audience; We are interested in the number of fixed points in AND-OR-NOT networks, i.e. Boolean networks in which the update function of each component is either a conjunction or a disjunction of positive or negative literals. As main result, we prove that the maximum number of fixed points in a loop-less connected AND-OR-NOT network with n components is at most the maximum number of maximal independent sets in a loop-less connected graph with n vertices, a quantity already known.

We investigate the problem maxDMM of computing a largest set of pairwise disjoint maximum matchings in undirected graphs. In this paper, n, m denote, respectively, the number of vertices and the number of edges. We solve maxDMM for bipartite graphs, by providing an \(O(n^{1.5}\sqrt{m/\log n} + mn\log n)\)-time algorithm. We design better algorithms for complete bipartite graphs, and bisplit graphs. (Bisplit graphs are bipartite graphs with the nested neighborhood property.) Specifically, we prove that the problem maxDMM is solvable in complete bipartite graphs in time O(m). A sequence \(S=(s_1,\cdots ,s_t)\) of positive integers is said to be color-feasible for a graph G, if there exists a proper edge-coloring of G with colors \(1,\cdots ,t\), such that precisely \(s_i\) edges have color i, for every \(i=1,\cdots ,t\). Actually, for complete bipartite graphs, we prove that, for any sequence S of integers which is color-feasible for a complete bipartite graph G, an edge-coloring of G corresponding to S can be obtained in time O(m). For bisplit graphs, (1) we solve maxDMM in time \(O(mn\log n)\), and (2) we design an \(O(n^2\log n)\)-time algorithm to count all maximum matchings. This latter time is the same time in which runs the best known algorithm computing the number of maximum matchings in bisplit graphs [17], but our algorithm is much simpler than the one given in [17]. The key idea underlying both results is that bisplit graphs have an O(n)-time enumeration of their minimal vertex covers.

International audience; We present a new approach for the problem of finding overlapping communities in graphs and social networks. Our approach consists of a novel problem definition and three accompanying algorithms. We are particularly interested in graphs that have labels on their vertices, although our methods are also applicable to graphs with no labels. Our goal is to find k communities so that the total edge density over all k communities is maximized. In the case of labeled graphs, we require that each community is succinctly described by a set of labels. This requirement provides a better understanding for the discovered communities. The proposed problem formulation leads to the discovery of vertex-overlapping and dense communities that cover as many graph edges as possible. We capture these properties with a simple objective function, which we solve by adapting efficient approximation algorithms for the generalized maximum-coverage problem and the densest-subgraph problem. Our proposed algorithm is a generic greedy scheme. We experiment with three variants of the scheme, obtained by varying the greedy step of finding a dense subgraph. We validate our algorithms by comparing with other state-of-the-art community-detection methods on a variety of performance measures. Our experiments confirm that our algorithms achieve results of high quality in terms of the reported measures, and are practical in terms of performance.

8th IFIP TC 1/WG 2.2 International Conference on Theoretical Computer Science, Graphs are often used to model risk management in various systems. Particularly, Caskurlu et al. in [6] have considered a system which essentially represents a tripartite graph. The goal in this model is to reduce the risk in the system below a predefined risk threshold level. It can be shown that the main goal in this risk management system can be formulated as a Partial Vertex Coverproblem on bipartite graphs. It is well-known that the vertex cover problem is in P on bipartite graphs; however, the computational complexity of the partial vertex cover problem on bipartite graphs is open. In this paper, we show that the partial vertex cover problem is NP-hard on bipartite graphs. Then, we show that the budgeted maximum coverage problem (a problem related to partial vertex cover problem) admits an 8/9-approximation algorithm in the class of bipartite graphs, which matches the integrality gap of a natural LP relaxation. © 2014 IFIP International Federation for Information Processing.

International audience; We consider the connected variant of the classic mixed search game where, in each search step, cleaned edges form a connected subgraph. We consider graph classes with bounded connected (and monotone) mixed search number and we deal with the question whether the obstruction set, with respect of the contraction partial ordering, for those classes is finite. In general, there is no guarantee that those sets are finite, as graphs are not well quasi ordered under the contraction partial ordering relation. In this paper we provide the obstruction set for k=2, where k is the number of searchers we are allowed to use. This set is finite, it consists of 177 graphs and completely characterises the graphs with connected (and monotone) mixed search number at most 2. Our proof reveals that the “sense of direction” of an optimal search searching is important for connected search which is in contrast to the unconnected original case. We also give a double exponential lower bound on the size of the obstruction set for the classes where this set is finite.

In a bounded max-coloring of a vertex/edge weighted graph, each color class is of cardinality at most $b$ and of weight equal to the weight of the heaviest vertex/edge in this class. The bounded max-vertex/edge-coloring problems ask for such a coloring minimizing the sum of all color classes' weights. In this paper we present complexity results and approximation algorithms for those problems on general graphs, bipartite graphs and trees. We first show that both problems are polynomial for trees, when the number of colors is fixed, and $H_b$ approximable for general graphs, when the bound $b$ is fixed. For the bounded max-vertex-coloring problem, we show a 17/11-approximation algorithm for bipartite graphs, a PTAS for trees as well as for bipartite graphs when $b$ is fixed. For unit weights, we show that the known 4/3 lower bound for bipartite graphs is tight by providing a simple 4/3 approximation algorithm. For the bounded max-edge-coloring problem, we prove approximation factors of $3-2/\sqrt{2b}$, for general graphs, $\min\{e, 3-2/\sqrt{b}\}$, for bipartite graphs, and 2, for trees. Furthermore, we show that this problem is NP-complete even for trees. This is the first complexity result for max-coloring problems on trees., 13 pages, 5 figures

International audience; We study the problem of maintaining a given distribution of random graphs under an arbitrary sequence of vertex insertions and deletions. Since our goal is to model the evolution of dynamic logical networks, we work in a local model where we do not have direct access to the list of all vertices. Instead, we assume access to a global primitive that returns a random vertex, chosen uniformly from the whole vertex set. In this preliminary work, we focus on a simple model of uniform directed random graphs where all vertices have a fixed outdegree. We describe and analyze several algorithms for the maintenance task; the most elaborate of our algorithms are asymptotically optimal.

In this paper, we present a new characterization of complement Threshold Tolerance graphs (co-TT for short) and find a recognition algorithm for the subclass of split co-TT graphs running in O(n^2) time. Currently, the best recognition algorithms for co-TT graphs and for split co-TT graphs run in O(n^4) time (Hammer and Simeone (1981) [4]; Monma et al. (1988) [7]).

International audience; This paper concerns probabilistic distributed graph algorithms to solve classical graph problems such as colouring, maximal matching or maximal independent set. We consider anonymous networks (no unique identifiers are available) where vertices communicate by single bit messages. We present a general framework, based on coverings, for proving lower bounds for the bit complexity and thus the execution time to solve these problems. In this way we obtain new proofs of some well known results and some new ones. The last part gives impossibility results on the existence of Las Vegas distributed algorithms to break symmetries at distance $k$ for $k\geq 3.$

We present a characterization of the linear rank-width of distance-hereditary graphs. Using the characterization, we show that the linear rank-width of every \(n\)-vertex distance-hereditary graph can be computed in time \(\mathcal {O}(n^2\cdot \log (n))\), and a linear layout witnessing the linear rank-width can be computed with the same time complexity. For our characterization, we combine modifications of canonical split decompositions with an idea of [Megiddo, Hakimi, Garey, Johnson, Papadimitriou: The complexity of searching a graph. JACM 1988], used for computing the path-width of trees. We also provide a set of distance-hereditary graphs which contains the set of distance-hereditary vertex-minor obstructions for linear rank-width. The set given in [Jeong, Kwon, Oum: Excluded vertex-minors for graphs of linear rank-width at most k. STACS 2013: 221–232] is a subset of our obstruction set.

For any simple graph G, let D(G) denote the degree set {degG(v) : v ∈ V (G)}. Let S be a finite, nonempty set of positive integers. In this paper, we first determine the families of graphs G which are unicyclic, bipartite satisfying D(G) = S, and further obtain the graphs of minimum orders in such families. More general, for a given pair (S, T) of finite, nonempty sets of positive integers of the same cardinality, it is shown that there exists a bipartite graph B(X, Y ) such that D(X) = S, D(Y ) = T and the minimum orders of different types are obtained for such graphs

Given a directed graph D = (V,A) we define its intersection graph I(D) = (A,E) to be the graph having A as a node-set and two nodes of I(D) are adjacent if their corresponding arcs share a common node that is the tail of at least one of these arcs. We call them facility location graphs since they arise from the classical uncapacitated facility location problem. In this paper we show that facility location graphs are hard to recognize but they are easy to recognize when the underlying graph is triangle-free. We also determine the complexity of the vertex coloring, the stable set and the facility location problem for triangle-free facility location graphs.

International audience; We study the Max k-colored clustering problem, where, given an edge-colored graph with k colors, we seek to color the vertices of the graph so as to find a clustering of the vertices maximizing the number (or the weight) of matched edges, i.e. the edges having the same color as their extremities. We show that the cardinality problem is NP-hard even for edge-colored bipartite graphs with a chromatic degree equal to two and k ≥ 3. Our main result is a constant approximation algorithm for the weighted version of the Max k-colored clustering problem which is based on a rounding of a natural linear programming relaxation. For graphs with chromatic degree equal to two, we improve this ratio by exploiting the relation of our problem with the Max 2-and problem. We also present a reduction to the maximum-weight independent set (IS) problem in bipartite graphs which leads to a polynomial time algorithm for the case of two colors.

International audience; We first devise a branching algorithm that computes a minimum independent dominating set with running time O∗(1.3351n)=O∗(20.417n)O∗(1.3351n)=O∗(20.417n) and polynomial space. This improves upon the best state of the art algorithms for this problem. We then study approximation of the problem by moderately exponential time algorithms and show that it can be approximated within ratio 1+ϵ1+ϵ, for any ϵ>0ϵ>0, in a time smaller than the one of exact computation and exponentially decreasing with ϵϵ. We also propose approximation algorithms with better running times for ratios greater than 3 in general graphs and give improved moderately exponential time approximation results in triangle-free and bipartite graphs. These latter results are based upon a new bound on the number of maximal independent sets of a given size in these graphs, which is a result interesting per se.

International audience; Many real-world complex networks are best modeled as bipartite (or 2-mode) graphs, where nodes are divided into two sets with links connecting one side to the other. However, there is currently a lack of methods to analyze properly such graphs as most existing measures and methods are suited to classical graphs. A usual but limited approach consists in deriving 1-mode graphs (called projections) from the underlying bipartite structure, though it causes important loss of information and data storage issues. We introduce here internal links and pairs as a new notion useful for a bipartite analysis, which gives insights into the information lost by projecting the bipartite graph. We illustrate the relevance of these concepts in several real-world instances, illustrating how it enables to discriminate behaviors among various cases when we compare them to a benchmark of random graphs. Then, we show that we can draw benefit from this concept for both modeling complex networks and storing them in a compact format.

We describe several classes of finite, planar Toeplitz graphs and present results on their chromatic number. We then turn to counting maximal independent sets in these graphs and determine recurrence equations and generating functions for some special cases.

Previous work on counting maximal independent sets for paths and certain 2-dimensional grids is extended in two directions: 3-dimensional grid graphs are included and, for some/any l ∈ N, maximal distance-l independent (or simply: maximal l-independent) sets are counted for some grids. The transfer matrix method has been adapted and successfully applied.

International audience; For graph $G(V,E)$, a minimum path cover (MPC) is a minimum cardinality set of vertex disjoint paths that cover $V$ (i.e., every vertex of $G$ is in exactly one path in the cover). This problem is a natural generalization of the Hamiltonian path problem. Cocomparability graphs (the complements of graphs that have an acyclic transitive orientation of their edge sets) are a well studied subfamily of perfect graphs that includes many popular families of graphs such as interval, permutation, and cographs. Furthermore, for every cocomparability graph $G$ and acyclic transitive orientation of the edges of $\overline{G}$ there is a corresponding poset $P_G$; it is easy to see that an MPC of $G$ is a linear extension of $P_G$ that minimizes the bump number of $P_G$. Although there are directly graph-theoretical MPC algorithms (i.e., algorithms that do not rely on poset formulations) for various subfamilies of cocomparability graphs, notably interval graphs, until now all MPC algorithms for cocomparability graphs themselves have been based on the bump number algorithms for posets. In this paper we present the first directly graph-theoretical MPC algorithm for cocomparability graphs; this algorithm is based on two consecutive graph searches followed by a certifying algorithm. Surprisingly, except for a lexicographic depth first search (LDFS) preprocessing step, this algorithm is identical to the corresponding algorithm for interval graphs. The running time of the algorithm is $O({\rm min}(n^2, n + {\rm mloglogn}))$, with the nonlinearity coming from LDFS.

We give linear and polynomial time algorithms for computing the hull number of distance-hereditary and chordal graphs, respectively. The complexity of computing the hull number in chordal and distance-hereditary graphs has been open since the introduction of the notion in [M. G. Everett and S. B. Seidman, Discrete Math., 57 (1985), pp. 217--223]. Prior to our result polynomial time algorithms were only known for subclasses of considered graph classes, e.g., split graphs, cographs, interval graphs. Our techniques allow us to give at the same time a linear time algorithm for computing the geodetic number in distance-hereditary graphs. Another consequence of the techniques used is an incremental output-polynomial algorithm to list the set of (inclusion-wise) minimal hull sets in any graphs.

Graph Theory, For a positive integer k, a k-tuple dominating set of a graph G is a subset S of V (G) such that |N [v] ∩ S| ≥ k for every vertex v, where N [v] = {v} ∪ {u ∈ V (G) : uv ∈ E(G)}. The upper k-tuple domination number of G, denoted by Γ×k (G), is the maximum cardinality of a minimal k-tuple dominating set of G. In this paper we present an upper bound on Γ×k (G) for r-regular graphs G with r ≥ k, and characterize extremal graphs achieving the upper bound. We also establish an upper bound on Γ×2 (G) for claw-free r-regular graphs. For the algorithmic aspect, we show that the upper k-tuple domination problem is NP-complete for bipartite graphs and for chordal graphs.

Given an undirected graph G = ( V , E ) , the minimum sum coloring problem (MSCP) is to find a legal vertex coloring of G, using colors represented by natural numbers ( 1,2 , ? ) such that the total sum of the colors assigned to the vertices is minimized. In this paper, we present EXSCOL, a heuristic algorithm based on independent set extraction for this NP-hard problem. EXSCOL identifies iteratively collections of disjoint independent sets of equal size and assign to each independent set the smallest available color. For the purpose of computing large independent sets, EXSCOL employs a tabu search based heuristic. Experimental evaluations on a collection of 52 DIMACS and COLOR2 benchmark graphs show that the proposed approach achieves highly competitive results. For more than half of the graphs used in the literature, our approach improves the current best known upper bounds.

International audience; We present in this paper an experimental study of six heuristics for a well-studied NP-complete graph problem: the vertex cover. These algorithms are adapted to process huge graphs. Indeed, executed on a current laptop computer, they offer reasonable CPU running times (between twenty seconds and eight hours) on graphs for which sizes are between 200 *106 and 100 *109 vertices and edges. We have run algorithms on specific graph families (we propose generators) and also on random power law graphs. Some of these heuristics can produce good solutions. We give here a comparison and an analysis of results obtained on several instances, in terms of quality of solutions and complexity, including running times.

Fuzzy circular interval graphs are a generalization of proper circular arc graphs and have been recently introduced by Chudnovsky and Seymour as a fundamental subclass of claw-free graphs. In this paper, we provide a polynomial-time algorithm for recognizing such graphs, and more importantly for building a suitable representation., 12 pages, 2 figures

Graphs and Algorithms, An independent dominating set D of a graph G = (V,E) is a subset of vertices such that every vertex in V \ D has at least one neighbor in D and D is an independent set, i.e. no two vertices of D are adjacent in G. Finding a minimum independent dominating set in a graph is an NP-hard problem. Whereas it is hard to cope with this problem using parameterized and approximation algorithms, there is a simple exact O(1.4423^n)-time algorithm solving the problem by enumerating all maximal independent sets. In this paper we improve the latter result, providing the first non trivial algorithm computing a minimum independent dominating set of a graph in time O(1.3569^n). Furthermore, we give a lower bound of \Omega(1.3247^n) on the worst-case running time of this algorithm, showing that the running time analysis is almost tight.

International audience; In this paper, we deal with the problem of finding quasi-independent sets in graphs. This problem is formally defined in three versions, which are shown to be polynomially equivalent. The one that looks most general, namely, $f$-max quasi-independent set, consists of, given a graph and a non-decreasing function $f$, finding a maximum size subset $Q$ of the vertices of the graph, such that the number of edges in the induced subgraph is less than or equal to $f(\vert Q \vert)$. For this problem, we show an exact solution method that runs within time $O^\ast(2^{\frac{d-27/23}{d+1}n})$ on graphs of average degree bounded by $d$. For the most specifically defined $\gamma$-max quasi-independent set and $k$-max quasi-independent set problems, several results on complexity and approximation are shown, and greedy algorithms are proposed, analyzed and tested.