3
$\begingroup$

Given a cycle of length > 3 in a planar graph, I'm looking to partition it into 4 sublists of length 2 or more such that:

  1. No sublist contains two vertices with a chord between them
  2. The last element in each sublist is the first element in the next
  3. Every element in each sublist is adjacent to its neighbors in the original cycle
  4. The difference in size between the sublists is kept minimal, given constraints 1 to 3

Overall I'm not really sure if this is required to be solved using graph structures, or if it's possible to transform it into something more general.

$\endgroup$
4
  • $\begingroup$ Since you used the word 'partition', are we to understand that the 4 sublists concatenated together makes the original cycle? $\endgroup$ Apr 13, 2015 at 14:45
  • $\begingroup$ Correct, assuming the last element in each list is removed (point 2). $\endgroup$
    – Aeris130
    Apr 13, 2015 at 15:04
  • $\begingroup$ What's a chord? Is that the same thing as an edge? $\endgroup$
    – D.W.
    Apr 13, 2015 at 23:53
  • $\begingroup$ Do the sublists have to form a connected subgraph? Or can they just be any set of vertices in the cycle? $\endgroup$ Apr 14, 2015 at 7:33

1 Answer 1

2
$\begingroup$

If the original cycle has length $n$, there is a straightforward $O(n^5)$ time algorithm: simply guess which vertex each sublist should start at.

In other words, let the original cycle go through the vertices $v_1,v_2,\dots,v_n,v_1$. Then you can choose indices $i,j,k,l$ (such that $1 \le i < j < k < l \le n$), where the first sublist contains $v_i,v_{i+1},\dots,v_j$, the second sublist contains $v_j,v_{j+1},\dots,v_k$, and so on (assuming index arithmetic wraps around modulo $n$). There are only ${n \choose 4} \in O(n^4)$ possible choices for $i,j,k,l$, so you can exhaustively try them all and test each one to see whether it meets all your requirements, and then keep whichever one is best (according to your "difference-in-size" metric).

This proves that the problem can be solved in polynomial time.

$\endgroup$

Your Answer

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

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