Filter by type:

Sort by year:

Covering the edges of bipartite graphs by cycles of length 4

Henning Fernau, Pinar Heggernes, Daniel Meister, and Reza Saei
Submitted Paper Submitted for possible journal publication

Maximal induced matchings in triangle-free graphs

Manu Basavaraju, Pinar Heggernes, Pim van 't Hof, Reza Saei, and Yngve Villanger
Journal Paper Journal of Graph Theory 83(3) (2016), 231-250

Abstract

An induced matching in a graph is a set of edges whose endpoints induce a 1-regular subgraph. It is known that every n-vertex graph has at most 10n/5 ≈ 1.5849n maximal induced matchings, and this bound is the best possible. We prove that every n-vertex triangle-free graph has at most 3n/3 ≈ 1.4423n maximal induced matchings; this bound is attained by every disjoint union of copies of the complete bipartite graph K3,3. Our result implies that all maximal induced matchings in an n-vertex triangle-free graph can be listed in time O(1.4423n), yielding the fastest known algorithm for finding a maximum induced matching in a triangle-free graph.

Computing the metric dimension for chain graphs

Henning Fernau, Pinar Heggernes, Pim van 't Hof, Daniel Meister, and Reza Saei
Journal Paper Information Processing Letters 115(9) (2015), 671 - 676

Abstract

The metric dimension of a graph G is the smallest size of a set R of vertices that can distinguish each vertex pair of G by the shortest-path distance to some vertex in R. Computing the metric dimension is NP-hard, even when restricting inputs to bipartite graphs. We present a linear-time algorithm for computing the metric dimension for chain graphs, which are bipartite graphs whose vertices can be ordered by neighborhood inclusion.

Finding Disjoint Paths in Split Graphs

Pinar Heggernes, Pim van 't Hof, Erik Jan van Leeuwen, and Reza Saei
Journal Paper Theory of Computing Systems 57(1) (2015), 140 - 159

Abstract

The well-known DISJOINT PATHS problem takes as input a graph G and a set of k pairs of terminals in G, and the task is to decide whether there exists a collection of k pairwise vertex-disjoint paths in G such that the vertices in each terminal pair are connected to each other by one of the paths. This problem is known to be NP-complete, even when restricted to planar graphs or interval graphs. Moreover, although the problem is fixed-parameter tractable when parameterized by k due to a celebrated result by Robertson and Seymour, it is known not to admit a polynomial kernel unless NP ⊆ coNP/poly. We prove that DISJOINT PATHS remains NP-complete on split graphs, and show that the problem admits a kernel with O(k2) vertices when restricted to this graph class. We furthermore prove that, on split graphs, the edge-disjoint variant of the problem is also NP-complete and admits a kernel with O(k3) vertices. To the best of our knowledge, our kernelization results are the first non-trivial kernelization results for these problems on graph classes.

Algorithmic and combinatorial problems on graph classes

Reza Saei
Thesis PhD dissertation, University of Bergen, 2015

Graph classes and Ramsey numbers

Rémy Belmonte, Pinar Heggernes, Pim van 't Hof, Reza Saei, and Arash Rafiey
Journal Paper Discrete Applied Mathematics 173 (2014), 16 - 27

Abstract

For a graph class G and any two positive integers i and j, the Ramsey number RG(i, j) is the smallest positive integer such that every graph in G on at least RG(i, j) vertices has a clique of size i or an independent set of size j. For the class of all graphs, Ramsey numbers are notoriously hard to determine, and they are known only for very small values of i and j. Even if we restrict G to be the class of claw-free graphs, it is highly unlikely that a formula for determining RG(i, j) for all values of i and j will ever be found, as there are infinitely many nontrivial Ramsey numbers for claw-free graphs that are as difficult to determine as for arbitrary graphs. Motivated by this difficulty, we establish here exact formulas for all Ramsey numbers for three important subclasses of claw-free graphs: line graphs, long circular interval graphs, and fuzzy circular interval graphs. On the way to obtaining these results, we also establish all Ramsey numbers for the class of perfect graphs. Such positive results for graph classes are rare: a formula for determining RG(i, j) for all values of i and j, when G is the class of planar graphs, was obtained by Steinberg and Tovey (1993), and this seems to be the only previously known result of this kind. We complement our aforementioned results by giving exact formulas for determining all Ramsey numbers for several graph classes related to perfect graphs.

Subset feedback vertex sets in chordal graphs

Petr Golovach, Pinar Heggernes, Dieter Kratsch, and Reza Saei
Journal PaperJournal of Discrete Algorithms 26 (2014), 7 - 15

Abstract

Given a graph G = (V , E) and a set S ⊆ V , a set U ⊆ V is a subset feedback vertex set of (G, S) if no cycle in G[V \ U] contains a vertex of S. The Subset Feedback Vertex Set problem takes as input G, S, and an integer k, and the question is whether (G, S) has a subset feedback vertex set of cardinality or weight at most k. Both the weighted and the unweighted versions of this problem are NP-complete on chordal graphs, even on their subclass split graphs. We give an algorithm with running time O(1.6708n) that enumerates all minimal subset feedback vertex sets on chordal graphs on n vertices. As a consequence, Subset Feedback Vertex Set can be solved in time O(1.6708n) on chordal graphs, both in the weighted and in the unweighted case. As a comparison, on arbitrary graphs the fastest known algorithm for these problems has O(1.8638n) running time. We also obtain that a chordal graph G has at most 1.6708n minimal subset feedback vertex sets, regardless of S. This narrows the gap with respect to the best known lower bound of 1.5848n on this graph class. For arbitrary graphs, the gap is substantially wider, as the best known upper and lower bounds are 1.8638n and 1.5927n, respectively.

Maximal induced matchings in triangle-free graphs

Manu Basavaraju, Pinar Heggernes, Pim van 't Hof, Reza Saei, and Yngve Villanger
Conference PaperWG 2014, LNCS 8747: 93-104, Springer

Abstract

An induced matching in a graph is a set of edges whose endpoints induce a 1-regular subgraph. It is known that every n-vertex graph has at most 10n/5 ≈ 1.5849n maximal induced matchings, and this bound is best possible. We prove that every n-vertex triangle-free graph has at most 3n/3 ≈ 1.4423n maximal induced matchings, and this bound is attained by every disjoint union of copies of the complete bipartite graph K3,3. Our result implies that all maximal induced matchings in an n-vertex triangle-free graph can be listed in time O(1.4423n), yielding the fastest known algorithm for finding a maximum induced matching in a triangle-free graph.

Finding Disjoint Paths in Split Graphs

Pinar Heggernes, Pim van 't Hof, Erik Jan van Leeuwen, and Reza Saei
Conference PaperSOFSEM 2014, LNCS 8327: 315-326, Springer

Abstract

The well-known Disjoint Paths problem takes as input a graph G and a set of k pairs of terminals in G, and the task is to decide whether there exists a collection of k pairwise vertex-disjoint paths in G such that the vertices in each terminal pair are connected to each other by one of the paths. This problem is known to NP-complete, even when restricted to planar graphs or interval graphs. Moreover, although the problem is fixed-parameter tractable when parameterized by k due to a celebrated result by Robertson and Seymour, it is known not to admit a polynomial kernel unless NP ⊆ coNP/poly. We prove that Disjoint Paths remains NP-complete on split graphs, and show that the problem admits a kernel with O(k2) vertices when restricted to this graph class. We furthermore prove that, on split graphs, the edge-disjoint variant of the problem is also NP-complete and admits a kernel with O(k3) vertices. To the best of our knowledge, our kernelization results are the first nontrivial kernelization results for these problems on graph classes.

Signed edge k-subdomination numbers in graphs

A. Khodkar, and S.M. Sheikholeslami, and Reza Saei
Journal PaperArs Combinatoria 109 (2013), 129 - 141

Abstract

The closed neighborhood NG[e] of an edge e in a graph G is the set consisting of e and of all edges having a common end-vertex with e. Let f be a function on E(G), the edge set of G, into the set {-1, 1}. If ∑x∈ N[e] f(x) ≥ 1 for at least k edges e of G, then f is called a signed edge k-subdominating function of G. The minimum of the values ∑e∈ E(G) f(e), taken over all signed edge k-subdominating function f of G, is called the signed edge k-subdomination number of G and is denoted by γ'ks (G). In this note we initiate the study of the signed edge k-subdomination in graphs and present some (sharp) bounds for this parameter.

An exact algorithm for Subset Feedback Vertex Set on chordal graphs

Petr Golovach, Pinar Heggernes, Dieter Kratsch, and Reza Saei
Conference PaperIPEC 2012, LNCS 7535: 85 - 96, Springer

Abstract

Given a graph G = (V, E) and a set S ⊆ V , a set U ⊆ V is a subset feedback vertex set of (G, S) if no cycle in G[V \U] contains a vertex of S. The Subset Feedback Vertex Set problem takes as input G, S, and an integer k, and the question is whether (G, S) has a subset feedback vertex set of cardinality or weight at most k. Both the weighted and the unweighted versions of this problem are NP-complete on chordal graphs, even on their subclass split graphs. We give an algorithm with running time O(1.6708n) that enumerates all minimal subset feedback vertex sets on chordal graphs with n vertices. As a consequence, Subset Feedback Vertex Set can be solved in time O(1.6708n) on chordal graphs, both in the weighted and in the unweighted case. On arbitrary graphs, the fastest known algorithm for the problems has O(1.8638n) running time.

Ramsey numbers for line graphs and perfect graphs

Rémy Belmonte, Pinar Heggernes, Pim van 't Hof, and Reza Saei
Conference PaperCOCOON 2012, (Best Paper Award), LNCS 7434: 204 - 215, Springer

Abstract

For any graph class G and any two positive integers i and j, the Ramsey number RG(i,j) is the smallest integer such that every graph in G on at least RG(i,j) vertices has a clique of size i or an independent set of size j. For the class of all graphs Ramsey numbers are notoriously hard to determine, and the exact values are known only for very small integers i and j. For planar graphs all Ramsey numbers can be determined by an exact formula, whereas for claw-free graphs there exist Ramsey numbers that are as difficult to determine as for arbitrary graphs. No further graph classes seem to have been studied for this purpose. Here, we give exact formulas for determining all Ramsey numbers for various classes of graphs. Our main result is an exact formula for all Ramsey numbers for line graphs, which form a large subclass of claw-free graphs and are not perfect. We obtain this by proving a general result of independent interest: an upper bound on the number of edges any graph can have if it has bounded degree and bounded matching size. As complementary results, we determine all Ramsey numbers for perfect graphs and for several subclasses of perfect graphs.

Maximal induced matchings in triangle-free graphs

Manu Basavaraju, Pinar Heggernes, Pim van 't Hof, Reza Saei, and Yngve Villanger
Unreviewed PaperArxiv: CoRR abs/1312.5180 (2013)

Abstract

An induced matching in a graph is a set of edges whose endpoints induce a 1-regular subgraph. It is known that any n-vertex graph has at most 10n/5 ≈ 1.5849n maximal induced matchings, and this bound is best possible. We prove that any n-vertex triangle-free graph has at most 3n/3 ≈ 1.4423n maximal induced matchings, and this bound is attained by any disjoint union of copies of the complete bipartite graph K3,3. Our result implies that all maximal induced matchings in an n-vertex triangle-free graph can be listed in time O(1.4423n), yielding the fastest known algorithm for finding a maximum induced matching in a triangle-free graph.

Minus edge k-subdomination number of a graph

A.N. Ghameshlou, Reza Saei, and S.M. Sheikholeslami
Journal PaperAKCE International Journal of Graphs and Combinatorics 8 (2011), 1 - 11

Abstract

The closed neighborhood NG[e] of an edge e in a graph G is the set consisting of e and of all edges having a common end-vertex with e. Let f be a function on E(G), the edge set of G, into the set {-1, 0, 1}. If ∑x∈ N[e] f(x) ≥ 1 for at least k edges e of G, then f is called a minus edge k-subdominating function of G. The minimum of the values ∑e∈ E(G) f(e), taken over all minus edge k-subdominating functions f of G, is called the minus edge k-subdomination number of G and is denoted by γ'km(G). In this note we initiate the study of minus edge k-subdomination numbers in graphs and present some (sharp) bounds for this parameter.

Signed (b,k)-matchings in graphs

A.N. Ghameshlou, Reza Saei, S.M. Sheikholeslami, and L. Volkmann
Journal PaperAn. Şt. Univ. Ovidius Constanţa 18 (2010), 127 - 138

Abstract

Let G be a simple graph without isolated vertices with vertex set V (G) and edge set E(G), b be a positive integer and k an integer with 1 ≤ k ≤ |V (G)|. A function f : E(G) → {-1, 1} is said to be a signed (b, k)-matching of G if ∑e∈ E(v) f(e) ≤ b for at least k vertices v of G, where E(v) is the set of all edges at v. The value max ∑e∈ E(G) f(e), taking over all signed (b,k)-matching f of G, is called the signed (b, k)- matching number of G and is denoted by β'(b,k)(G). In this paper we initiate the study of the signed (b,k)-matching number in graphs and present some bounds for this parameter.

Signed (b,k)-edge covers in graphs

A.N. Ghameshlou, A. Khodkar, Reza Saei, and S.M. Sheikholeslami
Journal PaperIntelligent Information Management 2 (2010), 143 - 148

Abstract

Let G be a simple graph with vertex set V(G) and edge set E(G). Let G have at least k vertices of degree at least b, where k and b are positive integers. A function f : E(G) → {-1,1} is said to be a signed (b,k)-edge cover of G if ∑e∈E(v) f(e) ≥ b for at least k vertices of G, where E(v)={uv ∈ E(G) | u ∈ N(v)}. The value min∑e∈E(G) f(e), taking over all signed (b,k)-edge covers f of G is called the signed (b,k)-edge cover number of G and denoted by ρ'b,k(G). In this paper we give some bounds on the signed (b,k)-edge cover number of graphs.

Negative k-subdecision number of a graph

A.N. Ghameshlou, A. Khodkar, Reza Saei, and S.M. Sheikholeslami
Journal PaperAKCE International Journal of Graphs and Combinatorics 6 (2009), 361 - 371

Abstract

Let G be a simple connected graph without isolated vertex with vertex set V(G) and edge set E(G). A function f : V (G) → {-1, 1} is said to be a negative k-subdecision function of G if ∑x∈NG(v) f(x) ≤ 1 for at least k vertices v of G. The value max∑x∈V(G) f(x), taking over all negative k-subdecision functions f of G, is called the negative k-subdecision number of G and is denoted by βkD(G). In this paper we initiate the study of the negative k-subdecision numbers in graphs and present some bounds for this parameter.

Signed star k-subdomination numbers in graphs

Reza Saei, and S.M. Sheikholeslami
Journal PaperDiscrete Applied Mathematics 156 (2008), 3066 - 3070

Abstract

Let G be a simple graph without isolated vertex with vertex set V(G) and edge set E(G). A function f : E(G) → {-1, 1} is said to be a signed star k-subdominating function of G if ∑e∈E(v) f(e) ≥ 1 for at least k vertices v of G, where E(v) = {uv ∈ E(G) | u ∈ N(v)}. The value min∑e∈E(G) f(e), taking over all signed star k-subdominating function f of G is called the signed star k-subdomination number of G and denoted by γkSS(G). In this paper we give some bounds on the signed star k-subdomination number of graphs.

Majority domination number in graphs

Reza Saei
ThesisMaster dissertation, Azarbaijan Shahid Madani University, 2008 (in Persian)