Search

Parameterization above (or below) a guarantee is a successful concept in parameterized algorithms. The idea is that many computational problems admit "natural" guarantees bringing to algorithmic questions whether a better solution (above the guarantee) could be obtained efficiently. For example, for every boolean CNF formula on m clauses, there is an assignment that satisfies at least m/2 clauses. How difficult is it to decide whether there is an assignment satisfying more than m / 2 + k clauses? Or, if an n-vertex graph has a perfect matching, then its vertex cover is at least n/2. Is there a vertex cover of size at least n / 2 + k for some k ≥ 1 and how difficult is it to find such a vertex cover? The above guarantee paradigm has led to several exciting discoveries in the areas of parameterized algorithms and kernelization. We argue that this paradigm could bring forth fresh perspectives on well-studied problems in approximation algorithms. Our example is the longest cycle problem. One of the oldest results in extremal combinatorics is the celebrated Dirac's theorem from 1952. Dirac's theorem provides the following guarantee on the length of the longest cycle: for every 2-connected n-vertex graph G with minimum degree δ (G) ≤ n / 2 , the length of a longest cycle L is at least 2 δ (G) . Thus the "essential" part in finding the longest cycle is in approximating the "offset" k = L - 2 δ (G) . The main result of this paper is the above-guarantee approximation theorem for k. Informally, the theorem says that approximating the offset k is not harder than approximating the total length L of a cycle. In other words, for any (reasonably well-behaved) function f, a polynomial time algorithm constructing a cycle of length f(L) in an undirected graph with a cycle of length L, yields a polynomial time algorithm constructing a cycle of length 2 δ (G) + Ω (f (k)) . [ABSTRACT FROM AUTHOR]

We investigate the parameterized complexity of finding diverse sets of solutions to three fundamental combinatorial problems. The input to the Weighted Diverse Bases problem consists of a matroid M , a weight function ω : E (M) → N , and integers k ≥ 1 , d ≥ 1 . The task is to decide if there is a collection of k bases B 1 , ⋯ , B k of M such that the weight of the symmetric difference of any pair of these bases is at least d . The input to the Weighted Diverse Common Independent Sets problem consists of two matroids M 1 , M 2 defined on the same ground set E , a weight function ω : E → N , and integers k ≥ 1 , d ≥ 1 . The task is to decide if there is a collection of k common independent sets I 1 , ⋯ , I k of M 1 and M 2 such that the weight of the symmetric difference of any pair of these sets is at least d . The input to the Diverse Perfect Matchings problem consists of a graph G and integers k ≥ 1 , d ≥ 1 . The task is to decide if G contains k perfect matchings M 1 , ⋯ , M k such that the symmetric difference of any two of these matchings is at least d . We show that none of these problems can be solved in polynomial time unless P = NP . We derive fixed-parameter tractable ( FPT ) algorithms for all three problems with (k , d) as the parameter, and present a p o l y (k , d) -sized kernel for Weighted Diverse Bases. [ABSTRACT FROM AUTHOR]

We introduce the following submodular generalization of the Shortest Cycle problem. For a nonnegative monotone submodular cost function f defined on the edges (or the vertices) of an undirected graph G, we seek for a cycle C in G of minimum cost = f(C). We give an algorithm that given an n-vertex graph G, parameter ɛ > 0, and the function f represented by an oracle, in time n(log 1/ɛ) finds a cycle C in G with f(C)≤ (1+ɛ).. This is in sharp contrast with the non-approximability of the closely related Monotone Submodular Shortest (s,t-Path problem, which requires exponentially many queries to the oracle for finding an n2/3-ɛ-approximation Goel et al. [7], FOCS 2009. We complement our algorithm with a matching lower bound. We show that for every ɛ > 0, obtaining a (1+ɛ)-approximation requires at least nΩ (log 1/ ɛ) queries to the oracle. When the function f is integer-valued, our algorithm yields that a cycle of cost can be found in time n(log). In particular, for = n(1) this gives a quasipolynomial-time algorithm computing a cycle of minimum submodular cost. Interestingly, while a quasipolynomial-time algorithm often serves as a good indication that a polynomial time complexity could be achieved, we show a lower bound that n(log n) queries are required even when = (n). We also consider special cases of monotone submodular functions, corresponding to the number of different color classes needed to cover a cycle in an edge-colored multigraph G. For special cases of the corresponding minimization problem, we obtain fixed-parameter tractable algorithms and polynomial-time algorithms, when restricted to certain classes of inputs. [ABSTRACT FROM AUTHOR]

A subset T ⊆ V (G) of vertices of a graph G is said to be cyclable if G has a cycle C containing every vertex of T , and for a positive integer k , a graph G is k - cyclable if every set of vertices of size at most k is cyclable. The Terminal Cyclability problem asks, given a graph G and a set T of vertices, whether T is cyclable, and the k - Cyclability problem asks, given a graph G and a positive integer k , whether G is k -cyclable. These problems are generalizations of the classical Hamiltonian Cycle problem. We initiate the study of these problems for graph classes that admit polynomial algorithms for Hamiltonian Cycle. We show that Terminal Cyclability can be solved in linear time for interval graphs, bipartite permutation graphs and cographs. Moreover, we construct certifying algorithms that either produce a solution, that is a cycle, or output a graph separator that certifies a no-answer. We use these results to show that k - Cyclability can be solved in polynomial time when restricted to the aforementioned graph classes. [ABSTRACT FROM AUTHOR]

Paths P 1 , ... , P k are mutually induced if any two distinct P i and P j have neither common vertices nor adjacent vertices (except perhaps their end-vertices). The Induced Disjoint Paths problem is to decide if a graph G with k pairs of specified vertices (s i , t i) contains k mutually induced paths P i such that each P i connects s i and t i. This problem is NP-complete even for k = 2. We prove that it can be solved in polynomial time for AT-free graphs even when k is part of the input. Consequently, the problem of deciding if an AT-free graph contains a fixed graph H as an induced topological minor admits a polynomial-time algorithm. We show that such an algorithm is essentially optimal by proving that the problem is W [ 1 ] -hard with parameter | V H | , even for a subclass of AT-free graphs, namely cobipartite graphs. We also show that the problems k -in-a-Path and k -in-a-Tree are polynomial-time solvable on AT-free graphs even if k is part of the input. [ABSTRACT FROM AUTHOR]

An enumeration kernel as defined by Creignou et al. (2017) [11] for a parameterized enumeration problem consists of an algorithm that transforms each instance into one whose size is bounded by the parameter plus a solution-lifting algorithm that efficiently enumerates all solutions from the set of the solutions of the kernel. We propose to consider two new versions of enumeration kernels by asking that the solutions of the original instance can be enumerated in polynomial time or with polynomial delay from the kernel solutions. Using the NP-hard Matching Cut problem parameterized by structural parameters such as the vertex cover number or the cyclomatic number of the input graph, we show that the new enumeration kernels present a useful notion of data reduction for enumeration problems which allows to compactly represent the set of feasible solutions. [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]

For a graph H, a graph G is an H-graph if it is an intersection graph of connected subgraphs of some subdivision of H. H-graphs naturally generalize several important graph classes like interval graphs or circular-arc graph. This class was introduced in the early 1990s by Bíró, Hujter, and Tuza. Recently, Chaplick et al. initiated the algorithmic study of H-graphs by showing that a number of fundamental optimization problems like Maximum Clique, Maximum Independent Set, or Minimum Dominating Set are solvable in polynomial time on H-graphs. We extend and complement these algorithmic findings in several directions. First we show that for every fixed H, the class of H-graphs is of logarithmically-bounded boolean-width (via mim-width). Pipelined with the plethora of known algorithms on graphs of bounded boolean-width, this describes a large class of problems solvable in polynomial time on H-graphs. We also observe that H-graphs are graphs with polynomially many minimal separators. Combined with the work of Fomin, Todinca and Villanger on algorithmic properties of such classes of graphs, this identify another wide class of problems solvable in polynomial time on H-graphs. The most fundamental optimization problems among the problems solvable in polynomial time on H-graphs are Maximum Clique, Maximum Independent Set, and Minimum Dominating Set. We provide a more refined complexity analysis of these problems from the perspective of parameterized complexity. We show that Maximum Independent Set and Minimum Dominating Set are W[1]-hard being parameterized by the size of H plus the size of the solution. On the other hand, we prove that when H is a tree, then Minimum Dominating Set is fixed-parameter tractable parameterized by the size of H. For Maximum Clique we show that it admits a polynomial kernel parameterized by H and the solution size. [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]

A subgraph complement of the graph G is a graph obtained from G by complementing all the edges in one of its induced subgraphs. We study the following algorithmic question: for a given graph G and graph class G , is there a subgraph complement of G which is in G ? We show that this problem can be solved in polynomial time for various choices of the graphs class G , such as bipartite, d-degenerate, or cographs. We complement these results by proving that the problem is NP -complete when G is the class of regular graphs. [ABSTRACT FROM AUTHOR]

We introduce the rendezvous game with adversaries. In this game, two players, Facilitator and Divider , play against each other on a graph. Facilitator has two agents and Divider has a team of k agents located in some vertices. They take turns in moving their agents to adjacent vertices (or staying put). Facilitator wins if his agents meet in some vertex. Divider aims to prevent the rendezvous of Facilitator's agents. We show that deciding whether Facilitator can win is PSPACE -hard and, when parameterized by k , co-W [ 2 ] -hard. Moreover, even deciding whether Facilitator can win within τ steps is co-NP -complete already for τ = 2. On the other hand, for chordal and P 5 -free graphs, we prove that the problem is solvable in polynomial time. Finally, we show that the problem is fixed-parameter tractable parameterized by both the graph's neighborhood diversity and the number of steps τ. [ABSTRACT FROM AUTHOR]

A graph H is a square root of a graph G, or equivalently, G is the square of H, if G can be obtained from H by adding an edge between any two vertices in H that are of distance 2. The SQUARE ROOT problem is that of deciding whether a given graph admits a square root. The problem of testing whether a graph admits a square root which belongs to some specified graph class ℋ is called the ℋ-SQUARE ROOT problem. By showing boundedness of treewidth we prove that SQUARE ROOT is polynomial-time solvable on some classes of graphs with small clique number and that ℋ-SQUARE ROOT is polynomial-time solvable when ℋ is the class of cactuses. [ABSTRACT FROM AUTHOR]

For a fixed graph H , the H - Minor Edit problem takes as input a graph G and an integer k and asks whether G can be modified into H by a total of at most k edge contractions, edge deletions and vertex deletions. Replacing edge contractions by vertex dissolutions yields the H - Topological Minor Edit problem. For each problem we show polynomial-time solvable and NP -complete cases depending on the choice of H . Moreover, when G is AT-free, chordal or planar, we show that H - Minor Edit is polynomial-time solvable for all graphs H . [ABSTRACT FROM AUTHOR]

The Eulerian Editing problem asks, given a graph G and an integer k , whether G can be modified into an Eulerian graph using at most k edge additions and edge deletions. We show that this problem is polynomial-time solvable for both undirected and directed graphs. We generalize these results for problems with degree parity constraints and degree balance constraints, respectively. We also consider the variants where vertex deletions are permitted. Combined with known results, this leads to full complexity classifications for both undirected and directed graphs and for every subset of the three graph operations. [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]

We show that all minimal edge dominating sets of a graph can be generated in incremental polynomial time. We present an algorithm that solves the equivalent problem of enumerating minimal (vertex) dominating sets of line graphs in incremental polynomial, and consequently output polynomial, time. Enumeration of minimal dominating sets in graphs has 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; it has been open for several decades and has triggered extensive research. To obtain our result, we present a flipping method to generate all minimal dominating sets of a graph. Its basic idea is to apply a flipping operation to a minimal dominating set $$D^*$$ to generate minimal dominating sets $$D$$ such that $$G[D]$$ contains more edges than $$G[D^*]$$ . We show that the flipping method works efficiently on line graphs, resulting in an algorithm with delay $$O(n^2m^2|\mathcal {L}|)$$ between each pair of consecutively output minimal dominating sets, where $$n$$ and $$m$$ are the numbers of vertices and edges of the input graph, respectively, and $$\mathcal {L}$$ is the set of already generated minimal dominating sets. Furthermore, we are able to improve the delay to $$O(n^2m|\mathcal {L}|)$$ on line graphs of bipartite graphs. Finally we show that the flipping method is also efficient on graphs of large girth, resulting in an incremental polynomial time algorithm to enumerate the minimal dominating sets of graphs of girth at least 7. [ABSTRACT FROM AUTHOR]

The Coloring problem is to test whether a given graph can be colored with at most k colors for some given k , such that no two adjacent vertices receive the same color. The complexity of this problem on graphs that do not contain some graph H as an induced subgraph is known for each fixed graph H . A natural variant is to forbid a graph H only as a subgraph. We call such graphs strongly H -free and initiate a complexity classification of Coloring for strongly H -free graphs. We show that Coloring is NP -complete for strongly H -free graphs, even for k = 3 , when H contains a cycle, has maximum degree at least 5, or contains a connected component with two vertices of degree 4. We also give three conditions on a forest H of maximum degree at most 4 and with at most one vertex of degree 4 in each of its connected components, such that Coloring is NP -complete for strongly H -free graphs even for k = 3 . Finally, we classify the computational complexity of Coloring on strongly H -free graphs for all fixed graphs H up to seven vertices. In particular, we show that Coloring is polynomial-time solvable when H is a forest that has at most seven vertices and maximum degree at most 4. [ABSTRACT FROM AUTHOR]

Abstract: For a positive integer , an -club in a graph is a set of vertices that induces a subgraph of of diameter at most . We study a relation of clubs and cliques. For a positive integer , we say that a graph class has the -clique-power property if for every graph , every maximal clique in is an -club in . Our main combinatorial results show that both 4-chordal graphs and AT-free graphs have the -clique-power property for all . This has various algorithmic consequences. In particular we show that a maximum -club in can be computed in polynomial time when is a chordal bipartite or a strongly chordal or a distance hereditary graph. On weakly chordal graphs, we obtain a polynomial-time algorithm when is an odd integer, which is best possible as the problem is NP-hard for even values of . We complement these results by proving the NP-hardness of the problem for every fixed on 4-chordal graphs. Finally, if is an AT-free graph, we prove that the problem can be solved in polynomial time when , which gives an interesting contrast to the fact that the problem is NP-hard for on this graph class. [Copyright &y& Elsevier]

The Contractibility problem takes as input two graphs G and H, and the task is to decide whether H can be obtained from G by a sequence of edge contractions. The Induced Minor and Induced Topological Minor problems are similar, but the first allows both edge contractions and vertex deletions, whereas the latter allows only vertex deletions and vertex dissolutions. All three problems are NP-complete, even for certain fixed graphs H. We show that these problems can be solved in polynomial time for every fixed H when the input graph G is chordal. Our results can be considered tight, since these problems are known to be W[ 1]-hard on chordal graphs when parameterized by the size of H. To solve Contractibility and Induced Minor, we define and use a generalization of the classic Disjoint Paths problem, where we require the vertices of each of the k paths to be chosen from a specified set. We prove that this variant is NP-complete even when k=2, but that it is polynomial-time solvable on chordal graphs for every fixed k. Our algorithm for Induced Topological Minor is based on another generalization of Disjoint Paths called Induced Disjoint Paths, where the vertices from different paths may no longer be adjacent. We show that this problem, which is known to be NP-complete when k=2, can be solved in polynomial time on chordal graphs even when k is part of the input. Our results fit into the general framework of graph containment problems, where the aim is to decide whether a graph can be modified into another graph by a sequence of specified graph operations. Allowing combinations of the four well-known operations edge deletion, edge contraction, vertex deletion, and vertex dissolution results in the following ten containment relations: (induced) minor, (induced) topological minor, (induced) subgraph, (induced) spanning subgraph, dissolution, and contraction. Our results, combined with existing results, settle the complexity of each of the ten corresponding containment problems on chordal graphs. [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]

Abstract: The stable roommates problem with payments has as input a graph with an edge weighting and the problem is to find a stable solution. A solution is a matching M with a vector that satisfies for all and for all u unmatched in M. A solution is stable if it prevents blocking pairs, i.e., pairs of adjacent vertices u and v with , or equivalently, if the total blocking value . By pinpointing a relationship to the accessibility of the coalition structure core of matching games, we give a constructive proof for showing that every yes-instance of the stable roommates problem with payments allows a path of linear length that starts in an arbitrary unstable solution and that ends in a stable solution. This generalizes a result of Chen, Fujishige and Yang (2011) [4] for bipartite instances to general instances. We also show that the problems Blocking Pairs and Blocking Value, which are to find a solution with a minimum number of blocking pairs or a minimum total blocking value, respectively, are NP-hard. Finally, we prove that the variant of the first problem, in which the number of blocking pairs must be minimized with respect to some fixed matching, is NP-hard, whereas this variant of the second problem is polynomial-time solvable. [Copyright &y& Elsevier]