Search

We design an algorithm that generates an $n$-vertex unlabeled chordal graph uniformly at random in expected polynomial time. Along the way, we develop the following two results: (1) an $\mathsf{FPT}$ algorithm for counting and sampling labeled chordal graphs with a given automorphism $\pi$, parameterized by the number of moved points of $\pi$, and (2) a proof that the probability that a random $n$-vertex labeled chordal graph has a given automorphism $\pi\in S_n$ is at most $1/2^{c\max\{\mu^2,n\}}$, where $\mu$ is the number of moved points of $\pi$ and $c$ is a constant. Our algorithm for sampling unlabeled chordal graphs calls the aforementioned $\mathsf{FPT}$ algorithm as a black box with potentially large values of the parameter $\mu$, but the probability of calling this algorithm with a large value of $\mu$ is exponentially small., Comment: Accepted for publication at STACS 2025 (International Symposium on Theoretical Aspects of Computer Science); 41 pages

We prove a robust contraction decomposition theorem for $H$-minor-free graphs, which states that given an $H$-minor-free graph $G$ and an integer $p$, one can partition in polynomial time the vertices of $G$ into $p$ sets $Z_1,\dots,Z_p$ such that $\operatorname{tw}(G/(Z_i \setminus Z')) = O(p + |Z'|)$ for all $i \in [p]$ and $Z' \subseteq Z_i$. Here, $\operatorname{tw}(\cdot)$ denotes the treewidth of a graph and $G/(Z_i \setminus Z')$ denotes the graph obtained from $G$ by contracting all edges with both endpoints in $Z_i \setminus Z'$. Our result generalizes earlier results by Klein [SICOMP 2008] and Demaine et al. [STOC 2011] based on partitioning $E(G)$, and some recent theorems for planar graphs by Marx et al. [SODA 2022], for bounded-genus graphs (more generally, almost-embeddable graphs) by Bandyapadhyay et al. [SODA 2022], and for unit-disk graphs by Bandyapadhyay et al. [SoCG 2022]. The robust contraction decomposition theorem directly results in parameterized algorithms with running time $2^{\widetilde{O}(\sqrt{k})} \cdot n^{O(1)}$ or $n^{O(\sqrt{k})}$ for every vertex/edge deletion problems on $H$-minor-free graphs that can be formulated as Permutation CSP Deletion or 2-Conn Permutation CSP Deletion. Consequently, we obtain the first subexponential-time parameterized algorithms for Subset Feedback Vertex Set, Subset Odd Cycle Transversal, Subset Group Feedback Vertex Set, 2-Conn Component Order Connectivity on $H$-minor-free graphs. For other problems which already have subexponential-time parameterized algorithms on $H$-minor-free graphs (e.g., Odd Cycle Transversal, Vertex Multiway Cut, Vertex Multicut, etc.), our theorem gives much simpler algorithms of the same running time., Comment: 50 pages, 2 figures

A {\em bipartite tournament} is a directed graph $T:=(A \cup B, E)$ such that every pair of vertices $(a,b), a\in A,b\in B$ are connected by an arc, and no arc connects two vertices of $A$ or two vertices of $B$. A {\em feedback vertex set} is a set $S$ of vertices in $T$ such that $T - S$ is acyclic. In this article we consider the {\sc Feedback Vertex Set} problem in bipartite tournaments. Here the input is a bipartite tournament $T$ on $n$ vertices together with an integer $k$, and the task is to determine whether $T$ has a feedback vertex set of size at most $k$. We give a new algorithm for {\sc Feedback Vertex Set in Bipartite Tournaments}. The running time of our algorithm is upper-bounded by $O(1.6181^k + n^{O(1)})$, improving over the previously best known algorithm with running time $2^kk^{O(1)} + n^{O(1)}$ [Hsiao, ISAAC 2011]. As a by-product, we also obtain the fastest currently known exact exponential-time algorithm for the problem, with running time $O(1.3820^n)$., Comment: 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016)

The \textsc{Capacitated $d$-Hitting Set} problem involves a universe $U$ with a capacity function $\mathsf{cap}: U \rightarrow \mathbb{N}$ and a collection $\mathcal{A}$ of subsets of $U$, each of size at most $d$. The goal is to find a minimum subset $S \subseteq U$ and an assignment $\phi : \mathcal{A} \rightarrow S$ such that for every $A \in \mathcal{A}$, $\phi(A) \in A$, and for each $x \in U$, $|\phi^{-1}(x)| \leq \mathsf{cap}(x)$. For $d=2$, this is known as \textsc{Capacitated Vertex Cover}. In the weighted variant, each element of $U$ has a positive integer weight, with the objective of finding a minimum-weight capacitated hitting set. Chuzhoy and Naor [SICOMP 2006] provided a factor-3 approximation for \textsc{Capacitated Vertex Cover} and showed that the weighted case lacks an $o(\log n)$-approximation unless $P=NP$. Kao and Wong [SODA 2017] later independently achieved a $d$-approximation for \textsc{Capacitated $d$-Hitting Set}, with no $d - \epsilon$ improvements possible under the Unique Games Conjecture. Our main result is a parameterized approximation algorithm with runtime $\left(\frac{k}{\epsilon}\right)^k 2^{k^{O(kd)}}(|U|+|\mathcal{A}|)^{O(1)}$ that either concludes no solution of size $\leq k$ exists or finds $S$ of size $\leq 4/3 \cdot k$ and weight at most $2+\epsilon$ times the minimum weight for solutions of size $\leq k$. We further show that no FPT-approximation with factor $c > 1$ exists for unweighted \textsc{Capacitated $d$-Hitting Set} with $d \geq 3$, nor with factor $2 - \epsilon$ for the weighted version, assuming the Exponential Time Hypothesis. These results extend to \textsc{Capacitated Vertex Cover} in multigraphs. Additionally, a variant of multi-dimensional \textsc{Knapsack} is shown hard to FPT-approximate within $2 - \epsilon$., Comment: Accepted to SODA 2025, Abstract is shortened due to space requirement

In this article we show that Maximum Partial List H-Coloring is polynomial-time solvable on P_5-free graphs for every fixed graph H. In particular, this implies that Maximum k-Colorable Subgraph is polynomial-time solvable on P_5-free graphs. This answers an open question from Agrawal, Lima, Lokshtanov, Saurabh & Sharma [SODA 2024]. This also improves the $n^{\omega(G)}$-time algorithm for Maximum Partial H-Coloring by Chudnovsky, King, Pilipczuk, Rz\k{a}\.{z}ewski & Spirkl [SIDMA 2021] to polynomial-time algorithm.

The classic greedy coloring (first-fit) algorithm considers the vertices of an input graph $G$ in a given order and assigns the first available color to each vertex $v$ in $G$. In the {\sc Grundy Coloring} problem, the task is to find an ordering of the vertices that will force the greedy algorithm to use as many colors as possible. In the {\sc Partial Grundy Coloring}, the task is also to color the graph using as many colors as possible. This time, however, we may select both the ordering in which the vertices are considered and which color to assign the vertex. The only constraint is that the color assigned to a vertex $v$ is a color previously used for another vertex if such a color is available. Whether {\sc Grundy Coloring} and {\sc Partial Grundy Coloring} admit fixed-parameter tractable (FPT) algorithms, algorithms with running time $f(k)n^{\OO(1)}$, where $k$ is the number of colors, was posed as an open problem by Zaker and by Effantin et al., respectively. Recently, Aboulker et al. (STACS 2020 and Algorithmica 2022) resolved the question for \Grundycol\ in the negative by showing that the problem is W[1]-hard. For {\sc Partial Grundy Coloring}, they obtain an FPT algorithm on graphs that do not contain $K_{i,j}$ as a subgraph (a.k.a. $K_{i,j}$-free graphs). Aboulker et al.~re-iterate the question of whether there exists an FPT algorithm for {\sc Partial Grundy Coloring} on general graphs and also asks whether {\sc Grundy Coloring} admits an FPT algorithm on $K_{i,j}$-free graphs. We give FPT algorithms for {\sc Partial Grundy Coloring} on general graphs and for {\sc Grundy Coloring} on $K_{i,j}$-free graphs, resolving both the questions in the affirmative. We believe that our new structural theorems for partial Grundy coloring and ``representative-family'' like sets for $K_{i,j}$-free graphs that we use in obtaining our results may have wider algorithmic applications.

In the Hedge Cut problem, the edges of a graph are partitioned into groups called hedges, and the question is what is the minimum number of hedges to delete to disconnect the graph. Ghaffari, Karger, and Panigrahi [SODA 2017] showed that Hedge Cut can be solved in quasipolynomial-time, raising the hope for a polynomial time algorithm. Jaffke, Lima, Masar\'ik, Pilipczuk, and Souza [SODA 2023] complemented this result by showing that assuming the Exponential Time Hypothesis (ETH), no polynomial-time algorithm exists. In this paper, we show that Hedge Cut is fixed-parameter tractable parameterized by the solution size $\ell$ by providing an algorithm with running time $\binom{O(\log n) + \ell}{\ell} \cdot m^{O(1)}$, which can be upper bounded by $c^{\ell} \cdot (n+m)^{O(1)}$ for any constant $c>1$. This running time captures at the same time the fact that the problem is quasipolynomial-time solvable, and that it is fixed-parameter tractable parameterized by $\ell$. We further generalize this algorithm to an algorithm with running time $\binom{O(k \log n) + \ell}{\ell} \cdot n^{O(k)} \cdot m^{O(1)}$ for Hedge $k$-Cut., Comment: 12 pages, 1 figure, to appear in SODA 2025

We give two new approximation algorithms to compute the fractional hypertree width of an input hypergraph. The first algorithm takes as input $n$-vertex $m$-edge hypergraph $H$ of fractional hypertree width at most $\omega$, runs in polynomial time and produces a tree decomposition of $H$ of fractional hypertree width $O(\omega \log n \log \omega)$. As an immediate corollary this yields polynomial time $O(\log^2 n \log \omega)$-approximation algorithms for (generalized) hypertree width as well. To the best of our knowledge our algorithm is the first non-trivial polynomial-time approximation algorithm for fractional hypertree width and (generalized) hypertree width, as opposed to algorithms that run in polynomial time only when $\omega$ is considered a constant. For hypergraphs with the bounded intersection property we get better bounds, comparable with that recent algorithm of Lanzinger and Razgon [STACS 2024]. The second algorithm runs in time $n^{\omega}m^{O(1)}$ and produces a tree decomposition of $H$ of fractional hypertree width $O(\omega \log^2 \omega)$. This significantly improves over the $(n+m)^{O(\omega^3)}$ time algorithm of Marx [ACM TALG 2010], which produces a tree decomposition of fractional hypertree width $O(\omega^3)$, both in terms of running time and the approximation ratio. Our main technical contribution, and the key insight behind both algorithms, is a variant of the classic Menger's Theorem for clique separators in graphs: For every graph $G$, vertex sets $A$ and $B$, family ${\cal F}$ of cliques in $G$, and positive rational $f$, either there exists a sub-family of $O(f \cdot \log^2 n)$ cliques in ${\cal F}$ whose union separates $A$ from $B$, or there exist $f \cdot \log |{\cal F}|$ paths from $A$ to $B$ such that no clique in ${\cal F}$ intersects more than $\log |{\cal F}|$ paths., Comment: 28 pages, 1 figure, preliminary version accepted at FOCS 2024

For a finite set $\mathcal{F}$ of graphs, the $\mathcal{F}$-Hitting problem aims to compute, for a given graph $G$ (taken from some graph class $\mathcal{G}$) of $n$ vertices (and $m$ edges) and a parameter $k\in\mathbb{N}$, a set $S$ of vertices in $G$ such that $|S|\leq k$ and $G-S$ does not contain any subgraph isomorphic to a graph in $\mathcal{F}$. As a generic problem, $\mathcal{F}$-Hitting subsumes many fundamental vertex-deletion problems that are well-studied in the literature. The $\mathcal{F}$-Hitting problem admits a simple branching algorithm with running time $2^{O(k)}\cdot n^{O(1)}$, while it cannot be solved in $2^{o(k)}\cdot n^{O(1)}$ time on general graphs assuming the ETH. In this paper, we establish a general framework to design subexponential parameterized algorithms for the $\mathcal{F}$-Hitting problem on a broad family of graph classes. Specifically, our framework yields algorithms that solve $\mathcal{F}$-Hitting with running time $2^{O(k^c)}\cdot n+O(m)$ for a constant $c<1$ on any graph class $\mathcal{G}$ that admits balanced separators whose size is (strongly) sublinear in the number of vertices and polynomial in the size of a maximum clique. Examples include all graph classes of polynomial expansion and many important classes of geometric intersection graphs. Our algorithms also apply to the \textit{weighted} version of $\mathcal{F}$-Hitting, where each vertex of $G$ has a weight and the goal is to compute the set $S$ with a minimum weight that satisfies the desired conditions. The core of our framework is an intricate subexponential branching algorithm that reduces an instance of $\mathcal{F}$-Hitting (on the aforementioned graph classes) to $2^{O(k^c)}$ general hitting-set instances, where the Gaifman graph of each instance has treewidth $O(k^c)$, for some constant $c<1$ depending on $\mathcal{F}$ and the graph class.

In a disk graph, every vertex corresponds to a disk in $\mathbb{R}^2$ and two vertices are connected by an edge whenever the two corresponding disks intersect. Disk graphs form an important class of geometric intersection graphs, which generalizes both planar graphs and unit-disk graphs. We study a fundamental optimization problem in algorithmic graph theory, Bipartization (also known as Odd Cycle Transversal), on the class of disk graphs. The goal of Bipartization is to delete a minimum number of vertices from the input graph such that the resulting graph is bipartite. A folklore (polynomial-time) $3$-approximation algorithm for Bipartization on disk graphs follows from the classical framework of Goemans and Williamson [Combinatorica'98] for cycle-hitting problems. For over two decades, this result has remained the best known approximation for the problem (in fact, even for Bipartization on unit-disk graphs). In this paper, we achieve the first improvement upon this result, by giving a $(3-\alpha)$-approximation algorithm for Bipartization on disk graphs, for some constant $\alpha>0$. Our algorithm directly generalizes to the broader class of pseudo-disk graphs. Furthermore, our algorithm is robust in the sense that it does not require a geometric realization of the input graph to be given., Comment: In APPROX'24

We prove that the tree independence number of every even-hole-free graph is at most polylogarithmic in its number of vertices. More explicitly, we prove that there exists a constant c>0 such that for every integer n>1 every n-vertex even-hole-free graph has a tree decomposition where each bag has stability (independence) number at most c log^10 n. This implies that the Maximum Weight Independent Set problem, as well as several other natural algorithmic problems that are known to be NP-hard in general, can be solved in quasi-polynomial time if the input graph is even-hole-free.

Classical work on metric space based committee selection problem interprets distance as ``near is better''. In this work, motivated by real-life situations, we interpret distance as ``far is better''. Formally stated, we initiate the study of ``obnoxious'' committee scoring rules when the voters' preferences are expressed via a metric space. To this end, we propose a model where large distances imply high satisfaction and study the egalitarian avatar of the well-known Chamberlin-Courant voting rule and some of its generalizations. For a given integer value $1 \le \lambda \le k$, the committee size k, a voter derives satisfaction from only the $\lambda$-th favorite committee member; the goal is to maximize the satisfaction of the least satisfied voter. For the special case of $\lambda = 1$, this yields the egalitarian Chamberlin-Courant rule. In this paper, we consider general metric space and the special case of a $d$-dimensional Euclidean space. We show that when $\lambda$ is $1$ and $k$, the problem is polynomial-time solvable in $\mathbb{R}^2$ and general metric space, respectively. However, for $\lambda = k-1$, it is NP-hard even in $\mathbb{R}^2$. Thus, we have ``double-dichotomy'' in $\mathbb{R}^2$ with respect to the value of {\lambda}, where the extreme cases are solvable in polynomial time but an intermediate case is NP-hard. Furthermore, this phenomenon appears to be ``tight'' for $\mathbb{R}^2$ because the problem is NP-hard for general metric space, even for $\lambda=1$. Consequently, we are motivated to explore the problem in the realm of (parameterized) approximation algorithms and obtain positive results. Interestingly, we note that this generalization of Chamberlin-Courant rules encodes practical constraints that are relevant to solutions for certain facility locations.

A three-path-configuration is a graph consisting of three pairwise internally-disjoint paths the union of every two of which is an induced cycle of length at least four. A graph is 3PC-free if no induced subgraph of it is a three-path-configuration. We prove that 3PC-free graphs have poly-logarithmic tree-independence number. More explicitly, we show that there exists a constant $c$ such that every $n$-vertex 3PC-free graph graph has a tree decomposition in which every bag has stability number at most $c (\log n)^2$. This implies that the Maximum Weight Independent Set problem, as well as several other natural algorithmic problems, that are known to be NP-hard in general, can be solved in quasi-polynomial time if the input graph is 3PC-free.

In MaxSAT with Cardinality Constraint problem (CC-MaxSAT), we are given a CNF-formula $\Phi$, and $k \ge 0$, and the goal is to find an assignment $\beta$ with at most $k$ variables set to true (also called a weight $k$-assignment) such that the number of clauses satisfied by $\beta$ is maximized. MaxCov can be seen as a special case of CC-MaxSAT, where the formula $\Phi$ is monotone, i.e., does not contain any negative literals. CC-MaxSAT and MaxCov are extremely well-studied problems in the approximation algorithms as well as parameterized complexity literature. Our first contribution is that the two problems are equivalent to each other in the context of FPT-Approximation parameterized by $k$ (approximation is in terms of number of clauses satisfied/elements covered). We give a randomized reduction from CC-MaxSAT to MaxCov in time $O(1/\epsilon)^{k} \cdot (m+n)^{O(1)}$ that preserves the approximation guarantee up to a factor of $1-\epsilon$. Furthermore, this reduction also works in the presence of fairness and matroid constraints. Armed with this reduction, we focus on designing FPT-Approximation schemes (FPT-ASes) for MaxCov and its generalizations. Our algorithms are based on a novel combination of a variety of ideas, including a carefully designed probability distribution that exploits sparse coverage functions. These algorithms substantially generalize the results in Jain et al. [SODA 2023] for CC-MaxSAT and MaxCov for $K_{d,d}$-free set systems (i.e., no $d$ sets share $d$ elements), as well as a recent FPT-AS for Matroid-Constrained MaxCov by Sellier [ESA 2023] for frequency-$d$ set systems., Comment: Abstract shortened due to arxiv restrictions

We prove that for every integer $t\geq 1$ there exists an integer $c_t\geq 1$ such that every $n$-vertex even-hole-free graph with no clique of size $t$ has treewidth at most $c_t\log{n}$. This resolves a conjecture of Sintiari and Trotignon, who also proved that the logarithmic bound is asymptotically best possible. It follows that several \textsf{NP}-hard problems such as \textsc{Stable Set}, \textsc{Vertex Cover}, \textsc{Dominating Set} and \textsc{Coloring} admit polynomial-time algorithms on this class of graphs. As a consequence, for every positive integer $r$, $r$-{\sc Coloring} can be solved in polynomial time on even-hole-free graphs without any assumptions on clique size. As part of the proof, we show that there is an integer $d$ such that every even-hole-free graph has a balanced separator which is contained in the (closed) neighborhood of at most $d$ vertices. This is of independent interest; for instance, it implies the existence of efficient approximation algorithms for certain \textsf{NP}-hard problems while restricted to the class of all even-hole-free graphs., Comment: arXiv admin note: text overlap with arXiv:2307.13684

An independent set in a graph G is a set of pairwise non-adjacent vertices. A graph $G$ is bipartite if its vertex set can be partitioned into two independent sets. In the Odd Cycle Transversal problem, the input is a graph $G$ along with a weight function $w$ associating a rational weight with each vertex, and the task is to find a smallest weight vertex subset $S$ in $G$ such that $G - S$ is bipartite; the weight of $S$, $w(S) = \sum_{v\in S} w(v)$. We show that Odd Cycle Transversal is polynomial-time solvable on graphs excluding $P_5$ (a path on five vertices) as an induced subgraph. The problem was previously known to be polynomial-time solvable on $P_4$-free graphs and NP-hard on $P_6$-free graphs [Dabrowski, Feghali, Johnson, Paesani, Paulusma and Rz\k{a}\.zewski, Algorithmica 2020]. Bonamy, Dabrowski, Feghali, Johnson and Paulusma [Algorithmica 2019] posed the existence of a polynomial-time algorithm on $P_5$-free graphs as an open problem, this was later re-stated by Rz\k{a}\.zewski [Dagstuhl Reports, 9(6): 2019] and by Chudnovsky, King, Pilipczuk, Rz\k{a}\.zewski, and Spirkl [SIDMA 2021], who gave an algorithm with running time $n^{O(\sqrt{n})}$.

In the Euclidean Bottleneck Steiner Tree problem, the input consists of a set of $n$ points in $\mathbb{R}^2$ called terminals and a parameter $k$, and the goal is to compute a Steiner tree that spans all the terminals and contains at most $k$ points of $\mathbb{R}^2$ as Steiner points such that the maximum edge-length of the Steiner tree is minimized, where the length of a tree edge is the Euclidean distance between its two endpoints. The problem is well-studied and is known to be NP-hard. In this paper, we give a $k^{O(k)} n^{O(1)}$-time algorithm for Euclidean Bottleneck Steiner Tree, which implies that the problem is fixed-parameter tractable (FPT). This settles an open question explicitly asked by Bae et al. [Algorithmica, 2011], who showed that the $\ell_1$ and $\ell_{\infty}$ variants of the problem are FPT. Our approach can be generalized to the problem with $\ell_p$ metric for any rational $1 \le p \le \infty$, or even other metrics on $\mathbb{R}^2$., Comment: In SODA'24

Let $A$ and $B$ be sets of vertices in a graph $G$. Menger's theorem states that for every positive integer $k$, either there exists a collection of $k$ vertex-disjoint paths between $A$ and $B$, or $A$ can be separated from $B$ by a set of at most $k-1$ vertices. Let $\Delta$ be the maximum degree of $G$. We show that there exists a function $f(\Delta) = (\Delta+1)^{\Delta^2+1}$, so that for every positive integer $k$, either there exists a collection of $k$ vertex-disjoint and pairwise anticomplete paths between $A$ and $B$, or $A$ can be separated from $B$ by a set of at most $k \cdot f(\Delta)$ vertices. We also show that the result can be generalized from bounded-degree graphs to graphs excluding a topological minor. On the negative side, we show that no such relation holds on graphs that have degeneracy 2 and arbitrarily large girth, even when $k = 2$. Similar results were obtained independently and concurrently by Hendrey, Norin, Steiner, and Turcotte [arXiv:2309.07905]., Comment: 9 pages

An independent set in a graph $G$ is a set $S$ of pairwise non-adjacent vertices in $G$. A family $\mathcal{F}$ of independent sets in $G$ is called a $k$-independence covering family if for every independent set $I$ in $G$ of size at most $k$, there exists an $S \in \mathcal{F}$ such that $I \subseteq S$. Lokshtanov et al. [ACM Transactions on Algorithms, 2018] showed that graphs of degeneracy $d$ admit $k$-independence covering families of size $\binom{k(d+1)}{k} \cdot 2^{o(kd)} \cdot \log n$, and used this result to design efficient parameterized algorithms for a number of problems, including STABLE ODD CYCLE TRANSVERSAL and STABLE MULTICUT. In light of the results of Lokshtanov et al. it is quite natural to ask whether even more general families of graphs admit $k$-independence covering families of size $f(k)n^{O(1)}$. Graphs that exclude a complete bipartite graph $K_{d+1,d+1}$ with $d+1$ vertices on both sides as a subgraph, called $K_{d+1,d+1}$-free graphs, are a frequently considered generalization of $d$-degenerate graphs. This motivates the question whether $K_{d,d}$-free graphs admit $k$-independence covering families of size $f(k,d)n^{O(1)}$. Our main result is a resounding "no" to this question -- specifically we prove that even $K_{2,2}$-free graphs (or equivalently $C_4$-free graphs) do not admit $k$-independence covering families of size $f(k)n^{\frac{k}{4}-\epsilon}$., Comment: 8 pages, 1 figure

In the Minimum Bisection problem, input is a graph $G$ and the goal is to partition the vertex set into two parts $A$ and $B$, such that $||A|-|B|| \le 1$ and the number $k$ of edges between $A$ and $B$ is minimized. This problem can be viewed as a clustering problem where edges represent similarity, and the task is to partition the vertices into two equally sized clusters, while minimizing the number of pairs of similar objects that end up in different clusters. In this paper, we initiate the study of a fair version of Minimum Bisection. In this problem, the vertices of the graph are colored using one of $c \ge 1$ colors. The goal is to find a bisection $(A, B)$ with at most $k$ edges between the parts, such that for each color $i\in [c]$, $A$ has exactly $r_i$ vertices of color $i$. We first show that Fair Bisection is $W$[1]-hard parameterized by $c$ even when $k = 0$. On the other hand, our main technical contribution shows that is that this hardness result is simply a consequence of the very strict requirement that each color class $i$ has {\em exactly} $r_i$ vertices in $A$. In particular, we give an $f(k,c,\epsilon)n^{O(1)}$ time algorithm that finds a balanced partition $(A, B)$ with at most $k$ edges between them, such that for each color $i\in [c]$, there are at most $(1\pm \epsilon)r_i$ vertices of color $i$ in $A$. Our approximation algorithm is best viewed as a proof of concept that the technique introduced by [Lampis, ICALP '18] for obtaining FPT-approximation algorithms for problems of bounded tree-width or clique-width can be efficiently exploited even on graphs of unbounded width. The key insight is that the technique of Lampis is applicable on tree decompositions with unbreakable bags (as introduced in [Cygan et al., SIAM Journal on Computing '14]). Along the way, we also derive a combinatorial result regarding tree decompositions of graphs., Comment: Full version of ESA 2023 paper. Abstract shortened to meet the character limit

We present the first polynomial-time algorithm to exactly compute the number of labeled chordal graphs on $n$ vertices. Our algorithm solves a more general problem: given $n$ and $\omega$ as input, it computes the number of $\omega$-colorable labeled chordal graphs on $n$ vertices, using $O(n^7)$ arithmetic operations. A standard sampling-to-counting reduction then yields a polynomial-time exact sampler that generates an $\omega$-colorable labeled chordal graph on $n$ vertices uniformly at random. Our counting algorithm improves upon the previous best result by Wormald (1985), which computes the number of labeled chordal graphs on $n$ vertices in time exponential in $n$. An implementation of the polynomial-time counting algorithm gives the number of labeled chordal graphs on up to $30$ vertices in less than three minutes on a standard desktop computer. Previously, the number of labeled chordal graphs was only known for graphs on up to $15$ vertices. In addition, we design two approximation algorithms: (1) an approximate counting algorithm that computes a $(1\pm\varepsilon)$-approximation of the number of $n$-vertex labeled chordal graphs, and (2) an approximate sampling algorithm that generates a random labeled chordal graph according to a distribution whose total variation distance from the uniform distribution is at most $\varepsilon$. The approximate counting algorithm runs in $O(n^3\log{n}\log^7(1/\varepsilon))$ time, and the approximate sampling algorithm runs in $O(n^3\log{n}\log^7(1/\varepsilon))$ expected time., Comment: Accepted for publication at ESA 2023 (European Symposium on Algorithms); 52 pages, 4 figures

We re-visit the complexity of kernelization for the $d$-Hitting Set problem. This is a classic problem in Parameterized Complexity, which encompasses several other of the most well-studied problems in this field, such as Vertex Cover, Feedback Vertex Set in Tournaments (FVST) and Cluster Vertex Deletion (CVD). In fact, $d$-Hitting Set encompasses any deletion problem to a hereditary property that can be characterized by a finite set of forbidden induced subgraphs. With respect to bit size, the kernelization complexity of $d$-Hitting Set is essentially settled: there exists a kernel with $O(k^d)$ bits ($O(k^d)$ sets and $O(k^{d-1})$ elements) and this it tight by the result of Dell and van Melkebeek [STOC 2010, JACM 2014]. Still, the question of whether there exists a kernel for $d$-Hitting Set with fewer elements has remained one of the most major open problems~in~Kernelization. In this paper, we first show that if we allow the kernelization to be lossy with a qualitatively better loss than the best possible approximation ratio of polynomial time approximation algorithms, then one can obtain kernels where the number of elements is linear for every fixed $d$. Further, based on this, we present our main result: we show that there exist approximate Turing kernelizations for $d$-Hitting Set that even beat the established bit-size lower bounds for exact kernelizations -- in fact, we use a constant number of oracle calls, each with ``near linear'' ($O(k^{1+\epsilon})$) bit size, that is, almost the best one could hope for. Lastly, for two special cases of implicit 3-Hitting set, namely, FVST and CVD, we obtain the ``best of both worlds'' type of results -- $(1+\epsilon)$-approximate kernelizations with a linear number of vertices. In terms of size, this substantially improves the exact kernels of Fomin et al. [SODA 2018, TALG 2019], with simpler arguments., Comment: Accepted to ESA'23

A graph $G$ contains a graph $H$ as an induced minor if $H$ can be obtained from $G$ by vertex deletions and edge contractions. The class of $H$-induced-minor-free graphs generalizes the class of $H$-minor-free graphs, but unlike $H$-minor-free graphs, it can contain dense graphs. We show that if an $n$-vertex $m$-edge graph $G$ does not contain a graph $H$ as an induced minor, then it has a balanced vertex separator of size $O_{H}(\sqrt{m})$, where the $O_{H}(\cdot)$-notation hides factors depending on $H$. More precisely, our upper bound for the size of the balanced separator is $O(\min(|V(H)|^2, \log n) \cdot \sqrt{|V(H)|+|E(H)|} \cdot \sqrt{m})$. We give an algorithm for finding either an induced minor model of $H$ in $G$ or such a separator in randomized polynomial-time. We apply this to obtain subexponential $2^{O_{H}(n^{2/3} \log n)}$ time algorithms on $H$-induced-minor-free graphs for a large class of problems including maximum independent set, minimum feedback vertex set, 3-coloring, and planarization. For graphs $H$ where every edge is incident to a vertex of degree at most 2, our results imply a $2^{O_{H}(n^{2/3} \log n)}$ time algorithm for testing if $G$ contains $H$ as an induced minor. Our second main result is that there exists a fixed tree $T$, so that there is no $2^{o(n/\log^3 n)}$ time algorithm for testing if a given $n$-vertex graph contains $T$ as an induced minor unless the Exponential Time Hypothesis (ETH) fails. Our reduction also gives NP-hardness, which solves an open problem asked by Fellows, Kratochv\'il, Middendorf, and Pfeiffer [Algorithmica, 1995], who asked if there exists a fixed planar graph $H$ so that testing for $H$ as an induced minor is NP-hard., Comment: 34 pages

We introduce a new framework for the analysis of preprocessing routines for parameterized counting problems. Existing frameworks that encapsulate parameterized counting problems permit the usage of exponential (rather than polynomial) time either explicitly or by implicitly reducing the counting problems to enumeration problems. Thus, our framework is the only one in the spirit of classic kernelization (as well as lossy kernelization). Specifically, we define a compression of a counting problem $P$ into a counting problem $Q$ as a pair of polynomial-time procedures: $\mathsf{reduce}$ and $\mathsf{lift}$. Given an instance of $P$, $\mathsf{reduce}$ outputs an instance of $Q$ whose size is bounded by a function $f$ of the parameter, and given the number of solutions to the instance of $Q$, $\mathsf{lift}$ outputs the number of solutions to the instance of $P$. When $P=Q$, compression is termed kernelization, and when $f$ is polynomial, compression is termed polynomial compression. Our technical (and other conceptual) contributions concern both upper bounds and lower bounds.

The streaming model was introduced to parameterized complexity independently by Fafianie and Kratsch [MFCS14] and by Chitnis, Cormode, Hajiaghayi and Monemizadeh [SODA15]. Subsequently, it was broadened by Chitnis, Cormode, Esfandiari, Hajiaghayi and Monemizadeh [SPAA15] and by Chitnis, Cormode, Esfandiari, Hajiaghayi, McGregor, Monemizadeh and Vorotnikova [SODA16]. Despite its strong motivation, the applicability of the streaming model to central problems in parameterized complexity has remained, for almost a decade, quite limited. Indeed, due to simple $\Omega(n)$-space lower bounds for many of these problems, the $k^{O(1)}\cdot {\rm polylog}(n)$-space requirement in the model is too strict. Thus, we explore {\em semi-streaming} algorithms for parameterized graph problems, and present the first systematic study of this topic. Crucially, we aim to construct succinct representations of the input on which optimal post-processing time complexity can be achieved. - We devise meta-theorems specifically designed for parameterized streaming and demonstrate their applicability by obtaining the first $k^{O(1)}\cdot n\cdot {\rm polylog}(n)$-space streaming algorithms for well-studied problems such as Feedback Vertex Set on Tournaments, Cluster Vertex Deletion, Proper Interval Vertex Deletion and Block Vertex Deletion. In the process, we demonstrate a fundamental connection between semi-streaming algorithms for recognizing graphs in a graph class H and semi-streaming algorithms for the problem of vertex deletion into H. - We present an algorithmic machinery for obtaining streaming algorithms for cut problems and exemplify this by giving the first $k^{O(1)}\cdot n\cdot {\rm polylog}(n)$-space streaming algorithms for Graph Bipartitization, Multiway Cut and Subset Feedback Vertex Set.

We show that the \textsc{Maximum Weight Independent Set} problem (\textsc{MWIS}) can be solved in quasi-polynomial time on $H$-free graphs (graphs excluding a fixed graph $H$ as an induced subgraph) for every $H$ whose every connected component is a path or a subdivided claw (i.e., a tree with at most three leaves). This completes the dichotomy of the complexity of \textsc{MWIS} in $\mathcal{F}$-free graphs for any finite set $\mathcal{F}$ of graphs into NP-hard cases and cases solvable in quasi-polynomial time, and corroborates the conjecture that the cases not known to be NP-hard are actually polynomial-time solvable. The key graph-theoretic ingredient in our result is as follows. Fix an integer $t \geq 1$. Let $S_{t,t,t}$ be the graph created from three paths on $t$ edges by identifying one endpoint of each path into a single vertex. We show that, given a graph $G$, one can in polynomial time find either an induced $S_{t,t,t}$ in $G$, or a balanced separator consisting of $\Oh(\log |V(G)|)$ vertex neighborhoods in $G$, or an extended strip decomposition of $G$ (a decomposition almost as useful for recursion for \textsc{MWIS} as a partition into connected components) with each particle of weight multiplicatively smaller than the weight of $G$. This is a strengthening of a result of Majewski et al.\ [ICALP~2022] which provided such an extended strip decomposition only after the deletion of $\Oh(\log |V(G)|)$ vertex neighborhoods. To reach the final result, we employ an involved branching strategy that relies on the structural lemma presented above., Comment: 59 pages, 4 figures

We investigate a fundamental vertex-deletion problem called (Induced) Subgraph Hitting: given a graph $G$ and a set $\mathcal{F}$ of forbidden graphs, the goal is to compute a minimum-sized set $S$ of vertices of $G$ such that $G-S$ does not contain any graph in $\mathcal{F}$ as an (induced) subgraph. This is a generic problem that encompasses many well-known problems that were extensively studied on their own, particularly (but not only) from the perspectives of both approximation and parameterization. In this paper, we study the approximability of the problem on a large variety of graph classes. Our first result is a linear-time $(1+\varepsilon)$-approximation reduction from (Induced) Subgraph Hitting on any graph class $\mathcal{G}$ of bounded expansion to the same problem on bounded degree graphs within $\mathcal{G}$. This directly yields linear-size $(1+\varepsilon)$-approximation lossy kernels for the problems on any bounded-expansion graph classes. Our second result is a linear-time approximation scheme for (Induced) Subgraph Hitting on any graph class $\mathcal{G}$ of polynomial expansion, based on the local-search framework of Har-Peled and Quanrud [SICOMP 2017]. This approximation scheme can be applied to a more general family of problems that aim to hit all subgraphs satisfying a certain property $\pi$ that is efficiently testable and has bounded diameter. Both of our results have applications to Subgraph Hitting (not induced) on wide classes of geometric intersection graphs, resulting in linear-size lossy kernels and (near-)linear time approximation schemes for the problem., Comment: 52 pages, subsuming the article arXiv:2304.12789

We give an algorithm that takes as input an $n$-vertex graph $G$ and an integer $k$, runs in time $2^{O(k^2)} n^{O(1)}$, and outputs a tree decomposition of $G$ of width at most $k$, if such a decomposition exists. This resolves the long-standing open problem of whether there is a $2^{o(k^3)} n^{O(1)}$ time algorithm for treewidth. In particular, our algorithm is the first improvement on the dependency on $k$ in algorithms for treewidth since the $2^{O(k^3)} n^{O(1)}$ time algorithm given by Bodlaender and Kloks [ICALP 1991] and Lagergren and Arnborg [ICALP 1991]. We also give an algorithm that given an $n$-vertex graph $G$, an integer $k$, and a rational $\varepsilon \in (0,1)$, in time $k^{O(k/\varepsilon)} n^{O(1)}$ either outputs a tree decomposition of $G$ of width at most $(1+\varepsilon)k$ or determines that the treewidth of $G$ is larger than $k$. Prior to our work, no approximation algorithms for treewidth with approximation ratio less than $2$, other than the exact algorithms, were known. Both of our algorithms work in polynomial space., Comment: 57 pages, 2 figures. STOC 2023. In version v2 added a conclusion section

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 $\textsf{OPT}=f(C)$. We give an algorithm that given an $n$-vertex graph $G$, parameter $\varepsilon > 0$, and the function $f$ represented by an oracle, in time $n^{\mathcal{O}(\log 1/\varepsilon)}$ finds a cycle $C$ in $G$ with $f(C)\leq (1+\varepsilon)\cdot \textsf{OPT}$. 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 $n^{2/3-\varepsilon}$-approximation [Goel et al., FOCS 2009]. We complement our algorithm with a matching lower bound. We show that for every $\varepsilon > 0$, obtaining a $(1+\varepsilon)$-approximation requires at least $n^{\Omega(\log 1/ \varepsilon)}$ queries to the oracle. When the function $f$ is integer-valued, our algorithm yields that a cycle of cost $\textsf{OPT}$ can be found in time $n^{\mathcal{O}(\log \textsf{OPT})}$. In particular, for $\textsf{OPT}=n^{\mathcal{O}(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^{\mathcal{O}(\log n)}$ queries are required even when $\textsf{OPT} = \mathcal{O}(n)$., Comment: 17 pages, 1 figure. Accepted to SODA 2023

We initiate a systematic study of approximation schemes for fundamental optimization problems on disk graphs, a common generalization of both planar graphs and unit-disk graphs. Our main contribution is a general framework for designing efficient polynomial-time approximation schemes (EPTASes) for vertex-deletion problems on disk graphs, which results in EPTASes for many problems including Vertex Cover, Feedback Vertex Set, Small Cycle Hitting (in particular, Triangle Hitting), $P_k$-Hitting for $k\in\{3,4,5\}$, Path Deletion, Pathwidth $1$-Deletion, Component Order Connectivity, Bounded Degree Deletion, Pseudoforest Deletion, Finite-Type Component Deletion, etc. All EPTASes obtained using our framework are robust in the sense that they do not require a realization of the input graph. To the best of our knowledge, prior to this work, the only problems known to admit (E)PTASes on disk graphs are Maximum Clique, Independent Set, Dominating set, and Vertex Cover, among which the existing PTAS [Erlebach et al., SICOMP'05] and EPTAS [Leeuwen, SWAT'06] for Vertex Cover require a realization of the input disk graph (while ours does not). The core of our framework is a reduction for a broad class of (approximation) vertex-deletion problems from (general) disk graphs to disk graphs of bounded local radius, which is a new invariant of disk graphs introduced in this work. Disk graphs of bounded local radius can be viewed as a mild generalization of planar graphs, which preserves certain nice properties of planar graphs. Specifically, we prove that disk graphs of bounded local radius admit the Excluded Grid Minor property and have locally bounded treewidth. This allows existing techniques for designing approximation schemes on planar graphs (e.g., bidimensionality and Baker's technique) to be directly applied to disk graphs of bounded local radius.

We prove that Graph Isomorphism and Canonization in graphs excluding a fixed graph $H$ as a minor can be solved by an algorithm working in time $f(H)\cdot n^{O(1)}$, where $f$ is some function. In other words, we show that these problems are fixed-parameter tractable when parameterized by the size of the excluded minor, with the caveat that the bound on the running time is not necessarily computable. The underlying approach is based on decomposing the graph in a canonical way into unbreakable (intuitively, well-connected) parts, which essentially provides a reduction to the case where the given $H$-minor-free graph is unbreakable itself. This is complemented by an analysis of unbreakable $H$-minor-free graphs, performed in a second subordinate manuscript, which reveals that every such graph can be canonically decomposed into a part that admits few automorphisms and a part that has bounded treewidth., Comment: Part I of a full version of a paper accepted at STOC 2022

A set $X \subseteq V(G)$ in a graph $G$ is $(q,k)$-unbreakable if every separation $(A,B)$ of order at most $k$ in $G$ satisfies $|A \cap X| \leq q$ or $|B \cap X| \leq q$. In this paper, we prove the following result: If a graph $G$ excludes a fixed complete graph $K_h$ as a minor and satisfies certain unbreakability guarantees, then $G$ is almost rigid in the following sense: the vertices of $G$ can be partitioned in an isomorphism-invariant way into a part inducing a graph of bounded treewidth and a part that admits a small isomorphism-invariant family of labelings. This result is the key ingredient in the fixed-parameter algorithm for Graph Isomorphism parameterized by the Hadwiger number of the graph, which is presented in a companion paper., Comment: Part II of a full version of a paper appearing at STOC 2022

Wordle is a single-player word-guessing game where the goal is to discover a secret word $w$ that has been chosen from a dictionary $D$. In order to discover $w$, the player can make at most $\ell$ guesses, which must also be words from $D$, all words in $D$ having the same length $k$. After each guess, the player is notified of the positions in which their guess matches the secret word, as well as letters in the guess that appear in the secret word in a different position. We study the game of Wordle from a complexity perspective, proving NP-hardness of its natural formalization: to decide given a dictionary $D$ and an integer $\ell$ if the player can guarantee to discover the secret word within $\ell$ guesses. Moreover, we prove that hardness holds even over instances where words have length $k = 5$, and that even in this case it is NP-hard to approximate the minimum number of guesses required to guarantee discovering the secret word. We also present results regarding its parameterized complexity and offer some related open problems., Comment: Accepted at FUN2022

Suppose we are given a pair of points $s, t$ and a set $S$ of $n$ geometric objects in the plane, called obstacles. We show that in polynomial time one can construct an auxiliary (multi-)graph $G$ with vertex set $S$ and every edge labeled from $\{0, 1\}$, such that a set $S_d \subseteq S$ of obstacles separates $s$ from $t$ if and only if $G[S_d]$ contains a cycle whose sum of labels is odd. Using this structural characterization of separating sets of obstacles we obtain the following algorithmic results. In the Obstacle-Removal problem the task is to find a curve in the plane connecting s to t intersecting at most q obstacles. We give a $2.3146^qn^{O(1)}$ algorithm for Obstacle-Removal, significantly improving upon the previously best known $q^{O(q^3)} n^{O(1)}$ algorithm of Eiben and Lokshtanov (SoCG'20). We also obtain an alternative proof of a constant factor approximation algorithm for Obstacle-Removal, substantially simplifying the arguments of Kumar et al. (SODA'21). In the Generalized Points-Separation problem, the input consists of the set S of obstacles, a point set A of k points and p pairs $(s_1, t_1),... (s_p, t_p)$ of points from A. The task is to find a minimum subset $S_r \subseteq S$ such that for every $i$, every curve from $s_i$ to $t_i$ intersects at least one obstacle in $S_r$. We obtain $2^{O(p)} n^{O(k)}$-time algorithm for Generalized Points-Separation problem. This resolves an open problem of Cabello and Giannopoulos (SoCG'13), who asked about the existence of such an algorithm for the special case where $(s_1, t_1), ... (s_p, t_p)$ contains all the pairs of points in A. Finally, we improve the running time of our algorithm to $f(p,k) n^{O(\sqrt{k})}$ when the obstacles are unit disks, where $f(p,k) = 2^O(p) k^{O(k)}$, and show that, assuming the Exponential Time Hypothesis (ETH), the running time dependence on $k$ of our algorithms is essentially optimal., Comment: Short version of this paper will appear in SoCG'2022

We design the first subexponential-time (parameterized) algorithms for several cut and cycle-hitting problems on $H$-minor free graphs. In particular, we obtain the following results (where $k$ is the solution-size parameter). 1. $2^{O(\sqrt{k}\log k)} \cdot n^{O(1)}$ time algorithms for Edge Bipartization and Odd Cycle Transversal; 2. a $2^{O(\sqrt{k}\log^4 k)} \cdot n^{O(1)}$ time algorithm for Edge Multiway Cut and a $2^{O(r \sqrt{k} \log k)} \cdot n^{O(1)}$ time algorithm for Vertex Multiway Cut, where $r$ is the number of terminals to be separated; 3. a $2^{O((r+\sqrt{k})\log^4 (rk))} \cdot n^{O(1)}$ time algorithm for Edge Multicut and a $2^{O((\sqrt{rk}+r) \log (rk))} \cdot n^{O(1)}$ time algorithm for Vertex Multicut, where $r$ is the number of terminal pairs to be separated; 4. a $2^{O(\sqrt{k} \log g \log^4 k)} \cdot n^{O(1)}$ time algorithm for Group Feedback Edge Set and a $2^{O(g \sqrt{k}\log(gk))} \cdot n^{O(1)}$ time algorithm for Group Feedback Vertex Set, where $g$ is the size of the group. 5. In addition, our approach also gives $n^{O(\sqrt{k})}$ time algorithms for all above problems with the exception of $n^{O(r+\sqrt{k})}$ time for Edge/Vertex Multicut and $(ng)^{O(\sqrt{k})}$ time for Group Feedback Edge/Vertex Set. We obtain our results by giving a new decomposition theorem on graphs of bounded genus, or more generally, an $h$-almost-embeddable graph for any fixed constant $h$. In particular we show the following. Let $G$ be an $h$-almost-embeddable graph for a constant $h$. Then for every $p\in\mathbb{N}$, there exist disjoint sets $Z_1,\dots,Z_p \subseteq V(G)$ such that for every $i \in \{1,\dots,p\}$ and every $Z'\subseteq Z_i$, the treewidth of $G/(Z_i\backslash Z')$ is $O(p+|Z'|)$. Here $G/(Z_i\backslash Z')$ is the graph obtained from $G$ by contracting edges with both endpoints in $Z_i \backslash Z'$., Comment: A preliminary version appears in SODA'22

The emergence of programmable data-plane targets has motivated a new hybrid design for network streaming analytics systems that combine these targets' fast packet processing speeds with the rich compute resources available at modern stream processors. However, these systems require careful query planning; that is, specifying the minute details of executing a given set of queries in a way that makes the best use of the limited resources and programmability offered by data-plane targets. We use such an existing system, Sonata, and real-world packet traces to understand how executing a fixed query workload is affected by the unknown dynamics of the traffic that defines the target's input workload. We observe that static query planning, as employed by Sonata, cannot handle even small changes in the input workload, wasting data-plane resources to the point where query execution is confined mainly to userspace. This paper presents the design and implementation of DynamiQ, a new network streaming analytics platform that employs dynamic query planning to deal with the dynamics of real-world input workloads. Specifically, we develop a suite of practical algorithms for (i) computing effective initial query plans (to start query execution) and (ii) enabling efficient updating of portions of such an initial query plan at runtime (to adapt to changes in the input workload). Using real-world packet traces as input workload, we show that compared to Sonata, DynamiQ reduces the stream processor's workload by two orders of magnitude.

In its most traditional setting, the main concern of optimization theory is the search for optimal solutions for instances of a given computational problem. A recent trend of research in artificial intelligence, called solution diversity, has focused on the development of notions of optimality that may be more appropriate in settings where subjectivity is essential. The idea is that instead of aiming at the development of algorithms that output a single optimal solution, the goal is to investigate algorithms that output a small set of sufficiently good solutions that are sufficiently diverse from one another. In this way, the user has the opportunity to choose the solution that is most appropriate to the context at hand. It also displays the richness of the solution space. When combined with techniques from parameterized complexity theory, the paradigm of diversity of solutions offers a powerful algorithmic framework to address problems of practical relevance. In this work, we investigate the impact of this combination in the field of Kemeny Rank Aggregation, a well-studied class of problems lying in the intersection of order theory and social choice theory and also in the field of order theory itself. In particular, we show that the Kemeny Rank Aggregation problem is fixed-parameter tractable with respect to natural parameters providing natural formalizations of the notions of diversity and of the notion of a sufficiently good solution. Our main results work both when considering the traditional setting of aggregation over linearly ordered votes, and in the more general setting where votes are partially ordered., Comment: Accepted to the 30th International Joint Conference on Artificial Intelligence (IJCAI 2021)

For a graph class ${\cal H}$, the graph parameters elimination distance to ${\cal H}$ (denoted by ${\bf ed}_{\cal H}$) [Bulian and Dawar, Algorithmica, 2016], and ${\cal H}$-treewidth (denoted by ${\bf tw}_{\cal H}$) [Eiben et al. JCSS, 2021] aim to minimize the treedepth and treewidth, respectively, of the "torso" of the graph induced on a modulator to the graph class ${\cal H}$. Here, the torso of a vertex set $S$ in a graph $G$ is the graph with vertex set $S$ and an edge between two vertices $u, v \in S$ if there is a path between $u$ and $v$ in $G$ whose internal vertices all lie outside $S$. In this paper, we show that from the perspective of (non-uniform) fixed-parameter tractability (FPT), the three parameters described above give equally powerful parameterizations for every hereditary graph class ${\cal H}$ that satisfies mild additional conditions. In fact, we show that for every hereditary graph class ${\cal H}$ satisfying mild additional conditions, with the exception of ${\bf tw}_{\cal H}$ parameterized by ${\bf ed}_{\cal H}$, for every pair of these parameters, computing one parameterized by itself or any of the others is FPT-equivalent to the standard vertex-deletion (to ${\cal H}$) problem. As an example, we prove that an FPT algorithm for the vertex-deletion problem implies a non-uniform FPT algorithm for computing ${\bf ed}_{\cal H}$ and ${\bf tw}_{\cal H}$. The conclusions of non-uniform FPT algorithms being somewhat unsatisfactory, we essentially prove that if ${\cal H}$ is hereditary, union-closed, CMSO-definable, and (a) the canonical equivalence relation (or any refinement thereof) for membership in the class can be efficiently computed, or (b) the class admits a "strong irrelevant vertex rule", then there exists a uniform FPT algorithm for ${\bf ed}_{\cal H}$., Comment: 70 pages, To appear in SODA 2022. arXiv admin note: text overlap with arXiv:2103.09715, arXiv:2105.04660 by other authors

In the Disjoint Paths problem, the input is an undirected graph $G$ on $n$ vertices and a set of $k$ vertex pairs, $\{s_i,t_i\}_{i=1}^k$, and the task is to find $k$ pairwise vertex-disjoint paths connecting $s_i$ to $t_i$. The problem was shown to have an $f(k)n^3$ algorithm by Robertson and Seymour. In modern terminology, this means that Disjoint Paths is fixed parameter tractable (FPT), parameterized by the number of vertex pairs. This algorithm is the cornerstone of the entire graph minor theory, and a vital ingredient in the $g(k)n^3$ algorithm for Minor Testing (given two undirected graphs, $G$ and $H$ on $n$ and $k$ vertices, respectively, the objective is to check whether $G$ contains $H$ as a minor). All we know about $f$ and $g$ is that these are computable functions. Thus, a challenging open problem in graph algorithms is to devise an algorithm for Disjoint Paths where $f$ is single exponential. That is, $f$ is of the form $2^{{\sf poly}(k)}$. The algorithm of Robertson and Seymour relies on topology and essentially reduces the problem to surface-embedded graphs. Thus, the first major obstacle that has to be overcome in order to get an algorithm with a single exponential running time for Disjoint Paths and {\sf Minor Testing} on general graphs is to solve Disjoint Paths in single exponential time on surface-embedded graphs and in particular on planar graphs. Even when the inputs to Disjoint Paths are restricted to planar graphs, a case called the Planar Disjoint Paths problem, the best known algorithm has running time $2^{2^{O(k)}}n^2$. In this paper, we make the first step towards our quest for designing a single exponential time algorithm for Disjoint Paths by giving a $2^{O(k^2)}n^{O(1)}$-time algorithm for Planar Disjoint Paths., Comment: Full version of STOC 2020 paper; 83 pages

Given two points s and t in the plane and a set of obstacles defined by closed curves, what is the minimum number of obstacles touched by a path connecting s and t? This is a fundamental and well-studied problem arising naturally in computational geometry, graph theory (under the names Min-Color Path and Minimum Label Path), wireless sensor networks (Barrier Resilience) and motion planning (Minimum Constraint Removal). It remains NP-hard even for very simple-shaped obstacles such as unit-length line segments. In this paper we give the first constant factor approximation algorithm for this problem, resolving an open problem of [Chan and Kirkpatrick, TCS, 2014] and [Bandyapadhyay et al., CGTA, 2020]. We also obtain a constant factor approximation for the Minimum Color Prize Collecting Steiner Forest where the goal is to connect multiple request pairs (s1, t1), . . . ,(sk, tk) while minimizing the number of obstacles touched by any (si, ti) path plus a fixed cost of wi for each pair (si, ti) left disconnected. This generalizes the classic Steiner Forest and Prize-Collecting Steiner Forest problems on planar graphs, for which intricate PTASes are known. In contrast, no PTAS is possible for Min-Color Path even on planar graphs since the problem is known to be APXhard [Eiben and Kanj, TALG, 2020]. Additionally, we show that generalizations of the problem to disconnected obstacles, Comment: To appear in SODA 2021

In the Disjoint Paths problem, the input consists of an $n$-vertex graph $G$ and a collection of $k$ vertex pairs, $\{(s_i,t_i)\}_{i=1}^k$, and the objective is to determine whether there exists a collection $\{P_i\}_{i=1}^k$ of $k$ pairwise vertex-disjoint paths in $G$ where the end-vertices of $P_i$ are $s_i$ and $t_i$. This problem was shown to admit an $f(k)n^3$-time algorithm by Robertson and Seymour (Graph Minors XIII, The Disjoint Paths Problem, JCTB). In modern terminology, this means that Disjoint Paths is fixed parameter tractable (FPT) with respect to $k$. Remarkably, the above algorithm for Disjoint Paths is a cornerstone of the entire Graph Minors Theory, and conceptually vital to the $g(k)n^3$-time algorithm for Minor Testing (given two undirected graphs, $G$ and $H$ on $n$ and $k$ vertices, respectively, determine whether $G$ contains $H$ as a minor). In this semi-survey, we will first give an exposition of the Graph Minors Theory with emphasis on efficiency from the viewpoint of Parameterized Complexity. Secondly, we will review the state of the art with respect to the Disjoint Paths and Planar Disjoint Paths problems. Lastly, we will discuss the main ideas behind a new algorithm that combines treewidth reduction and an algebraic approach to solve Planar Disjoint Paths in time $2^{k^{O(1)}}n^{O(1)}$ (for undirected graphs)., Comment: Survey. Appeared in "Treewidth, Kernels, and Algorithms - Essays Dedicated to Hans L. Bodlaender on the Occasion of His 60th Birthday", 2020

For an integer $t$, a graph $G$ is called {\em{$C_{>t}$-free}} if $G$ does not contain any induced cycle on more than~$t$ vertices. We prove the following statement: for every pair of integers $d$ and $t$ and a CMSO$_2$ statement~$\phi$, there exists an algorithm that, given an $n$-vertex $C_{>t}$-free graph $G$ with weights on vertices, finds in time $n^{O(\log^4 n)}$ a maximum-weight vertex subset $S$ such that $G[S]$ has degeneracy at most $d$ and satisfies $\phi$. The running time can be improved to $n^{O(\log^2 n)}$ assuming $G$ is $P_t$-free, that is, $G$ does not contain an induced path on $t$ vertices. This expands the recent results of the authors [to appear at FOCS 2020 and SOSA 2021] on the {\sc{Maximum Weight Independent Set}} problem on $P_t$-free graphs in two directions: by encompassing the more general setting of $C_{>t}$-free graphs, and by being applicable to a much wider variety of problems, such as {\sc{Maximum Weight Induced Forest}} or {\sc{Maximum Weight Induced Planar Graph}}., Comment: 49 pages, 2 figures. Major changes from first (preliminary) version including changing title, adding co-authors, and significant addition to content of the paper

A class ${\cal F}$ of graphs is called {\em tame} if there exists a constant $k$ so that every graph in ${\cal F}$ on $n$ vertices contains at most $O(n^k)$ minimal separators, {\em strongly-quasi-tame} if every graph in ${\cal F}$ on $n$ vertices contains at most $O(n^{k \log n})$ minimal separators, and {\em feral} if there exists a constant $c > 1$ so that ${\cal F}$ contains $n$-vertex graphs with at least $c^n$ minimal separators for arbitrarily large $n$. The classification of graph classes into tame or feral has numerous algorithmic consequences, and has recently received considerable attention. A key graph-theoretic object in the quest for such a classification is the notion of a $k$-{\em creature}. In a recent manuscript [Abrishami et al., Arxiv 2020] conjecture that every hereditary class ${\cal F}$ that excludes $k$-creatures for some fixed constant $k$ is tame. We give a counterexample to this conjecture and prove the weaker result that a hereditary class ${\cal F}$ is strongly quasi-tame if it excludes $k$-creatures for some fixed constant $k$ and additionally every minimal separator can be dominated by another fixed constant $k'$ number of vertices. The tools developed also lead to a number of additional results of independent interest. {\bf (i) We obtain a complete classification of all hereditary graph classes defined by a finite set of forbidden induced subgraphs into strongly quasi-tame or feral. This generalizes Milani\v{c} and Piva\v{c} [WG'19]. {\bf (ii)} We show that hereditary class that excludes $k$-creatures and additionally excludes all cycles of length at least $c$, for some constant $c$, are tame. This generalizes the result of [Chudnovsky et al., Arxiv 2019]. {\bf (iii)} We show that every hereditary class that excludes $k$-creatures and additionally excludes a complete graph on $c$ vertices for some fixed constant $c$ is tame., Comment: 32 pages 5, 5 figures

The cut-set $\partial(S)$ of a graph $G=(V,E)$ is the set of edges that have one endpoint in $S\subset V$ and the other endpoint in $V\setminus S$, and whenever $G[S]$ is connected, the cut $[S,V\setminus S]$ of $G$ is called a connected cut. A bond of a graph $G$ is an inclusion-wise minimal disconnecting set of $G$, i.e., bonds are cut-sets that determine cuts $[S,V\setminus S]$ of $G$ such that $G[S]$ and $G[V\setminus S]$ are both connected. Contrasting with a large number of studies related to maximum cuts, there exist very few results regarding the largest bond of general graphs. In this paper, we aim to reduce this gap on the complexity of computing the largest bond, and the maximum connected cut of a graph. Although cuts and bonds are similar, we remark that computing the largest bond and the maximum connected cut of a graph tends to be harder than computing its maximum cut. We show that it does not exist a constant-factor approximation algorithm to compute the largest bond, unless P = NP. Also, we show that {\sc Largest Bond} and {\sc Maximum Connected Cut} are NP-hard even for planar bipartite graphs, whereas \textsc{Maximum Cut} is trivial on bipartite graphs and polynomial-time solvable on planar graphs. In addition, we show that {\sc Largest Bond} and {\sc Maximum Connected Cut} are NP-hard on split graphs, and restricted to graphs of clique-width $w$ they can not be solved in time $f(w)\times n^{o(w)}$ unless the Exponential Time Hypothesis fails, but they can be solved in time $f(w)\times n^{O(w)}$. Finally, we show that both problems are fixed-parameter tractable when parameterized by the size of the solution, the treewidth, and the twin-cover number., Comment: This paper resulted from a merge of two papers submitted to arXiv (arXiv:1908.03389 and arXiv:1910.01071). Both preliminary versions were presented at the 14th International Symposium on Parameterized and Exact Computation (IPEC 2019)