Source author record

Yngve Villanger

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Data Structures and Algorithms Computational Complexity Discrete Mathematics math.CO

Catalog footprint

Research overview

13works

4topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2015arXiv

Output-Polynomial Enumeration on Graphs of Bounded (Local) Linear MIM-Width

The linear induced matching width (LMIM-width) of a graph is a width parameter defined by using the notion of branch-decompositions of a set function on ternary trees. In this paper we study output-polynomial enumeration algorithms on graphs of bounded LMIM-width and graphs of bounded local LMIM-width. In particular, we show that all 1-minimal and all 1-maximal (σ,ρ)-dominating sets, and hence all minimal dominating sets, of graphs of bounded LMIM-width can be enumerated with polynomial (linear) delay using polynomial space. Furthermore, we show that all minimal dominating sets of a unit square graph can be enumerated in incremental polynomial time.

preprint2014arXiv

Exploring Subexponential Parameterized Complexity of Completion Problems

Let ${\cal F}$ be a family of graphs. In the ${\cal F}$ -Completion problem, we are given a graph $G$ and an integer $k$ as input, and asked whether at most $k$ edges can be added to $G$ so that the resulting graph does not contain a graph from ${\cal F}$ as an induced subgraph. It appeared recently that special cases of ${\cal F}$ -Completion, the problem of completing into a chordal graph known as Minimum Fill-in, corresponding to the case of ${\cal F}=\{C_4,C_5,C_6,\ldots\}$ , and the problem of completing into a split graph, i.e., the case of ${\cal F}=\{C_4, 2K_2, C_5\}$ , are solvable in parameterized subexponential time $2^{O(\sqrt{k}\log{k})}n^{O(1)}$ . The exploration of this phenomenon is the main motivation for our research on ${\cal F}$ -Completion. In this paper we prove that completions into several well studied classes of graphs without long induced cycles also admit parameterized subexponential time algorithms by showing that: - The problem Trivially Perfect Completion is solvable in parameterized subexponential time $2^{O(\sqrt{k}\log{k})}n^{O(1)}$ , that is ${\cal F}$ -Completion for ${\cal F} =\{C_4, P_4\}$ , a cycle and a path on four vertices. - The problems known in the literature as Pseudosplit Completion, the case where ${\cal F} = \{2K_2, C_4\}$ , and Threshold Completion, where ${\cal F} = \{2K_2, P_4, C_4\}$ , are also solvable in time $2^{O(\sqrt{k}\log{k})} n^{O(1)}$ . We complement our algorithms for ${\cal F}$ -Completion with the following lower bounds: - For ${\cal F} = \{2K_2\}$ , ${\cal F} = \{C_4\}$ , ${\cal F} = \{P_4\}$ , and ${\cal F} = \{2K_2, P_4\}$ , ${\cal F}$ -Completion cannot be solved in time $2^{o(k)} n^{O(1)}$ unless the Exponential Time Hypothesis (ETH) fails. Our upper and lower bounds provide a complete picture of the subexponential parameterized complexity of ${\cal F}$ -Completion problems for ${\cal F}\subseteq\{2K_2, C_4, P_4\}$ .

preprint2013arXiv

Connecting Terminals and 2-Disjoint Connected Subgraphs

Given a graph $G=(V,E)$ and a set of terminal vertices $T$ we say that a superset $S$ of $T$ is $T$ -connecting if $S$ induces a connected graph, and $S$ is minimal if no strict subset of $S$ is $T$ -connecting. In this paper we prove that there are at most ${|V \setminus T| \choose |T|-2} \cdot 3^{\frac{|V \setminus T|}{3}}$ minimal $T$ -connecting sets when $|T| \leq n/3$ and that these can be enumerated within a polynomial factor of this bound. This generalizes the algorithm for enumerating all induced paths between a pair of vertices, corresponding to the case $|T|=2$ . We apply our enumeration algorithm to solve the {\sc 2-Disjoint Connected Subgraphs} problem in time $O^*(1.7804^n)$ , improving on the recent $O^*(1.933^n)$ algorithm of Cygan et al. 2012 LATIN paper.

preprint2013arXiv

Large induced subgraphs via triangulations and CMSO

We obtain an algorithmic meta-theorem for the following optimization problem. Let ϕ be a Counting Monadic Second Order Logic (CMSO) formula and t be an integer. For a given graph G, the task is to maximize |X| subject to the following: there is a set of vertices F of G, containing X, such that the subgraph G[F] induced by F is of treewidth at most t, and structure (G[F],X) models ϕ. Some special cases of this optimization problem are the following generic examples. Each of these cases contains various problems as a special subcase: 1) "Maximum induced subgraph with at most l copies of cycles of length 0 modulo m", where for fixed nonnegative integers m and l, the task is to find a maximum induced subgraph of a given graph with at most l vertex-disjoint cycles of length 0 modulo m. 2) "Minimum Γ-deletion", where for a fixed finite set of graphs Γ containing a planar graph, the task is to find a maximum induced subgraph of a given graph containing no graph from Γ as a minor. 3) "Independent Π-packing", where for a fixed finite set of connected graphs Π, the task is to find an induced subgraph G[F] of a given graph G with the maximum number of connected components, such that each connected component of G[F] is isomorphic to some graph from Π. We give an algorithm solving the optimization problem on an n-vertex graph G in time O(#pmc n^{t+4} f(t,ϕ)), where #pmc is the number of all potential maximal cliques in G and f is a function depending of t and ϕ only. We also show how a similar running time can be obtained for the weighted version of the problem. Pipelined with known bounds on the number of potential maximal cliques, we deduce that our optimization problem can be solved in time O(1.7347^n) for arbitrary graphs, and in polynomial time for graph classes with polynomial number of minimal separators.

preprint2013arXiv

Largest chordal and interval subgraphs faster than 2^n

We prove that in an n-vertex graph, induced chordal and interval subgraphs with the maximum number of vertices can be found in time $O(2^{λn})$ for some $λ<1$ . These are the first algorithms breaking the trivial $2^n n^{O(1)}$ bound of the brute-force search for these problems.

preprint2013arXiv

Maximal induced matchings in triangle-free graphs

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 $10^{n/5} \approx 1.5849^n$ maximal induced matchings, and this bound is best possible. We prove that any $n$ -vertex triangle-free graph has at most $3^{n/3} \approx 1.4423^n$ maximal induced matchings, and this bound is attained by any disjoint union of copies of the complete bipartite graph $K_{3,3}$ . Our result implies that all maximal induced matchings in an $n$ -vertex triangle-free graph can be listed in time $O(1.4423^n)$ , yielding the fastest known algorithm for finding a maximum induced matching in a triangle-free graph.

preprint2013arXiv

Subexponential fixed-parameter tractability of cluster editing

In the Correlation Clustering, also known as Cluster Editing, we are given an undirected n-vertex graph G and a positive integer k. The task is to decide if G can be transformed into a cluster graph, i.e., a disjoint union of cliques, by changing at most k adjacencies, i.e. by adding/deleting at most k edges. We give a subexponential algorithm that, in time 2^O(sqrt(pk)) + n^O(1) decides whether G can be transformed into a cluster graph with p cliques by changing at most k adjacencies. We complement our algorithmic findings by the following tight lower bounds on the asymptotic behaviour of our algorithm. We show that, unless ETH fails, for any constant 0 < s <= 1, there is p = Theta(k^s) such that there is no algorithm deciding in time 2^o(sqrt(pk)) n^O(1) whether G can be transformed into a cluster graph with p cliques by changing at most k adjacencies.

preprint2013arXiv

TREEWIDTH and PATHWIDTH parameterized by vertex cover

After the number of vertices, Vertex Cover is the largest of the classical graph parameters and has more and more frequently been used as a separate parameter in parameterized problems, including problems that are not directly related to the Vertex Cover. Here we consider the TREEWIDTH and PATHWIDTH problems parameterized by k, the size of a minimum vertex cover of the input graph. We show that the PATHWIDTH and TREEWIDTH can be computed in O*(3^k) time. This complements recent polynomial kernel results for TREEWIDTH and PATHWIDTH parameterized by the Vertex Cover.

preprint2012arXiv

A Polynomial kernel for Proper Interval Vertex Deletion

It is known that the problem of deleting at most k vertices to obtain a proper interval graph (Proper Interval Vertex Deletion) is fixed parameter tractable. However, whether the problem admits a polynomial kernel or not was open. Here, we answers this question in affirmative by obtaining a polynomial kernel for Proper Interval Vertex Deletion. This resolves an open question of van Bevern, Komusiewicz, Moser, and Niedermeier.

preprint2012arXiv

Generating All Minimal Edge Dominating Sets with Incremental-Polynomial Delay

For an arbitrary undirected simple graph G with m edges, we give an algorithm with running time O(m^4 |L|^2) to generate the set L of all minimal edge dominating sets of G. For bipartite graphs we obtain a better result; we show that their minimal edge dominating sets can be enumerated in time O(m^4 |L|). In fact our results are stronger; both algorithms generate the next minimal edge dominating set with incremental-polynomial delay O(m^5 |L|) and O(m^4 |L|) respectively, when L is the set of already generated minimal edge dominating sets. Our algorithms are tailored for and solve the equivalent problems of enumerating minimal (vertex) dominating sets of line graphs and line graphs of bipartite graphs, with incremental-polynomial delay, and consequently in output-polynomial time. Enumeration of minimal dominating sets in graphs has very recently been shown to be equivalent to enumeration of minimal transversals in hypergraphs. The question whether the minimal transversals of a hypergraph can be enumerated in output-polynomial time is a fundamental and challenging question in Output-Sensitive Enumeration; it has been open for several decades and has triggered extensive research in the field.

preprint2011arXiv

k-Gap Interval Graphs

We initiate the study of a new parameterization of graph problems. In a multiple interval representation of a graph, each vertex is associated to at least one interval of the real line, with an edge between two vertices if and only if an interval associated to one vertex has a nonempty intersection with an interval associated to the other vertex. A graph on n vertices is a k-gap interval graph if it has a multiple interval representation with at most n+k intervals in total. In order to scale up the nice algorithmic properties of interval graphs (where k=0), we parameterize graph problems by k, and find FPT algorithms for several problems, including Feedback Vertex Set, Dominating Set, Independent Set, Clique, Clique Cover, and Multiple Interval Transversal. The Coloring problem turns out to be W[1]-hard and we design an XP algorithm for the recognition problem.

preprint2011arXiv

Subexponential Parameterized Algorithm for Minimum Fill-in

The Minimum Fill-in problem is to decide if a graph can be triangulated by adding at most k edges. Kaplan, Shamir, and Tarjan [FOCS 1994] have shown that the problem is solvable in time O(2^(O(k)) + k2 * nm) on graphs with n vertices and m edges and thus is fixed parameter tractable. Here, we give the first subexponential parameterized algorithm solving Minimum Fill-in in time O(2^(O(\sqrt{k} log k)) + k2 * nm). This substantially lower the complexity of the problem. Techniques developed for Minimum Fill-in can be used to obtain subexponential parameterized algorithms for several related problems including Minimum Chain Completion, Chordal Graph Sandwich, and Triangulating Colored Graph.

preprint2010arXiv

A Quartic Kernel for Pathwidth-One Vertex Deletion

The pathwidth of a graph is a measure of how path-like the graph is. Given a graph G and an integer k, the problem of finding whether there exist at most k vertices in G whose deletion results in a graph of pathwidth at most one is NP- complete. We initiate the study of the parameterized complexity of this problem, parameterized by k. We show that the problem has a quartic vertex-kernel: We show that, given an input instance (G = (V, E), k); |V| = n, we can construct, in polynomial time, an instance (G', k') such that (i) (G, k) is a YES instance if and only if (G', k') is a YES instance, (ii) G' has O(k^{4}) vertices, and (iii) k' \leq k. We also give a fixed parameter tractable (FPT) algorithm for the problem that runs in O(7^{k} k \cdot n^{2}) time.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Yngve Villanger

Research overview

Is this your work?

13 publications

Output-Polynomial Enumeration on Graphs of Bounded (Local) Linear MIM-Width

Exploring Subexponential Parameterized Complexity of Completion Problems

Connecting Terminals and 2-Disjoint Connected Subgraphs

Large induced subgraphs via triangulations and CMSO

Largest chordal and interval subgraphs faster than 2^n

Maximal induced matchings in triangle-free graphs

Subexponential fixed-parameter tractability of cluster editing

TREEWIDTH and PATHWIDTH parameterized by vertex cover

A Polynomial kernel for Proper Interval Vertex Deletion

Generating All Minimal Edge Dominating Sets with Incremental-Polynomial Delay

k-Gap Interval Graphs

Subexponential Parameterized Algorithm for Minimum Fill-in

A Quartic Kernel for Pathwidth-One Vertex Deletion

See the researcher in context

Building this map preview