International audience

Motivated by the role of triadic closures in social networks, and the importance of finding a maximum subgraph avoiding a fixed pattern, we introduce and initiate the parameterized study of the StrongF-closure problem, where F is a fixed graph. This is a generalization of Strong Triadic Closure, whereas it is a relaxation of F-free Edge Deletion. In StrongF-closure, we want to select a maximum number of edges of the input graph G, and mark them as strong edges, in the following way: whenever a subset of the strong edges forms a subgraph isomorphic to F, then the corresponding induced subgraph of G is not isomorphic to F. Hence, the subgraph of G defined by the strong edges is not necessarily F-free, but whenever it contains a copy of F, there are additional edges in G to forbid that strong copy of F in G. We study StrongF-closure from a parameterized perspective with various natural parameterizations. Our main focus is on the number k of strong edges as the parameter. We show that the problem is FPT with this parameterization for every fixed graph F, whereas it does not admit a polynomial kernel even when $$F =P_3$$ F=P3. In fact, this latter case is equivalent to the Strong Triadic Closure problem, which motivates us to study this problem on input graphs belonging to well known graph classes. We show that Strong Triadic Closure does not admit a polynomial kernel even when the input graph is a split graph, whereas it admits a polynomial kernel when the input graph is planar, and even d-degenerate. Furthermore, on graphs of maximum degree at most 4, we show that Strong Triadic Closure is FPT with the above guarantee parameterization $$k - \mu (G)$$ k-μ(G), where $$\mu (G)$$ μ(G) is the maximum matching size of G. We conclude with some results on the parameterization of StrongF-closure by the number of edges of G that are not selected as strong.

Problems related to finding induced subgraphs satisfying given properties form one of the most studied areas within graph algorithms. However, for many applications, it is desirable that the found subgraph has as few connections to the rest of the graph as possible, which gives rise to the Secluded Π- Subgraph problem. Here, input k is the size of the desired subgraph, and input t is a limit on the number of neighbors this subgraph has in the rest of the graph. This problem has been studied from a parameterized perspective, and unfortunately it turns out to be W[1]-hard for many graph properties Π, even when parameterized by k + t . We show that the situation changes when we are looking for a connected induced subgraph satisfying Π. In particular, we show that the Connected Secluded Π -Subgraph problem is FPT when parameterized by just t for many important graph properties Π.

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.

We are pleased to present this special issue of Algorithmica, which contains the extended journal versions of selected papers previously presented at the 9th International Symposium on Parameterized and Exact Computation, IPEC 2014, September 10–12, Wroclaw, Poland. The symposium is an established annual meeting of the multivariate and exact algorithms communities. This issue consists of nine papers, reviewed thoroughly according to the usual, high standard of the journal. In The Parameterized Complexity of Geometric Graph Isomorphism, V. Arvind and Gaurav Rattan present improved FPT algorithm for Geometric Graph Isomorphism problem, where one is to decide whether there is a distance preserving bijection between two sets of points in k-dimensional euclidian space. Igor Razgon in On the read-once property of branching programs and CNFs of bounded treewidthproves a space lower bound for non-deterministic read-oncebranching programs on functions expressible as CNFswith treewidth at most k of their primal graphs. In Finding Shortest Paths between Graph Colourings, Matthew Johnson, Dieter Kratsch, Stefan Kratsch, Viresh Patel, and Daniel Paulusma give a complete picture of the parameterized complexity of the k-colouring reconfiguration problem, where the goal is to modify one proper colouring into another one, by changing the colour of one vertex at a time. Given a system of linear equations Ax = b over the binary field one can ask whether there is a solution of weight at most t , exactly t or at least t . In Solving Linear

Listing, generating or 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.

The Hadwiger number of a graph $G$ is the largest integer $h$ such that $G$ has the complete graph $K_h$ as a minor. We show that the problem of determining the Hadwiger number of a graph is \sf NP-hard on co-bipartite graphs but can be solved in polynomial time on cographs and on bipartite permutation graphs. We also consider a natural generalization of this problem that asks for the largest integer $h$ such that $G$ has a minor with $h$ vertices and diameter at most $s$. We show that this problem can be solved in polynomial time on AT-free graphs when $s\geq 2$ but is \sf NP-hard on chordal graphs for every fixed $s\geq 2$.

Abstract Motivated by challenges related to domination, connectivity, and information propagation in social and other networks, we initiate the study of the VECTOR CONNECTIVITY problem. This problem takes as input a graph G and an integer kv for every vertex v of G, and the objective is to find a vertex subset S of minimum cardinality such that every vertex v either belongs to S, or is connected to at least kv vertices of S by disjoint paths. If we require each path to be of length exactly 1, we get the well‐known VECTOR DOMINATION problem, which is a generalization of the famous DOMINATING SET problem and several of its variants. Consequently, our problem becomes NP‐hard if an upper bound on the length of the disjoint paths is also supplied as input. Due to the hardness of these domination variants even on restricted graph classes, like split graphs, VECTOR CONNECTIVITY seems to be a natural problem to study for drawing the boundaries of tractability for this type of problems. We show that VECTOR CONNECTIVITY can actually be solved in polynomial time on split graphs, in addition to cographs and trees. We also show that the problem can be approximated in polynomial time within a factor of on all n‐vertex graphs.Copyright © 2014 Wiley Periodicals, Inc. NETWORKS, Vol. 63(4), 277–285 2014

The Bipartite Contraction problem takes as input an $n$-vertex graph $G$ and an integer $k$, and the task is to determine whether we can obtain a bipartite graph from $G$ by a sequence of at most $k$ edge contractions. We show that Bipartite Contraction is fixed-parameter tractable when parameterized by $k$. Despite a strong resemblance between Bipartite Contraction and the classical Odd Cycle Transversal (OCT) problem, the methods developed to tackle OCT do not seem to be directly applicable to Bipartite Contraction. To obtain our result, we combine several techniques and concepts that are central in parameterized complexity: iterative compression, irrelevant vertices, and important separators. To the best of our knowledge, this is the first time the irrelevant vertex technique and the concept of important separators are applied in unison. Furthermore, our algorithm may serve as a comprehensible example of the usage of the irrelevant vertex technique.

The problem of determining the cutwidth of a graph is a notoriously hard problem which remains NP-complete under severe restrictions on input graphs. Until recently, nontrivial polynomial-time cutwidth algorithms were known only for subclasses of graphs of bounded treewidth. Very recently, Heggernes et al. (SIAM J. Discrete Math., 25 (2011), pp. 1418--1437) initiated the study of cutwidth on graph classes containing graphs of unbounded treewidth and showed that a greedy algorithm computes the cutwidth of threshold graphs. We continue this line of research and present the first polynomial-time algorithm for computing the cutwidth of bipartite permutation graphs. Our algorithm runs in linear time. We stress that the cutwidth problem is NP-complete on bipartite graphs and its computational complexity is open even on small subclasses of permutation graphs, such as trivially perfect graphs.

We initiate the study of the Bipartite Contraction problem from the perspective of parameterized complexity. In this problem we are given a graph $G$ and an integer $k$, and the task is to determine whether we can obtain a bipartite graph from $G$ by a sequence of at most $k$ edge contractions. Our main result is an $f(k) n^{O(1)}$ time algorithm for Bipartite Contraction. Despite a strong resemblance between Bipartite Contraction and the classical Odd Cycle Transversal (OCT) problem, the methods developed to tackle OCT do not seem to be directly applicable to Bipartite Contraction. Our algorithm is based on a novel combination of the irrelevant vertex technique, introduced by Robertson and Seymour, and the concept of important separators. Both techniques have previously been used as key components of algorithms for fundamental problems in parameterized complexity. However, to the best of our knowledge, this is the first time the two techniques are applied in unison.

We give a linear-time algorithm to compute the cutwidth of threshold graphs, thereby resolving the computational complexity of cutwidth on this graph class. Threshold graphs are a well-studied subclass of interval graphs and of split graphs, both of which are unrelated subclasses of chordal graphs. To complement our result, we show that cutwidth is NP-complete on split graphs, and consequently also on chordal graphs. The cutwidth of interval graphs is still open, and only very few graph classes are known so far on which polynomial-time cutwidth algorithms exist. Thus we contribute to define the border between graph classes on which cutwidth is polynomially solvable and on which it remains NP-complete.

Abstract We show that the mixed search number and the linear‐width of interval graphs and of split graphs can be computed in linear time and in polynomial time, respectively. © 2009 Wiley Periodicals, Inc. NETWORKS, 2010

We present an algorithm with runtime $O(k^{2k}n^3m)$ for the following NP-complete problem [M. Garey and D. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman and Co., San Francisco, 1979, problem GT35]: 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 [H. Kaplan, R. Shamir, and R. E. Tarjan, SIAM J. Comput., 28 (1999), pp. 1906–1922; R. G. Downey and M. R. Fellows, Parameterized Complexity, Springer-Verlag, New York, 1999; M. Serna and D. Thilikos, Bull. Eur. Assoc. Theory Comput. Sci. EATCS, 86 (2005), pp. 41–65; G. Gutin, S. Szeider, and A. Yeo, in Proceedings IWPEC 2006, Lecture Notes in Comput. Sci. 4169, Springer-Verlag, Berlin, 2006, pp. 60–71], first posed by Kaplan, Shamir, and Tarjan, of whether this problem was fixed parameter tractable. The problem has applications in profile minimization for sparse matrix computations [J. A. George and J. W. H. Liu, Computer Solution of Large Sparse Positive Definite Systems, Prentice-Hall, Englewood Cliffs, NJ, 1981; R. E. Tarjan, in Sparse Matrix Computations, J. R. Bunch and D. J. Rose, eds., Academic Press, 1976, pp. 3–22], and our results show tractability for the case of a small number k of zero elements in the envelope. Our algorithm performs bounded search among possible ways of adding edges to a graph to obtain an interval graph and combines this with a greedy algorithm when graphs of a certain structure are reached by the search.

We present an algorithm with runtime O(k(2k)n3 * 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.

The problem of computing minimal triangulations of graphs, also called minimal fill, was introduced and solved in 1976 by Rose, Tarjan, and Lueker [SIAM J. Comput., 5 (1976), pp. 266-283] in time $O(nm)$ and thus $O(n^3)$ for dense graphs. Although the topic has received increasing attention since then and several new results on characterizing and computing minimal triangulations have been presented, this first time bound has remained the best. In this paper we introduce an $O(n^\alpha \log n)$ time algorithm for computing minimal triangulations, where $O(n^\alpha)$ is the time required to multiply two $n \times n$ matrices. The current best known $\alpha$ is less than $2.376$, and thus our result breaks the longstanding asymptotic time complexity bound for this problem. To achieve this result, we introduce and combine several techniques that are new to minimal triangulation algorithms, such as working on the complement of the input graph, graph search for a vertex set A that bounds the size of the connected components when A is removed, and matrix multiplication.

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.