CS Paper Radar

What You Earn from What You Learn: Characterization and Complexity of the Value of Information

Ratip Emin Berker, Ioannis Anagnostides, Emanuel Tewolde, Brian Hu Zhang, Tuomas Sandholm, Vincent Conitzer

cs.GT ·submitted 2026-10-14 03:03 UTC · v1
publishedtheory

Abstract

We examine the value of information in extensive-form decision problems: the largest multiplicative gain that a decision maker can obtain from an information refinement, taken over all payoff environments. This measures the structural importance of information disentangled from any particular payoff specification, and generalizes the notion of value of recall recently introduced by Berker et al. (AAAI'25). We establish a unifying characterization of the value of information under any information refinement, uncovering an intriguing connection to the maximum fractional chromatic number over a certain family of conflict graphs. We then employ our characterization to elucidate the complexity of two central information refinements. First, for the value of perfect information in perfect-recall decision problems, we find that the relevant conflict graphs are cographs, so the fractional chromatic number collapses to the clique number. Even though the clique number is tractable for a given cograph, we show that the additional layer of optimization (over the family of graphs) makes computing the value of perfect information NP-complete. On the positive side, we prove fixed-parameter tractability in terms of the degree of imperfect information. Second, for the value of recall in imperfect-recall decision problems (with no absentmindedness), we first show that the value of recall can realize the fractional chromatic number of any graph. Interestingly, this implies that, unlike the value of perfect information, the value of recall can take fractional values. Building on this reduction, we then establish S2P-completeness. This addresses questions left open by Berker et al. (AAAI'25)---both on the characterization and the complexity of the value of recall---and shows that computing the value of recall is strictly harder than the value of perfect information.

Comment
40 pages, 7 figures, main body to be published in Proceedings of the Twenty-second Conference on Web and Internet Economics (WINE-26), Hong Kong, China, 2026

Closest papers

Nearest neighbours by meaning across the whole index.

How Difficult Is It to Recognize CIS Graphs?

cs.DM math.CO ·2026-08-11 ·Rongchuan Tao, Mengxi Yang, Wenan Zang
similarity 0.59
Abstract

A graph $G$ is called $CIS$ if each maximal clique intersects each maximal stable set of $G$, with maximality taken with respect to set inclusion. CIS graphs resemble perfect graphs in several respects and have interesting applications in game theory. The complexity of recognizing CIS graphs was posed as an open problem by Chvátal in the 1990s and has since led to conflicting conjectures. We settle the problem by showing that recognizing CIS graphs is $\mathsf{coNP}\text{-complete}$.

0.38

Parallel AI Agent Collaboration as Graph-Structured Distributed Block Optimization

cs.MA cs.AImath.OC ·2026-10-21 ·Hanmin Li, Yury Demidovich, Peter Richtárik
theory similarity 0.58
Abstract · 24 pages, 8 figures

Parallel AI agents can produce useful local edits yet degrade a shared solution when their edits are combined. We model this coordination problem as discrete block optimization with an exactly evaluable objective and a known dependency graph. Independent sets certify compatible edits whose verified gains, measured against the same current solution, add exactly. A coordinator constructs a safe compatible candidate and can also evaluate interacting edits to capture favorable interactions. We prove that an optimal fractional coloring yields a merger that preserves a $1/χ_f(G)$ fraction of the total verified local improvement, where $χ_f(G)$ is the graph's fractional chromatic number. This guarantee is tight among mergers that select a subset of the same proposals. Under conditional local-improvement guarantees and a block error-bound condition, repeated collaboration converges geometrically in the objective gap. The rate separates task structure, agent allocation, and computation cost, yielding a linear program for agent assignment and an explicit time-cost trade-off. Code-repair experiments show that verified merging resolves conflicts between individually useful edits that cause naive merging to fail. On larger conflict-free tasks, parallel agents reduce modeled completion time at higher input-token-equivalent cost. On three public road networks, fractional integration retains 922 units of verified graph-cut improvement across 90 paired runs. For route-search agents sharing exclusive access to vehicle routes, fractional scheduling reduces measured wall time by a median of 15% across twelve paired runs, with route-cost changes varying across runs.

0.29

Feedback Vertex Set, Max Cut, and Edge Coloring on the Strong Product of a Graph and a Path

cs.CC cs.DMmath.CO ·2026-11-10 ·Jan Diester, Kolja Kühn, Manuel Rapp, Samuel Schneider, Torsten Ueckerdt
similarity 0.58
Abstract

We examine the computational complexity of well-known problems on subgraphs of the strong product of two paths. Namely, for Max Cut we show NP-hardness on induced subgraphs of $P \boxtimes P$ answering a question by Dvořák, Huynh, Joret, Liu, and Wood (2021). For 3-Edge Coloring we show NP-hardness on subgraphs of $P \boxtimes P$ and that it is equivalent to 3-Edge Coloring on planar graphs for induced subgraphs of $P \boxtimes P$. It is a long standing open question whether 3-Edge Coloring on planar graphs is NP-hard. As a second contribution, we consider graphs of the form $G \boxtimes P$ and show that Feedback Vertex Set on these graphs is FPT in the clique-width of $G$. Furthermore, we show that it can be solved in polynomial time if $G$ is chordal or co-comparable and that the computational complexity depends on the parity of $P$ if $G$ is bipartite. Namely, it is solvable in polynomial time if $P$ has an even number of vertices but is NP-complete otherwise. For Max Cut, we show that it can be solved in polynomial time if $G$ is bipartite.

0.07

Wyner's Common Information and the Common Entropy are NP-Hard to Compute

cs.IT ·2026-10-11 ·Roberto Bruno, Ugo Vaccaro
theory similarity 0.58
Abstract · A preliminary version of the manuscript

Wyner's common information $J(p)$ and the common entropy $G(p)$ of a pair of random variables $(X,Y)$ with finite ranges and joint distribution $p$ are both defined by an optimization over the auxiliary random variables $W$ that make $X$ and $Y$ conditionally independent: $J(p)$ is the infimum of the mutual information $I(X,Y;W)$, and $G(p)$ is the infimum of the entropy $H(W)$. We prove that both quantities are NP-hard to compute. For Wyner's common information, deciding whether $J(p)$ is strictly smaller than a given integer $r$ is NP-hard, and the problem is NP-complete on tables that are uniform on their support and have the same number of positive entries in every row. The reduction is from Maximum Edge Biclique and rests on an exact criterion, in terms of rectangles in the support of $p$, for improving on the auxiliary $W=X$; every yes-instance satisfies $J(p)<r-1/(4N^2)$ and every no-instance satisfies $J(p)=r$, where $N$ is the number of positive entries of $p$. For the common entropy, deciding whether $G(p)\le r$ for a rational number $r$ is NP-hard, even for tables with at most four nonzero entries in each row, all taking one of two values. The reduction is from exact cover by $3$-sets and rests on a majorization property of the masses of the nonnegative rank-one decompositions of $p$, combined with a quantitative form of the Schur concavity of entropy. In both cases the separation between yes- and no-instances is inverse-polynomial in the size of $p$, so that approximating $J(p)$ or $G(p)$ within a suitable inverse-polynomial additive error is also NP-hard. The two mechanisms are genuinely different: we exhibit a table on which a large rectangle in the support lowers $J$ below the threshold of our first reduction while leaving $G$ on it.

0.15

On Collusion-Free Teaching in Planar Graphs

cs.DM cs.CCcs.LG ·2026-10-13 ·Liana Khazaliya, Clemens Kuske
theoryhot direction similarity 0.57
Abstract

Non-clashing teaching minimizes teaching complexity among models satisfying the Goldman--Mathias collusion-avoidance criterion. While the Vapnik--Chervonenkis dimension (VCdim) measures the complexity of learning from samples, non-clashing teaching dimension (NCTD) measures the number of examples required when a teacher can select them. Whether NCTD is always bounded above by VCdim remains a fundamental open question in learning theory. In this paper, we investigate this question for the concept classes of closed neighborhoods in planar graphs. We prove a tight upper bound of two on their NCTD, thereby establishing the conjectured inequality for this family. For the positive variant NCTD+, in which teaching sets contain only positive examples, we obtain a tight upper bound of four. Finally, we show that deciding whether either NCTD+ or NCTD is at most one is NP-complete, even for concept classes of closed neighborhoods in planar graphs. In particular, despite the upper bound of two on NCTD for such classes, distinguishing between NCTD values of one and two remains NP-hard.

0.37

Core stability recognition for minimum-cost spanning tree games: Parameterized perspective

cs.GT cs.CC ·2026-09-16 ·Michal Dvořák, Ioannis Kakatelis, Dušan Knop
similarity 0.57
Abstract

Minimum-cost spanning tree game (MSTG) is a cooperative game played on an undirected edge-weighted graph $(G,w)$ representing the network, where each vertex corresponds to a player and each edge has an associated cost~$w$. A distinguished vertex $s \in V(G)$ represents the supply or source. For any coalition of players $S$, the characteristic cost function $c(S)$ is defined as the minimum cost of a spanning tree with respect to $w$, connecting exactly the vertices in $S \cup \{s\}$. In this paper we study the computational complexity of deciding core membership for MSTG. In general, deciding whether a given allocation is in the core is \textsf{coNP}-hard~(Faigle et al.,International Journal of Game Theory,1997). We study the core recognition problem under the name {\sc MSTG Core Non-Membership}. We extend the hardness to graphs which are very close to being planar. On the positive side, we present several algorithmic results within the framework of parameterized complexity. We show that {\sc MSTG Core Non-Membership} is fixed-parameter tractable when parameterized by the support size of the allocation. Turning into structural parameters of graphs, we show that the problem admits an FPT algorithm parameterized by treewidth and signed neighborhood diversity. Last but not least, we investigate kernelization. While in general graphs, under standard complexity-theoretical assumptions, {\sc MSTG Core Non-Membership} does not admit a polynomial kernel parameterized by the vertex cover number, we design a cubic kernel in planar graphs. Furthermore, in general graphs, we obtain quadratic kernel for signed neighborhood diversity and linear kernel for the parameter feedback edge number.

0.21

Complexity and algorithms for proper conflict-free coloring in graphs

cs.DM math.CO ·2026-08-11 ·Dinabandhu Pradhan, Vaishali Sharma
similarity 0.57
Abstract

A proper conflict-free (PCF) $k$-coloring of a graph $G$ is a proper $k$-coloring such that there exists a color that appears exactly once in the neighborhood of every non-isolated vertex $v\in V(G)$. The PCF chromatic number, denoted by $χ_{pcf}(G)$, is the least integer $k$ such that there exists a PCF $k$-coloring of $G$. Given a graph $G$ and a positive integer $k$, PCF $k$-COLORABILITY is to decide whether $G$ admits a PCF $k$-coloring. Ahn et al. [Discrete Appl. Math. 377 (2025) 10-17] proved that PCF $k$-COLORABILITY is NP-complete for bipartite graphs. We strengthen this result by proving that PCF $k$-COLORABILITY is NP-complete for perfect elimination bipartite graphs, which is a proper subclass of bipartite graphs. We also show that the PCF chromatic number of a graph cannot be approximated within $O(n^{1-\varepsilon})$ unless P=NP, for any $\varepsilon>0$. On the positive side, we provide linear-time algorithms for PCF $k$-COLORABILITY in block graphs, proper interval graphs, chain graphs, and pseudo-split graphs. We show that $χ_{pcf}(G)\leq ω(G)+1$ for block graphs, proper interval graphs, and pseudo-split graphs (except $C_5$), and we characterize all graphs for which the equality holds.

0.41

Minimum Label $k$-Cut on Planar Graphs: Complexity and Color Structure

cs.DS ·2026-10-29 ·Yuanhao Wang, Wei Wang
theory similarity 0.56
Abstract

Minimum Label $k$-Cut asks for a minimum-size set of colors such that deleting all edges of these colors leaves at least $k$ connected components. We study how the structure of the underlying graph and its color classes affects the complexity of this problem. Regarding fixed-parameter tractability with respect to $k$ on simple planar graphs, we prove that the problem is W[1]-hard, even when the underlying graph is a cactus graph and each color appears at most twice. Furthermore, for cactus graphs in which every color class is connected, we establish a complexity boundary in terms of the maximum monochromatic degree: when this degree is at most two, an optimal solution can be found in $O(Nk^2)$ time, where $N$ is the input size, with no restriction on color frequency or the number of blocks spanned by a color; allowing the maximum monochromatic degree to increase to three already makes the decision version NP-complete. Finally, we prove that the problem remains W[1]-hard parameterized by $k$ on fan graphs, even when every color class is an induced path. These results show that bounding color frequency does not suffice to eliminate parameterized hardness. They also establish a monochromatic-degree boundary for connected colors on cactus graphs and identify complexity barriers to extending this tractable case to outerplanar graphs.

0.16