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.
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.
| 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:babalabo@aya.or.jp
http://babalabo.blogdns.com/EN
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.
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 Köîigsberg
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:babalabo@aya.or.jp
http://babalabo.blogdns.com/EN/
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.
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.
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.
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.
-----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://babalabo.blogdns.com/labo/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://babalabo.blogdns.com/labo/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.
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.