Search

A linkage in a graph G of size k is a subgraph L of G whose connected components are k paths. The pattern of a linkage of size k is the set of k pairs formed by the endpoints of these paths. A consequence of the Unique Linkage Theorem is the following: there exists a function f: N rightarrow N such that if a plane graph G contains a sequence\scrC of at least f(k) nested cycles and a linkage of size at most k whose pattern vertices lay outside the outer cycle of scrC, then G contains a linkage with the same pattern avoiding the inner cycle of\scrC. In this paper we prove the following variant of this result: Assume that all the cycles in\scrC are "orthogonally" traversed by a linkage P and L is a linkage whose pattern vertices may lay either outside the outer cycle or inside the inner cycle of scrC := [C1,...,Cp, . . ., C2p-1]. We prove that there are two functions g, f: Nrightarrow N, such that if L has size at most k, P has size at least f(k), and | scrC | geq g(k), then there is a linkage with the same pattern as L that is "internally combed" by P, in the sense that L cap Cp subseteq P\cap Cp. This result applies to any graph that is partially embedded on a disk (wherescrC is also embedded). In fact, we prove this result in the most general version where the linkage L is s-scattered: every two vertices of distinct paths are within a distance bigger than s. We deduce several variants of this result in the cases where s = 0 and s > 0. These variants permit the application of the Unique Linkage Theorem on several path routing problems on embedded graphs. [ABSTRACT FROM AUTHOR]

A fundamental theorem of Whitney from 1933 asserts that 2-connected graphs G and H are 2-isomorphic, or equivalently, their cycle matroids are isomorphic if and only if G can be transformed into H by a series of operations called Whitney switches. In this paper we consider the quantitative question arising from Whitney's theorem: Given two 2-isomorphic graphs, can we transform one into another by applying at most k Whitney switches? This problem is already NP-complete for cycles, and we investigate its parameterized complexity. We show that the problem admits a kernel of size O(k) and thus is fixed-parameter tractable when parameterized by k. [ABSTRACT FROM AUTHOR]

We obtain new polynomial kernels and compression algorithms for Path Cover and Cycle Cover, the well-known generalizations of the classical Hamiltonian Path and Hamiltonian Cycle problems. Our choice of parameterization is strongly influenced by the work of Bir'o, Hujter, and Tuza, who in 1992 introduced H-graphs, intersection graphs of connected subgraphs of a subdivision of a fixed (multi-)graph H. In this work, we turn to proper H-graphs, where the containment relationship between the representations of the vertices is forbidden. As the treewidth of a graph measures how similar the graph is to a tree, the size of graph H is the parameter measuring the closeness of the graph to a proper interval graph. We prove the following results. Path Cover admits a kernel of size scrO (| H| 8), where | H| is the size of graph H. In other words, we design an algorithm that for an n-vertex graph G and integer k geq 1, in time polynomial in n and | H|, outputs a graph Gprime of size scrO (| H| 8) and kprime leq | V (Gprime)| such that the vertex set of G is coverable by k vertex-disjoint paths if and only if the vertex set of Gprime is coverable by kprime vertex-disjoint paths. Hamiltonian Cycle admits a kernel of size scrO (| H| 8). Cycle Cover admits a polynomial kernel. We prove it by providing a compression of size scrO (| H| 10) into another NP-complete problem, namely, Prize Collecting Cycle Cover, that is, we design an algorithm that, in time polynomial in n and | H|, outputs an equivalent instance of Prize Collecting Cycle Cover of size scrO (| H| 10). In all our algorithms we assume that a proper H-decomposition is given as a part of the input. [ABSTRACT FROM AUTHOR]

An undirected graph G is d-degenerate if every subgraph of G has a vertex of degree at most d. By the classical theorem of Erdös and Gallai from 1959, every graph of degeneracy d > 1 contains a cycle of length at least d + 1. The proof of Erdös and Gallai is constructive and can be turned into a polynomial time algorithm constructing a cycle of length at least d + 1. But can we decide in polynomial time whether a graph contains a cycle of length at least d + 2? An easy reduction from Hamiltonian Cycle provides a negative answer to this question: Deciding whether a graph has a cycle of length at least d+2 is NP-complete. Surprisingly, the complexity of the problem changes drastically when the input graph is 2-connected. In this case we prove that deciding whether G contains a cycle of length at least d + k can be done in time 2O(k) .| V (G)| O(1). In other words, deciding whether a 2-connected n-vertex G contains a cycle of length at least d+log n can be done in polynomial time. Similar algorithmic results hold for long paths in graphs. We observe that deciding whether a graph has a path of length at least d+1 is NP-complete. However, we prove that if graph G is connected, then deciding whether G contains a path of length at least d+k can be done in time 2O(k) .nO(1). We complement these results by showing that the choice of degeneracy as the ``above guarantee parameterization"" is optimal in the following sense: For any ε > 0 it is NP-complete to decide whether a connected (2-connected) graph of degeneracy d has a path (cycle) of length at least (1 + ε )d. [ABSTRACT FROM AUTHOR]

In the EDGE EDITING TO CONNECTED f-Degree Graph problem we are given a graph G, an integer fc, and a function f assigning integers to vertices of G. The task is to decide whether there is a connected graph F on the same vertex set as G, such that for every vertex v, its degree in F is f(v), and the number of edges in E(G)ΔE(F), the symmetric difference of E(G) and E(F), is at most k. We show that Edge EDITING TO CONNECTED f-DEGREE GRAPH is fixed- parameter tractable (FPT) by providing an algorithm solving the problem on an n-vertex graph in time2O(k)nO(1). We complement this result by showing that the weighted version of the problem with costs 1 and 0 is W[l]-hard when parameterized by k and the maximum value of f even when the input graph is a tree. Our FPT algorithm is based on a nontrivial combination of color-coding and fast computations of representative families over the direct sum matroid of l-elongation of the co-graphic matroid associated with G and a uniform matroid over the set of nonedges of G. We believe that this combination could be useful in designing parameterized algorithms for other edge editing and connectivity problems. [ABSTRACT FROM AUTHOR]

Seymour's decomposition theorem for regular matroids is a fundamental result with a number of combinatorial and algorithmic applications. In this work we demonstrate how this theorem can be used in the design of parameterized algorithms on regular matroids. We consider the problem of covering a set of vectors of a given finite dimensional linear space (vector space) by a subspace generated by a set of vectors of minimum size. Specifically, in the SPACE COVER problem, we are given a matrix M and a subset of its columns T; the task is to find a minimum set F of columns of M disjoint with T such that the linear span of F contains all vectors of T. For graphic matroids this problem is essentially Steiner Forest and for cographic matroids this is a generalization of MULTIWAY CUT. Our main result is the algorithm with running time 2Oh(k). | | M| |Oh(1) solving SPACE COVER in the case when M is a totally unimodular matrix over rationals, where k is the size of F. In other words, we show that on regular matroids the problem is fixed-parameter tractable parameterized by the rank of the covering subspace. [ABSTRACT FROM AUTHOR]

The notion of resolving sets in a graph was introduced by Slater [Proceedings of the Sixth Southeastern Conference on Combinatorics, Graph Theory, and Computing, Util. Math., Winnipeg, 1975, pp. 549-559] and Harary and Melter [Ars Com bin., 2 (1976), pp. 191-195] as a way of uniquely identifying every vertex in a graph. A set of vertices in a graph is a resolving set if for any pair of vertices x and y there is a vertex in the set which has distinct distances to x and y. A smallest resolving set in a graph is called a metric basis and its size, the metric dimension of the graph. The problem of computing the metric dimension of a graph is a well-known NP-hard problem and while it was known to be polynomial time solvable on trees, it is only recently that efforts have been made to understand its computational complexity on various restricted graph classes. In recent work, Foucaud [Algorithmica, 2016, pp. 1-31] showed that this problem is NP-complete even on interval graphs. They complemented this result by also showing that it is fixed-parameter tractable (FPT) parameterized by the metric dimension of the graph. In this work, we show that this FPT result can in fact be extended to all graphs of bounded tree-length. This includes well-known classes like chordal graphs, AT-free graphs, and permutation graphs. We also show that this problem is FPT parameterized by the modular-width of the input graph. [ABSTRACT FROM AUTHOR]

The cyclability of a graph is the maximum integer k for which every k vertices lie on a cycle. The algorithmic version of the problem, given a graph G and a nonnegative integer k, decide whether the cyclability of G is at least k, is NP-hard. We study the parametrized complexity of this problem. We prove that this problem, parameterized by k, is co-W[1]-hard and that it does not admit a polynomial kernel on planar graphs, unless NP ⊆ co-NP=poly. On the positive side, we give an FPT algorithm for planar graphs that runs in time 22O(k2 log k). n2. Our algorithm is based on a series of graph-theoretical results on cyclic linkages in planar graphs. [ABSTRACT FROM AUTHOR]

The Hadwiger number of a graph G is the largest integer h such that G has the complete graph Kh as a minor. We show that the problem of determining the Hadwiger number of a graph is 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 ≥ 2 but is NP-hard on chordal graphs for every fixed s ≥ 2. [ABSTRACT FROM AUTHOR]

Paths P1,..., Pk in a graph G = (V,E) are said to be mutually induced if for any 1 ≤ i < j ≤ k, Pi and Pj have neither common vertices nor adjacent vertices (except perhaps their end-vertices). The Induced Disjoint Paths problem is to test whether a graph G with k pairs of specified vertices (si, ti) contains k mutually induced paths Pi such that Pi connects si and ti for i = 1,...,k. We show that this problem is fixed-parameter tractable for claw-free graphs when parameterized by k. Several related problems, such as the k-in-a-Path problem, are proved to be fixed-parameter tractable for claw-free graphs as well. We show that an improvement of these results in certain directions is unlikely, for example, by noting that the Induced Disjoint Paths problem cannot have a polynomial kernel for line graphs (a type of claw-free graphs), unless NP ⊆ coNP/poly. Moreover, the problem becomes NP-complete, even when k = 2, for the more general class of K1,4-free graphs. Finally, we show that the nO(k)-time algorithm of Fiala et al. for testing whether a claw-free graph contains some k-vertex graph H as a topological induced minor is essentially optimal by proving that this problem is W[1]-hard even if G and H are line graphs. [ABSTRACT FROM AUTHOR]

We obtain asymptotically tight algorithmic bounds for Max-Cut and Edge Dominating Set problems on graphs of bounded clique-width. We show that on an n-vertex graph of clique-width t both problems (1) cannot be solved in time f(t)no(t) for any function f of t unless exponential time hypothesis fails, and (2) can be solved in time nO(t). [ABSTRACT FROM AUTHOR]

We study the parameterized complexity of the following Euler subgraph problems: (a) Large Euler Subgraph: For a given graph G and integer parameter k, does G contain an induced Eulerian subgraph with at least k vertices? (b) Long Circuit: For a given graph G and integer parameter k, does G contain an Eulerian subgraph with at least k edges? Our main algorithmic result is that Large Euler Subgraph is fixed parameter tractable (FPT) on undirected graphs. The complexity of the problem changes drastically on directed graphs, and we obtain the following complexity dichotomy: Large Euler Subgraph is NP-hard for every fixed k > 3 and is solvable in polynomial time for k ≤ 3. For Long Circuit, we prove that the problem is FPT on directed and undirected graphs. [ABSTRACT FROM AUTHOR]

Cops and robber is a classical pursuit-evasion game on undirected graphs, where the task is to identify the minimum number of cops sufficient to catch the robber. In this paper, we investigate the changes in problem's complexity and combinatorial properties with constraining the following natural game parameters: fuel, the number of steps each cop can make; cost, the total sum of steps along edges all cops can make; and time, the number of rounds of the game. [ABSTRACT FROM AUTHOR]

The notions of hypertree width and generalized hypertree width were introduced by Gottlob, Leone, and Scarcello in order to extend the concept of hypergraph acyclicity. These notions were further generalized by Grohe and Marx, who introduced the fractional hypertree width of a hypergraph. All these width parameters on hypergraphs are useful for extending the tractability of many problems in database theory and artificial intelligence. In this paper, we study the approximability of (generalized, fractional) hypertree width of sparse hypergraphs where the criterion of sparsity reflects the sparsity of their incidence graphs. Our first step is to prove that the (generalized, fractional) hypertree width of a hypergraph H is constant factor sandwiched by the treewidth of its incidence graph when the incidence graph belongs to some apex-minor-free graph class (the family of apex-minor-free graph classes includes planar graphs and graphs of bounded genus). This determines the combinatorial borderline above in which the notion of (generalized, fractional) hypertree width becomes essentially more general than treewidth, justifying that way its functionality as a hypergraph acyclicity measure. While for more general sparse families of hypergraphs treewidth of incidence graphs and all hypertree width parameters may differ arbitrarily, there are sparse families where a constant factor approximation algorithm is possible. In particular, we give a constant factor approximation polynomial time algorithm for (generalized, fractional) hypertree width on hypergraphs whose incidence graphs belong to some H-minor-free graph class. [ABSTRACT FROM AUTHOR]

We show that Edge Dominating Set, Hamiltonian Cycle, and Graph Coloring are W[1]-hard parameterized by clique-width. It was an open problem, explicitly mentioned in several papers, whether any of these problems is fixed parameter tractable when parameterized by the clique-width, that is, solvable in time g(k) ∙ nO(1) on n-vertex graphs of clique-width k, where g is some function of k only. Our results imply that the running time O(nf(k)) of many clique-widthbased algorithms is essentially the best we can hope for (up to a widely believed assumption from parameterized complexity, namely FPT ≠ W[1]). [ABSTRACT FROM AUTHOR]

We show that Edge Dominating Set, Hamiltonian Cycle, and Graph Coloring are W[1]-hard parameterized by clique-width. It was an open problem, explicitly mentioned in several papers, whether any of these problems is fixed parameter tractable when parameterized by the clique-width, that is, solvable in time g(k) · nO(1) on η-vertex graphs of clique-width k, where g is some function of k only. Our results imply that the running time O(nf(k)) of many clique-widthbased algorithms is essentially the best we can hope for (up to a widely believed assumption from parameterized complexity, namely FPT ≠ W[1]). [ABSTRACT FROM AUTHOR]

In the early studies on graph searching a graph was considered as a system of tunnels in which a fast and clever fugitive is hidden. The ‘classical’ search problem is to find a search plan using the minimal number of searchers. In this paper, we consider a new criterion of optimization, namely, the search cost. First, we prove monotone properties of searching with the smallest cost. Then, making use of monotone properties, we prove that for any graph G the search cost of G is equal to the smallest number of edges of all interval supergraphs of G. Finally, we show how to compute the search cost of a cograph and the corresponding search strategy in linear time. [ABSTRACT FROM AUTHOR]