Search

Abstract: In this paper, we study the geodetic convexity of graphs, focusing on the problem of the complexity of computing a minimum hull set of a graph in several graph classes. For any two vertices of a connected graph , the closed interval of and is the set of vertices that belong to some shortest -path. For any , let . A subset is geodesically convex or convex if . In other words, a subset is convex if, for any and for any shortest -path , . Given a subset , the convex hull of is the smallest convex set that contains . We say that is a hull set of if . The size of a minimum hull set of is the hull number of , denoted by . The Hull Number problem is to decide whether , for a given graph and an integer . Dourado et al. showed that this problem is NP-complete in general graphs. In this paper, we answer an open question of Dourado et al. (2009) [1] by showing that the Hull Number problem is NP-hard even when restricted to the class of bipartite graphs. Then, we design polynomial-time algorithms to solve the Hull Number problem in several graph classes. First, we deal with the class of complements of bipartite graphs. Then, we generalize some results in Araujo et al. (2011) [2] to the class of -graphs and to cacti. Finally, we prove tight upper bounds on the hull numbers. In particular, we show that the hull number of an -node graph without simplicial vertices is at most in general, at most if is regular or has no triangle, and at most if has girth at least . [Copyright &y& Elsevier]

This paper studies Upper Domination , i.e. , the problem of computing the maximum cardinality of a minimal dominating set in a graph with respect to classical and parameterised complexity as well as approximability. [ABSTRACT FROM AUTHOR]

Graph editing problems offer an interesting perspective on sub- and supergraph identification problems for a large variety of target properties. They have also attracted significant attention in recent years, particularly in the area of parameterized complexity as the problems have rich parameter ecologies. In this paper we examine generalisations of the notion of editing a graph to obtain a regular subgraph. In particular we extend the notion of regularity to include two variants of edge-regularity along with the unifying constraint of strong regularity. We present a number of results, with the central observation that these problems retain the general complexity profile of their regularity-based inspiration: when the number of edits k and the maximum degree r are taken together as a combined parameter, the problems are tractable (i.e. in FPT ), but are otherwise intractable. We also examine variants of the basic editing to obtain a regular subgraph problem from the perspective of parameterizing by the treewidth of the input graph. In this case the treewidth of the input graph essentially becomes a limiting parameter on the natural k + r parameterization. [ABSTRACT FROM AUTHOR]

Community detection in graphs aims at identifying modules within a network and, possibly, their hierarchical organization by only using the information encoded in the graph modeling the network. Generally speaking, a community in a network is a subset of its nodes showing higher degree of interconnection with each other than to the remaining nodes. This is an informal characterization and different formal definitions of communities have been proposed in the literature, also in relation to the available information. For most such definitions, the problem of detecting a proper partition of the given network into a prefixed number of community is NP -hard. In this paper, we consider the case in which a weight is associated to each edge of the graph, measuring the amount of interconnection between the corresponding pair of nodes. Under this hypothesis, we introduce and explore a new definition of community, that is, min–max communities , to model highly connected sets of nodes: a min–max community is a set of vertices such that the weakest (minimal) relation inside the community is stronger than the strongest (maximal) relation outside. By analyzing the structural properties induced by this definition, we prove that the problem of partitioning a complete weighted graph into k > 0 communities is tractable. We also show that a slight modification to this framework results into an NP -complete problem. [ABSTRACT FROM AUTHOR]

A graph G 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, a set graph is the underlying graph of the digraph representation of a hereditarily finite set. In this paper, we continue the study of set graphs and related topics, focusing on computational complexity aspects. We prove that set graph recognition is NP-complete, even when the input is restricted to bipartite graphs with exactly two leaves. The problem remains NP-complete if, in addition, we require that the extensional acyclic orientation be also slim, that is, that the digraph obtained by removing any arc from it is not extensional. Our approach in fact allows us to also show that the counting variants of the above problems are #P-complete, and prove similar complexity results for problems related to a generalization of extensional acyclic digraphs, the so-called hyper-extensional digraphs, which were proposed by Aczel to describe hypersets. Our proofs are based on reductions from variants of the Hamiltonian Path problem. We also consider a variant of the well-known notion of a separating code in a digraph, the so-called open-out-separating code, and show that it is NP-complete to determine whether an input extensional acyclic digraph contains an open-out-separating code of given size. [ABSTRACT FROM AUTHOR]

Abstract: In this paper, we consider the selective graph coloring problem. Given an integer and a graph with a partition of V, it consists in deciding whether there exists a set in G such that for all , and such that the graph induced by is k-colorable. We investigate the complexity status of this problem in various classes of graphs. [Copyright &y& Elsevier]

Abstract: The guarding game is a game in which several cops try to guard a region in a (directed or undirected) graph against Robber. Robber and the cops are placed on the vertices of the graph; they take turns in moving to adjacent vertices (or staying), cops inside the guarded region, Robber on the remaining vertices (the robber-region). The goal of Robber is to enter the guarded region at a vertex with no cop on it. The problem is to determine whether for a given graph and given number of cops the cops are able to prevent Robber from entering the guarded region. Fomin et al. (2011) [7] proved that the problem is NP-complete when the robber-region is restricted to a tree. Further they prove that is it PSPACE-complete when the robber-region is restricted to a directed acyclic graph, and they ask about the problem complexity for arbitrary graphs. In this paper we prove that the problem is E-complete for arbitrary directed graphs. [Copyright &y& Elsevier]

Abstract: In this paper, we introduce the fast–mixed search model, which is a combination of the fast search model and the mixed search model. Given a graph in which a fugitive hides on vertices or along edges, the fast–mixed search problem is to find the minimum number of searchers to capture the fugitive in the fast–mixed search model. We establish a relation between the fast–mixed search problem and the induced-path cover problem. We also consider relations between the fast–mixed search problem and other graph search problems. We prove that Fast–Mixed Searching From Leaves is NP-complete, and it remains NP-complete for planar graphs with maximum degree 3. We also prove that Fast–Mixed Searching Between Leaves is NP-complete, and it remains NP-complete for graphs with maximum degree 4. We present linear-time algorithms for computing the fast–mixed search number and optimal search strategies of some classes of graphs, including trees, cacti, and proper interval graphs. [Copyright &y& Elsevier]

Abstract: In this paper, we show that the inverse problems of Hamiltonian Cycle and 3Dimensional Matching are coNP-complete. This completes the study of inverse problems of the six natural NP-complete problems from Garey and Johnson (1979) and answers an open question from Chen (2003) . We show that the coNP-completeness of the inverse problem of Hamiltonian Cycle holds for undirected as well as for directed graphs. [Copyright &y& Elsevier]

Abstract: The max-edge-coloring problem is a natural weighted generalization of the classical edge-coloring problem arising in the domain of communication systems. In this problem each color class is assigned the weight of the heaviest edge in this class and the objective is to find a proper edge-coloring of the input graph minimizing the sum of all color classes’ weights. We present new approximation results, that improve substantially the known ones, for several variants of the problem with respect to the class of the underlying graph. In particular, we deal with variants which are known to be NP-hard (general and bipartite graphs) or are proven to be NP-hard in this paper (complete graphs with bi-valued edge weights) or whose complexity question still remains open (trees). [Copyright &y& Elsevier]

A graph G 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, a set graph is the underlying graph of the digraph representation of a hereditarily finite set. In this paper, we continue the study of set graphs and related topics, focusing on computational complexity aspects. We prove that set graph recognition is NP-complete, even when the input is restricted to bipartite graphs with exactly two leaves. The problem remains NP-complete if, in addition, we require that the extensional acyclic orientation be also slim, that is, that the digraph obtained by removing any arc from it is not extensional. Our approach in fact allows us to also show that the counting variants of the above problems are #P-complete, and prove similar complexity results for problems related to a generalization of extensional acyclic digraphs, the so-called hyper-extensional digraphs, which were proposed by Aczel to describe hypersets. Our proofs are based on reductions from variants of the Hamiltonian Path problem. We also consider a variant of the well-known notion of a separating code in a digraph, the so-called open-out-separating code, and show that it is NP-complete to determine whether an input extensional acyclic digraph contains an open-out-separating code of given size. [ABSTRACT FROM AUTHOR]