Search

A graph $G = (V,E)$ is said to be monopolar if its vertex set admits a partition $V = (C \uplus{} I)$ where $G[C]$ is a cluster graph and $I$ is an independent set in $G$. Monopolar graphs generalize both bipartite graphs and split graphs, and they have been extensively studied from both graph-theoretic and algorithmic points of view. In this work we focus on the problem MONOPOLAR RECOGNITION (MR) of deciding whether a given graph is monopolar. MR is known to be solvable in polynomial time in certain classes of graphs such as cographs and claw-free graphs, and to be NP-Hard in various restricted classes such as subcubic planar graphs. We initiate the study of exact exponential-time algorithms for MR and allied problems. We design an algorithm that solves MR in $\OhStar(1.3734^{n})$ time on input graphs with $n$ vertices. In fact we solve the more general problems MONOPOLAR EXTENSION (ME) and LIST MONOPOLAR PARTITION (LMP), which were introduced in the literature as part of the study of graph monopolarity, in $\OhStar(1.3734^{n})$ time. We also design fast parameterized algorithms for MR using two notions of distance from triviality as the parameters. Our FPT algorithms solve MR in $\OhStar(3.076^{k_{v}})$ and $\OhStar(2.253^{k_{e}})$ time, where $k_{v}$ and $k_{e}$ are, respectively, the sizes of the smallest claw-free vertex and edge deletion sets of the input graph. These results are a significant addition to the small number of FPT algorithms currently known for MR. Le and Nevries have shown that if a graph $G$ is chair-free, then an instance $(G,C')$ of ME can be solved in polynomial time for any subset $C'$ of its vertices. We significantly generalize this result; we show that we can solve instances $(G,C')$ of ME in polynomial time for arbitrary graphs $G$ and any chair-free vertex deletion set $C'$ of $G$. We believe this result could be of independent interest.

Lokshtanov et al.~[STOC 2017] introduced \emph{lossy kernelization} as a mathematical framework for quantifying the effectiveness of preprocessing algorithms in preserving approximation ratios. \emph{$\alpha$-approximate reduction rules} are a central notion of this framework. We propose that carefully crafted $\alpha$-approximate reduction rules can yield improved approximation ratios in practice, while being easy to implement as well. This is distinctly different from the (theoretical) purpose for which Lokshtanov et al. designed $\alpha$-approximate Reduction Rules. As evidence in support of this proposal we present a new 2-approximate reduction rule for the \textsc{Dominating Set} problem. This rule, when combined with an approximation algorithm for \textsc{Dominating Set}, yields significantly better approximation ratios on a variety of benchmark instances as compared to the latter algorithm alone. The central thesis of this work is that $\alpha$-approximate reduction rules can be used as a tool for designing approximation algorithms which perform better in practice. To the best of our knowledge, ours is the first exploration of the use of $\alpha$-approximate reduction rules as a design technique for practical approximation algorithms. We believe that this technique could be useful in coming up with improved approximation algorithms for other optimization problems as well.

We investigate the parameterized complexity of finding diverse sets of solutions to three fundamental combinatorial problems, two from the theory of matroids and the third from graph theory. The input to the Weighted Diverse Bases problem consists of a matroid $M$, a weight function $\omega:E(M)\to\mathbb{N}$, and integers $k\geq 1, d\geq 0$. The task is to decide if there is a collection of $k$ bases $B_{1}, \dotsc, B_{k}$ of $M$ such that the weight of the symmetric difference of any pair of these bases is at least $d$. This is a diverse variant of the classical matroid base packing problem. 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 $\omega:E\to\mathbb{N}$, and integers $k\geq 1, d\geq 0$. The task is to decide if there is a collection of $k$ common independent sets $I_{1}, \dotsc, 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$. This is motivated by the classical weighted matroid intersection problem. The input to the Diverse Perfect Matchings problem consists of a graph $G$ and integers $k\geq 1, d\geq 0$. The task is to decide if $G$ contains $k$ perfect matchings $M_{1},\dotsc,M_{k}$ such that the symmetric difference of any two of these matchings is at least $d$. We show that Weighted Diverse Bases and Weighted Diverse Common Independent Sets are both NP-hard, and derive fixed-parameter tractable (FPT) algorithms for all three problems with $(k,d)$ as the parameter.

We show that given a SM instance G as input we can find a largest collection of pairwise edge-disjoint stable matchings of G in time linear in the input size. This extends two classical results: 1. The Gale-Shapley algorithm, which can find at most two ("extreme") pairwise edge-disjoint stable matchings of G in linear time, and 2. The polynomial-time algorithm for finding a largest collection of pairwise edge-disjoint perfect matchings (without the stability requirement) in a bipartite graph, obtained by combining K\"{o}nig's characterization with Tutte's f-factor algorithm. Moreover, we also give an algorithm to enumerate all maximum-length chains of disjoint stable matchings in the lattice of stable matchings of a given instance. This algorithm takes time polynomial in the input size for enumerating each chain. We also derive the expected number of such chains in a random instance of Stable Matching., Comment: Conference: International Workshop on Graph-Theoretic Concepts in Computer Science 2021 (https://wg2021.mimuw.edu.pl)

We initiate the study of the Diverse Pair of (Maximum/ Perfect) Matchings problems which given a graph $G$ and an integer $k$, ask whether $G$ has two (maximum/perfect) matchings whose symmetric difference is at least $k$. Diverse Pair of Matchings (asking for two not necessarily maximum or perfect matchings) is NP-complete on general graphs if $k$ is part of the input, and we consider two restricted variants. First, we show that on bipartite graphs, the problem is polynomial-time solvable, and second we show that Diverse Pair of Maximum Matchings is FPT parameterized by $k$. We round off the work by showing that Diverse Pair of Matchings has a kernel on $\mathcal{O}(k^2)$ vertices., Comment: To appear at ISAAC 2020

A clique coloring of a graph is an assignment of colors to its vertices such that no maximal clique is monochromatic. We initiate the study of structural parameterizations of the Clique Coloring problem which asks whether a given graph has a clique coloring with $q$ colors. For fixed $q \ge 2$, we give an $\mathcal{O}^{\star}(q^{tw})$-time algorithm when the input graph is given together with one of its tree decompositions of width $tw$. We complement this result with a matching lower bound under the Strong Exponential Time Hypothesis. We furthermore show that (when the number of colors is unbounded) Clique Coloring is XP parameterized by clique-width.

The $r$-th iterated line graph $L^{r}(G)$ of a graph $G$ is defined by: (i) $L^{0}(G) = G$ and (ii) $L^{r}(G) = L(L^{(r- 1)}(G))$ for $r > 0$, where $L(G)$ denotes the line graph of $G$. The Hamiltonian Index $h(G)$ of $G$ is the smallest $r$ such that $L^{r}(G)$ has a Hamiltonian cycle. Checking if $h(G) = k$ is NP-hard for any fixed integer $k \geq 0$ even for subcubic graphs $G$. We study the parameterized complexity of this problem with the parameter treewidth, $tw(G)$, and show that we can find $h(G)$ in time $O*((1 + 2^{(\omega + 3)})^{tw(G)})$ where $\omega$ is the matrix multiplication exponent and the $O*$ notation hides polynomial factors in input size. The NP-hard Eulerian Steiner Subgraph problem takes as input a graph $G$ and a specified subset $K$ of terminal vertices of $G$ and asks if $G$ has an Eulerian (that is: connected, and with all vertices of even degree.) subgraph $H$ containing all the terminals. A second result (and a key ingredient of our algorithm for finding $h(G)$) in this work is an algorithm which solves Eulerian Steiner Subgraph in $O*((1 + 2^{(\omega + 3)})^{tw(G)})$ time., Comment: 46 pages

In this work, we study the $d$-Hitting Set and Feedback Vertex Set problems through the paradigm of finding diverse collections of $r$ solutions of size at most $k$ each, which has recently been introduced to the field of parameterized complexity [Baste et al., 2019]. This paradigm is aimed at addressing the loss of important side information which typically occurs during the abstraction process which models real-world problems as computational problems. We use two measures for the diversity of such a collection: the sum of all pairwise Hamming distances, and the minimum pairwise Hamming distance. We show that both problems are FPT in $k + r$ for both diversity measures. A key ingredient in our algorithms is a (problem independent) network flow formulation that, given a set of `base' solutions, computes a maximally diverse collection of solutions. We believe that this could be of independent interest., Comment: 17 pages, 3 figures

When modeling an application of practical relevance as an instance of a combinatorial problem X, we are often interested not merely in finding one optimal solution for that instance, but in finding a sufficiently diverse collection of good solutions. In this work we initiate a systematic study of diversity from the point of view of fixed-parameter tractability theory. First, we consider an intuitive notion of diversity of a collection of solutions which suits a large variety of combinatorial problems of practical interest. We then present an algorithmic framework which --automatically-- converts a tree-decomposition-based dynamic programming algorithm for a given combinatorial problem X into a dynamic programming algorithm for the diverse version of X. Surprisingly, our algorithm has a polynomial dependence on the diversity parameter., Comment: Accepted to Twenty-Ninth International Joint Conference on Artificial Intelligence, {IJCAI} 2020, 16 pages

In the \textsc{Subset Feedback Vertex Set (Subset-FVS)} problem the input is a graph $G$, a subset \(T\) of vertices of \(G\) called the `terminal' vertices, and an integer $k$. The task is to determine whether there exists a subset of vertices of cardinality at most $k$ which together intersect all cycles which pass through the terminals. \textsc{Subset-FVS} generalizes several well studied problems including \textsc{Feedback Vertex Set} and \textsc{Multiway Cut}. This problem is known to be \NP-Complete even in split graphs. Cygan et al. proved that \textsc{Subset-FVS} is fixed parameter tractable (\FPT) in general graphs when parameterized by $k$ [SIAM J. Discrete Math (2013)]. In split graphs a simple observation reduces the problem to an equivalent instance of the $3$-\textsc{Hitting Set} problem with same solution size. This directly implies, for \textsc{Subset-FVS} \emph{restricted to split graphs}, (i) an \FPT algorithm which solves the problem in $\OhStar(2.076^k)$ time \footnote{The \(\OhStar()\) notation hides polynomial factors.}% for \textsc{Subset-FVS} in Chordal % Graphs [Wahlstr\"om, Ph.D. Thesis], and (ii) a kernel of size $\mathcal{O}(k^3)$. We improve both these results for \textsc{Subset-FVS} on split graphs; we derive (i) a kernel of size $\mathcal{O}(k^2)$ which is the best possible unless $\NP \subseteq \coNP/{\sf poly}$, and (ii) an algorithm which solves the problem in time $\mathcal{O}^*(2^k)$. Our algorithm, in fact, solves \textsc{Subset-FVS} on the more general class of \emph{chordal graphs}, also in $\mathcal{O}^*(2^k)$ time.

A {\em tournament} is a directed graph $T$ such that every pair of vertices is connected by an arc. A {\em feedback vertex set} is a set $S$ of vertices in $T$ such that $T - S$ is acyclic. We consider the {\sc Feedback Vertex Set} problem in tournaments. Here the input is a tournament $T$ and a weight function $w : V(T) \rightarrow \mathbb{N}$ and the task is to find a feedback vertex set $S$ in $T$ minimizing $w(S) = \sum_{v \in S} w(v)$. We give the first polynomial time factor $2$ approximation algorithm for this problem. Assuming the Unique Games conjecture, this is the best possible approximation ratio achievable in polynomial time.

We investigate the following above-guarantee parameterization of the classical Vertex Cover problem: Given a graph $G$ and $k\in\mathbb{N}$ as input, does $G$ have a vertex cover of size at most $(2LP-MM)+k$? Here $MM$ is the size of a maximum matching of $G$, $LP$ is the value of an optimum solution to the relaxed (standard) LP for Vertex Cover on $G$, and $k$ is the parameter. Since $(2LP-MM)\geq{LP}\geq{MM}$, this is a stricter parameterization than those---namely, above-$MM$, and above-$LP$---which have been studied so far. We prove that Vertex Cover is fixed-parameter tractable for this stricter parameter $k$: We derive an algorithm which solves Vertex Cover in time $O^{*}(3^{k})$, pushing the envelope further on the parameterized tractability of Vertex Cover.

Problems of the following kind have been the focus of much recent research in the realm of parameterized complexity: Given an input graph (digraph) on $n$ vertices and a positive integer parameter $k$, find if there exist $k$ edges (arcs) whose deletion results in a graph that satisfies some specified parity constraints. In particular, when the objective is to obtain a connected graph in which all the vertices have even degrees---where the resulting graph is \emph{Eulerian}---the problem is called Undirected Eulerian Edge Deletion. The corresponding problem in digraphs where the resulting graph should be strongly connected and every vertex should have the same in-degree as its out-degree is called Directed Eulerian Edge Deletion. Cygan et al. [\emph{Algorithmica, 2014}] showed that these problems are fixed parameter tractable (FPT), and gave algorithms with the running time $2^{O(k \log k)}n^{O(1)}$. They also asked, as an open problem, whether there exist FPT algorithms which solve these problems in time $2^{O(k)}n^{O(1)}$. In this paper we answer their question in the affirmative: using the technique of computing \emph{representative families of co-graphic matroids} we design algorithms which solve these problems in time $2^{O(k)}n^{O(1)}$. The crucial insight we bring to these problems is to view the solution as an independent set of a co-graphic matroid. We believe that this view-point/approach will be useful in other problems where one of the constraints that need to be satisfied is that of connectivity.

Poljak and Turzik (Discrete Mathematics 1986) introduced the notion of {\lambda}-extendible properties of graphs as a generalization of the property of being bipartite. They showed that for any 0 < {\lambda} < 1 and {\lambda}-extendible property {\Pi}, any connected graph G on n vertices and m edges contains a spanning subgraph H in {\Pi} with at least {\lambda}m + (1-{\lambda})(n-1)/2 edges. The property of being bipartite is {\lambda}-extendible for {\lambda} = 1/2, and so the Poljak-Turzik bound generalizes the well-known Edwards-Erdos bound for Max-Cut. Other examples of {\lambda}-extendible properties include: being an acyclic oriented graph, a balanced signed graph, or a q-colorable graph for some integer q. Mnich et. al. (FSTTCS 2012) defined the closely related notion of strong {\lambda}-extendibility. They showed that the problem of finding a subgraph satisfying a given strongly {\lambda}-extendible property {\Pi} is fixed-parameter tractable (FPT) when parameterized above the Poljak-Turzik bound - does there exist a spanning subgraph H of a connected graph G such that H in {\Pi} and H has at least {\lambda}m + (1-{\lambda})(n-1)/2 + k edges? - subject to the condition that the problem is FPT on a certain simple class of graphs called almost-forests of cliques. In this paper we settle the kernelization complexity of nearly all problems parameterized above Poljak-Turzik bounds, in the affirmative. We show that these problems admit quadratic kernels (cubic when {\lambda} = 1/2), without using the assumption that the problem is FPT on almost-forests of cliques. Thus our results not only remove the technical condition of being FPT on almost-forests of cliques from previous results, but also unify and extend previously known kernelization results in this direction. Our results add to the select list of generic kernelization results known in the literature.

The input to the NP-hard Point Line Cover problem (PLC) consists of a set $P$ of $n$ points on the plane and a positive integer $k$, and the question is whether there exists a set of at most $k$ lines which pass through all points in $P$. A simple polynomial-time reduction reduces any input to one with at most $k^2$ points. We show that this is essentially tight under standard assumptions. More precisely, unless the polynomial hierarchy collapses to its third level, there is no polynomial-time algorithm that reduces every instance $(P,k)$ of PLC to an equivalent instance with $O(k^{2-\epsilon})$ points, for any $\epsilon>0$. This answers, in the negative, an open problem posed by Lokshtanov (PhD Thesis, 2009). Our proof uses the machinery for deriving lower bounds on the size of kernels developed by Dell and van Melkebeek (STOC 2010). It has two main ingredients: We first show, by reduction from Vertex Cover, that PLC---conditionally---has no kernel of total size $O(k^{2-\epsilon})$ bits. This does not directly imply the claimed lower bound on the number of points, since the best known polynomial-time encoding of a PLC instance with $n$ points requires $\omega(n^{2})$ bits. To get around this we build on work of Goodman et al. (STOC 1989) and devise an oracle communication protocol of cost $O(n\log n)$ for PLC; its main building block is a bound of $O(n^{O(n)})$ for the order types of $n$ points that are not necessarily in general position, and an explicit algorithm that enumerates all possible order types of n points. This protocol and the lower bound on total size together yield the stated lower bound on the number of points. While a number of essentially tight polynomial lower bounds on total sizes of kernels are known, our result is---to the best of our knowledge---the first to show a nontrivial lower bound for structural/secondary parameters.

Poljak and Turz\'ik (Discrete Math. 1986) introduced the notion of \lambda-extendible properties of graphs as a generalization of the property of being bipartite. They showed that for any 0<\lambda<1 and \lambda-extendible property \Pi, any connected graph G on n vertices and m edges contains a subgraph H \in {\Pi} with at least \lambda m+ (1-\lambda)/2 (n-1) edges. The property of being bipartite is 1/2-extendible, and thus this bound generalizes the Edwards-Erd\H{o}s bound for Max-Cut. We define a variant, namely strong \lambda-extendibility, to which the bound applies. For a strongly \lambda-extendible graph property \Pi, we define the parameterized Above Poljak- Turz\'ik (APT) (\Pi) problem as follows: Given a connected graph G on n vertices and m edges and an integer parameter k, does there exist a spanning subgraph H of G such that H \in {\Pi} and H has at least \lambda m + (1-\lambda)/2 (n - 1) + k edges? The parameter is k, the surplus over the number of edges guaranteed by the Poljak-Turz\'ik bound. We consider properties {\Pi} for which APT (\Pi) is fixed- parameter tractable (FPT) on graphs which are O(k) vertices away from being a graph in which each block is a clique. We show that for all such properties, APT (\Pi) is FPT for all 0<\lambda<1. Our results hold for properties of oriented graphs and graphs with edge labels. Our results generalize the result of Crowston et al. (ICALP 2012) on Max-Cut parameterized above the Edwards-Erd\H{o}s bound, and yield FPT algorithms for several graph problems parameterized above lower bounds, e.g., Max q-Colorable Subgraph problem. Our results also imply that the parameterized above-guarantee Oriented Max Acyclic Digraph problem is FPT, thus solving an open question of Raman and Saurabh (Theor. Comput. Sci. 2006)., Comment: 23 pages, no figure

Given an input graph G and an integer k, the parameterized K_4-minor cover problem asks whether there is a set S of at most k vertices whose deletion results in a K_4-minor-free graph, or equivalently in a graph of treewidth at most 2. This problem is inspired by two well-studied parameterized vertex deletion problems, Vertex Cover and Feedback Vertex Set, which can also be expressed as Treewidth-t Vertex Deletion problems: t=0 for Vertex Cover and t=1 for Feedback Vertex Set. While a single-exponential FPT algorithm has been known for a long time for \textsc{Vertex Cover}, such an algorithm for Feedback Vertex Set was devised comparatively recently. While it is known to be unlikely that Treewidth-t Vertex Deletion can be solved in time c^{o(k)}.n^{O(1)}, it was open whether the K_4-minor cover problem could be solved in single-exponential FPT time, i.e. in c^k.n^{O(1)} time. This paper answers this question in the affirmative.

We show that the dominating set problem parameterized by solution size is fixed-parameter tractable (FPT) in graphs that do not contain the claw (K(1,3)), the complete bipartite graph on four vertices where the two parts have one and three vertices, respectively) as an induced subgraph. We present an algorithm that uses 2^O(k^2)n^O(1) time and polynomial space to decide whether a claw-free graph on n vertices has a dominating set of size at most k. Note that this parameterization of dominating set is W[2]-hard on the set of all graphs, and thus is unlikely to have an FPT algorithm for graphs in general. The most general class of graphs for which an FPT algorithm was previously known for this parameterization of dominating set is the class of K(i,j)-free graphs, which exclude, for some fixed i,j, the complete bipartite graph K(i,j) as a subgraph. For i,i >= 2, the class of claw-free graphs and any class of K(i,j)-free graphs are not comparable with respect to set inclusion. We thus extend the range of graphs over which this parameterization of dominating set is known to be fixed-parameter tractable. We also show that, in some sense, it is the presence of the claw that makes this parameterization of the dominating set problem hard. More precisely, we show that for any t ?>= 4, the dominating set problem parameterized by the solution size is W[2]-hard in graphs that exclude the t-claw K(1,t) as an induced subgraph. Our arguments also imply that the related connected dominating set and dominating clique problems are W[2]-hard in these graph classes. Finally, we show that for any t, the clique problem parameterized by solution size, which is W[1]-hard on general graphs, is FPT in t-claw-free graphs. Our results add to the small and growing collection of FPT results for graph classes defined by excluded subgraphs, rather than by excluded minors.

We study a general class of problems called F-deletion problems. In an F-deletion problem, we are asked whether a subset of at most $k$ vertices can be deleted from a graph $G$ such that the resulting graph does not contain as a minor any graph from the family F of forbidden minors. We obtain a number of algorithmic results on the F-deletion problem when F contains a planar graph. We give (1) a linear vertex kernel on graphs excluding $t$-claw $K_{1,t}$, the star with $t$ leves, as an induced subgraph, where $t$ is a fixed integer. (2) an approximation algorithm achieving an approximation ratio of $O(\log^{3/2} OPT)$, where $OPT$ is the size of an optimal solution on general undirected graphs. Finally, we obtain polynomial kernels for the case when F contains graph $\theta_c$ as a minor for a fixed integer $c$. The graph $\theta_c$ consists of two vertices connected by $c$ parallel edges. Even though this may appear to be a very restricted class of problems it already encompasses well-studied problems such as {\sc Vertex Cover}, {\sc Feedback Vertex Set} and Diamond Hitting Set. The generic kernelization algorithm is based on a non-trivial application of protrusion techniques, previously used only for problems on topological graph classes.

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., Comment: Full version of an extended abstract accepted for publication in the proceedings of WG 2010. 18 pages, 1 figure

We study the recently introduced Connected Feedback Vertex Set (CFVS) problem from the view-point of parameterized algorithms. CFVS is the connected variant of the classical Feedback Vertex Set problem and is defined as follows: given a graph G=(V,E) and an integer k, decide whether there exists a subset F of V, of size at most k, such that G[V F] is a forest and G[F] is connected. We show that Connected Feedback Vertex Set can be solved in time $O(2^{O(k)}n^{O(1)})$ on general graphs and in time $O(2^{O(\sqrt{k}\log k)}n^{O(1)})$ on graphs excluding a fixed graph H as a minor. Our result on general undirected graphs uses as subroutine, a parameterized algorithm for Group Steiner Tree, a well studied variant of Steiner Tree. We find the algorithm for Group Steiner Tree of independent interest and believe that it will be useful for obtaining parameterized algorithms for other connectivity problems., Comment: 12 pages

We show that the k-Dominating Set problem is fixed parameter tractable (FPT) and has a polynomial kernel for any class of graphs that exclude K_{i,j} as a subgraph, for any fixed i, j >= 1. This strictly includes every class of graphs for which this problem has been previously shown to have FPT algorithms and/or polynomial kernels. In particular, our result implies that the problem restricted to bounded- degenerate graphs has a polynomial kernel, solving an open problem posed by Alon and Gutner., Comment: 12 pages, 1 figure, 1 table