Counting $P_3$-convex sets in graphs

This paper characterizes the graphs maximizing the number of $P_3$-convex sets, establishes the $\#\mathsf{P}$-completeness of counting these sets on split graphs, and provides efficient linear-time algorithms for trees and threshold graphs alongside a novel exact exponential-time approach for general graphs.

The Gist

Imagine a graph as a city map. The dots (vertices) are houses, and the lines (edges) are the streets connecting them.

In this paper, the authors are playing a game called "The Neighborhood Watch" (which they call P3-convexity).

The Rules of the Game

Here is how the game works:

1. You pick a group of houses to be "Black" (part of your neighborhood watch).
2. All other houses are "White" (not part of the watch).
3. The Golden Rule: If two "Black" houses are connected by a street that goes through exactly one "White" house (a path of three houses: Black $\to$ White $\to$ Black), that middle "White" house must also become "Black."
   • Why? Because if two watch members are neighbors of a third house, that third house is effectively "surrounded" by the watch and must join them to keep the neighborhood safe.

The Goal: The paper asks: "How many different valid Neighborhood Watch groups can we form in a city of $n$ houses?"

---

Part 1: The "Perfect" Cities (Extremal Graphs)

The authors first asked: What kind of city layout allows for the maximum number of valid watch groups?

• The Chaos City (Disconnected): If you have a city with no streets at all, or just isolated pairs of houses, every single possible group of houses is a valid watch group. There are no rules to break! This gives you the absolute maximum number of combinations ($2^n$).
• The Connected City: But what if the city must be connected (everyone can reach everyone)?
  • The authors found that the Star City (one central hub connected to everyone else, like a spiderweb) and the Long Road (a single line of houses) are the champions.
  • Specifically, a Star (one big house in the middle, everyone else connected only to it) allows for the most valid groups. It's like a popular celebrity; you can invite any combination of their fans, and the rules rarely force you to add someone you didn't want.

Part 2: The Hard Puzzle (Complexity)

Next, they asked: How hard is it to count these groups for a random, messy city?

• The Bad News: For most cities, counting the groups is impossible to do quickly. It belongs to a class of problems called #P-complete.
  • Analogy: Imagine trying to count every possible way to arrange a deck of cards, but with extra rules that make you check every single arrangement against a complex checklist. Even with a supercomputer, if the city is big enough, the number of combinations is so huge that you'd need longer than the age of the universe to finish.
  • They proved this is true even for "Split Graphs" (cities divided into a clique of best friends and a group of strangers).

Part 3: The Easy Cities (Tractable Cases)

However, not all cities are hard. The authors found two types of cities where you can count the groups instantly (in linear time):

1. Tree Cities: Cities with no loops (like a family tree or a branching river). Because there are no circles, you can solve the puzzle by starting at the top and working your way down, making decisions step-by-step.
2. Threshold Cities: These are highly structured cities where houses are ranked by importance. You can build them by adding either a lonely house or a "super-house" that connects to everyone. Because of this strict order, the math simplifies beautifully.

Part 4: The "Super-Strategy" (Exponential Algorithms)

Since the problem is hard for general cities, the authors designed a smart strategy to solve it faster than the "brute force" method (which would try every single combination).

Think of it like clearing a room:

1. The Brute Force: Try every combination of people in the room. (Takes forever).
2. The Smart Strategy:
   • Step 1: Find a big group of people who don't know each other (an Independent Set). Let's call them the "Quiet Group."
   • Step 2: Decide the status (Black or White) of everyone outside the Quiet Group first.
   • Step 3: Use the rules to see if the status of the outside group forces some people in the Quiet Group to be Black or White.
   • Step 4: If the rules don't force a decision, you are left with a smaller puzzle: "How many ways can we arrange the remaining people in the Quiet Group?"
   • The Trick: The authors realized this remaining puzzle is exactly the same as counting Independent Sets (groups of people who don't know each other), a problem that has very fast, specialized solvers.

By breaking the city into "Major Blocks," "Stars," and "Quiet Groups," they created an algorithm that is much faster than the old way, especially for cities where you can easily find large groups of strangers.

Summary

• The Problem: Counting valid "neighborhood watches" in a graph.
• The Winner: Star-shaped graphs have the most valid watches.
• The Difficulty: Counting them is generally a nightmare for computers (#P-complete).
• The Solution:
  • For simple trees and structured graphs, we have instant formulas.
  • For complex graphs, we use a "divide and conquer" strategy that turns the hard problem into a slightly easier one (counting independent sets), making it solvable for moderately sized cities.

The paper is essentially a guidebook on how to organize chaos, finding the most flexible city layouts, and building the best tools to count the possibilities in the messy ones.

Technical Summary

Here is a detailed technical summary of the paper "Counting P3-convex sets in graphs" by Dourado et al.

1. Problem Definition

The paper investigates $P_3$-convexity, a specific type of graph convexity generated by all paths of length two (three vertices).

• Definition: A subset of vertices $S \subseteq V(G)$ is $P_3$-convex if for every path $x-z-y$ in $G$ where $x, y \in S$, the middle vertex $z$ is also in $S$. Equivalently, a set is $P_3$-convex if every vertex outside the set has at most one neighbor inside the set.
• Objective: The primary goal is to count the number of such sets in a graph $G$, denoted as $noc(G)$.
• Research Questions:
  1. Extremal: Which $n$-vertex graphs maximize $noc(G)$?
  2. Complexity: What is the computational complexity of counting these sets?
  3. Algorithms: Can the problem be solved efficiently for specific graph classes, and can exact exponential-time algorithms be designed for general graphs?

2. Methodology

The authors employ a mix of combinatorial analysis, complexity theory reductions, and algorithmic design:

• Combinatorial Characterization: Using structural properties of graphs (e.g., degree constraints, induced subgraphs) to derive bounds and characterize extremal graphs.
• Dynamic Programming (DP): Developing recursive formulations for trees based on vertex coloring states (Black, White-with-black-parent, White-without-black-parent).
• Complexity Reductions: Reducing the problem to known #P-complete problems (specifically counting independent sets) to establish hardness.
• Exact Exponential Algorithms: Utilizing a "branch-and-reduce" strategy combined with structural decomposition. The core idea involves:
  1. Partitioning the graph into a large independent set $I$ and a remainder.
  2. Enumerating valid partial colorings of the remainder.
  3. Applying propagation rules to force colors on $I$.
  4. Reducing the remaining choices to counting independent sets in an auxiliary graph, solved using fast algorithms (e.g., Gaspers and Lee's $O^*(1.2356^n)$).

3. Key Contributions and Results

A. Extremal Graph Theory

The paper settles the question of which graphs maximize the number of $P_3$-convex sets.

• General Graphs: The maximum number of $P_3$-convex sets is $2^n$. This occurs if and only if the graph has maximum degree$\Delta(G) \le 1$ (i.e., a disjoint union of isolated vertices and edges).
• Connected Graphs: For connected graphs, the maximum is $2^{n-1} + n$.
• Extremal Connected Graphs: Equality holds if and only if $G$ is isomorphic to:
  • The star graph $K_{1, n-1}$.
  • The path graph $P_4$ (for $n=4$).
  • The path graph $P_5$ (for $n=5$).
  • Note: For $n \ge 6$, the star graph $K_{1, n-1}$ is the unique maximizer.

B. Computational Complexity

• #P-Completeness: Counting $P_3$-convex sets is #P-complete, even when restricted to split graphs (graphs partitionable into a clique and an independent set).
  • The proof involves a reduction from counting independent sets. The authors construct a split graph $H$ from an input graph $G$ such that $noc(H)$ relates directly to the number of independent sets in $G$.
  • This hardness holds even for split graphs that do not contain two vertex-disjoint induced copies of $K_{1,4}$.
• Polynomial-Time Solvable Cases:
  • Trees: The problem is solvable in linear time $O(|V| + |E|)$ using a dynamic programming approach on rooted trees.
  • Threshold Graphs: The problem is solvable in linear time $O(|V| + |E|)$. The authors derive a closed-form formula based on the canonical split partition of the threshold graph, analyzing cases where the convex set intersects the clique part in 0, 1, or all vertices.

C. Exact Exponential-Time Algorithms

For general graphs, the authors propose three improved exact algorithms that outperform the naive $O^*(2^n)$ brute-force approach.

• Strategy: The algorithms decompose the graph into three phases:
  1. Major Blocks: Removing vertices inducing non-trivial connected components in their neighborhoods.
  2. Star Extraction: Iteratively removing induced stars ($K_{1,3}$, $K_{1,4}$, or $K_{1,5}$) depending on the variant.
  3. Independent Set Extraction: The remaining graph is triangle-free; a large independent set $I$ is extracted.
• Performance: The running time depends on the size of the independent set $I$ found. The algorithms achieve the following worst-case time complexities:
  • Variant A (Claws $K_{1,3}$): $O^*(1.8612^n)$.
  • Variant B ($K_{1,4}$): $O^*(1.8384^n)$.
  • Variant C ($K_{1,5}$): $O^*(1.8336^n)$.
• Special Classes: For graph classes with guaranteed large independent sets (e.g., bipartite graphs, planar graphs, bounded degree graphs), the exponential base can be significantly reduced. For example, on bipartite graphs ($\alpha = 1/2$), the complexity drops to approximately $O^*(1.57^n)$.

4. Significance

• Theoretical Insight: The paper provides a complete characterization of extremal graphs for $P_3$-convexity, distinguishing between general and connected cases, and clarifying the role of star and path graphs.
• Complexity Landscape: It establishes the boundary between tractable and intractable instances for counting convex sets, showing that while the problem is hard for split graphs, it becomes easy for trees and threshold graphs.
• Algorithmic Advancement: The proposed exact exponential algorithms represent a significant improvement over brute-force enumeration. By leveraging structural decomposition and fast independent set counting, the authors provide a practical framework for solving this counting problem on general graphs, with specific optimizations for graph classes where large independent sets are guaranteed.
• Methodological Framework: The combination of propagation rules (forcing colors based on $P_3$ constraints) and reduction to independent set counting offers a template that could be adapted for other convexity problems or enumeration tasks in graph theory.