CS Paper Radar

Max Weight Independent Set in graphs with no long claws nor large induced bicliques

Maria Chudnovsky, Paweł Rzążewski

cs.DS ·submitted 2026-10-30 22:00 UTC · v1

Abstract

The complexity of Max Weight Independent Set (MWIS) in graphs excluding a fixed subdivided claw is one of the central open problems in algorithmic graph theory. We show that MWIS can be solved in polynomial time in graphs excluding a fixed subdivided claw and a fixed biclique as an induced subgraph. This strengthens a result of Abrishami, Chudnovsky, Dibek, Pilipczuk, and Rzążewski [ACM TALG 2026] who showed an analogous result, but under a stronger assumption that some biclique is excluded as a subgraph.

Closest papers

Nearest neighbours by meaning across the whole index.

Output-linear time enumeration of potential maximal cliques

cs.DS ·2026-10-14 ·Pierre Bergé, Vincent Limouzy, Nicolas Schivre
top venue similarity 0.70
Abstract · This paper was accepted at SODA 2027. 54 pages, 18 figures

First defined by Bouchitté and Todinca, Potential Maximal Cliques (PMC) are a well studied notion in graph theory due to its numerous applications. The PMCs of an undirected graph $G$ are defined as the maximal cliques of the minimal triangulations of $G$. Their number can be exponential in the size of the graph. PMCs were crucial in the design of a polynomial-time algorithm which solves Maximum Weight Independent Set on $P_6$-free graphs (Grzesik, Klimošová, Pilipczuk, Pilipczuk, 2020). They also play a central role in the proposal of a polynomial-time algorithm to solve Largest Induced Subgraph of treewidth $\le t$ (Fomin, Todinca, Villanger, 2013). Last but not least, certainly one of the main application of PMCs is the existence of an exact dynamic-programming algorithm to determine the treewidth of a graph (Fomin, Kratsch, Todinca, Villanger, 2008) which uses its list of PMCs as an input. In fact, the enumeration of PMCs stands as the bottleneck for the computation of treewidth with this method: the PMC-enumeration step takes output-quadratic time (Bouchitté, Todinca, 2002) while the dynamic-programming one takes a time linear in the number of PMCs. This two-step procedure was proven to be among the most performing approaches in practice to determine treewidth. Answering a longstanding open question, we propose an algorithm to enumerate PMCs in output-linear time, i.e. a running time linear in the number of PMCs. This offers nice perspectives not only from the theoretical viewpoint - better running time for the PMC-based methods determining treewidth, for Minimum Fill-In and Largest Induced Subgraph of treewidth $\le t$ - but also from the practical side, with the possibility to propose top-performance implementation.

0.68

Odd Cycle Transversal on $H$-free graphs

cs.DS cs.DMmath.CO ·2026-09-25 ·Esther Galby, Paloma T. de Lima, Andrea Munaro, Amir Nikabadi
similarity 0.68
Abstract

\textsc{Odd Cycle Transversal} is a classic $\mathsf{NP}$-hard graph optimization problem asking for a minimum-weight set of vertices whose deletion makes the input graph bipartite, or equivalently, a maximum-weight induced bipartite subgraph. We show that \textsc{Odd Cycle Transversal} is quasi-polynomial-time solvable on $kP_4$-free graphs, for every fixed $k \in \mathbb{N}$. In fact, we provide an $n^{O_k(\log n)}$-time algorithm for the more general \textsc{Max-Weight List $2$-Colorable Induced Subgraph}, where the notation $O_{k}(\cdot)$ hides factors depending on $k$. Paired with known results from the literature, this allows us to obtain a complete complexity dichotomy for these two problems on $H$-free graphs into cases solvable in quasi-polynomial time and cases which are $\mathsf{NP}$-hard, in particular resolving an open problem of Agrawal, Lima, Lokshtanov, Saurabh, and Sharma [SODA 2024]. Our algorithms are based on a new structural tool that may be of independent interest. We introduce the notion of $H$-amiable family and show that, for every fixed graph $H$ without isolated vertices and every fixed $k\ge2$, every $kH$-free graph admits an $H$-amiable family of quasi-polynomial size that can be constructed in quasi-polynomial time. Besides yielding the aforementioned algorithms, this result gives, for every fixed connected graph $H$ and every fixed $k\ge2$, a reduction from \textsc{Max-Weight Independent Set} on $kH$-free graphs to the same problem on $H$-free graphs with $n^{O_{H,k}(\log n)}$ overhead. In this setting, it improves the $n^{O_{H,k}(\log^3 n)}$ overhead obtained by specializing the general reduction of Gartland and Lokshtanov [FOCS 2020].

0.16

Induced Forest Minor Theorem for Graphs Without an Induced Star

cs.DM math.CO ·2026-09-09 ·Robert Hickingbotham, Gwenaël Joret
theory similarity 0.66
Abstract

Motivated by recent work on tree independence number, we study the path independence number of a graph $G$: the minimum integer $k$ such that there is a path decomposition of $G$ where each bag induces a graph with independence number at most $k$. We show that every graph excluding both an induced forest minor and an induced star has bounded path independence number. This characterises when a graph class that excludes an induced star has bounded path independence number while also partially resolving a conjecture of Dallard, Krnc, Kwon, Milani{č}, Munaro, Štorgel and Wiederrecht (2024). Furthermore, we show that graphs excluding both an apex-forest induced minor and an induced star have bounded tree independence number. As a consequence, for every fixed apex-forest $H$ and integer $t$, there is a polynomial-time algorithm to test whether a $K_{1,t}$-induced-subgraph-free graph contains $H$ as an induced minor. Moreover, it follows that the Maximum Weight Independent Set problem, as well as several other NP-hard problems, can be solved in polynomial-time on $K_{1,t}$-induced-subgraph-free graphs that exclude $H$ as an induced minor.

0.34

Independent Set Discovery on Biclique-Free Graphs Is Fixed-Parameter Tractable

cs.DS ·2026-08-19 ·Chenghua Liu, Boning Meng
similarity 0.66
Abstract

\textnormal{\textsc{Independent Set Discovery}} asks whether a configuration of $k$ tokens on distinct vertices can be transformed into an independent $k$-set by a sequence of token slides, each moving one token to an unoccupied neighbor; only the terminal configuration must be independent. \textnormal{\textsc{Independent Set Discovery}} is a central problem in solution discovery: its target is not prescribed and must be chosen together with the token movements needed to reach it. Fellows et al. proved it FPT in $k$ on every fixed bounded-degeneracy class and every nowhere-dense class, leaving the biclique-free case open. The biclique-free setting lies substantially beyond both regimes: biclique-free classes can have unbounded degeneracy and even be somewhere dense. We resolve the open problem affirmatively. Given an $n$-vertex, $m$-edge graph promised to be $K_{d,d}$-free and an initial $k$-token configuration, our deterministic algorithm computes the minimum number of slides and, in time $2^{O(dk\log k)}(n+m)^{O(1)}$, returns an optimal independent target and a shortest collision-free slide sequence or certifies that no independent target is reachable. Thus the problem is FPT in $k$ for every fixed $d$ and uniformly FPT in $k+d$. The proof combines an exact minimum-cost assignment characterization of token movement with local branching on bounded, cost-relevant \emph{cheap prefixes} of candidate lists. The method also yields an exact FPT algorithm for weighted independent transversals on $K_{d,d}$-free graphs with overlapping candidate sets, direct exact FPT algorithms for both problems on bounded-degeneracy graphs, an edge-count-sensitive XP algorithm, sharper bounds for bounded $s$-codegree and unbalanced biclique exclusion, and an exact extension to weighted movement on a separate directed graph.

0.20

Maximum Edge Open Packing on AT-Free, Chordal, and Convex Bipartite Graphs

cs.DM math.CO ·2026-10-01 ·Gautam K. Das, Kamal Santra
similarity 0.66
Abstract

An edge open packing is a set of edges whose endpoints induce a disjoint union of stars. We study the problem of finding a maximum edge open packing in AT-free, chordal, and convex bipartite graphs. For AT-free graphs, we use the oriented star-conflict graph $A_G$, introduced by Das and Santra, for which $ρ_e^o(G)=α(A_G)$, and prove that $A_G$ is AT-free whenever $G$ is AT-free. Consequently, a known maximum independent set algorithm for AT-free graphs yields an $O(n^2+m^4)$-time algorithm for Maximum Edge Open Packing, where $n$ and $m$ denote the numbers of vertices and edges of $G$, respectively. For chordal graphs, we develop an $O(n^4)$-time dynamic programming algorithm over a nice tree decomposition derived from a clique tree, exploiting the structural fact that the endpoint set of an edge open packing intersects every clique in at most two vertices. Finally, for convex bipartite graphs, we obtain an $O(n^4)$-time dynamic programming algorithm based on two boundary indices that separate consecutive star components. This result extends the previously known algorithm for biconvex bipartite graphs and, in particular, provides an improved explicit running-time bound for that class.

0.07

Tolerant Testers for Subgraph-Freeness

cs.DS ·2026-10-14 ·Reut Levi, Jonathan Meiri
published similarity 0.66
Abstract

In this paper we study the problem of tolerantly testing the property of being $H$-free (which also implies distance approximation from being $H$-free). In the general-graphs model, we show that tolerant $K_k$-freeness testing can be achieved with query complexity that is polynomial in the arboricity of the input graph $G$, $arb(G)$, and independent of the size of $G$ (for graphs in which the average degree is $Ω(1))$. Specifically for triangles, our algorithm distinguishes graphs which are $ε$-close to being triangle-free from graphs that are $3ε(1+η)$-far from being triangle-free with expected query complexity which is $\tilde{O}(arb^3(G))$ (for constant $η$ and $ε$). For general $k$-cliques our algorithm distinguishes graphs which are $ε$-close to being $K_k$-free from graphs which are ${k \choose 2}ε(1+η)$-far from being $K_k$-free with expected query complexity which is polynomial in $k$, $1/ε$, $1/η$ and $arb(G)$. We then generalize our result and provide a similar result for any motif $H$ which is $2$-connected and has radius $1$. This includes for example the wheel graph. Finally, we show that our tester can be applied to the bounded-degree model for tolerantly testing $H$-freeness for any motif $H$. The query complexity of the algorithm is polynomial in the degree bound, $d$, improving the previous state-of-the-art by Marko and Ron (TALG 2009) that obtained quasi-polynomial query complexity in $d$.

0.32

Path Isolation and Reachability in Surface-Embedded Graphs with Restricted Cycle and Cut Structure

cs.CC ·2026-11-06 ·Neelabjo Shubhashis Choudhury, Chetan Gupta, Raghunath Tewari
theory similarity 0.65
Abstract · 18 pages. 1 figure

We study the reachability problem in directed surface-embedded graphs under two structural restrictions, using isolating weight assignments. First, we consider graphs whose underlying undirected embeddings contain at most polynomially many simple surface non-separating cycles. We develop a polynomially bounded, logspace-computable skew-symmetric edge-weight assignment with nonzero circulation around every simple cycle. This yields an unambiguous logspace (UL) upper bound for directed reachability. The construction also gives an SPL upper bound for bipartite perfect matching in the corresponding undirected graph class. Second, for $g$-genus directed graphs admitting a balanced hierarchical genus decomposition with $O(\log n)$ crossing edges at every partition, we obtain an unambiguous $O(\log g \cdot \log n)$-space bound for reachability. Our approach combines path-isolating weights for lower-genus subgraphs using polynomially bounded FKS hashing refinements at successive merging levels.

0.30

Compact Representations of Geometric Bipartite Graphs via Weighted Biclique Covers

cs.DS cs.DB ·2026-08-21 ·Aryan Esmailpour, Khoi Le, Stavros Sintos
top venuehot direction similarity 0.64
Abstract

Bipartite graphs are a fundamental representation for relational data arising in recommendation systems, social networks, and communication graphs. A key challenge in these settings is to store and transmit large bipartite graphs compactly while preserving exact structural and path information. We study biclique-based representations of bipartite graphs $\boldsymbol{G}=(\boldsymbol{V},\boldsymbol{U},\boldsymbol{E})$, where the edge set is encoded using a collection of complete bipartite subgraphs. We focus on the Weighted Biclique Covering problem, which minimizes the total number of vertices used across all bicliques, and introduce a generalized variant that additionally penalizes the number of bicliques, capturing practical overheads in storage, transmission, and model complexity. While the weighted biclique covering problem is known to be $\mathsf{NP}$-Complete, we show that the generalized variant is also $\mathsf{NP}$-Complete. Despite this hardness, many real-world bipartite graphs admit low-dimensional geometric embeddings or can be well approximated by them. Leveraging this observation, we develop the first approximation algorithms with provable guarantees for the (generalized) weighted biclique covering problem on geometric bipartite graphs. Specifically, for $δ$-disk bipartite graphs in low-dimensional $\ell_\infty^d$ spaces, we design a polynomial-time algorithm that achieves an $O(\log |\boldsymbol{U}| \cdot \log^d |\boldsymbol{V}|)$-approximation, combining ideas from greedy set cover, geometric range searching, and densest subgraph optimization. We also show how our algorithms extend to $\ell_α^d$ metrics for any $α\geq 1$. Finally, we evaluate our algorithms on real-world bipartite datasets and show that they efficiently compute significantly smaller biclique-based representations than natural baselines, while scaling to large graphs.

0.62