A Polynomial Time Solution
for Plesnik's Problem
by Irrigation Canal Method
|
To look figures properly you need an
SVG-viewer
, which is obtainable here.
Plesnik Paper (1979) is available here :
Hamiltonian Cycle Problem in Planar Digraphs with Degree Bound Two |
-----Original Message
No.0-----
From: babalabo [mailto:babalabo@aya.or.jp]
Sent: Sat Jan 29, 2005 4:11 pm
To: theory-edge@yahoogroups.com
Subject: [theory-edge] Hamiltonian Cycle Problem in Planar Digraphs with Degree Bound Two
Hamiltonian Cycle Problem in Planar Digraphs with Degree Bound Two
Hi Vlad and all!
now we are discussing aged Hamiltonian Circuit Problem in somewhat
fresh light at the mailing list algorithm-forge. the beginning
was a post by Christoph, one of members of the list, who dug out
a very important but almost overlooked paper written by Plesnik
in 1978. this is really a grenade of mega-tonnage. we've already
kept a very advanced point near the pole. today I posted a brief
introduction for our claim. as it contains 6 figures, maybe much
readable. please check the thread and come into our camp.
CURRENT: http://groups.yahoo.com/group/algorithm-forge/message/2856
START: http://groups.yahoo.com/group/algorithm-forge/message/2838
Michiro
-----Original Message No.
1-----
From: babalabo [mailto:babalabo@aya.or.jp]
Sent: Sunday, January 30, 2005 1:08 AM
To: algorithm-forge@yahoogroups.com
Subject: [algorithm-forge] a temporal answer to William
a temporal answer to William
Hi Lubomir and all!
To make our claim clear, I want to introduce a new problem, namely Cubic Planar
Circuit Problem (QPC), while I will call the Directed Cubic
Planar Graph Problem Plesnik's Problem (PNK). PNK is
extendable up to directed planar graph with degree bound two, where
Def-1. A Cubic Planar Circuit graph (abbreviate to cubic circuit) is a directed cubic planar graph which is composed of switches and wires, where a switch is an even cycle of alternating in-points and out-points, and a wire is an arc connecting an in-point and an out-point. We say a vertex in a cubic circuit Q is an in-point (respectively out-point) iff it has two in-coming (respectively out-going) arcs, i.e., we call it by its major arc orientation within the three arcs of the vertex. If Q has no switches, then it is fixed. There exist two types of fixed circuit, one is hamiltonian and the other is non-hamiltonian.
Cubic Circuit Problem (QPC): Given cubic circuit Q. Does there exist a directed Hamiltonian Cycle on Q?
Let m=n/2 be an integer, then a cubic circuit Q has 2m vertices since Q is a cubic graph and a cubic graph is always even. A set of switches of Q is a 2-factor of Q, i.e., spanning cycles, and it is sure that the cycles never intersect each other and the decomposition into switches is always unique as far as the instance if of PNK problem. The switches have 2m vertices and 2m arcs. The number of wires is m and any hamiltonian cycle of Q passes all the wires. In other words, the wires forms and Eulerian Cycle regarding switches as nodes. The necessary and sufficient condition for a graph to be Eulerian is that every node is of even degree, and it is fulfilled by the next theorem.
Even Cut-set Theorem: Intersection of a cycle and a cut-set of a graph is always even.
Neglecting the wiring inside of a switch, wires from/to a switch is a cut-set of the circuit, hence it must be even and the numbers of out-going wires and in-coming wires must be the same for a switch. Our QPC problem asks if there exists or not a switching state which makes the circuit hamiltonian. See Fig.1-3. Now we may have one more problem for consideration, which is known to be NP-complete, too.
Undirected PNK problem (UPNK): Given undirected cubic planar graph G. Does there exist a hamiltonian cycle on G?
PNK-UPNK Theorem: Two problems UPNK and PNK are in a sense equivalent, i.e., an instance G of UPNK has a hamiltonian cycle iff there exists an orientation D of G such that D has a directed hamiltonian cycle.
Imagine that you are going to solve an undirected hamiltonian instance. Then you may try to make a set of orientation of edges, which composes a directed spanning cycle of the graph. Thus you are solving a directed problem.
Fixed Circuit Theorem: If an instance G of PNK Problem has no switches, then the circuit of G is fixed and solvable in linear time.
Fixed Circuit Conjecture: If a fixed cubic circuit Q has a hamiltonian cycle P, then the cycle P is the only one hamiltonian cycle of Q. Note: This conjecture is proven later at MSG #5.
A fixed circuit is an extreme instance for our QPC problem. When a fixed circuit Q has a hamiltonian cycle P, then every arc of P must be pre-determined by some cause, so it must be hard-wired. Accordingly we conjecture that if Q is a fixed hamiltonian circuit, then the hamiltonian cycle P is unique. For example, K4 has no switches, i.e. a fixed cubic circuit, and its hamiltonian cycle is the only one hamiltonian cycle for some possible orientation of K4.
Our first task is to transform an instance of PNK into a cubic circuit with switches and wires. For the sake of this we introduce a special graph called semi-point graph.
Def-1.1. A semi-point graph H is a derived graph from an arbitrary directed graph G by splitting a vertex v in G into two points, out- semi-point and in-semi-point. Accordingly H has 2n vertices and m arcs, where n is the number of vertices of G and m is the number of arcs of G. Obviously for a semi-point graph H, every path is an alternating path of out/in-semi-points and every cycle in H is even.
Since our objective graph is of PNK, there is no intersection between alternating cycles in H. in other words, a set of arcs of a PNK instance is partitioned into distinct cycles, paths and arcs in one way. If there existed no cycles in H, then we have got a fixed circuit. In such a case it is almost sure that it is decidable if the circuit is hamiltonian or not at once because there is no freedom in the circuit.
|
If the cycles cover the whole points of H, then we have a normal cubic circuit. How about the case when there remained some paths and the cycles that do not cover the points of the graph? It is no hard to understand that the paths are already determined because the orientation of arcs at the end points of the paths are decided and a half of arcs in the paths are to be thrown out. In other words, we can replace a path by a determined arc, i.e., a wire, and obtain a normal circuit consists of only switches and wires. In this case the number of points decreases and the graph is reduced in some degree.
Now we can answer the first question by Sir William R. Hamilton, "If a dodecahedron has a spanning cycle or not?". It is clear that a dodecahedron has only two types of cycles, C5 and C10. C5 cannot be a switch in our cubic circuit. How about C10. Yes, it may be possible. Then take out an arbitrary C10 from the graph and see. Then you will find that it remains two C5. this means that dodecahedron has a fixed cubic circuit and a hamiltonian circuit is to be found within constant steps provided that you know a tiny set of constraint conditions for arcs to be in a hamiltonian circuit. You cannot fail any more. Fig.1-6 shows this situation. Note: This paragraph was wrong. See the bottom line.
| Fig.1-6. Dodecahedron has a fixed hamiltonian cycle |
| Fig.1-7. Dodecahedron with two switches |
Four-Colored Wires Conjecture: 4 colors are enough to wire between switches of a normal cubic circuit.
Perhaps this theorem is provable applying the Four Color Theorem. Planarity is the most significant notion in PNK and QPC. So I guess that this theorem would become necessary at some time point.
Michiro
Nasu
mailto:zelkova@aya.or.jp
http://www.aya.or.jp/~babalabo/babalab/bindex.html
P.S. To look at the figures you need an SVG-viewer, that is obtainable everywhere on the net, for example visit Adobe. You also have to allow ActiveX and Java script to view SVG. All figures are placed at our in-house server above URL, so it may be probable that our server is off at any moment. If you could not access the figures, please try again later. BTW I'm using Open Office for my SVG-editor. it's free and truly good. Amaya sponsored by W3C is the only one in-line SVG editor available so far but it seems that it is still far from finished...
After math: Above description regarding dodecahedron was too hasty argument and failed to show the entire proof. For example you can extract two distinct C8 from the graph and these two C8 gives you a solution by just trying to make two alternating cycles. In this case 2x2=4 paterns may be possible.
-----Original Message No.
2-----
From: babalabo [mailto:babalabo@aya.or.jp]
Sent: Monday, January 31, 2005 7:18 AM
To: algorithm-forge@yahoogroups.com
Subject: RE: [algorithm-forge] a temporal answer to William
Hi Labomir and all!
I believe that you enjoyed my last mail. We introduced a new problem named Cubic Planar Circuit Problem (QPC) and showed that a Plesnik's Problem (PNK) is transformable to QPC. QPC is a problem as to the simplest printed circuit with only switches and wires. In the view of QPC, a PNK instance is one of the three below.
(1)
A fixed (hard-wired) circuit with no switches
(2) A cubic circuit with fewer switches than to cover the vertices
(3) A normal cubic circuit with switches enough to cover the vertices
For case (1) we conjectured that the instance is solvable in time proportional to the input size, as it seems that the circuit is totally hard-wired. In case (2) we can replace alternating paths with pre-determined wires and reduce the instance into a normal cubic circuit. So hereafter assume we that our problem is always given in a form of normal cubic circuit unless mentioned otherwise. Under this premise, PNK is said to be equivalent to QPC.
I wrote, "The wires forms an Eulerian Cycle regarding switches as nodes". See Fig.2-1. This is the point. Since all wires are pre-determined arcs, so to say the third arc or the minor arc which is necessary to make a spanning cycle as there is no other arc with the orientation from/to the point, a hamiltonian cycle must passes all the wires and it means that wires forms an eulerian cycle.
Hamiltonian Circuit Problem is known to be NP-complete, on the other hand Eulerian Circuit Problem is solvable in linear time. The difference is great! The relation between hamiltonian cycles and eulerian cycles were somewhat obscure. One graph is eulerian but not hamiltonian, another is the opposite and some are simultaneously eulerian and hamiltonian. See Fig.2-2. Even a polynomial time reduction from Eulerian Problem to Hamiltonian Problem is known [Yao, 1997]. But as far as I've heard, there is no known method to transform a Hamiltonian Circuit Problem to Eulerian Problem. Here we break it through. Now I would like to introduce one more problem to tighten our understanding
Def-2. An eulerian cycle is a closed spanning trail, which includes each edge of a multi-graph G. We are concerned with only planar graphs drawn on a plane. A drawing D of a planar graph G is a physical diagram of G drawn on a 2D plane. An eulerian cycle p of a drawing D of a planar multi-graph G is enveloping iff every adjacent edges of p is exactly of neighbor to each other in D. In other words the path p never leaps edges incident to the point for connecting two edges.
Enveloping Eulerian Cycle Problem (EECP): Given a drawing D of a directed planar multi-graph G. Does there exist an enveloping eulerian cycle on D?
This problem is to be answered independently apart from our concerned QPC problem. Original eulerian cycle problem has a simple solution, i.e., it is solvable iff every vertex of the graph is even degree. I expect that EECP may have somewhat simple solution comparable to the original one. Another variation of EECP problem is undirected graph version, but the difference may be small.
Fig.2-3. Two drawings with/without enveloping eulerian cycle |
Fig.2-3 shows an example of drawings of an undirected graph with/without enveloping eulerian cycles. It is important to know that enveloping eulerian property is not a property of a graph but a property of a drawing of the gprah. In fact the two drawings of Fig.2-3 are of the same graph.
Def-2.1. A derived directed multi-graph D from a cubic circuit Q by reducing a switch of Q into a node of D is called a QPC wiring diagram of the circuit Q.
A QPC wiring diagram D of a cubic circuit Q is considered to be always a drawing of Q. Now we should re-consider that cubic circuit Q is itself a drawing of a PNK base graph.
Euler-Hamilton Cycle Theorem: A cubic circuit Q has a directed hamiltonian cycle iff the QPC wiring diagram D of Q has an EECP solution, i.e., the diagram D has an enveloping directed eulerian cycle. Note: This theorem is basically adaptable only for the case where the circuit Q is elementary. It is rewrite later at MSG #3.
At last the two giants Euler and Hamilton have shaken hands. There is nothing for us to add any more. In one word, QPC is equivalent to EECP. OK? To say that a QPC-diagram D has an enveloping eulerian cycle p means that the cubic circuit has a switching state which makes it enable to represent a hamiltonian cycle P of the circuit because an enveloping eulerian cycle p is nothing but one of possible switching states of the cubic circuit consecutively traversing each node.
Euler
solved the famous problem known as Seven Bridges of Kvnigsberg
in 1736, which is acknowledged to be the first paper of graph theory/topology.
Hierholzer published its complete proof in 1873. Fleury's algorithm to find an eulerian
cycle appeared in no later than 1921, but even a child can draw unicursal figures.
Isn’t it much easier to find/draw an enveloping eulerian cycle than the original?
Michiro
mailto:zelkova@aya.or.jp
http://www.aya.or.jp/~babalabo/babalab/bindex.html
P.S. In a historical reason we sometimes say like Hamiltonian Circuit Problem. But to avoid a confusion between cycles and our circuit we use hamiltonian cycle instead of hamiltonian circuit for individual objects. Further we abuse cycle for closed trail like eulerian cycle, but I believe it does not confuse anything.
-----Original
Message
No.
3-----
From: babalabo [mailto:babalabo@aya.or.jp]
Sent: Tuesday, February 01, 2005 11:58 PM
To: algorithm-forge@yahoogroups.com
Subject: RE: [algorithm-forge] a temporal answer to William
Hi Lubomir and all!
At first my apology for calling you by a wrong name in my previous mail. m(_)m
I believe that we got a real progress and the scene was changed. Do you think that we've just got a new NP-complete problem to be added at the tail of the long list of known NP-complete problems supposedly more than several thousands? Then we already have enough, but I don't think so. The difference is clear. Well what is it? We introduced a new concept/situation, i.e., drawing of graphs. This hadn't ever existed and never been looked into.
Do you remember I used to say that graph theory is a part of physics? It was my belief and now I have an evidence for my guess. A graph represents abstract relation between points. But it is something more than that. A graph is itself a physical/solid entity, which eventually demands a shape, and now we discovered it on 2D plane. We have to learn shapes to solve our grand problem. A hamiltonian cycle divides the infinite space into solid inside and vast outside. It establishes the object as an individual entity. See Fig.3-1.
The enveloping eulerian cycle is another expression of this. However we have to make a small supplement for the Euler-Hamilton Theorem. Because to make a QPC wiring diagram, we reduced a switch into a node and neglected the inner structure of the switch. In other words, QPC-diagram is valid only if the circuit is flat or of single layer. So I retract it once and re-propose it like below.
Def-3. A vertex of a switch S of a cubic planar circuit Q is called a terminal and a contact is a mechanical movement of the switch to contact two neighboring terminals. The number of the terminal is always even and if S has 2m terminals, then we say S is an m-contact switch and denote m-switch. 1-switch does not exist because we do not treat multi-graphs as cubic circuit. See Fig3-2.
Def-4. An outer/inner terminal is a terminal incident with an outer/inner wire respectively. A switch S is elementary iff S has no inner terminals. A switch S is simple if S has no inner switches. Otherwise it is complex. A 2-switch is always elementary as was shown in Fig.3-2. A cubic circuit Q is elementary iff every switch of Q is elementary. Similarly a cubic circuit Q is simple if it does not contain a complex switch; otherwise it is a complex circuit. Fig.3-3. Shows those three types of cubic circuits.
Euler-Hamilton Cycle Theorem revised: An elementary cubic circuit Q has a directed hamiltonian cycle iff the QPC wiring diagram D of Q has an EECP solution, i.e., the diagram D has an enveloping directed eulerian cycle.
Hmmm.. . Our great loss! But inevitable, don't mind. As it is our first experience to encounter a situation like this, we had better take some exercises to be accustomed with the new concept. I collected some/many of enveloping/no enveloping eulerian cycles in Fig.3-4. In that figure, every node is considered to be an elementary switch without inner terminals. A shape at the top center is an exception, which cannot be an enveloping eulerian cycle.
Do you think that it is possible to find an enveloping eulerian cycle in a drawing? I think it is possible in any way assuming that we recognize all the faces (halls) in the drawing. We would count up the entire crossing nodes shared by more than two faces, and check the containment relation of the faces. These are enough information to decide whether the drawing has an enveloping eulerian cycle. Note: a cubic circuit has switching states, but its wiring diagram has not. Be aware that here we are considering in the latter circumstance.
Although we did not thoroughly investigate it yet, it seems that the rule is not so complicated. If there is no containment pair of faces, it is done. If there existed one then check their crossing node if it is shared with a third face, and so on... it is sure that to find a solutions is as easy as a child can perform joyfully. Only you have to learn how to make a sausage with ground meat and a long intestine. Fig.3-5 would explain this situation a bit more clearly. Note: a crossing node in a QPC-diagram is always a switch of the cubic circuit, vice versa.
Now consider the second case, i.e., a simple circuit. "Enveloping eulerian cycle" is not enough to explain this situation. However in a simple circuit, since there is no complex switch, there is no mechanical part inside any switch, i.e., the inner wiring of each switch is fixed or hard-wired. Therefore the difference between an elementary circuit and a simple circuit is not large. Perhaps to find an extended enveloping eulerian cycle is no harder than for an elementary circuit.
Fig.3-6 shows a case study where an elementary circuit and a simple circuit has the same wiring diagram. Of course such cases are quite banal. Observing Fig.3-6, it seems that the difference between an elementary switch and a simple switch is a matter of topology. Although I don't have enough words to explain this situation so far, we can rely on the fact that all the switches are hard-wired in a simple circuit, so there must be some clear resolution.
Of course to find a solution for a complex circuit may not be easy, rather to say so hard. I have no clue for now. Have you? Anyway I'll attack the stronghold on the height tomorrow after making some portable-foods to bring with.
Michiro
-----Original
Message
No. 4-----
From: babalabo [mailto:babalabo@aya.or.jp]
Sent: Thursday, February 03, 2005 6:58 AM
To: algorithm-forge@yahoogroups.com
Subject: RE: [algorithm-forge] a temporal answer to William
Hi Lubomir and all!
Essentially I think that our problem was solved! I already reached the conclusion even before my breakfast. But my genie resident in my stomach shouted loudly, "GOOGLE!" (I don’t know where he learnt the term) so I couldn't help beginning to cook for us. I arranged a big pan of curry stew, which is enough for a week long camp. But to begin with, I'll give you simple two problems. Please think of them and tell me your answer.
Kamikiri-Euler Cycle Problem: Given a sheet of paper on which an eulerian planar graph is drawn. Can you cut it through along the eulerian trail and turn it to exactly two pieces? Crossing points are very small but at least regarded to have minimum dimension.
Paddy Field-Open Gate Problem: Given a number of paddy fields filled with water and water gates connecting each fields at some and other points. How can you open/close the gates and level the water surface of all the fields.
Sometimes we are said, "bamboo and paper culture". That is true. We love paper so much and our traditional paper is very strong and durable almost permanently if not burnt out. Perhaps you know our ORIGAMI craft folding a square paper to make up something amusing. KIRIGAMI (cutting paper) is another popular paper craft in Japan. KIRIE (papercutting) is a fine paper art drawing pictures using exacto knives instead of paintbrushes.
KAMIKIRI is one of such our paper culture. Rather it is a performance on a stage cutting a paper and making anything they want. Once given a subject from audience, a much elaborate picture is cut out from a thoroughly white paper very rapidly maybe within a minute just using a pair of scissors. The point is that the master piece must be a whole piece, and never mended by paste nor Scotch tape, even the remainder must be in one piece until the craft is completed like a peel when you peeling an apple with your knife. At present several masters with god hands are alive. Yes, he is actually solving the problem above in real time.
Well, I'll try my own KAMIKIRI, where KAMI means a paper and KIRI is a noun turns from the verb KIRU, to cut. BTW in our language KAMI simultaneously means GOD, as well as HAIR and UPWORD, while KAMI-SAN is/was my wife. So it seems that KAMI indicates something supreme for us. Now show up!
Proof of KECP: possible. It is known that a planar eulerian graph is dual to a planar bipartite graph. Hence it is sure that the graph is 2-colorable, say in black and white. Along the eulerian trail, there exist always a black area at one hand and white area at another hand. Note: the outmost face contains virtually infinite white (possibly black) area. Thus the trail chains all the black area as well as white area. QED.
Now we've got a map in black and white. We know which is the figure and which is the ground, don’t we? The most significant point is that this map is the only one map for the graph regardless if it has a hamiltonian cycle or not. Suppose that the black domain is the figure. Then turn the color to water blue. Then you'll see a beautiful scene of Japanese paddy fields. I have to supply water to all my fields. How can I do it? Shall we need street blood for the water? No!
I think that I will simply open all the gates peacefully. Am I wrong? It is sure that some
gates would work and others would not. But you are not responsible for that. It depends on
the local condition, which you don’t know. All of what
you have to do is just to open the gates and merge the water surfaces into a single face.
You exactly know whether a cycle surrounds a black area or a white area. So you would not
fail to operate them. If you find a cycle still remains after merging all of your water
surfaces, then it is a cycle surrounding a ground area and you can just release the
isolated island by turning some gate to the opposite direction.
Here a water gate is our switch on a cubic circuit and if the switch is complex, then the switch itself has its own black and white map inside. You can command the switch, "open your gate" and the switch is able to command its sub-switches to open their gates and so on. Basically this operation is done just once. It might be that some switches are much larger and connecting multi-faces and work like this: in a switching state it connects faces f1 and f2 but disconnects f2 and f3. But don't be too afraid of that. These information is bounded locally and you can eventually make the best disposition in polynomial time because the number of the switches is after all smaller than n. I don't describe here the detail but you can rely on the fact that each paddy field is independent and immovable. In Chinese it is said that the water obeys both round and square vases.
Michiro
-----Original
Message No.
5-----
From: babalabo [mailto:babalabo@aya.or.jp]
Sent: Friday, February 04, 2005 9:00 PM
To: algorithm-forge@yahoogroups.com
Subject: RE: [algorithm-forge] a temporal answer to William
Hi Lubomir and all!
In my starting mail I conjectured if cubic circuit Q is fixed, i.e., with no switches and if Q has a hamiltonian circuit P, then P is the only one hamiltonian cycle of Q. I found a simple proof for it while I was bathing in my tub today. EUREKA forgotten.
Fixed Cubic Circuit Theorem: If an instance G of Plesnik's Problem has no switches, then the cubic circuit Q of G is fixed and solvable in linear time. Especially if G is hamiltonian, then G has only one hamiltonian cycle.
Proof of FCC Theorem: Let the semi-point graph of the cubic circuit Q be H. By the premise Q has no switch, i.e., H has no cycles, and hence H is a forest (a graph without cycles, possibly disconnected). However as G is an instance of PNK class, G has no vertex of in/out-degree equal to or more than 3. Consequently the semi-point graph H has no points of degree more than two and cannot be a tree (accurately a linear forest). In other words, H is consist of only disjoint arcs and paths, and these single arcs and the end arcs of the paths are all determined, because they are the only one in/out arcs in G for the point to which they were incident.
Fig.5-1. Switch-less Circuit is totally
hard-wired SVG does not support Greek letters; read Q as Q, p as p |
Once an end arc of an alternating path p of H is determined, every arc on the path p with the same orientation is simultaneously determined. For example, suppose a path p={e1,e2,...,em} in H. then arcs e1,e3,...,em are all determined. This implies that every path in H must be of odd length. If not, needless to say the graph is non-hamiltonian. Thus we already have a set of determined arcs and they clearly forms a 2-factor F of Q. If F is a spanning cycle of Q, then the cycle is the only one hamiltonian cycle of G. otherwise G is non-hamiltonian. QED
Def-5. We need a little more additional notation for describing our method. Consider a plesnik graph G, its cubic circuit Q and the QPC wiring diagram D of Q. diagram D is always a directed planar eulerian graph and as we learned yesterday, the diagram D is 2-colorable in black and white. We call the major part of the map D the ground and the minor part the figure. Note: the major part always contains an infinite area. Let a face (an area on the 2D plane surrounded by a cycle including no object inside) in the diagram D be fij, i=0/1, 0:ground, 1:figure. Then the set F of faces fij of D are partitioned into two parts, F0={f01,f02,...,f0m} and F1={f11, f12,...,f1n}, where F={F0,F1} and m/n is the number of the faces belonging to the ground/figure respectively, i.e., F0/F1 is the ground/figure face set. Especially f00 denotes the infinite outmost area of F0. We may sometime call the face f00 ground 00.
Let a set of switches in the circuit Q be S={S1,S2,...,Sk}, where k is the number of the switches in the circuit Q. (here we are just considering the top layer of the circuit. this method will be applied later to every layer of the switches) each switch Si has two state si0 and si1. We describe the function of a switch Si like below.
si=set of faces merged by Si in state 0, set of faces merged by Si in state 1.
For example, s1={00,01}, {11,12} means (1) faces f00 and f01 are merged in state s10 of switch S1, and (2) faces f11 and f12 are merged in state s11. If it were necessary for more complicated cases, the set of faces would be separated by parenthesis like s1={(00,01), (11,14)}, {(11,12), (13,14,15)}.
Def-5.1. Switching state s of a circuit Q is a product s1xs2x...xsk of the states of the switches S1,S2,...,Sk on the circuit Q, and each switch state si takes a value 0/1. So we indicate a switching state s of Q by a k digit zero-suppressed binary number like s=00101.
Now take the first example appeared in Fig.3-3, which is an elementary Circuit. Look at the Fig.5-2. There exist two solutions 011 and 100, where 011 represents a switching state such that switch S1 is in state s10, S2 is in s21 and S3 is s31. Let s=s10+s21+s31 be a solution. Then the merged face set F(s)={11,12,13}+{00,01}+{00,02}={00,01,02}+{11,12,13}=F0+F1. Very good! That is, if in a switching state, the set of merged faces contains all the faces, then we are done. Lets try the next sample, a simple circuit. Correction: 2005-01-12.
Note: you may think that our calculation here described is quite odd, but you must know that this is a calculation for water in paddy fields and addition of water is a bit queer than other operations for solid entities. Is it a correspondence that this story had begun at a brides and rivers. I think it might be not an accident as I consider that a cycle especially a hamiltonian cycle symbolizes circulation and horizontality which is the characteristics of water.
Look at the Fig.5-3. In this simple circuit three switches are all the same and leave all the ground faces inside since for each switch Si in both state 0 and 1, the ground 00 does not appear any lines. Consequently this graph has no hamiltonian cycle. However the following simple circuit has a solution. The difference is only the terminal points of the inner wire.
For the previous diagram, terminal #2 and terminal #7 are connected by an inner wire, while in the alternative, two switches have a inner connection from #2 to #6 (or its mirror image). Switching states are,
s1={11,12,14},
{01,03,12,14}
s2={00,02,11,12}, {01,02,12,13}
s3={00,02,11,14}, {02,03,13,14}
Two solutions, 101 and 110 are possible. E.g. if s=s11+s20+s31, i.e., switching state 101, then F(s)={01,03,12,14}+{00,02,11,12}+{02,03,13,14}={00,01,02,03}+{11,12,13,14}=F0+F1=F. Correction: 2005-01-12.
Today we've studied each case of elementary circuits and simple circuits. Now I believe that you've got how our method works. It is sure that we can treat simple circuits basically in the same way with elementary circuits, and with no doubts our method is able to solve those problems. As you can easily imagine, for complex circuits we just repeat this method recursively for all the layers. But is it bottom-up or top-down? I suppose that bottom-up may be reasonable. Anyway we've already passed the mountaintop some high noon but unconsciously. Note: Wrong. We will later see that the method must be top-down with recursive calls. 2005-02-12.
Michiro
P.S. I decided to embed bitmap images directly in my mail (actually putting a link to an image file placed at my server site). Perhaps this manner is more convenient for you than to look at them in another window. Other reason: I noticed that FireFox is not yet supporting SVG. So I believe this is better than to offer links to SVG files. Note: Nevertheless we are using SVG in this summary.
-----Original Message No. 6-----
From: babalabo [mailto:babalabo@aya.or.jp]
Sent: Tuesday, February 08, 2005 2:13 AM
To: algorithm-forge@yahoogroups.com
Subject: RE: [algorithm-forge] a temporal answer to William
Hi Guenter and all!
I wrote,
> I'm just merging the stuffs into a HTML page. that would be helpful.
> I've almost done and I'll release it as soon as tomorrow.
Here it is! http://www.aya.or.jp/~babalabo/plesnik/.
I believe that it is quite readable as it contains 20 or more figures!
So to say a half of pages are filled with figures. maybe just a comics for you.
Let's go onward! In my last mail we studied two cases of QPC circuit, an elementary circuit and a simple circuit, and confirmed that it was solvable. Now I want to formalize the method adapted to our resolution in set-theoretical terms.
Irrigation Canal Problem: Given
a set F of
elements. Let S={S1, S2,..., Sk} be a collection of subset pair Si=(Si0, Si1), Si0, Si1
F and 1
ik. Does there exist a family of
k subsets taking a set Sij, j=0/1 in each set pair Si such that F=
,
j=0/1.
This is the core question of our problem. Do you think that it is NP-complete? Yes, so I think. because this problem is eventually derived from Plesnik's Problem which is NP-complete. So even if you show me another evidence that this is truly NP-complete, it would not bend my course at all. Here is a similar set theoretical problem also known to be NP-complete. Note: We will change the title of this problem later. See the bottom-line post script.
Set Cover Problem: Given
a family of set S1, S2, ..., Sn, does there exist a subfamily of k sets Si1, Si2, ..., Sik such that 
=
.
Yes, I know your reaction. I admit that these two problems are almost equivalent and there is no reason to believe that the former is solvable in polynomial time. For example if k=n, then the second problem is trivial. However k=n/2 is the volume zone of the problem and maybe the hardest. But, I bet my life on the naming of the problem. I did not named the problem "Irrigation Canal Problem" just for a fun. It is meaningful as it really relates to what we learnt at the sidewalk of our Paddy Field.
Regarding the description of the problem, the most strange is that the distinction of the ground and the figure is entirely disappeared from the lines. I don't know if this is a good news or a bad news, but the secret key may be hidden around there. Now let's try to solve the problem literally as an Irrigation Canal Problem. We have a partition of F={F0, F1}, i.e., the distinction between the ground F0 and the figure F1, and try to make a sole water pool of F1, where the water pool is a closed water surface and the waterside path forms a hamiltonian cycle. I think that this operation is very easily done. Because we can supply enough water from reservoir, only if the graph has a hamiltonian cycle. All what we have to avoid is making an isolated island in the water. This is quite a passive operation and we do not fail to perform this.
Recall Fleury's algorithm for eulerian cycles. The following is provided by planetmath.org.
- Pick any vertex to start
- From that vertex pick an edge to traverse, considering following rule: never cross a bridge of the reduced graph unless there is no other choice
- Darken that edge, as a reminder that you can't traverse it again
- Travel that edge, coming to the next vertex
- Repeat 2-4 until all edges have been traversed, and you are back at the starting vertex
"Reduced graph" means the original graph minus the darkened (already used) edges. How do you read this? You can draw an eulerian cycle just by avoiding a bridge not to shut off your return path to the starting point. I think that this algorithm is quite similar to our considering algorithm for the Irrigation Canal Problem. We can avoid to close a land border as well as they avoid a bridge not dare to go into a difficult situation. In my view point, Irrigation Canal Problem is just an extension of Eulerian Circuit Problem, and then I claim that the problem is solvable in polynomial time. However this resolution is not visible in the set theoretical view point. I recognize that the key concept is horizontality of the water. Note: To say that Irrigation Canal Problem is an extension of Eulerian problem is not correct. See the bottom line.
Michiro
P.S. As you may notice, I changed the term QCP (Cubic Circuit Problem) to QPC (Cubic Planar Circuit) Problem to emphasize the planarity of the objective graphs. Because the planarity is the matter of life or death for us now.
Note: To avoid your confusion: we have to say that the above set theoretical problem and what we call Irrigation Canal Problem are actually not the same. In other words the above problem is a generalization of ICP problem and our ICP problem is its special instance. Now we understand that we received really a good news since it was certain that we ourselves removed the ground/figure distinction and made up the problem too much simplified. Unconsciously we left apart from the NP-complete zone and have turned into a polynomial time zone. We had better to give another name for the problem described above, so hereafter we call it Set Pair Cover Problem.
We shoud say that our Irrigation Canal Problem is a special case of Eulerian Circuit Problem. Because we still need an enveloping eulerian cycle and it is a particular type of eulerian cycles. Fig.6-3 shows some Irrigation Canal solutions for the eulerian graph at Fig.6-1 assuming that the vertices of the eulerian graph are switches of some corresponding QPC circuit.
I embedded small math expressions into the text as tiny GIF files. I wanted to use MathML of W3C standard and tried various math-editors, but cannot find sufficiently good one. Practically MS Word provides the best WYSIWYG math-editor but regretfully it does not output MathML. Other editors, such as Amaya, OpenOffice, etc. are still unsatisfactory for daily use.
-----Original Message No. 7-----
From: babalabo [mailto:babalabo@aya.or.jp]
Sent: Sunday, February 13, 2005 4:28 AM
To: algorithm-forge@yahoogroups.com
Subject: [algorithm-forge] A Polynomial Time Solution for Plesnik's Problem by
Irrigation Canal Method
A Polynomial Time Solution for Plesnik's Problem by Irrigation Canal Method
Hi Guenter and all!
I updated my Plesnik-Page at http://www.aya.or.jp/~babalabo/plesnik adding 3 figures for my recent MSG to you. It includes some corrections and remarks. Please check it out. Now I understand that our Irrigation Canal Problem and the set theoretical problem described at my last MSG, which is now called Set Pair Cover Problem are not the same. Briefly speaking, the latter may be NP-complete but the former is supposedly of polynomial time. However we failed to show it as I wrote to Bojan. I think that it is informative to show you how we had failed at first.
Our problem is to find a hamiltonian cycle, which forms a water pool in our 2-colored map. In other words a waterside walk gives us a hamiltonian cycle. However we look it in a bit different way something like a spanning tree made of irrigation canals. Take a look at Fig.7-1. Of course a tree is a minimal connected graph with no cycles and this characteristics of tree is what we are seeking. As you know every connected graph has at least one spanning tree and there exists a linear time algorithm to build up a spanning tree from a graph. Our algorithm is based on a well-known Depth First Search Algorithm for traversing a spanning tree. The algorithm was about the following.
(1)
Take an arbitrary crossing point S,
and let S
be the root of the tree.
(2)
Select a face f
that contains the crossing point S.
(3)
Select a crossing point S'
in f
which is not in any faces ever selected. If there exists none of such a point in f,
then backtrack to the previous point S
and continue the selection of a face f.
(4)
Select a face f'
which contains the crossing point S'
and does not contain any point ever selected. If there exists none of such a face f',
then back track to the previous face f
and continue the selection of a crossing point S'
in f.
(5)
If it returns back to the root, then end, while If the graph is disconnected then it has
no solution.
It seems that this algorithm gives us a spanning tree made of canals, but it doesn't work as we expected, because we need not only to select a face/crossing point but also choose a switching state. To choose the positive state, i.e., to select state 1 as default is at least reasonable but eventually not effective. For example if it has only one solution, then we have to decide the states definitively in any way. In other words, we need an exhaustive search to decide the switching states. See Fig.7-2. This graph has only one solution 010. However we have no criterion to decide that the switch S1 is to be state 0. If a problem needs an exhaustive search, then it cannot be solvable in P-time. If we have m switches to be decided, then our computation becomes O(2m). This depends on the Hamming distance of the switching states between the starting diagram and the solution. See Fig.7-3. So we returned to the switching state descriptor of the problem.
s1={(11,12,14)},
{(01,03), (12,14)}
s2={(00,02),
(11,12)}, {(01,02), (12,13)}
s3={(00,02,03)},
{(11,13,14)}
Now we found that some faces appear in both state 0 and state 1. In this case, faces 02, 12 and 14. A face, which appears in both states, is effectively connected to some other faces. Accordingly we consider that we can remove them from the descriptor safely.
s1={11},
{01,03}
s2={00, 11}, {01, 13}
s3={00,03}, {11,13}
In this constraint condition we have just two candidates of the solution, 010 and 101. 101 is easily discarded as ground-faces (00,02) and (01,03) are disconnected, or water-faces 11, 12 and 14 forms a cyclic canal. This is really very close to our image what we have called Irrigation Method. So we regained our hope! We don't know whether this method is almighty or not, but I think that it is very important that the hamming distance between 010 and 101 is the largest of all. In other words, it seems that we clearly found out the difference.
Michiro
P.S. I recommend you to go straight to the Plesnik-Page as it is better provided with figures even for this MSG. But just wait a moment until I've made up the link.