Pinar Heggernes

MFCS Conference 2018 Conference Paper

Rainbow Vertex Coloring Bipartite Graphs and Chordal Graphs

• Pinar Heggernes
• Davis Issac
• Juho Lauri
• Paloma T. Lima
• Erik Jan van Leeuwen

Given a graph with colors on its vertices, a path is called a rainbow vertex path if all its internal vertices have distinct colors. We say that the graph is rainbow vertex-connected if there is a rainbow vertex path between every pair of its vertices. We study the problem of deciding whether the vertices of a given graph can be colored with at most k colors so that the graph becomes rainbow vertex-connected. Although edge-colorings have been studied extensively under similar constraints, there are significantly fewer results on the vertex variant that we consider. In particular, its complexity on structured graph classes was explicitly posed as an open question. We show that the problem remains NP-complete even on bipartite apex graphs and on split graphs. The former can be seen as a first step in the direction of studying the complexity of rainbow coloring on sparse graphs, an open problem which has attracted attention but limited progress. We also give hardness of approximation results for both bipartite and split graphs. To complement the negative results, we show that bipartite permutation graphs, interval graphs, and block graphs can be rainbow vertex-connected optimally in polynomial time.

TCS Journal 2016 Journal Article

Enumerating minimal connected dominating sets in graphs of bounded chordality

• Petr A. Golovach
• Pinar Heggernes
• Dieter Kratsch

Enumerating objects of specified type is one of the principal tasks in algorithmics. In graph algorithms one often enumerates vertex subsets satisfying a certain property. We study the enumeration of all minimal connected dominating sets of an input graph from various graph classes of bounded chordality. We establish enumeration algorithms as well as lower and upper bounds for the maximum number of minimal connected dominating sets in such graphs. In particular, we present algorithms to enumerate all minimal connected dominating sets of chordal graphs in time O ( 1. 7159 n ), of split graphs in time O ( 1. 3803 n ), and of AT-free, strongly chordal, and distance-hereditary graphs in time O ⁎ ( 3 n / 3 ), where n is the number of vertices of the input graph. Our algorithms imply corresponding upper bounds for the number of minimal connected dominating sets for these graph classes.

TCS Journal 2016 Journal Article

The Firefighter problem on graph classes

• Fedor V. Fomin
• Pinar Heggernes
• Erik Jan van Leeuwen

The Firefighter problem aims to save as many vertices of a graph as possible from a fire that starts in a vertex and spreads through the graph. At every time step a new firefighter may be placed on some vertex, and then the fire advances to every vertex that is not protected by a firefighter and has a neighbor on fire. The problem is notoriously hard: it is NP-hard even when the input graph is a bipartite graph or a tree of maximum degree 3, it is NP-hard to approximate within n 1 − ϵ for any ϵ > 0, and it is W [ 1 ] -hard when parameterized by the number of saved vertices. We show that Firefighter can be solved in polynomial time on interval graphs, split graphs, permutation graphs, and P k -free graphs for fixed k. To complement these results, we show that the problem remains NP-hard on unit disk graphs.

TCS Journal 2015 Journal Article

Induced Subgraph Isomorphism on proper interval and bipartite permutation graphs

• Pinar Heggernes
• Pim van 't Hof
• Daniel Meister
• Yngve Villanger

Given two graphs G and H as input, the Induced Subgraph Isomorphism (ISI) problem is to decide whether G has an induced subgraph that is isomorphic to H. This problem is NP-complete already when G and H are restricted to disjoint unions of paths, and consequently also NP-complete on proper interval graphs and on bipartite permutation graphs. We show that ISI can be solved in polynomial time on proper interval graphs and on bipartite permutation graphs, provided that H is connected. As a consequence, we obtain that ISI is fixed-parameter tractable on these two graph classes, when parametrised by the number of connected components of H. Our results contrast and complement the following known results: W [ 1 ] -hardness of ISI on interval graphs when parametrised by the number of vertices of H, NP-completeness of ISI on connected interval graphs and on connected permutation graphs, and NP-completeness of Subgraph Isomorphism on connected proper interval graphs and connected bipartite permutation graphs.

I&C Journal 2013 Journal Article

Fixed-parameter algorithms for Cochromatic Number and Disjoint Rectangle Stabbing via iterative localization

• Pinar Heggernes
• Dieter Kratsch
• Daniel Lokshtanov
• Venkatesh Raman
• Saket Saurabh

Given a permutation π of { 1, …, n } and a positive integer k, can π be partitioned into at most k subsequences, each of which is either increasing or decreasing? We give an algorithm with running time 2 O ( k 2 log k ) n O ( 1 ) that solves this problem, thereby showing that it is fixed parameter tractable. This NP-complete problem is equivalent to deciding whether the cochromatic number of a given permutation graph on n vertices is at most k. Our algorithm solves in fact a more general problem: within the mentioned running time, it decides whether the cochromatic number of a given perfect graph on n vertices is at most k. To obtain our result we use a combination of two well-known techniques within parameterized algorithms: iterative compression and greedy localization. Consequently we name this combination “iterative localization”. We further demonstrate the power of this combination by giving an algorithm with running time 2 O ( k 2 log k ) n log n that decides whether a given set of n non-overlapping axis-parallel rectangles can be stabbed by at most k of a given set of horizontal and vertical lines.

TCS Journal 2013 Journal Article

Minimal dominating sets in graph classes: Combinatorial bounds and enumeration

• Jean-François Couturier
• Pinar Heggernes
• Pim van ’t Hof
• Dieter Kratsch

The number of minimal dominating sets that a graph on n vertices can have is known to be at most 1. 715 9 n. This upper bound might not be tight, since no examples of graphs with 1. 570 5 n or more minimal dominating sets are known. For several classes of graphs, we substantially improve the upper bound on the number of minimal dominating sets. At the same time, we give algorithms for enumerating all minimal dominating sets, where the running time of each algorithm is within a polynomial factor of the proved upper bound for the graph class in question. In several cases, we provide examples of graphs containing the maximum possible number of minimal dominating sets for graphs in that class, thereby showing the corresponding upper bounds to be tight.

TCS Journal 2013 Journal Article

Parameterized complexity of vertex deletion into perfect graph classes

• Pinar Heggernes
• Pim van ’t Hof
• Bart M.P. Jansen
• Stefan Kratsch
• Yngve Villanger

Vertex deletion problems are at the heart of parameterized complexity. For a graph class F, the F -Deletion problem takes as input a graph G and an integer k. The question is whether it is possible to delete at most k vertices from G such that the resulting graph belongs to F. Whether Perfect Deletion is fixed-parameter tractable, and whether Chordal Deletion admits a polynomial kernel, when parameterized by k, have been stated as open questions in previous work. We show that Perfect Deletion and Weakly Chordal Deletion are W [ 2 ] -hard when parameterized by k. In search of positive results, we study a restricted variant of the F -Deletion problem. In this restricted variant, the deleted vertices must be taken from a specified set X, and we parameterize by | X |. We show that for Perfect Deletion and Weakly Chordal Deletion, although this restriction immediately ensures fixed-parameter tractability, it is not enough to yield polynomial kernels, unless NP ⊆ coNP / poly. On the positive side, for Chordal Deletion, the restriction enables us to obtain a kernel with O ( | X | 4 ) vertices.

TCS Journal 2011 Journal Article

Bandwidth on AT-free graphs

• Petr Golovach
• Pinar Heggernes
• Dieter Kratsch
• Daniel Lokshtanov
• Daniel Meister
• Saket Saurabh

We study the classical Bandwidth problem from the viewpoint of parametrised algorithms. Given a graph G = ( V, E ) and a positive integer k, the Bandwidth problem asks whether there exists a bijective function β: { 1, …, ∣ V ∣ } → V such that for every edge u v ∈ E, ∣ β − 1 ( u ) − β − 1 ( v ) ∣ ≤ k. It is known that under standard complexity assumptions, no algorithm for Bandwidth with running time of the form f ( k ) n O ( 1 ) exists, even when the input is restricted to trees. We initiate the search for classes of graphs where such algorithms do exist. We present an algorithm with running time n ⋅ 2 O ( k log k ) for Bandwidth on AT-free graphs, a well-studied graph class that contains interval, permutation, and cocomparability graphs. Our result is the first non-trivial algorithm that shows fixed-parameter tractability of Bandwidth on a graph class on which the problem remains NP -complete.

TCS Journal 2011 Journal Article

Computing minimum distortion embeddings into a path for bipartite permutation graphs and threshold graphs

• Pinar Heggernes
• Daniel Meister
• Andrzej Proskurowski

The problem of computing minimum distortion embeddings of a given graph into a line (path) was introduced in 2004 and has quickly attracted significant attention with subsequent results appearing at recent stoc and soda conferences. So far, all such results concern approximation algorithms or exponential-time exact algorithms. We give the first polynomial-time algorithms for computing minimum distortion embeddings of graphs into a path when the input graphs belong to specific graph classes. In particular, we solve this problem in polynomial time for bipartite permutation graphs and threshold graphs. For both graph classes, the distortion can be arbitrarily large. The graphs that we consider are unweighted.

TCS Journal 2011 Journal Article

Graphs of linear clique-width at most 3

• Pinar Heggernes
• Daniel Meister
• Charis Papadopoulos

A graph has linear clique-width at most k if it has a clique-width expression using at most k labels such that every disjoint union operation has an operand which is a single vertex graph. We give the first characterisation of graphs of linear clique-width at most 3, and we give the first polynomial-time recognition algorithm for graphs of linear clique-width at most 3. In addition, we present new characterisations of graphs of linear clique-width at most 2. We also give a layout characterisation of graphs of bounded linear clique-width; a similar characterisation was independently shown by Gurski and by Lozin and Rautenbach.

TCS Journal 2010 Journal Article

Clustering with partial information

• Hans L. Bodlaender
• Michael R. Fellows
• Pinar Heggernes
• Federico Mancini
• Charis Papadopoulos
• Frances Rosamond

The Correlation Clustering problem, also known as the Cluster Editing problem, seeks to edit a given graph by adding and deleting edges to obtain a collection of vertex-disjoint cliques, such that the editing cost is minimized. The Edge Clique Partitioning problem seeks to partition the edges of a given graph into edge-disjoint cliques, such that the number of cliques is minimized. Both problems are known to be NP-hard, and they have been previously studied with respect to approximation and fixed-parameter tractability. In this paper we study these two problems in a more general setting that we term fuzzy graphs, where the input graphs may have missing information, meaning that whether or not there is an edge between some pairs of vertices of the input graph can be undecided. For fuzzy graphs the Correlation Clustering and Edge Clique Partitioning problems have previously been studied only with respect to approximation. Here we give parameterized algorithms based on kernelization for both problems. We prove that the Correlation Clustering problem is fixed-parameter tractable on fuzzy graphs when parameterized by ( k, r ), where k is the editing cost and r is the minimum number of vertices required to cover the undecided edges. In particular we show that it has a polynomial-time reduction to a problem kernel on O ( k 2 + r ) vertices. We provide an analogous result for the Edge Clique Partitioning problem on fuzzy graphs. Using ( k, r ) as parameters, where k bounds the size of the partition, and r is the minimum number of vertices required to cover the undecided edges, we describe a polynomial-time kernelization to a problem kernel on O ( k 4 ⋅ 3 r ) vertices. This implies fixed-parameter tractability for this parameterization. Furthermore we also show that parameterizing only by the number of cliques k, is not enough to obtain fixed-parameter tractability. The problem remains, in fact, NP-hard for each fixed k > 2.

MFCS Conference 2009 Conference Paper

Choosability of P5-Free Graphs

• Petr A. Golovach
• Pinar Heggernes

Abstract A graph is k -choosable if it admits a proper coloring of its vertices for every assignment of k (possibly different) allowed colors to choose from for each vertex. It is NP-hard to decide whether a given graph is k -choosable for k ≥ 3, and this problem is considered strictly harder than the k -coloring problem. Only few positive results are known on input graphs with a given structure. Here, we prove that the problem is fixed parameter tractable on P 5 -free graphs when parameterized by k. This graph class contains the well known and widely studied class of cographs. Our result is surprising since the parameterized complexity of k -coloring is still open on P 5 -free graphs. To give a complete picture, we show that the problem remains NP-hard on P 5 -free graphs when k is a part of the input.

TCS Journal 2009 Journal Article

Single-edge monotonic sequences of graphs and linear-time algorithms for minimal completions and deletions

• Pinar Heggernes
• Charis Papadopoulos

We study graph properties that admit an increasing, or equivalently decreasing, sequence of graphs on the same vertex set such that for any two consecutive graphs in the sequence their difference is a single edge. This is useful for characterizing and computing minimal completions and deletions of arbitrary graphs into having these properties. We prove that threshold graphs and chain graphs admit such sequences. Based on this characterization and other structural properties, we present linear-time algorithms both for computing minimal completions and deletions into threshold, chain, and bipartite graphs, and for extracting a minimal completion or deletion from a given completion or deletion. Minimum completions and deletions into these classes are NP-hard to compute.

MFCS Conference 2008 Conference Paper

Clustering with Partial Information

• Hans L. Bodlaender
• Michael R. Fellows
• Pinar Heggernes
• Federico Mancini 0001
• Charis Papadopoulos
• Frances A. Rosamond

Abstract The Correlation Clustering problem, also known as the Cluster Editing problem, seeks to edit a given graph by adding and deleting edges to obtain a collection of vertex-disjoint cliques, such that the editing cost is minimized. The Edge Clique Partitioning problem seeks to partition the edges of a given graph into edge-disjoint cliques, such that the number of cliques is minimized. Both problems are known to be NP-hard, and they have been previously studied with respect to approximation and fixed parameter tractability. In this paper we study these two problems in a more general setting that we term fuzzy graphs, where the input graphs may have missing information, meaning that whether or not there is an edge between some pairs of vertices of the input graph can be undecided. For fuzzy graphs the Correlation Clustering and Edge Clique Partitioning problems have previously been studied only with respect to approximation. Here we give parameterized algorithms based on kernelization for both problems. We prove that the Correlation Clustering problem is fixed-parameter tractable on fuzzy graphs when parameterized by ( k, r ), where k is the editing cost and r is the minimum number of vertices required to cover the undecided edges. In particular we show that it has a polynomial-time reduction to a problem kernel on O ( k 2 + r ) vertices. We provide an analogous result for the Edge Clique Partitioning problem on fuzzy graphs. Using ( k, r ) as parameters, where k bounds the size of the partition, and r is the minimum number of vertices required to cover the undecided edges, we describe a polynomial-time kernelization to a problem kernel on O ( k 4 ·3 r ) vertices. This implies fixed-parameter tractability for this parameterization. Furthermore we also show that parameterizing only by the number of cliques k, is not enough to obtain fixed-parameter tractability. The problem remains, in fact, NP-hard for each fixed k > 2.

TCS Journal 2008 Journal Article

Sequential and parallel triangulating algorithms for Elimination Game and new insights on Minimum Degree

• Anne Berry
• Elias Dahlhaus
• Pinar Heggernes
• Geneviève Simonet

Elimination Game is a well-known algorithm that simulates Gaussian elimination of matrices on graphs, and it computes a triangulation of the input graph. The number of fill edges in the computed triangulation is highly dependent on the order in which Elimination Game processes the vertices, and in general the produced triangulations are neither minimum nor minimal. In order to obtain a triangulation which is close to minimum, the Minimum Degree heuristic is widely used in practice, but until now little was known on the theoretical mechanisms involved. In this paper we show some interesting properties of Elimination Game; in particular that it is able to compute a partial minimal triangulation of the input graph regardless of the order in which the vertices are processed. This results in a new algorithm to compute minimal triangulations that are sandwiched between the input graph and the triangulation resulting from Elimination Game. One of the strengths of the new approach is that it is easily parallelizable, and thus we are able to present the first parallel algorithm to compute such sandwiched minimal triangulations. In addition, the insight that we gain through Elimination Game is used to partly explain the good behavior of the Minimum Degree algorithm. We also give a new algorithm for producing minimal triangulations that is able to use the minimum degree idea to a wider extent.

STOC Conference 2007 Conference Paper

Interval completion with few edges

• Pinar Heggernes
• Christophe Paul
• Jan Arne Telle
• Yngve Villanger

We present an algorithm with runtime O(k (2k) n 3 * m) for the following NP-complete problem: Given an arbitrary graph G on n vertices and m edges, can we obtain an interval graph by adding at most k new edges to G? This resolves the long-standing open question, first posed by Kaplan, Shamir and Tarjan, of whether this problem could be solved in time f(k) * n (O(1)) .The problem has applications in Physical Mapping of DNA and in Profile Minimization for Sparse Matrix Computations. For the first application, our results show tractability for the case of a small number k of false negative errors, and for the second, a small number k of zero elements in the envelope.

MFCS Conference 2006 Conference Paper

Optimal Linear Arrangement of Interval Graphs

• Johanne Cohen
• Fedor V. Fomin
• Pinar Heggernes
• Dieter Kratsch
• Gregory Kucherov

Abstract We study the optimal linear arrangement (OLA) problem on interval graphs. Several linear layout problems that are NP-hard on general graphs are solvable in polynomial time on interval graphs. We prove that, quite surprisingly, optimal linear arrangement of interval graphs is NP-hard. The same result holds for permutation graphs. We present a lower bound and a simple and fast 2-approximation algorithm based on any interval model of the input graph.

SODA Conference 2005 Conference Paper

Computing minimal triangulations in time O(n alpha log n) = o(n 2. 376 )

• Pinar Heggernes
• Jan Arne Telle
• Yngve Villanger

TCS Journal 2001 Journal Article

A practical algorithm for making filled graphs minimal

• Jean R.S. Blair
• Pinar Heggernes
• Jan Arne Telle

For an arbitrary filled graph G + of a given original graph G, we consider the problem of removing fill edges from G + in order to obtain a graph M that is both a minimal filled graph of G and a subgraph of G +. For G + with f fill edges and e original edges, we give a simple O(f(e+f)) algorithm which solves the problem and computes a corresponding minimal elimination ordering of G. We report on experiments with an implementation of our algorithm, where we test graphs G corresponding to some real sparse matrix applications and apply well-known and widely used ordering heuristics to find G +. Our findings show the amount of fill that is commonly removed by a minimalization for each of these heuristics, and also indicate that the runtime of our algorithm on these practical graphs is better than the presented worst-case bound.