0
$\begingroup$

We know that finding the size of the maximal independent set of a planar graph is NP-complete. I'm curious about whether it remains NP-complete for maximal planar graphs, i.e., the graphs in which adding any edge will destroy its planarity, or equivalently, all edges of whose faces are bounded by three edges.

I've asked the AI Chat robot of DeepAI (https://deepai.org/chat), and it says the problem is in P. This is the algorithm it provided:

There is a simple polynomial-time algorithm to find the maximal independent set in a maximal planar graph. Here are the steps of the algorithm:

  1. Create a planar embedding of the maximal planar graph if not already given.

  2. Identify any vertices of degree two (called degree-2 vertices).

  3. Remove any degree-2 vertices from the graph and add them to the independent set.

  4. Repeat steps 2-3 until no degree-2 vertices remain.

  5. Pick any vertex of degree at most three (called a low-degree vertex) and remove it from the graph. Add it to the independent set.

  6. Update the degrees of the neighbors of the removed vertex.

  7. Repeat steps 5-6 until no low-degree vertices remain.

  8. Identify any isolated vertices and add them to the independent set.

  9. Output the set of vertices collected during the algorithm as the maximal independent set.

The algorithm works because of the special structure of maximal planar graphs. In step 3, removing a degree-2 vertex does not affect the planarity of the graph, as the two neighboring vertices can be connected directly. In step 5, removing a low-degree vertex can also be done without affecting the planarity of the graph because the remaining neighbors can be connected to maintain planarity. Finally, step 8 ensures that any isolated vertices are automatically included in the independent set, as they cannot be adjacent to any other vertex in the graph. The algorithm runs in O(n) time, making it efficient for large graphs.

However, I'm skeptical about this algorithm. Two low-degree vertices might be adjacent, so step 5 may put two adjacent vertices in the independent set. I asked it who proposed this algorithm, and it says Robert E. Tarjan proposed this algorithm in the paper "A class of algorithms which traverse a planar graph from both ends", but I can't find this paper. Now I'm very confused about whether on earth this problem can be solved in polynomial time, and I have no clue about how to sort it out by myself. Can you help me?

Edit 2023/3/14: I've studied a proof of NP-completeness of maximal independent set on 2-connected cubic planar graphs. The proof is given in the paper "Face covers and the genus problem for apex graphs" (https://users.fmf.uni-lj.si/mohar/Papers/ApexGenus.pdf, page 10-11). The author proposed a reduction from planar 3-SAT. Suppose there is a 3-SAT formula of $n$ variables (denoted $v_1,v_2,\cdots,v_n$) and $m$ clauses (denoted $c_1,c_2,\cdots,c_m$). The incidence graph of the formula consists of $n+m$ vertices, in which each variable and clause has a corresponding vertex. An edge $(v_i,c_j)$ is in the graph if and only if $v_i$ or $\neg v_i$ appears in $c_j$. It is proved that when the incidence graph is planar, 3-SAT remains NP-complete. Then the paper introduced a variation of the incidence graph: each clause vertex is replaced by a triangle that is consists of three variables in the clause, and each variable vertex is replaced by a cycle of length $2k$, where $k$ is the number of times the variable occurring in any clause. The cycle consists of vertices indicating the sign (positive or negative) of the variable in the corresponding clauses. If a vertex $x_i$ occurs in $k$ clauses $c_1,c_2,\cdots,c_k$, then the cycle of $x_i$ consists of $2k$ vertices: $c_1^{\mathrm{pos}},c_1^{\mathrm{neg}},c_2^{\mathrm{pos}},c_2^{\mathrm{neg}},\cdots,c_k^{\mathrm{pos}},c_k^{\mathrm{neg}}$. Now we construct the edges. If variable $x_i$ occurs in clause $c_j$ without being negated, then add an edge between the corresponding variable vertex in the clause triangle and $c_j^{\mathrm{neg}}$ in the vertex cycle. If $x_i$ is negated, then then add an edge between the vertex in the clause triangle and $c_j^{\mathrm{pos}}$. The resulting graph is 2-connected, cubic and planar (we can see the planarity because every vertex in the original incidence graph is "inflated" to a triangle or a cycle).

Here is an example. Suppose we have the following formula $$\begin{aligned} F&=(x_1\lor \neg x_2\lor x_3)\quad&(c_1)\\ &\land(\neg x_1\lor x_3\lor \neg x_4)\quad&(c_2)\\ &\land(x_2\lor \neg x_3\lor x_4)\quad&(c_3) \end{aligned}$$ Then its graph is as follows: Graph

Obviously, for a $m$-clause formula, its graph contains $6m+3m=9m$ vertices. To form an independent set, we can pick at most one vertex from a triangle and $k$ vertices from a cycle. If in the cycle of $x_i$, we pick $c_j^{\mathrm{pos}}$ ($c_j^{\mathrm{neg}}$) in the independet set, then $x_i$ is assigned true (false). When precisely $k$ verices are picked in an $2k$-length cycle, the assignment of the corresponding variable is well-defined, i.e., all true or all false in the entire formula. When a vertex in a triangle is picked, it means this clause is satisfied. An edge between (say) $x_1$ in the triangle of clause $c_1$ and $c_1^{\mathrm{neg}}$ in the cycle of $x_1$ indicates that $x_1=0$ doesn't satisfy the clause (because the two vertices can't be selected simultaneously). Hence, when precisely $4m$ vertices are selected in the independent set, i.e. half are selected in cycles and one in each triangle, the formula is satisfied. So, deciding the satisfiability of the 3-CNF formula is now converted to deciding whether there is an independent set of size $4m$ in the graph.

However, I'm not able to derive a maximal planar graph from the incidence graph. I think there must be some relationship in the graph indicating that a variable can't be true and false simultaneously. Let's say there are two variables, $x_1$ and $x_2$, and four vertices, $x_1,\neg x_1,x_2,\neg x_2$. There must be edges $(x_1,\neg x_1)$ and $(x_2,\neg x_2)$ to make sure that $x_1$ and $\neg x_1$ (as well as $x_2$ and $\neg x_2$) don't occur simultaneously in the independent set. To make the graph maximally planar, the graph must be isomorphic to $K_4$; but the size of the maximal independent set in $K_4$ is $1$, while we require the size to be $2$ to assign each variable a value. Generally speaking, there seems to be too many constraints in a maximal planar graph to reduce a planar 3-SAT instance. I also searched for a polynomial-time algorithm for maximal independent set in maximal planar graphs, but found none.

Graph

Furthermore, I found an interesting fact at https://graphclasses.org/classes/gc_981.html (thanks to @pcpthm for proving the link). Maixmal independent set on every "minimal superclass" of maximal planar graphs listed in the page turns out to be NP-complete, while for every maximal subclass it can be solved in polynomial time. So it seems that maximal planar graph is at a somewhat "intermediate" position.

$\endgroup$
4
  • 2
    $\begingroup$ Asking ChatGPT is not a helpful way to research a question. It will gladly spout confident-sounding nonsense. Instead, a more helpful approach would be to study the proof that maximal independent set on planar graphs is NP-complete, then check whether you can adjust it to make sure the graphs constructed by that reduction are maximal planar. I encourage you to spend some time on that, then to summarize what you've found so far, including what is the key barrier to such an extension. Are you sure you mean "maximal" and not "maximum"? $\endgroup$
    – D.W.
    Commented Mar 12, 2023 at 23:17
  • $\begingroup$ @D.W. Thanks, but I think the terms "maximal independent set" and "maximal planar graph" are correct, according to Wikipedia. $\endgroup$
    – Soha
    Commented Mar 13, 2023 at 0:48
  • 4
    $\begingroup$ The status is unknown to ISGCI (database of known results) <graphclasses.org/classes/gc_981.html>. $\endgroup$
    – pcpthm
    Commented Mar 14, 2023 at 6:26
  • $\begingroup$ @Soha maximal independent set is trivially polytime solvable, which I guess is D.W.'s remark. $\endgroup$ Commented Aug 31, 2023 at 8:30

1 Answer 1

3
$\begingroup$

This is more of a comment, but I want to append an image. The following graph is maximal planar and every node has degree 4, thus the proposed algorithm does not work. The maximal independent set of this graph has 2 nodes.

graph

As I said, this is more of a comment / not an answer.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.