On interval number in cycle convexity

Julio Araujo 1 Guillaume Ducoffe 2 Nicolas Nisse 2 Karol Suchan 3
2 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : Many notions in graph convexity have been defined and studied for various applications, such as geode-tic convexity (generalizing the classical convexity in Euclidean space to graphs), monophonic convexity (to model spreading of rumor or disease in a network), etc. Each of the convexity notions led to the study of important graph invariants such as the hull number (minimum number of vertices whose hull set is the entire graph) or the interval number (minimum number of vertices whose interval is the whole graph). Recently, Araujo et al. introduced the notion of Cycle Convexity of graphs for its application in Knot Theory. Roughly, the tunnel number of a knot embedded in a plane is equivalent to the hull number of a corresponding planar 4-regular graph in cycle convexity. In this paper, we study the interval number of a graph in cycle convexity. Precisely, given a graph G, its interval number in cycle convexity, denoted by incc(G), is the minimum cardinality of a set S ⊆ V (G) such that every vertex w ∈ V (G) \ S has two distinct neighbors u, v ∈ S such that u and v lie in same connected component of G[S]. In this work, first we provide bounds on incc(G) and its relations to other graph convexity parameters, and explore its behavior on grids. Then, we present some hardness results by showing that deciding whether incc(G) ≤ k is NP-complete, even if G is a split graph or a bounded-degree planar graph, and that the problem is W[1]-hard in bipartite graphs when k is the parameter. As a consequence, we obtain that it cannot be approximated up to a constant factor in the class of split graphs (unless P = N P). On the positive side, we present polynomial-time algorithms to compute incc(G) for outerplanar graphs, cobipartite graphs and interval graphs. We also present FPT algorithms to compute it for (q, q − 4)-graphs, where q is the parameter and for bounded treewidth graphs.
Complete list of metadatas

Cited literature [32 references]  Display  Hide  Download

https://hal.inria.fr/hal-01394201
Contributor : Nicolas Nisse <>
Submitted on : Tuesday, November 8, 2016 - 7:32:59 PM
Last modification on : Wednesday, January 9, 2019 - 10:04:01 PM
Long-term archiving on: Tuesday, March 14, 2017 - 11:44:37 PM

File

ResearchReport8nov16.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01394201, version 1

Citation

Julio Araujo, Guillaume Ducoffe, Nicolas Nisse, Karol Suchan. On interval number in cycle convexity. [Research Report] Inria Sophia Antipolis; I3S. 2016. ⟨hal-01394201v1⟩

Share

Metrics

Record views

228

Files downloads

80